Prime Factorization

Factorization is a useful example because it starts from a nonlinear-looking integer relation and lets ToQUBO.jl handle the binary encoding and reformulation details behind the scenes.

We seek integer factors p and q such that

\[\begin{array}{rl} \text{find} & p,\, q \\ \text{s.t.} & p q = R \\ & 2 \le p \le \lceil\sqrt{R}\,\rceil \\ & \lceil\sqrt{R}\,\rceil \le q \le \lfloor R/2 \rfloor \end{array}\]

For a small toy instance, exact enumeration is practical and keeps the example deterministic.

Encode the Model

using JuMP
using QUBO
using QUBOTools

function factor(R::Integer)
    a = ceil(Int, √R)
    b = R ÷ 2

    model = Model(() -> ToQUBO.Optimizer(ExactSampler.Optimizer))

    @variable(model, 2 <= p <= a, Int)
    @variable(model, a <= q <= b, Int)
    @constraint(model, p * q == R)

    optimize!(model)

    return model, round(Int, value(p)), round(Int, value(q))
end

factor (generic function with 1 method)

Solve a Toy Instance

model, p, q = factor(15)

(p, q)

(3, 5)

Inspect the Reformulated Model Size

As in the other examples, the compiled form is stored on the optimizer backend, so inspection goes through JuMP.unsafe_backend(model).

n, l, qmat, α, β = QUBOTools.qubo(JuMP.unsafe_backend(model), :dense)

(n = n, alpha = α, beta = β, nonzero_quadratic_terms = count(!iszero, qmat))

(n = 10, alpha = 1.0, beta = 49.0, nonzero_quadratic_terms = 25)

This formulation is mainly educational: exact solving is reasonable only for small instances, but the example shows how integer structure is funneled into a QUBO workflow.