factoring
Factoring with the D-Wave System¶
In the Leap factoring demo, you saw how the D-Wave system factored an integer by running a multiplication circuit in reverse.
This notebook demonstrates how you can solve a constraint satisfaction problem (CSP) on a quantum computer with the example of factoring.
Factoring as a Constraint Satisfaction Problem describes the factoring problem as an example CSP.
Formulating the Problem for a D-Wave System shows how such CSPs can be formulated for solution on a quantum computer.
A Simple Example codes a small CSP to clarify the solution technique.
Factoring on the Quantum Computer codes a factoring problem for solution on the D-Wave system.
Further Information details some points touched on in previous sections and examines more closely the results returned from the quantum computer.
This notebook should help you understand both the techniques and Ocean software tools used for solving CSPs on D-Wave quantum computers.
New to Jupyter Notebooks? JNs are divided into text or code cells. Pressing the Run button in the menu bar moves to the next cell. Code cells are marked by an “In: []” to the left; when run, an asterisk displays until code completion: “In: [*]”.
Factoring as a Constraint Satisfaction Problem¶
The complexity class for classical integer factoring is believed to be between P and NP-hard. Although research has yielded algorithms that perform faster than the intuitive trial division, including Fermat’s algorithm, Pollard’s two algorithms, and sieve algorithms, it’s still an open question whether a classical algorithm exists that can factor in polynomial time. For quantum computing, Shor’s algorithm runs in polynomial time (the D-Wave system does not run this algorithm).
This notebook solves factoring on a D-Wave quantum computer by formulating it as a constraint satisfaction problem. CSPs require that all a problem’s variables be assigned values that result in the satisfying of all constraints. For factoring, the problem’s constraints are that the two variables representing factors, $a$ and $b$, be assigned only natural numbers and that their multiplication be equal to the factored number, $P$.
Among CSPs are hard problems well suited to solution on quantum computers. For example, the map-coloring problem is to color all regions of a map such that any two regions sharing a border have different colors (see a D-Wave system solve a four-color map-coloring problem here: Ocean software examples). The job-shop scheduling problem is to schedule multiple jobs done on several machines with constraints on the machines’ execution of tasks. You can apply the solution technique shown here to many CSPs.
Formulating the Problem for a D-Wave System¶
How can you formulate the factoring problem in a way that a quantum computer can understand?
D-Wave systems solve binary quadratic models (BQM), the Ising model traditionally used in statistical mechanics and its computer-science equivalent, the quadratic unconstrained binary optimization (QUBO) problem. Given $N$ variables $x_1,…,x_N$, where each variable $x_i$ can have binary values $0$ or $1$, the system finds assignments of values that minimize the QUBO
$\sum_i^N q_ix_i + \sum_{i