Systems, methods and apparatus for factoring numbers
View Patent ↗Systems, methods and apparatus for factoring numbers are provided. The factoring may be accomplished by creating a factor graph, mapping the factor graph onto an analog processor, initializing the analog processor to an initial state, evolving the analog processor to a final state, and receiving an output from the analog processor, the output comprising a set of factors of the number.
1. A method of factoring a product, the method comprising:
setting an initial condition of a multiplication circuit, wherein:
the multiplication circuit includes a plurality of quantum devices and a plurality of coupling devices between pairs of quantum devices; and
the initial condition includes:
a local bias value for at least one quantum device;
a coupling value for at least one coupling device; and
a binary value of the product to be factored;
performing a backwards evolution of the multiplication circuit; and
reading out a final state of at least one of the quantum devices, thereby determining a factor of the product.
2. The method of claim 1 wherein the multiplication circuit includes a plurality of bitwise multipliers, each bitwise multiplier comprising:
at least two of the quantum devices;
at least one of the coupling devices;
at least one input; and
at least one output.
3. The method of claim 2 wherein the at least one input of a first bitwise multiplier comprises:
a first bit to be multiplied;
a second bit to be multiplied;
an input sum bit outputted from a second bitwise multiplier; and
an input carry bit outputted from the second bitwise multiplier.
4. The method of claim 2 wherein the at least one output of a first bitwise multiplier comprises:
a first bit to be multiplied;
a second bit to be multiplied;
an output sum bit calculated from the at least one input; and
an output carry bit calculated from the at least one input.
5. The method of claim 1 wherein a set of quantum devices in the plurality of quantum devices represents a binary value of the product.
6. A computer system for factoring a product, the computer system comprising:
a central processing unit;
a multiplication circuit in communication with the central processing unit, the multiplication circuit comprising a plurality of bitwise multipliers, each bitwise multiplier including:
a plurality of quantum devices;
a plurality of coupling devices, each of the coupling devices coupling a pair of the quantum devices;
a plurality of inputs;
a plurality of outputs; and
a memory coupled to the central processing unit, the memory storing at least one program module encoding:
instructions for setting an initial condition of the multiplication circuit, the initial condition including:
a local bias value for at least one of the quantum devices;
a coupling value for at least one coupling devices; and
a binary value of the product to be factored;
instructions for performing a backwards evolution of the multiplication circuit; and
instructions for reading out a final state of at least one of the quantum devices, thereby determining a factor of the product.
7. The computer system of claim 6 wherein the plurality of quantum devices are arranged in a two-dimensional grid.