Systems and methods for solving computational problems

摘要

Solving computational problems may include generating a logic circuit representation of the computational problem, encoding the logic circuit representation as a discrete optimization problem, and solving the discrete optimization problem using a quantum processor. Output(s) of the logic circuit representation may be clamped such that the solving involves effectively executing the logic circuit representation in reverse to determine input(s) that corresponds to the clamped output(s). The representation may be of a multiplication circuit. The discrete optimization problem may be composed of a set of miniature optimization problems, where each miniature optimization problem encodes a respective logic gate from the logic circuit representation. A multiplication circuit may employ binary representations of factors, and these binary representations may be decomposed to reduce the total number of variables required to represent the multiplication circuit.

主权项

1. A method of operating a digital computer system and a quantum processor to factor an N-bit integer p as a product of a pair of integers a and b, the method comprising:
representing a, b, and p in binary using the digital computer system; decomposing the binary representations of a and b into two respective components (ah, al) and (bh, bl) via the digital computer system; constructing at least three component logic circuits which perform the multiplications of ahbh, albl, and (ah+al)(bh+bl), respectively, via the digital computer system, wherein each of the at least three component logic circuits includes at least one respective logic gate; encoding each respective one of the at least three component logic circuits which perform the multiplications of ahbh, albl, and (ah+al)(bh+bl), respectively, as a respective discrete optimization problem using the digital computer system, wherein each respective discrete optimization problem includes a respective set of miniature optimization problems, each miniature optimization problem encoding a respective one of the logic gates from the at least three component logic circuits, and wherein each respective miniature optimization problem is characterized by a respective objective function that is minimized when a truth table of the corresponding logic gate is obeyed; and solving each respective discrete optimization problem using the quantum processor, wherein solving each respective discrete optimization problem gives the components (ah, al) and (bh, bl) of the binary representations of a and b.