# Patent

## Title
Systems and methods for solving computational problems

## Abstract

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.

## Background
BACKGROUND
Field
The present systems, methods and articles generally relate to solving computational problems and particularly relate to solving discrete optimization problems and/or constraint satisfaction problems by reverse or undirected execution of their corresponding logic circuit representations.
Discrete Optimization
In mathematics and computer science, an optimization problem is one in which an optimal value of at least one parameter is sought. Typically, the parameter in question is defined by an objective function which comprises at least one variable. The optimal value of the parameter is then achieved by determining the value(s) of the at least one variable that maximize or minimize the objective function.
Discrete optimization is simply a special-case of optimization for which the variables used in the objective function are restricted to assume only discrete values. For example, the variables in the objective function may be restricted to all or a subset of the integers.
Constraint Satisfaction
The maximization or minimization of the objective function in an optimization problem (discrete or otherwise) is typically subject to a set of constraints, where a valid result may be required to satisfy all, or at least a subset, of the constraints. In some applications, simply finding a solution that satisfies all, or a subset, of the constraints may be all that is desired (i.e., there may be no additional objective function requiring maximization or minimization). Such problems are known as “constraint satisfaction problems” and may be viewed as a class of optimization problems in which the objective function is a measure of how well the constraints are (or are not) satisfied. Thus, throughout the remainder of this specification, the term “optimization problem” is used to encompass all forms of optimization problems, including constraint satisfaction problems.
Quadratic Unconstrained Binary Optimization Problems
A quadratic unconstrained binary optimization (“QUBO”) problem is a form of discrete optimization problem that involves finding a set of N binary variables {xi} that minimizes an objective function of the form:




  
    E
    ⁡
    
      (
      
        
          x
          1
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          x
          N
        
      
      )
    
  
  =
  
    
      ∑
      
        i
        ≤
        j
      
      N
    
    ⁢
    
      
        Q
        ij
      
      ⁢
      
        x
        i
      
      ⁢
      
        x
        j
      
    
  




where Q is typically a real-valued upper triangular matrix that is characteristic of the particular problem instance being studied. QUBO problems are known in the art and applications arise in many different fields, for example machine learning, pattern matching, economics and finance, and statistical mechanics, to name a few.

Logic Circuits

For any problem that can be solved, a solution may be reached by following a prescribed set of steps. In many cases, the prescribed set of steps may be designed to include a set of logical steps called “logical operations.” Logical operations are the fundamental steps that are typically implemented in digital electronics and most classical computer algorithms.
For many computational problems, a sequence of steps that leads to a solution can be described by a logic circuit representation. A logic circuit representation includes at least one logical input that is transformed to at least one logical output through at least one logical operation. A logic circuit representation may include any number of logical operations arranged either in series or in parallel (or a combination of series and parallel operations), where each logical operation has a corresponding set of at least one intermediate logical input and at least one intermediate logical output. Throughout this specification and the appended claims, the terms “intermediate logical input” and “intermediate logical output” are often used. Unless the specific context requires otherwise, the term “intermediate” here is intended to denote an input to/output from an individual logic gate which is an intermediate input/output with respect to the overall logic circuit. However, those of skill in the art will appreciate that a logical input to a logic circuit may correspond to an intermediate logical input to a particular logic gate, and similarly a logical output from a logic circuit may correspond to an intermediate logical output from a particular logic gate. For a first logical operation arranged in series with a second logical operation, at least one intermediate logical output from the first logical operation may correspond to at least one intermediate logical input to the second logical operation.
Each logical operation in a logic circuit is represented by a logic gate, for example, the NAND gate or the XOR gate, or a combination of logic gates. A logical operation may include any number of logic gates arranged either in series or in parallel (or a combination of series and parallel gates), where each logic gate has a corresponding set of at least one intermediate logical input and at least one intermediate logical output. For a first logic gate arranged in series with a second logic gate, at least one intermediate logical output from the first logic gate may correspond to at least one intermediate logical input to the second logic gate. The complete logic circuit representation of a computational problem may include any number of intermediate logical operations which themselves may include any number of intermediate logic gates. Furthermore, the at least one logical input to the logic circuit representation may traverse any number of intermediate logical inputs and intermediate logical outputs in being transformed to the at least one logical output from the logic circuit representation. Unless the specific context requires otherwise, throughout the remainder of this specification and the appended claims the terms “logical input” and “logical output” are used to generally describe any inputs and outputs in a logic circuit representation, including intermediate inputs and outputs.
In some implementations, one or more logical inputs may produce a plurality of logical outputs. For example, if the circuit, an operation, or a gate produces an N-bit number as the result, then N logical outputs may be required to represent this number. Alternatively, one or more logical inputs may produce a single logical output. For example, if the circuit, an operation, or a gate produces TRUE or FALSE as the result, then only one logical output may be required to convey this information. A circuit that produces TRUE or FALSE as the result embodies “Boolean logic” and is sometimes referred to as a “Boolean circuit.” Boolean circuits are commonly used to represent NP-complete constraint satisfaction problems.
Quantum Processor
A computer processor may take the form of an analog processor, for instance a quantum processor such as a superconducting quantum processor. A superconducting quantum processor may include a number of qubits and associated local bias devices, for instance two or more superconducting qubits. Further detail and embodiments of exemplary quantum processors that may be used in conjunction with the present systems, methods, and apparatus are described in US Patent Publication No. 2006-0225165 (now U.S. Pat. No. 7,533,068), US Patent Publication 2008-0176750, U.S. patent application Ser. No. 12/266,378 published as U.S. Patent Publication 2009-0121215, and PCT Patent Application Serial No. PCT/US09/37984 published as PCT Patent Publication 2009-120638.
Adiabatic Quantum Computation
Adiabatic quantum computation typically involves evolving a system from a known initial Hamiltonian (the Hamiltonian being an operator whose eigenvalues are the allowed energies of the system) to a final Hamiltonian by gradually changing the Hamiltonian. A simple example of an adiabatic evolution is:

He=(1−s)Hi+sHf 

where Hi is the initial Hamiltonian, Hf is the final Hamiltonian, He is the evolution or instantaneous Hamiltonian, and s is an evolution coefficient which controls the rate of evolution. As the system evolves, the coefficient s goes from 0 to 1 such that at the beginning (i.e., s=0) the evolution Hamiltonian He is equal to the initial Hamiltonian Hi and at the end (i.e., s=1) the evolution Hamiltonian He is equal to the final Hamiltonian Hf. Before the evolution begins, the system is typically initialized in a ground state of the initial Hamiltonian Hi and the goal is to evolve the system in such a way that the system ends up in a ground state of the final Hamiltonian Hf at the end of the evolution. If the evolution is too fast, then the system can be excited to a higher energy state, such as the first excited state. In the present systems, methods, and apparatus, an “adiabatic” evolution is considered to be an evolution that satisfies the adiabatic condition:

{dot over (s)}|1|dHe/ds|0|=δg2(s)

where {dot over (s)} is the time derivative of s, g(s) is the difference in energy between the ground state and first excited state of the system (also referred to herein as the “gap size”) as a function of s, and δ is a coefficient much less than 1.

The evolution process in adiabatic quantum computing may sometimes be referred to as annealing. The rate that s changes, sometimes referred to as an evolution or annealing schedule, is normally slow enough that the system is always in the instantaneous ground state of the evolution Hamiltonian during the evolution, and transitions at anti-crossings (i.e., when the gap size is smallest) are avoided. Further details on adiabatic quantum computing systems, methods, and apparatus are described in U.S. Pat. No. 7,135,701.
Quantum Annealing
Quantum annealing is a computation method that may be used to find a low-energy state, typically preferably the ground state, of a system. Similar in concept to classical annealing, the method relies on the underlying principle that natural systems tend towards lower energy states because lower energy states are more stable. However, while classical annealing uses classical thermal fluctuations to guide a system to its global energy minimum, quantum annealing may use quantum effects, such as quantum tunneling, to reach a global energy minimum more accurately and/or more quickly. It is known that the solution to a hard problem, such as a combinatorial optimization problem, may be encoded in the ground state of a system Hamiltonian and therefore quantum annealing may be used to find the solution to such hard problems. Adiabatic quantum computation is a special case of quantum annealing for which the system, ideally, begins and remains in its ground state throughout an adiabatic evolution. Thus, those of skill in the art will appreciate that quantum annealing systems and methods may generally be implemented on an adiabatic quantum computer, and vice versa. Throughout this specification and the appended claims, any reference to quantum annealing is intended to encompass adiabatic quantum computation unless the context requires otherwise.
Quantum annealing is an algorithm that uses quantum mechanics as a source of disorder during the annealing process. The optimization problem is encoded in a Hamiltonian HP, and the algorithm introduces strong quantum fluctuations by adding a disordering Hamiltonian HD that does not commute with HP. An example case is:

HE=HP+ΓHD,

where Γ changes from a large value to substantially zero during the evolution and HE may be thought of as an evolution Hamiltonian similar to He described in the context of adiabatic quantum computation above. The disorder is slowly removed by removing HD (i.e., reducing Γ). Thus, quantum annealing is similar to adiabatic quantum computation in that the system starts with an initial Hamiltonian and evolves through an evolution Hamiltonian to a final “problem” Hamiltonian HP whose ground state encodes a solution to the problem. If the evolution is slow enough, the system will typically settle in a local minimum close to the exact solution; the slower the evolution, the better the solution that will be achieved. The performance of the computation may be assessed via the residual energy (distance from exact solution using the objective function) versus evolution time. The computation time is the time required to generate a residual energy below some acceptable threshold value. In quantum annealing, HP may encode an optimization problem and therefore HP may be diagonal in the subspace of the qubits that encode the solution, but the system does not necessarily stay in the ground state at all times. The energy landscape of HP may be crafted so that its global minimum is the answer to the problem to be solved, and low-lying local minima are good approximations.
The gradual reduction of Γ in quantum annealing may follow a defined schedule known as an annealing schedule. Unlike traditional forms of adiabatic quantum computation where the system begins and remains in its ground state throughout the evolution, in quantum annealing the system may not remain in its ground state throughout the entire annealing schedule. As such, quantum annealing may be implemented as a heuristic technique, where low-energy states with energy near that of the ground state may provide approximate solutions to the problem.
BRIEF SUMMARY
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, may be summarized as including 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. Solving each respective discrete optimization problem using a quantum processor may include performing at least one of adiabatic quantum computation and quantum annealing. The method may further include mapping each respective discrete optimization problem to the quantum processor. The quantum processor may comprise qubits and couplers, and mapping each respective discrete optimization problem to the quantum processor may include, for each respective discrete optimization problem, programming the qubits and the couplers of the quantum processor in a configuration representing a problem Hamiltonian that corresponds to the discrete optimization problem.
A system to factor an N-bit integer p as a product of a pair of integers a and b may be summarized as including at least one quantum processor; a digital computer system including at least one non-transitory digital processor-readable medium which stores instructions that cause the at least one quantum processor to factor an N-bit integer p by: 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. The at least one quantum processor may include at least one quantum processor configured to perform adiabatic quantum computation or quantum annealing. The at least one quantum processor may include at least one superconducting quantum processor. The non-transitory processor-readable medium may store a discrete optimization module, and the instructions that cause the at least one quantum processor to factor an N-bit integer p may be stored in the discrete optimization module.



BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING(S)
In the drawings, identical reference numbers identify similar elements or acts. The sizes and relative positions of elements in the drawings are not necessarily drawn to scale. For example, the shapes of various elements and angles are not drawn to scale, and some of these elements are arbitrarily enlarged and positioned to improve drawing legibility. Further, the particular shapes of the elements as drawn are not intended to convey any information regarding the actual shape of the particular elements, and have been solely selected for ease of recognition in the drawings.
FIG. 1A is a functional diagram of an exemplary logic circuit.
FIG. 1B is a functional diagram of an exemplary Boolean circuit.
FIG. 2A is a flow-diagram of an embodiment of a method for solving a computational problem in accordance with the present systems and methods.
FIG. 2B is a flow-diagram of an embodiment of another method for solving a computational problem in accordance with the present systems and methods.
FIG. 3A is a schematic diagram of an embodiment of a logic circuit representation of a computational problem in accordance with the present systems and methods.
FIG. 3B is a schematic diagram of the same embodiment of a logic circuit representation as depicted in FIG. 3A, only FIG. 3B further illustrates the clamping of specific logical outputs in accordance with the present systems and methods.
FIG. 4 is a flow-diagram of an embodiment of yet another method for solving a computational problem in accordance with the present systems and methods.
FIG. 5 is a schematic diagram of an exemplary quantum processor implementing a single global annealing signal line.
FIG. 6 is a schematic diagram of an embodiment of a quantum processor that incorporates multiple annealing signal lines in accordance with the present systems and methods.
FIG. 7 is an approximate graph showing an exemplary annealing schedule for a system that implements a single global annealing signal line.
FIG. 8 is an approximate graph showing an exemplary annealing schedule for a system that implements multiple independently-controlled annealing signal lines in accordance with the present systems and methods.
FIG. 9 is another approximate graph showing an exemplary annealing schedule for a system that implements multiple independently-controlled annealing signal lines in accordance with the present systems and methods.
FIG. 10 is a schematic diagram of a portion of a superconducting quantum processor designed for adiabatic quantum computation (and/or quantum annealing).
FIG. 11 is a flow-diagram of an embodiment of a method for solving a computational problem in accordance with the present systems and methods.
FIG. 12 is a schematic diagram of an embodiment of a processor system in accordance with the present systems and methods.
FIG. 13 is a multiplication table showing the 8-bit product of two 4-bit integers.
FIG. 14 shows respective truth tables for the and gate, half adder, and full adder.
FIG. 15 is a schematic diagram showing a constraint network representing the multiplication of two 8-bit numbers.
FIG. 16 is a schematic diagram showing an optimization network representing the multiplication of two odd 8-bit numbers.
FIG. 17 is a schematic diagram showing detail of a disaggregated half adder located at the intersection of two variables.
FIG. 18 is a schematic diagram showing detail of a disaggregated full adder located at the intersection of two variables.
FIG. 19 is a flow-diagram of an embodiment of a method for 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 in accordance with the present systems and methods.
FIG. 20 illustrates an exemplary digital computer system including a digital computer processor that may be used to perform classical digital processing tasks described in the present systems and methods.



DETAILED DESCRIPTION
In the following description, some specific details are included to provide a thorough understanding of various disclosed embodiments. One skilled in the relevant art, however, will recognize that embodiments may be practiced without one or more of these specific details, or with other methods, components, materials, etc. In other instances, well-known structures associated with quantum processors, such as quantum devices, coupling devices, and control systems including microprocessors and drive circuitry have not been shown or described in detail to avoid unnecessarily obscuring descriptions of the embodiments of the present systems and methods. Throughout this specification and the appended claims, the words “element” and “elements” are used to encompass, but are not limited to, all such structures, systems and devices associated with quantum processors, as well as their related programmable parameters.
Unless the context requires otherwise, throughout the specification and claims which follow, the word “comprise” and variations thereof, such as, “comprises” and “comprising” are to be construed in an open, inclusive sense, that is as “including, but not limited to.”
Reference throughout this specification to “one embodiment,” or “an embodiment,” or “another embodiment” means that a particular referent feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment. Thus, the appearances of the phrases “in one embodiment,” or “in an embodiment,” or “another embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.
It should be noted that, as used in this specification and the appended claims, the singular forms “a,” “an,” and “the” include plural referents unless the content clearly dictates otherwise. Thus, for example, reference to a problem-solving system including “a quantum processor” includes a single quantum processor, or two or more quantum processors. It should also be noted that the term “or” is generally employed in its sense including “and/or” unless the content clearly dictates otherwise.
The headings provided herein are for convenience only and do not interpret the scope or meaning of the embodiments.
The various embodiments described herein provide systems and methods for solving computational problems. These systems and methods introduce a technique whereby a logic circuit representation of a computational problem is encoded as a discrete optimization problem, such as a QUBO, and this discrete optimization problem is then solved using a computer processor, such as a quantum processor. In some embodiments, the quantum processor may be specifically adapted to facilitate solving such discrete optimization problems by enabling the simultaneous control of multiple annealing schedules.
Throughout this specification and the appended claims, reference is often made to a “logic circuit representation of a computational problem.” As previously described, a logic circuit may incorporate a set of logical inputs, a set of logical outputs, and a set of logic gates (e.g., NAND gates, XOR gates, and the like) that transform the logical inputs to the logical outputs through a set of intermediate logical inputs and intermediate logical outputs. A complete logic circuit may include a representation of the input(s) to the computational problem, a representation of the output(s) of the computational problem, and a representation of the sequence of intermediate steps in between the input(s) and the output(s). Thus, for the purposes of the present systems and methods, the computational problem is defined by its input(s), its output(s), and the intermediate steps that transform the input(s) to the output(s) and a “logic circuit representation of the computational problem” accordingly may include all of these elements.
In some embodiments, the structure of a logic circuit stratifies into layers. For example, the logical input(s) may represent a first layer, each sequential logical (or arithmetic) operation may represent a respective additional layer, and the logical output(s) may represent another layer. As previously described, a logical operation may be executed by a single logic gate or by a combination of logic gates, depending on the specific logical operation being executed. Thus, a “layer” in a logic circuit may include a single logic gate or a combination of logic gates depending on the particular logic circuit being implemented.
FIG. 1A shows a functional diagram of an exemplary logic circuit 100a. Logic circuit 100a may embody a logic circuit representation of a computational problem and includes a set of five inputs A1-A5 that are transformed to a set of five outputs P1-P5 through a set of N layers L1-LN. Those of skill in the art will appreciate that alternative embodiments of logic circuits may include any number of inputs and any number of outputs (e.g., X inputs and Y outputs, where X may or may not be equal to Y) connected through any number of layers and/or logic gates. Furthermore, the number of outputs from any given layer may be different from the number of inputs to that layer, and while layers L1-LN are all connected in series in logic circuit 100a, alternative logic circuits may include layers and/or logic gates that are connected in parallel.
Logic circuit 100a includes a set of five outputs P1-P5 which together may represent a solution to a computational problem. However, for some problems the desired output(s) may already be known, or be restricted to satisfy some known criteria. In such instances, the logic circuit may include an additional component which assesses whether the solution represented by the logic states P1-P5 is acceptable. The additional component may then provide a single output which is TRUE if the solution is acceptable and FALSE if the solution is not acceptable. This is an example of a Boolean circuit.
FIG. 1B shows a functional diagram of an exemplary Boolean circuit 100b. Boolean circuit 100b is similar to logic circuit 100a from FIG. 1A, except that Boolean circuit 100b is adapted to provide a single Boolean output Bool from intermediate logical outputs P1-P5. If intermediate logical outputs P1-P5 represent an acceptable solution, then the single output Bool is TRUE; otherwise, the single output Bool is FALSE.
The present systems and methods introduce novel techniques for solving computational problems by encoding a logic circuit representation of the original computational problem as a discrete optimization problem. Solving the discrete optimization problem then effectively executes the logic circuit to solve the original computational problem. The methods described herein may be implemented using any form of computer processor; however, the discrete optimization problems that generally result from this approach are very hard and often cannot be solved using known classical solvers. These discrete optimization problems are particularly well-suited to be solved using a quantum processor, or more generally a computer processor that harnesses quantum effects to achieve computation. In some embodiments, the discrete optimization problem is cast as a QUBO problem (where energy minimization is sought) by configuring the qubits and couplers in a quantum processor (e.g., defining the problem Hamiltonian in an implementation of quantum annealing) such that there is a positive energy penalty introduced when a particular combination of intermediate input(s) and intermediate output(s) of a logic gate violates the truth table of the gate. For example, an AND gate having two intermediate inputs x1 and x2 and one intermediate output z may be represented by an objective function such as:

HAND(x1,x2;z)=x1x2−2(x1+x2)z+3z 

where the function is minimized (i.e., HAND=0) when the parameters x1, x2, and z are set such that the truth table of the AND gate is obeyed and a positive energy penalty is introduced (e.g., H>0) when the truth table of the AND gate is violated. In the case of an AND gate, this means that HAND(0,0,0)=HAND(0,1,0)=HAND(1,0,0)=HAND(1,1,1)=0, and HAND(x1,x2;z)>0 for all other combinations of x1, x2, and z. Similarly, the OR gate may, for example, be represented by an objective function such as:

HOR(x1,x2;z)=HAND(1−x1,1−x2;1−z)

and the NOT gate may, for example, be represented by an objective function such as:

HNOT(x;z)=2xz−x−z+1

From the above, those of skill in the art will appreciate how a similar objective function may be defined for any logic gate. Thus, in some embodiments, the QUBO problem representing a logic circuit is essentially comprised of a plurality of miniature optimization problems, where each gate in the logic circuit corresponds to a particular miniature optimization problem. Each miniature optimization problem is minimized (i.e., solved) when the inputs x1, x2 and the output z are set such that the truth table of the particular gate to which the miniature optimization problem corresponds is obeyed. In some embodiments, the values of the inputs x1, x2 and the output z may each correspond to the value (i.e., state) of a respective qubit in a quantum processor.

FIG. 2A shows a flow diagram of an embodiment of a method 200a for solving a computational problem in accordance with the present systems and methods. Method 200a includes three acts 201-203a, though those of skill in the art will appreciate that alternative embodiments may omit certain acts and/or include additional acts. At 201, a logic circuit representation of the computational problem is generated. Exemplary logic circuit representations are described in FIGS. 1A and 1B and these may be generated using systems and methods that are known in the art. For example, a logic circuit representation of the computational problem may be generated using a classical digital computer processor. In this case, the logic circuit representation of the computational problem may be stored in at least one computer- or processor-readable storage medium, such as a computer-readable non-transitory storage medium or memory (e.g., volatile or non-volatile). For computational problems of the class NP, the logic circuit representation will typically be polynomially-sized. At 202, the logic circuit representation of the computational problem is encoded as a discrete optimization problem. This encoding may be achieved, for example, using a classical digital computer processor. In this case, the discrete optimization problem may be stored in at least one computer- or processor-readable storage medium, such as a computer-readable non-transitory storage medium or memory (e.g., volatile or non-volatile). In some embodiments, the logic circuit may be encoded as an optimization objective, or a set of optimization objectives, so that bit strings which satisfy the logic circuit have energy of zero and all other bit strings have energy greater than zero. At 203a, the discrete optimization problem is solved, thereby establishing a solution to the original computational problem. In some embodiments, the discrete optimization problem may be solved using a computer processor, such as a quantum processor. Solving the discrete optimization problem may then involve, for example, evolving the quantum processor to the configuration that minimizes the energy of the system in order to establish a bit string that satisfies the optimization objective(s).
In some embodiments, encoding the logic circuit as a discrete optimization problem at 202 of method 200a enables a particular approach to solving the discrete optimization problem at 203a. This approach is described in FIG. 2B.
FIG. 2B shows a flow-diagram of an embodiment of a method 200b for solving a computational problem in accordance with the present systems and methods. Method 200b is similar to method 200a from FIG. 2A and includes three main acts 201-203b. Acts 201-203b of method 200b are the same, respectively, as acts 201-203a of method 200a, except that in method 200b act 203b is further broken down to include three acts 231-233. That is, in some embodiments the act of solving the discrete optimization problem 203b may itself include three acts 231-233. At 231, the discrete optimization problem is mapped to a computer processor. In some embodiments, the computer processor may include a quantum processor and mapping the discrete optimization problem to the computer processor may include programming the elements (e.g., qubits and couplers) of the quantum processor. Mapping the discrete optimization problem to the computer processor may include the discrete optimization problem in at least one computer or processor-readable storage medium, such as a computer-readable non-transitory storage medium or memory (e.g., volatile or non-volatile). At 232, at least one logical output is clamped. Throughout this specification and the appended claims, the term “clamped” is used to describe a variable that is held substantially fixed while the discrete optimization problem is solved, thereby forcing all of the other variables to adjust to accommodate the substantially fixed variable. Thus, to “clamp” an output means to program that output such that its state remains substantially fixed while the discrete optimization problem is solved. In the exemplary objective function defining the AND gate HAND(x1, x2; z) given above, clamping the output means substantially fixing the value of z. In an application of quantum annealing, the qubit corresponding to output z may be programmed to maintain a substantially fixed state while the qubits corresponding to inputs x1 and x2 may be evolved to determine respective states which minimize the objective function HAND, where the objective function HAND is encoded, at least in part, by the programmable couplings between the qubits representing the x1, x2, and z variables. For act 232, the at least one logical output that is clamped may be an output of the complete logic circuit representation, or it may be an intermediate logical output of a particular logical operation and/or a particular logic gate. At 233, the discrete optimization problem is solved by determining at least one logical input to the logic circuit that corresponds to the at least one clamped output.
In traditional problem-solving methods, the inputs to the problem are effectively clamped because they generally remain fixed for a given problem instance while the corresponding outputs are determined. However, in some embodiments of the present systems and methods it is the outputs of the problem (or the intermediate output(s) of a particular logical operation and/or logic gate) that are clamped so that solving the discrete optimization problem involves determining the inputs that correspond to the clamped outputs. Thus, some embodiments of the present systems and methods describe problem-solving techniques in which a logic circuit representation of the problem is established and then the logic circuit is effectively executed in reverse, or in an undirected fashion, to determine which inputs correspond to a given set of outputs. This problem-solving approach is illustrated in FIGS. 3A and 3B.
FIG. 3A is a schematic diagram of a logic circuit representation 300 of a computational problem. Circuit 300 includes a set of six logical inputs 301-306 and six logical outputs 311-316, though those of skill in the art will appreciate that an alternative logic circuit may incorporate any number of logical inputs and any number of logical outputs. Logical inputs 301-306 are transformed to logical outputs 311-316 through a plurality of logic gates 320 (only one called out in the Figure to reduce clutter). Each logic gate 320 has a corresponding set of at least one intermediate logical input 331 (only one called out in the Figure) and at least one intermediate logical output 332 (only one called out in the Figure). In some instances (as is the case for the specific logic gate labeled as 320), an intermediate logical input (e.g., 331) may correspond to an input (e.g., 301) to the complete circuit 300 and/or an intermediate logical output (e.g., 332) may correspond to an output (e.g., 311) from the complete circuit 300. Circuit 300 represents an embodiment of the general method 200a described in FIG. 2A. In accordance with the present systems and methods, circuit 300 may be mapped to a discrete optimization problem, such as a QUBO problem, which may then be stored and operated on in at least one computer or processor-readable storage medium, such as a computer-readable non-transitory storage medium or memory (e.g., volatile or non-volatile).
FIG. 3B is a schematic diagram of the same logic circuit representation 300 as depicted in FIG. 3A, only FIG. 3B further illustrates the clamping of specific logical outputs. In FIG. 3B, logical outputs 311 and 316, as well as intermediate logical output 333, have all been clamped—meaning that each has been fixed in a specific state (i.e., either 1 or 0). This clamping is illustrated by thickening of the lines corresponding to outputs 311, 316, and 333. Depending on the application, simultaneously clamped outputs (e.g., 311, 316, and 333) may be clamped in the same state (e.g., 0) or they may each be clamped in any state (e.g., any combination of 0s and 1s). While FIG. 3A represents an embodiment of general method 200a from FIG. 2A, FIG. 3B is an embodiment of method 200b from FIG. 2B. Thus, in solving logic circuit 300 with clamped variables 311, 316, and 333 as illustrated in FIG. 3B, a configuration having a set of inputs 301-306 and remaining outputs 312-315 that correspond to the clamped variables 311, 316 and 333 is determined. A particularly useful application of this technique is the case where the logic circuit representation of the computational problem is a Boolean circuit designed, for example, to verify a solution to the computational problem.
FIG. 4 shows a flow-diagram of an embodiment of a method 400 for solving a computational problem in accordance with the present systems and methods. Method 400 includes four acts 401-404, though those of skill in the art will appreciate that alternative embodiments may omit certain acts and/or include additional acts. At 401, a Boolean circuit that verifies a solution to the computational problem is generated. A Boolean circuit typically has a single output that may be one of two states: either TRUE or FALSE. In some embodiments, the Boolean circuit may test the solution to the computational problem and output TRUE if the solution is acceptable or FALSE is the solution is not acceptable. The Boolean circuit may be generated, for example, using a classical digital computer processor. In this case, the Boolean circuit may be stored in at least one computer or processor-readable storage medium, such as a computer-readable non-transitory storage medium or memory (e.g., volatile or non-volatile). At 402, the Boolean circuit is encoded as a discrete optimization problem in a manner similar to that described for act 202 of methods 200a and 200b. At 403, the output of the Boolean circuit is clamped. Depending on the nature of the problem, the output may be clamped as TRUE or it may be clamped as FALSE. In embodiments that are implemented on a quantum processor, this means that the qubit or qubits that represent the Boolean output are programmed in a substantially fixed state corresponding to either TRUE or FALSE. At 404, the discrete optimization problem is solved to effectively execute the Boolean circuit in reverse and determine at least one input that corresponds to the clamped output. The Boolean circuit may be solved, for example, by an operation of a quantum processor. In this case, the Boolean circuit may be stored and operated on in at least one computer or processor-readable storage medium, such as a computer-readable non-transitory storage medium or memory (e.g., volatile or non-volatile).
An example of an application where it may be desirable to clamp the output of the Boolean circuit as TRUE is factoring. In this case, the Boolean circuit may represent a multiplication circuit corresponding to the factoring problem, and clamping the Boolean output as TRUE enables the inputs (e.g., factors) that correspond to the product to be determined. An example of an application where it may be desirable to clamp the output of the Boolean circuit as FALSE is software verification and validation (also known as software quality control). In this case, the code embodying a piece of software or program may be represented by a Boolean logic circuit, where the output of the circuit (and/or any particular intermediate logical operation and/or logic gate) will be TRUE if the code has no errors (i.e., “bugs”). Clamping the output of the circuit (or intermediate output of a particular logical operation and/or logic gate) as FALSE then determines which inputs, if any, may produce the FALSE output. If such inputs exist, they may be identified as bugs in the code. Those of skill in the art will appreciate that the code embodying a piece of software may typically be stored on a physical medium, such as at least one computer- or processor-readable storage medium and/or a non-transitory storage medium or memory (e.g., volatile or non-volatile).
As previously described, methods 200a, 200b, and 400 are well-suited to be implemented using a quantum processor. Furthermore, these methods are particularly well-suited to be executed using an adiabatic quantum processor and/or a quantum processor that implements quantum annealing. Quantum annealing and/or adiabatic quantum computation may be implemented in a variety of different ways, but the end goal is generally the same: find a low-energy state, such as a ground state, of a system Hamiltonian where the system Hamiltonian encodes a computational problem and the low-energy state represents a solution to the computational problem. Approaches to meeting this goal generally involve evolving the elements of the quantum processor by the application of a dynamic annealing signal. Typically, a single global annealing signal line is coupled to all of the qubits in the quantum processor such that the same dynamic waveform is applied to every qubit. This ensures uniformed timing across the processor and also minimizes the number of physical lines required to evolve the system.
FIG. 5 shows a schematic diagram of an exemplary quantum processor 500 implementing a single global annealing signal line 530. Quantum processor 500 includes sixteen qubits 501-516 and forty-two couplers 520 (only one called out in the Figure) in a lattice architecture embodying nearest neighbor and next-nearest neighbor coupling. Global annealing signal line 530 is used to couple the same dynamic annealing waveform to each of qubits 501-516. Those of skill in the art will appreciate that the number of qubits and couplers, as well as the nearest neighbor and next-nearest neighbor coupling architecture, in quantum processor 500 are all used for illustrative purposes and that a quantum processor may implement any number of qubits and couplers arranged according to any coupling architecture. Qubits 501-516 and couplers 520 are capable of storing and performing operations on computer-readable information; thus, for the purposes of the present systems and methods, a quantum processor (e.g., 500) includes computer- or processor-readable storage media and/or non-transitory storage media or memory (e.g., volatile or non-volatile).
In some embodiments, the various methods described herein (e.g., methods 200a, 200b, and 400) may be implemented on a quantum processor having a single global annealing signal line, such as quantum processor 500. In other embodiments, however, the various methods described herein may benefit from a quantum processor that includes multiple annealing signal lines each capable of administering a unique dynamic waveform to a respective set of qubits in the processor.
FIG. 6 shows a schematic diagram of an embodiment of a quantum processor 600 that incorporates multiple annealing signal lines 631-634. Quantum processor 600 includes sixteen qubits 601-616 and forty-two couplers 620 (only one called out in the Figure) in a lattice architecture embodying nearest neighbor and next-nearest neighbor coupling. The four global annealing signal lines 631-634 are each arranged to couple a unique dynamic annealing waveform to the qubits in a respective row. Those of skill in the art will appreciate that the number of qubits, couplers, and annealing signal lines, as well as the coupling architecture and the layout of the annealing signal lines in quantum processor 600, are all used for illustrative purposes and that a quantum processor may implement any number of qubits, couplers, and annealing signal lines arranged according to any designer's preferences.
In embodiments in which the structure of a logic circuit (such as the logic circuit representations from methods 200a, 200b, and 400) stratifies into layers (for example, with the logical input(s) representing a first layer, each sequential logical operation representing a respective additional layer, and the logical output(s) representing another layer), each layer may be embodied by a respective set of qubits in the quantum processor. For example, in quantum processor 600 each row of qubits may be programmed to represent a respective layer of a logic circuit. That is, qubits 601-604 may be programmed to represent the inputs to a logic circuit, qubits 605-608 may be programmed to represent a first logical operation (executed by either one or a plurality of logic gates), qubits 609-612 may be programmed to represent a second logical operation (similarly executed by either one or a plurality of logic gates), and qubits 613-616 may be programmed to represent the outputs of the logic circuit. With various sets of qubits representing various layers of the problem, it can be advantageous to enable independent dynamic control of each respective set. For example, if a serial logic circuit (such as logic circuit 100a from FIG. 1A) is mapped to quantum processor 600, then the logical operation represented by qubits 609-612 may receive, as inputs, the outputs of the logical operation represented by qubits 605-608. It follows that the set of qubits 609-612 may advantageously be annealed after the set of qubits 605-608, and therefore a separate dynamic annealing signal line (i.e., lines 633 and 632, respectively) may be necessary to control each of the two sets of qubits.
Those of skill in the art will appreciate that the encoding of a logic circuit representation of a computational problem as a discrete optimization problem, and the subsequent mapping of the discrete optimization problem to a quantum processor, may result in any number of layers involving any number of qubits per layer. Furthermore, such a mapping may implement any scheme of inter-qubit coupling to enable any scheme of inter-layer coupling (i.e., coupling between the qubits of different layers) and intra-layer coupling (i.e., coupling between the qubits within a particular layer). The layout and number of elements presented in quantum processor 600 are used for illustrative purposes only and are in no way intended to limit the present system and methods.
The concept of implementing multiple annealing signal lines has previously been introduced (to facilitate system calibration) in PCT Patent Application Serial No. PCT/US2009/044537 published as PCT Patent Publication 2009-143166, where at least two annealing signal lines are implemented in such a way that no two coupled qubits are both coupled to the same annealing signal line. Conversely, in the present systems and methods it is preferred if the set of qubits that are controlled by a given annealing signal line includes at least two coupled qubits, because the set of qubits that are controlled by a given annealing signal line may correspond to a particular layer of a logic circuit representation and thus there will likely be at least some coupling between the at least two qubits that are in the same layer. However, the implementation of the teachings of PCT Application Serial No. PCT/US2009/044537 published as PCT Patent Publication 2009-143166 does not necessarily exclude the present systems and methods. Since multiple annealing signal lines may be programmed to carry the same annealing signal, any set of qubits that are coupled to the same annealing signal line may similarly be coupled to a pair of interdigitated annealing signal lines.
The application of multiple independently-controlled dynamic annealing signals in accordance with the present systems and methods enables a vastly increased variety and complexity of annealing schedules. This is illustrated in FIGS. 7-9.
FIG. 7 is an approximate graph showing an exemplary annealing schedule 700 for a system that implements a single global annealing signal line. The global annealing signal is represented by line 701 and is typically applied to all qubits in the quantum processor. In this example, the global annealing signal 701 starts at a maximum value and then gradually reduces to a minimum value (e.g., zero) by the end of the schedule. In conjunction with the annealing signal 701, a set of control signals 702 are typically applied to each qubit to contribute at least some of the terms of the problem Hamiltonian. These control signals typically begin at a minimum value (e.g., zero) and, as the annealing signal 701 is ramped down, are typically ramped up to a maximum value by the end of the schedule. Annealing schedule 700 is a common approach for systems that implement only a single global annealing signal line its versatility is limited by the fact that the same dynamic annealing waveform must be applied to all qubits.
Conversely, FIG. 8 is an approximate graph showing an exemplary annealing schedule 800 for a system that implements multiple (e.g., three) independently-controlled annealing signal lines in accordance with the present systems and methods. The three independently-controlled annealing signal lines are represented by lines 801, 811 and 821 and may each be used to anneal a respective one of three sets of qubits in a quantum processor. Unlike annealing schedule 700 from FIG. 7, the applied annealing signals 801, 811, 821 in schedule 800 each evolve differently over the course of the schedule. This means that over the course of annealing schedule 800 the three sets of qubits are each evolved in a different way. For example, qubits that are annealed by signal 801 evolve steadily from a maximum annealing signal to a minimum annealing signal (e.g., zero) over the course of schedule 800. However, qubits that are annealed by signal 811 are initially exposed to stronger annealing signals for a longer period of time as signal 811 does not begin to ramp down until long after signal 801. Furthermore, qubits that are annealed by signal 821 do not evolve at all because signal 821 remains at zero throughout the duration of schedule 800. Qubits that are annealed by signal 821 represent “clamped” variables and may, in accordance with methods 200b and 400, correspond to at least one output of a logic circuit representation.
The additional signals in schedule 800 (specifically, signals 802, 812, and 822) represent control signals that are respectively applied to the three sets of qubits to contribute at least some of the terms of the problem Hamiltonian. Similar to annealing schedule 700 from FIG. 7, in annealing schedule 800 each control signal 802, 812, 822 mirrors a respective annealing signal 801, 811, 821. That is, signals 801 and 802 respectively provide annealing and control signals to a first set of qubits; signals 811 and 812 respectively provide annealing and control signals to a second set of qubits; and signals 821 and 822 respectively provide annealing and control signals to a third set of qubits. At the end of the schedule, all control signals are applied at maximum value. Because the states of the qubits that are controlled by signal 822 are clamped in this example, signal 822 is applied at maximum value throughout the duration of schedule 800.
Annealing schedule 800 is illustrated herein as an example only, while the present systems and methods provide the versatility to enable many variations of annealing schedules. For example, in some embodiments an annealing signal may evolve in a non-linear manner, at a faster or slower rate than illustrated, and may even oscillate if appropriate. Furthermore, in some embodiments an annealing signal may not be mirrored by a corresponding control signal, or a control signal that mirrors an annealing signal may evolve in a way that does not coincide with the evolution of the corresponding annealing signal. In some embodiments, some annealing signals may complete their evolution before and/or after other annealing signals.
For illustrative purposes, FIG. 9 provides an approximate graph showing an exemplary annealing schedule 900 for a system that implements multiple independently-controlled annealing signal lines in accordance with the present systems and methods. In schedule 900, each respective annealing signal line is paired with a respective control signal line, and the two lines that make up each respective pair are illustrated using a distinguishable line-style. Annealing schedule 900 provides an example of a schedule in which multiple sets of qubits are effectively annealed in series, while the states of the qubits in one set remain clamped.
As illustrated in FIGS. 8 and 9, clamping the state of a qubit may be achieved by applying a static control signal to the qubit and no annealing signal. However, in practice a qubit that is coupled to other qubits in a quantum processor may be influenced by signals from those other qubits. For example, if a first qubit is coupled to a second qubit and an evolving annealing signal is applied to the second qubit then the first qubit may still effectively “see” a portion of that evolving annealing signal through the second qubit and be affected by it. In some embodiments, in order to achieve the desired clamping effect of applying a static control signal to a particular qubit as illustrated by line 822 in FIG. 8, it may be necessary to actually evolve (e.g., vary in magnitude over time) the applied control signal in order to compensate for fluctuations induced by the evolving annealing signal that is applied to another qubit to which the particular qubit is coupled. Thus, “clamping” an output may be achieved by programming a corresponding qubit in a substantially fixed state, but this may necessitate the application of a dynamic clamping signal if the state of the clamped qubit is undesirably evolved by a coupling to an unclamped qubit.
In accordance with some embodiments of the present systems, methods and apparatus, solving a discrete optimization problem (such as a QUBO problem) and/or a constraint satisfaction problem includes an implementation of quantum annealing or adiabatic quantum computation. As previously discussed, a typical adiabatic evolution may be represented by equation 1:

He=(1−s)HIn+sHf  (1)

where HIn is the initial Hamiltonian, Hf is the final or “problem” Hamiltonian, He is the evolution or instantaneous Hamiltonian, and s is the evolution coefficient which controls the rate of evolution. In general, s may vary from 0 to 1 with time t as s(t). A common approach to AQC, described, for example, in Amin, M. H. S., “Effect of local minima on quantum adiabatic optimization”, PRL 100, 130503 (2008), is to start with an initial Hamiltonian of the form shown in equation 2:




  
    
      
        
          H
          In
        
        =
        
          
            -
            
              1
              2
            
          
          ⁢
          
            
              ∑
              
                i
                =
                1
              
              n
            
            ⁢
            
              
                Δ
                i
              
              ⁢
              
                σ
                i
                x
              
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




where n represents the number of qubits, σix is the Pauli x-matrix for the ith qubit and Δi is the single qubit tunnel splitting induced in the ith qubit. Here, the σix terms are examples of “off-diagonal” terms. An initial Hamiltonian of this form may, for example, be evolved to a final Hamiltonian of the form:




  
    
      
        
          H
          f
        
        =
        
          -
          
            
              ɛ
              2
            
            [
            
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  n
                
                ⁢
                
                  
                    h
                    i
                  
                  ⁢
                  
                    σ
                    i
                    z
                  
                
              
              +
              
                
                  ∑
                  
                    i
                    ,
                    
                      j
                      =
                      1
                    
                  
                  n
                
                ⁢
                
                  
                    J
                    ij
                  
                  ⁢
                  
                    σ
                    i
                    z
                  
                  ⁢
                  
                    σ
                    j
                    z
                  
                
              
            
            ]
          
        
      
    
    
      
        (
        3
        )
      
    
  




where n represents the number of qubits, σiz is the Pauli z-matrix for the ith qubit, hi and Ji,j are dimensionless local fields coupled into each qubit, and ε is some characteristic energy scale for Hf. Here, the σiz and σizσjz terms are examples of “diagonal” terms. Throughout this specification and the appended claims, the terms “final Hamiltonian” and “problem Hamiltonian” are used interchangeably. In various embodiments of the present systems and methods, a logic circuit representation is converted to a discrete optimization problem such as a QUBO, and the QUBO is mapped directly to the problem Hamiltonian in the processor hardware. Hamiltonians such as HIn and Hf in equations 2 and 3, respectively, may be physically realized in a variety of different ways. A particular example is realized by an implementation of superconducting qubits.
FIG. 10 is a schematic diagram of a portion of a superconducting quantum processor 1000 designed for AQC (and/or quantum annealing). The portion of superconducting quantum processor 1000 shown in FIG. 10 includes two superconducting qubits 1001, 1002 and a tunable ZZ-coupler 1011 coupling information therebetween. While the portion of quantum processor 1000 shown in FIG. 10 includes only two qubits 1001, 1002 and one coupler 1011, those of skill in the art will appreciate that quantum processor 1000 may include any number of qubits and any number of coupling devices coupling information therebetween.
The portion of quantum processor 1000 shown in FIG. 10 may be implemented to physically realize AQC by initializing the system with the Hamiltonian described by equation 2 and evolving the system to the Hamiltonian described by equation 3 in accordance with the evolution described by equation 1. In various embodiments of the present systems and methods, determining a low energy state, such as the ground state, of the Hamiltonian described by equation 3 may map directly to a QUBO problem, where the QUBO problem encodes a logic circuit representation of a computational problem. This mapping between the QUBO and the problem Hamiltonian is achieved, at least in part, by the programmable assignments to the parameters in the Hamiltonian described by equation 3. Evolving the quantum processor 1000 to determine the ground state of the Hamiltonian described by equation 3 therefore solves the QUBO problem, which effectively executes the logic circuit representation of the computational problem. Quantum processor 1000 includes a plurality of programming interfaces 1021-1025 that are used to configure and control the state of quantum processor 1000. Each of programming interfaces 1021-1025 may be realized by a respective inductive coupling structure, as illustrated, that communicates with a programming system (not shown). Such a programming system may be separate from quantum processor 1000, or it may be included locally (i.e., on-chip with quantum processor 1000) as described in US Patent Publication 2008-0215850.
In the operation of quantum processor 1000, programming interfaces 1021 and 1024 may each be used to couple a flux signal into a respective compound Josephson junction 1031,1032 of qubits 1001 and 1002, thereby realizing the Δi terms in the system Hamiltonian. This coupling provides the off-diagonal σx terms of the Hamiltonian described by equation 2 and these flux signals are examples of “disordering signals.” Similarly, programming interfaces 1022 and 1023 may each be used to couple a flux signal into a respective qubit loop of qubits 1001 and 1002, thereby realizing the hi terms in the system Hamiltonian. This coupling provides the diagonal σz terms of equation 3. Furthermore, programming interface 1025 may be used to couple a flux signal into coupler 1011, thereby realizing the Jij terms in the system Hamiltonian. This coupling provides the diagonal σziσzj terms of equation 3. In FIG. 10, the contribution of each of programming interfaces 1021-1025 to the system Hamiltonian is indicated in boxes 1021a-1025a, respectively.
Throughout this specification and the appended claims, the term “quantum processor” is used to generally describe the collection of qubits (e.g., qubits 1001 and 1002) and couplers (e.g., coupler 1011). The qubits 1001 and 1002 and the couplers 1011 are referred to as the “computational elements” of the quantum processor 1000. In the context of a quantum processor, the term “programming subsystem” is used to generally describe the programming elements (e.g., programming interfaces 1022, 1023, and 1025) included in a quantum processor (e.g., processor 1000) and other associated control circuitry or instructions. As previously described, the programming elements of the operational subsystem may communicate with a programming system which may be separate from the quantum processor or included locally on the processor. Similarly, in the context of a quantum processor, the term “evolution subsystem” is used to generally describe the evolution elements 1021, 1024 used to evolve the computational elements of the quantum processor 1000. For example, the evolution subsystem may include annealing signal lines (530, 631-634) and their corresponding interfaces (1021, 1024) to the qubits (1001, 1002).
As previously described, in some embodiments of the present systems and methods, a logic circuit representation of a computational problem may be encoded as a QUBO problem, where the QUBO problem may comprise a plurality of miniature optimization problems. In such embodiments, each miniature optimization problem may encode a particular logic gate in the logic circuit. Each gate in the logic circuit may be characterized by a respective objective function that is mapped to a respective subset of qubits (and associated coupling devices) in a quantum processor, where the objective function is minimized when the truth table of the gate is obeyed. The objective function representing a particular logic gate may be mapped to a subset of qubits and associated coupling devices by accordingly programming the values of the hi and Jij terms for those qubits and coupling devices. This particular approach to solving computational problems is summarized in method 1100.
FIG. 11 shows a flow-diagram of an embodiment of a method 1100 for solving a computational problem in accordance with the present systems and methods. Method 1100 includes four acts 1101-1104, though those of skill in the art will appreciate that alternative embodiments may omit certain acts and/or include additional acts. At 1101, a logic circuit representation of the computational problem is generated, where the logic circuit representation comprises a plurality of logic gates. Exemplary logic circuit representations include those illustrated in FIGS. 1A, 1B, 3A, and 3B. The logic circuit representation of the computational problem may be generated by known techniques using, for example, a classical digital computer processor. At 1102, each logic gate from the logic circuit representation is encoded as a respective miniature optimization problem. In some embodiments, each logic gate may be encoded as a miniature optimization problem using, for example, a classical digital computer processor. Each respective miniature optimization problem may be characterized by a respective objective function that is minimized when the truth table of the corresponding logic gate is obeyed. Exemplary objective functions for the AND, OR, and NOT gates have been described, and from these a person of ordinary skill in the art will appreciate how similar objective functions for other logic gates may be formed. Furthermore, a person of ordinary skill in the art will appreciate that the exemplary objective functions for the AND, OR, and NOT gates provided herein are used for illustrative purposes only and alternative objective functions may be crafted that similarly represent the AND, OR, and NOT gates.
At 1103, each miniature optimization problem is mapped to a respective subset of qubits and coupling devices in a quantum processor. This mapping may be achieved, for example, by programming the hi and Jij parameters of a subset of qubits and coupling devices to realize the objective function that corresponds to the particular logic gate being mapped. In such a mapping, at least one respective qubit may correspond to each intermediate logic input of the logic gate, at least one respective qubit may correspond to each intermediate logic output of the logic gate, and the coupling devices therebetween (as well as, in some embodiments, additional qubits) may be programmed to provide the appropriate relations between the intermediate logic input(s) and intermediate logic output(s) in order to realize the objective function corresponding to the logic gate. At 1104, each miniature optimization problem is solved, which effectively executes the logic circuit representation to determine a solution to the computational problem. Solving each miniature optimization problem may involve, for example, evolving the quantum processor from an initial state represented by the Hamiltonian described by equation 2 to a final state represented by the Hamiltonian described by equation 3. The hi and Jij parameters in the Hamiltonian described by equation 3 may be programmed such that respective subsets of qubits and coupling devices in the quantum processor each encode an objective function corresponding to a respective logic gate (i.e., the mapping act 1103). Evolving the quantum processor from an initial state to a final state may then involve minimizing each objective function to assign values to the intermediate logic input(s) and intermediate logic output(s) of each logic gate. In some embodiments, solving each miniature optimization problem may involve clamping at least one intermediate logic input and/or at least one intermediate logic output as described, for example, in act 232 of method 200b. 
In many applications, the logic circuit representation of the computational problem includes many (e.g., 10s, 100s, 1000s, etc.) of logic gates, thus solving the computational problem by method 1100 may require solving a large number of inter-dependent miniature optimization problems, where each miniature optimization problem corresponds to a particular logic gate in the logic circuit representation. The miniature optimization problems are inter-dependent because the intermediate output(s) of a first logic gate may correspond to the intermediate input(s) of a second logic gate. The combination of all of the miniature optimization problems may be described as a single discrete optimization problem, such as a QUBO. Thus, method 1100 represents a specific implementation of methods 200a, 200b, and/or 400 where the discrete optimization problem is a set of inter-dependent miniature optimization problems. In some embodiments, multiple logic gates may be combined into a single miniature optimization problem. For example, a miniature optimization problem may, in some embodiments, encode all or a portion of a complete logical operation that comprises multiple logic gates. Those of skill in the art will appreciate that the specific mapping between logic gates and miniature optimization problems is highly instance-dependent, where it may be advantageous for some applications to implement a respective miniature optimization problem corresponding to each individual logic gate, while it may be advantageous for other applications to implement miniature optimization problems that each encode multiple (i.e., two or more) logic gates. In applications where multiple logic gates are encoded as a single miniature optimization problem, the miniature optimization problem effectively encodes an “intermediate logic circuit” and the objective function of the miniature optimization problem may exhibit a minimum value when the truth table of the miniature logic circuit is obeyed.
Throughout this specification and the appended claims, the term “miniature optimization problem” (and variations thereof) is frequently used. Unless the specific context requires otherwise, the term “miniature” here is intended to denote an optimization problem that represents a portion or component of a larger problem and comprises fewer variables and/or parameters than the larger problem. For example, an optimization problem that encodes the operation of an individual gate is a “miniature” optimization problem when that gate is part of a logic circuit representation of a larger computational problem.
The methods described herein (e.g., methods 200a, 200b, 400, and 1100) may be implemented using many different forms of processor systems. For example, many of the acts in each of methods 200a, 200b, 400, and 1100 may, in some embodiments, be performed using the same computer processor, such as a classical digital computer processor. However, in some embodiments it may be advantageous to implement a processor system that includes at least two processing subsystems, each specialized to perform a particular subset of the acts in methods 200a, 200b, 400, and 1100.
In some embodiments of the present systems and methods, a processor system may include a first processing subsystem operated to perform the generating of logic (e.g., Boolean) circuit representations (e.g., acts 201, 401, and 1101) and the encoding of these logic circuit representations as discrete optimization problems (e.g., acts 202, 402, and 1102). For example, the first processing subsystem may perform acts 201 and 202 of methods 200a and 200b and/or acts 401 and 402 of method 400, and/or acts 1101 and 1102 of method 1100. The first processing subsystem may include a classical digital computer processor including a computer- or processor-readable storage medium, such as a non-transitory storage medium or memory (e.g., volatile or non-volatile).
In some embodiments of the present systems and methods, a processor system may include a second processing subsystem operated to perform the solving of discrete optimization problems (e.g., act 203a of method 200a; acts 203b, 231-233 of method 200b; acts 403-404 of method 400; and/or acts 1103-1104 of method 1100). In various embodiments, the second processing subsystem may be the same physical system as the first processing subsystem, or it may include a second classical digital computer processor, or it may include a quantum processor such as a superconducting quantum processor. In any case, the second processing subsystem may include a plurality of computational elements (e.g., qubits and couplers in the case of a quantum processor). The second processing subsystem may also include a programming subsystem for mapping the discrete optimization problem (which, in some embodiments, may comprise a plurality of miniature optimization problems) to the plurality of computational elements by programming the computational elements. In some embodiments, programming the computational elements includes clamping at least one logical output of the logic circuit representation of the computational problem (or at least one intermediate logical output of a particular logic gate). The second processing subsystem may also include an evolution subsystem for evolving the computational elements of the second processing subsystem. In some embodiments, evolving the computational elements of the second processing subsystem includes determining at least one logical input that corresponds to the at least one clamped logical output.
FIG. 12 is a schematic diagram of an embodiment of a processor system 1200 in accordance with the present systems and methods. Processor system 1200 includes a first processing subsystem 1210 in communication with a second processing subsystem 1220. First processing subsystem 1210 includes a computer-readable storage medium 1211 for storing and operating on at least one of a computational problem, a logic circuit representation of the computational problem, a discrete optimization problem encoding the logic circuit representation of the computational problem, and a set of miniature optimization problems each encoding a respective logic gate in the logic circuit representation of the computation problem. Second processing subsystem 1220 includes a plurality of computational elements 1221, a programming subsystem 1222, and an evolution subsystem 1223. In the illustrated embodiment, second processing subsystem 1220 includes a quantum processor; therefore, computational elements 1221 include at least two qubits 1231, 1232 and at least one coupler 1233. To reduce clutter, the interactions between computational elements 1221 and programming subsystem 1222, as well as the interactions between computational elements 1221 and evolution subsystem 1223, are not shown in FIG. 12, though those of skill in the art will appreciate that these interactions may be similar to those described in FIG. 10.
In some embodiments, the present systems and methods may be applied to solve a factoring problem, such as the problem of factoring an N-bit integer p as a product of a pair of integers a and b. Using the systems and methods described herein, this problem may be solved by representing a, b, and p in binary, constructing the logic circuit which performs the multiplication of a and b, and requiring that the circuit output give the binary representation of p. In some embodiments, the circuit can be run in “reverse” (inferring unknown inputs from known outputs) by encoding the circuit as an optimization problem and clamping the output p. By construction, input/output bit strings which satisfy the circuit may have known energy, and all other bit strings may produce an energy that is greater than the known energy. By fixing the output(s) and minimizing the resultant optimization problem, the inputs giving the desired output(s) can be obtained. The optimization problem may be crafted to be realizable using a quantum processor designed to implement adiabatic quantum computation and/or quantum annealing. In some embodiments, the optimization problem may comprise a set of inter-dependent miniature optimization problems, where each miniature optimization problem corresponds to a respective logic gate in the logic circuit representation of the factoring problem.
The product of two 4-bit integers may be, schematically, formed from the multiplication table 1300 given in FIG. 13. Any output bit pi may be formed as the sum of appropriate products of the bits of a and b. For example, the first output bit may be given by:

p0=a0b0.

This imposes a constraint between inputs a0, b0 and the output p0. Extensionally, this constraint may be given by the table 1400a in FIG. 14, which lists the allowed combinations of inputs and outputs. This constraint is indicated as C^(a0, b0, p0) so that C^(a, b, p) is true for a, b, p satisfying the constraint and false otherwise. The next bit in FIG. 13 is given by:

p1=(a1b0+a0b1)mod 2≡(t+t′)mod 2,

where C^(a1; b0; t) and C^(a0; b1; t′). However, because t+t′ can be as large as 2, the carry bit that may be passed on to the next larger bit (in this case p2) should be considered. Indicating the carry bit by c, the allowed inputs t, t′ and outputs p, c may be defined extensionally through the table 1400b in FIG. 14. This constraint, denoted C2A(t; t′; p; c), enforces t+t′=p+2c. C2A(t; t′; p; c) is the half-adder of classical digital logic. The bit p1 may then be defined by:

C2A(t,t′,p1,c)(a1,b0,t)(a0,b1,t′).

To proceed to higher order bits, in some embodiments it may be convenient to define the full adder constraint C3A(t; t′; t′′; p; c) which realizes the constraint of table 1400c in FIG. 14. This constraint is true if t+t′+t′′=p+2c. If c is the carry from p1, then p2 and its associated carries may be determined by adding the contributions:

t+t′+t′′+c 

where C^(a2, b0, t)(a1, b1, t′)(a0, b2, t′′). This sum can be evaluated using full- and half-adders by introducing an intermediate result r:

C3A(t,t′,t′′,r,c′)C2A(r,c,p2,c′′)

where r=t+t′+t′′ mod 2. This conjunction of constraints enforces t+t′+t′′+c=p2+2(c′+c′′). The carries c′ and c′′ may then be passed to the summation determining p3. Continuing in this manner for all other bits, a conjunction of constraints relating all input bits a and b to all output bits p, and to all necessary intermediate bits (such as r, c′, and c′′ above), can be derived.

In some embodiments, a further simplification may be made which allows elimination of most C^ constraints. As shorthand the following constraints may be defined:

{tilde over (C)}2A(a,b,t,p,c)=∃r(a,b,r)C2A(r,t,p,c) (ab+t=p+2c)

{tilde over (C)}3A(a,b,t,t′,p,c)=∃r(a,b,r)C3A(r,t,t′,p,c) (ab+t+t′=p+2c)

These constraints build the necessary ^ constraints into the adders with r representing a^b. An advantage of representing multiplication as constraint satisfaction is that it allows variables to be bound to particular values, and the values (if any) of the remaining variables which satisfy the constraints may be determined. In this way, multiplication can be run in “reverse” to infer inputs from outputs.
Having reduced factoring to constraint satisfaction, constraint satisfaction may be reduced to optimization which may then be minimized using quantum annealing and/or adiabatic quantum computation.
Consider a constraint C(x) defined over a set of Boolean variables x. C(x) may be represented by a penalty function P(x), mapping bitstrings to the reals, defined so that:




  
    P
    ⁡
    
      (
      x
      )
    
  
  =
  
    {
    
      
        
          o
        
        
          
            if
            ⁢
            
              
            
            ⁢
            
              C
              ⁡
              
                (
                x
                )
              
            
          
        
      
      
        
          
            ≥
            
              o
              +
              1
            
          
        
        
          
            if
            ⁢
            
              
            
            -
            
              
                C
                ⁡
                
                  (
                  x
                  )
                
              
              .
            
          
        
      
    
  




The objective P encodes the feasible x as global minima having energy o, and all other infeasible x as having an energy at least o+1. In embodiments where the quantum processor can only realize up-to-quadratic functions of Boolean variables, P(x) may be implemented as an up-to-quadratic function of x. In some embodiments, all the constraints CA, C2A, {tilde over (C)}2A, C3A, and {tilde over (C)}3A may be realized as quadratic penalties PA, P2A, {tilde over (P)}2A, P3A, and {tilde over (P)}3A as follows:



  
    
      
    
    ⁢
    
      
        
          P
          A
        
        ⁡
        
          (
          
            a
            ,
            b
            ,
            p
          
          )
        
      
      =
      
        
          
            [
            
              
                
                  a
                
                
                  b
                
                
                  p
                
              
            
            ]
          
          ⁡
          
            [
            
              
                
                  0
                
                
                  1
                
                
                  
                    -
                    2
                  
                
              
              
                
                  0
                
                
                  0
                
                
                  
                    -
                    2
                  
                
              
              
                
                  0
                
                
                  0
                
                
                  3
                
              
            
            ]
          
        
        ⁡
        
          [
          
            
              
                a
              
            
            
              
                b
              
            
            
              
                p
              
            
          
          ]
        
      
    
  




  
    
      
    
    ⁢
    
      
        
          P
          
            2
            ⁢
            A
          
        
        ⁡
        
          (
          
            t
            ,
            
              t
              ′
            
            ,
            p
            ,
            c
          
          )
        
      
      =
      
        
          
            
              
                [
                
                  
                    
                      t
                    
                    
                      
                        t
                        ′
                      
                    
                    
                      p
                    
                    
                      c
                    
                  
                
                ]
              
              ⁡
              
                [
                
                  
                    
                      1
                    
                    
                      2
                    
                    
                      
                        -
                        2
                      
                    
                    
                      
                        -
                        4
                      
                    
                  
                  
                    
                      0
                    
                    
                      1
                    
                    
                      
                        -
                        2
                      
                    
                    
                      
                        -
                        4
                      
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      1
                    
                    
                      4
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      4
                    
                  
                
                ]
              
            
            ⁡
            
              [
              
                
                  
                    t
                  
                
                
                  
                    
                      t
                      ′
                    
                  
                
                
                  
                    
                      
                        
                          p
                        
                      
                      
                        
                          c
                        
                      
                    
                  
                
              
              ]
            
          
          .
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              
                P
                ~
              
              
                2
                ⁢
                A
              
            
            ⁡
            
              (
              
                a
                ,
                b
                ,
                t
                ,
                p
                ,
                c
              
              )
            
          
        
        =
        
          
            
              [
              
                
                  
                    a
                  
                  
                    b
                  
                  
                    t
                  
                  
                    p
                  
                  
                    c
                  
                
              
              ]
            
            ⁡
            
              [
              
                
                  
                    0
                  
                  
                    1
                  
                  
                    2
                  
                  
                    
                      -
                      2
                    
                  
                  
                    
                      -
                      4
                    
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    2
                  
                  
                    
                      -
                      2
                    
                  
                  
                    
                      -
                      4
                    
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    1
                  
                  
                    
                      -
                      4
                    
                  
                  
                    
                      -
                      6
                    
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    3
                  
                  
                    6
                  
                
                
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    0
                  
                  
                    8
                  
                
              
              ]
            
          
          ⁡
          
            [
            
              
                
                  a
                
              
              
                
                  b
                
              
              
                
                  
                    
                      
                        
                          
                            
                              t
                            
                          
                          
                            
                              p
                            
                          
                        
                      
                    
                    
                      
                        c
                      
                    
                  
                
              
            
            ]
          
        
      
    
  




  
    
      
    
    ⁢
    
      
        
          P
          
            3
            ⁢
            A
          
        
        ⁡
        
          (
          
            t
            ,
            
              t
              ′
            
            ,
            
              t
              ′′
            
            ,
            p
            ,
            c
          
          )
        
      
      =
      
        
          
            
              
                [
                
                  
                    
                      t
                    
                    
                      
                        t
                        ′
                      
                    
                    
                      
                        t
                        ′′
                      
                    
                    
                      p
                    
                    
                      c
                    
                  
                
                ]
              
              ⁡
              
                [
                
                  
                    
                      1
                    
                    
                      2
                    
                    
                      2
                    
                    
                      
                        -
                        2
                      
                    
                    
                      
                        -
                        4
                      
                    
                  
                  
                    
                      0
                    
                    
                      1
                    
                    
                      2
                    
                    
                      
                        -
                        2
                      
                    
                    
                      
                        -
                        4
                      
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      1
                    
                    
                      
                        -
                        2
                      
                    
                    
                      
                        -
                        4
                      
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      1
                    
                    
                      4
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      4
                    
                  
                
                ]
              
            
            ⁡
            
              [
              
                
                  
                    t
                  
                
                
                  
                    
                      t
                      ′
                    
                  
                
                
                  
                    
                      
                        
                          
                            
                              
                                
                                  t
                                  ′′
                                
                              
                            
                            
                              
                                p
                              
                            
                          
                        
                      
                      
                        
                          c
                        
                      
                    
                  
                
              
              ]
            
          
          .
          
            

          
          ⁢
          
            
              P
              ~
            
            
              3
              ⁢
              A
            
          
        
        =
        
          
            (
            
              a
              ,
              b
              ,
              t
              ,
              
                t
                ′
              
              ,
              p
              ,
              c
            
            )
          
          =
          
            
              
                [
                
                  
                    
                      a
                    
                    
                      b
                    
                    
                      t
                    
                    
                      
                        t
                        ′
                      
                    
                    
                      p
                    
                    
                      c
                    
                  
                
                ]
              
              ⁡
              
                [
                
                  
                    
                      0
                    
                    
                      1
                    
                    
                      2
                    
                    
                      2
                    
                    
                      
                        -
                        2
                      
                    
                    
                      
                        -
                        4
                      
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      2
                    
                    
                      2
                    
                    
                      
                        -
                        2
                      
                    
                    
                      
                        -
                        4
                      
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      1
                    
                    
                      4
                    
                    
                      
                        -
                        4
                      
                    
                    
                      
                        -
                        8
                      
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      1
                    
                    
                      
                        -
                        4
                      
                    
                    
                      
                        -
                        8
                      
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      3
                    
                    
                      8
                    
                  
                  
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      0
                    
                    
                      10
                    
                  
                
                ]
              
            
            ⁡
            
              [
              
                
                  
                    a
                  
                
                
                  
                    b
                  
                
                
                  
                    t
                  
                
                
                  
                    
                      t
                      ′
                    
                  
                
                
                  
                    p
                  
                
                
                  
                    c
                  
                
              
              ]
            
          
        
      
    
  



All penalties may have minimum value o=0. The conjunction of constraints C(x)^C′(x) may be realized by the addition of penalty functions, i.e., PC^C′(x)=PC(x)+{tilde over (P)}C′(x). Thus, the associated penalties may be added to represent the constraint network representing a multiplication circuit.

A constraint/optimization network 1500 representing the multiplication of two 8-bit numbers is shown in FIG. 15. Optimization variables are represented as edges in the Figure. In addition to the 2N=16 variables representing a and b there are a number of intermediate variables. The sij variables represent the partial sums needed to evaluate the output pj. There are N(N−1) partial sum variables. The cij variables represent the carries from the output pj. There are N−2+(N−1)2 carry variables. Lastly, there are the 2N variables representing the product p. The total variable count is therefore (2N+4)(N−1)+3.
The boxes of network 1500 in FIG. 15 represent the quadratic contributions. In some embodiments, complete connectivity is advantageous locally for the variables (edges) entering the box. P^ requires K3, P2A requires K4, P2A requires K5, P3A requires K5, and P3A requires K6. Kn is the fully connected graph on n vertices.
The objective function encoding the multiplication of two N-bit numbers can be used to factor the 2N-bit number represented by (p2N-1; p2N-2; . . . ; p0). Factoring odd integers is the focus, because if p is not odd then it can be repeatedly divide by 2 until it is odd. If p is odd then the multiplicands are odd so that a0=b0=1. These variables are thus eliminated from consideration. Since the p values are known they may be eliminated as well. The p variables are eliminated by specializing the constraints in which they appear. Consequently, the specialized constraints (which are still quadratic) may be defined as:

P2A0(t,t′,c)=P2A(t,t′,t′′,p=0,c) P2A1(t,t′,c)=P2A(t,t′,p=1,c)

P3A0(t,t′,t′′,c)=P3A(t,t′,t′′,p=0,c) P3A1(t,t′,t′′,c)=P3A(t,t′,t′′,p=1,c)

This reduces the total variable count to (2N+1)(N−1)−1. Eliminating these variables leaves the optimization network 1600 defined in FIG. 16. The P3Ap14,p15 constraint in the lower left corner corresponds to the constraint P3A(a, b, t, t′, p=p14, c=p15).
In accordance with the present systems and methods, two technical considerations may require a refinement of network 1600 from FIG. 16 for hardware implementation. Firstly, any individual input bit (either ai or bj) appears in many constraints and interacts with O(N) other bits. Physically, this variable may be represented in hardware as an extended element (much as it appears in FIG. 16 as the extended dark line). However, there is typically a maximum length to the extended element, and a maximum number of connections the element may support. Secondly, the precision to which distinct values in the penalty functions may be specified is typically limited, and it may be necessary to have fewer distinct weights appearing in the quadratic penalty functions.
Both these considerations can be addressed by, for example, disaggregating the {tilde over (P)} constraints, and breaking them into their constituent components P2A or P3A and P^. The optimization network in this case may be obtained from FIG. 16 by replacing each {tilde over (P)}2A and {tilde over (P)}3A element with element 1700 from FIG. 17 and element 1800 from FIG. 18, respectively. This requires the addition of (N−2)(N−1) variables ti,j representing the products aibj for 1≦i; j≦N. This brings the total variable count to (3N+1)(N−1)−1. Therefore, in some embodiments, to factor a 16-bit number may require N=8 and 174 variables. Without the {tilde over (P)} constraints the required values are {−4;−2; 0; 1; 2; 3; 4}.
In accordance with the present systems and methods, the mapping of a multiplication (i.e., factoring) circuit to a quantum processor having a finite number of qubits and limited connectivity between qubits may be facilitated by decomposing the multiplicands (i.e., the factors) into smaller pieces and performing operations on the pieces. For example, the product p of two numbers a and b may be written as:

p=ab 

When a and b are both written in binary form, they may each be decomposed into collections of binary segments. For example, a may be decomposed into a set of high bits ah and a set of low bits al, while b may be decomposed into a set of high bits bh and low bits bl:

a=(ah,al)=2n/2ah+al 

b=(bh,bl)=2n/2bh+bl 

Where n is the number of bits in a or b (which does not necessarily need to be the same but is for this example). For example, if both a and b are 8-bit numbers, then n=8 and ah, al, bh, and bl are all respective 4-bit numbers. This decomposition may be performed, for example, using a computer processor such as a classical digital computer processor as part of a digital computer system.

The product p of a and b then becomes:

p=ab=2nahbh+2n/2(ahhl+albh)+albl 

Each of the pairings ahbh, ahbl, albh, and albl is a respective component multiplication requiring on the order of (n/2)2 variables in the corresponding component multiplication circuit. There are four of these pairings, so the complete multiplication circuit for p=ab requires on the order of 4(n/2)2 ̃n2 variables distributed among four component multiplication circuits. However, in accordance with the present systems and methods, decomposing the multiplication circuit for p=ab into the four component multiplication circuits for ahbh, ahbl, albh, and albl (or decomposing into any number of circuits, depending on n), respectively, may facilitate mapping the problem to a quantum processor having limited connectivity because the components ahbh, ahbl, albh, and albl may, in some instances, have connectivities that better map to the quantum processor than the connectivity of a and b on their own.
The decomposition described above may also be used to reduce the total number of variables required to represent the multiplication circuit for p=ab. This may be achieved by reducing the four component multiplication circuits from the four pairings (ahbh, ahbl, albh, and albl) to three component multiplication circuits as follows:

(ahbl+albh)=(ah+al)(bh+bl)−ahbh−albl 

Since ahbh and albl have already been identified, the complete multiplication circuit for p=ab only requires that three, rather than four, component multiplication circuits be produced. These are:

ahbh;

albl; and

(ah+al)(bh+bl)

The sums (ah+al) and (bh+bl) each produce a respective (n/2+1)-bit number, thus the component multiplication circuit for (ah+al)(bh+bl) requires on the order of (n/2+1)2 variables. The total number of variables required to represent the three component multiplication circuits described above, and thus to completely represent the circuit for p=ab, is on the order of 3(n/2)2, or 3⁄4n2. Thus, by using this technique, the number of variables required to represent the multiplication circuit for p=ab (or, in other words, the number of qubits required to factor p and determine a and b) may be reduced by about 25%. Furthermore, the connectivity requirements for the component circuits may, in some instances, be more amenable to the connectivity available in the quantum processor hardware than the connectivity requirements of the original elements p, a, and b. The construction of the three component multiplication circuits (i.e., three component logic circuits) may be performed using, for example, a computer processor such as a classical digital computer processor as part of a digital computer system.

As described throughout the present systems and methods, the three component logic circuits (i.e., multiplication circuits) which perform the multiplications of ahbh, albl, and (ah+al)(bh+bl), respectively, may be encoded as at least one discrete optimization problem using the computer processor. The at least one discrete optimization problem may include miniature optimization problems representing logic gates, etc., as described throughout the present systems and methods.
A person of skill in the art may appreciate that the decomposition techniques described above are similar, in some respects, to known principles of “Toom-Cook” multiplication. The present systems and methods take advantage of the decomposition techniques described herein to facilitate mapping a factoring problem to a quantum processor having a finite number of qubits and limited connectivity between qubits by reducing the number of qubits required to represent the corresponding multiplication (i.e., factoring) circuit and/or simplifying the qubit connectivity required in order to represent the elements of the corresponding multiplication circuit.
In accordance with the present systems and methods, similar decomposition techniques to those described above may be applied recursively and/or more aggressively to decompose large factoring problems into a sequence of smaller problems.
The details of the above decomposition technique are summarized in FIG. 19.
FIG. 19 is a flow-diagram of an embodiment of a method 1900 for 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 in accordance with the present systems and methods. Method 1900 includes five acts 1901-1905, though those of skill in the art will appreciate that alternative embodiments may omit certain acts and/or include additional acts. At 1901, a, b, and p are represented in binary using a digital computer system. At 1902, the binary representations of a and b are decomposed into two respective components (ah, al) and (bh, bl) via the digital computer system. At 1903, at least three component logic circuits which perform the multiplications of ahbh, albl, and (ah+al)(bh+bl), respectively, are constructed via the digital computer system, wherein each of the at least three component logic circuits includes at least one respective logic gate. As described previously, the total number of variables (e.g., qubits in a quantum processor) required to represent the three component multiplications of ahbh, albl, and (ah+al)(bh+bl) may be less than the total number of variables required to represent the multiplication p=ab. At 1904, each respective one of the at least three component logic circuits is encoded 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. At 1905, each respective discrete optimization problem is solved using a 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. As described previously, solving each respective discrete optimization problem via a quantum processor may include using the quantum processor to perform at least one of adiabatic quantum computation and quantum annealing.
Although various aspects of the present systems and methods are described as involving “a digital computer system” or “computer processor” and successive acts may be described as performed via “the digital computer system” or via “the computer processor,” a person of skill in the art will appreciate that the present systems and methods may employ any number of digital computers (i.e., one or more digital computers) and successive acts (i.e., digital processing tasks) in any method may be performed on the same digital computer or on different digital computers (either in series or in parallel) that are in communication with one another, for example using conventional microprocessors.
FIG. 20 illustrates an exemplary digital computer system 2000 including a digital computer processor 2006 that may be used to perform classical digital processing tasks described in the present systems and methods. Digital computer system 2000 may serve as, for example, first processing subsystem 1210 from FIG. 12. Those skilled in the relevant art will appreciate that the present systems and methods can be practiced with other digital computer configurations, including hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, personal computers (“PCs”), network PCs, mini-computers, mainframe computers, and the like. The present systems and methods can also be practiced in distributed computing environments, where tasks or modules are performed by remote processing devices, which are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.
Digital computer system 2000 may include at least one processing unit 2006 (i.e., digital computer processor), at least one system memory 2008, and at least one system bus 2010 that couples various system components, including system memory 2008 to digital computer processor 2006. Digital computer system 2000 will at times be referred to in the singular herein, but this is not intended to limit the application to a single digital computer system 2000. For example, there may be more than one digital computer system 2000 or other classical computing device involved throughout the present systems and methods.
Digital computer processor 2006 may be any logic processing unit, such as one or more central processing units (“CPUs”), digital signal processors (“DSPs”), application-specific integrated circuits (“ASICs”), etc. Unless described otherwise, the construction and operation of the various blocks shown in FIG. 20 are of conventional design. As a result, such blocks need not be described in further detail herein, as they will be understood by those skilled in the relevant art.
System bus 2010 can employ any known bus structures or architectures, including a memory bus with a memory controller, a peripheral bus, and a local bus. System memory 2008 may include non-transitory memory and/or non-volatile memory such as read-only memory (“ROM”) and/or volatile memory such as random access memory (“RAM”) (not shown). A basic input/output system (“BIOS”) 2012, which can form part of the ROM, contains basic routines that help transfer information between elements within digital computer system 2000, such as during startup.
Digital computer system 2000 may also include other non-volatile memory 2014. Non-volatile memory 2014 may take a variety of forms, including: a hard disk drive for reading from and writing to a hard disk, an optical disk drive for reading from and writing to removable optical disks, and/or a magnetic disk drive for reading from and writing to magnetic disks. The optical disk can be a CD-ROM or DVD, while the magnetic disk can be a magnetic floppy disk or diskette. Non-volatile memory 2014 may communicate with digital computer processor 2006 via system bus 2010 and may include appropriate interfaces or controllers 2016 coupled between non-volatile memory 2014 and system bus 2010. Non-volatile memory 2014 may serve as long-term storage for computer-readable instructions, data structures, program modules and other data for digital computer system 2000. Although digital computer system 2000 has been described as employing hard disks, optical disks and/or magnetic disks, those skilled in the relevant art will appreciate that other types of non-volatile computer-readable media may be employed, such a magnetic cassettes, flash memory cards, Bernoulli cartridges, Flash, ROMs, smart cards, etc.
Various program modules, application programs and/or data can be stored in system memory 2008. For example, system memory 2008 may store an operating system 2018, end user application interfaces 2020 and server applications 2022. In accordance with the present systems and methods, system memory 2008 may implement or constitute discrete optimization module 2030 that stores and executes (via digital processor 2006) instructions for interacting with a quantum processor to perform discrete optimization as described herein (e.g., mapping logic circuits to discrete optimization and solving miniature optimization problems corresponding to logic gates, etc.). Discrete optimization module 2030 may interface with the programming subsystem of a quantum processor such as that illustrated in FIG. 10.
System memory 2008 may also include one or more networking applications 2050, for example, a Web server application and/or Web client or browser application for permitting digital computer system 2000 to exchange data with sources via the Internet, corporate Intranets, or other networks, as well as with other server applications executing on server computers. Networking application 2050 in the depicted embodiment may be markup language based, such as hypertext markup language (“HTML”), extensible hypertext markup language (“XHTML”), extensible markup language (“XML”) or wireless markup language (“WML”), and may operate with markup languages that use syntactically delimited characters added to the data of a document to represent the structure of the document. A number of Web server applications and Web client or browser applications are commercially available, such as those available from Mozilla and Microsoft.
While shown in FIG. 20 as being stored in system memory 2008, operating system 2018 and various applications/modules 2020, 2022, 2030, 2050 and other data can also be stored in nonvolatile memory 2014.
Digital computer system 2000 can operate in a networking environment using logical connections to at least one client computer system 2036 and at least one database system 2070. These logical connections may be formed using any means of digital communication, for example, through a network 2038, such as a local area network (“LAN”) or a wide area network (“WAN”) including, for example, the Internet. The networking environment may include wired or wireless enterprise-wide computer networks, intranets, extranets, and/or the Internet. Other embodiments may include other types of communication networks such as telecommunications networks, cellular networks, paging networks, and other mobile networks. The information sent or received via the logical connections may or may not be encrypted. When used in a LAN networking environment, digital computer system 2000 may be connected to the LAN through an adapter or network interface card (“NIC”) 2040 (communicatively linked to system bus 2010). When used in a WAN networking environment, digital computer system 2000 may include an interface and modem (not shown), or a device such as NIC 2040, for establishing communications over the WAN. Non-networked communications may additionally, or alternatively be employed.
In a networked environment, program modules, application programs, data, or portions thereof can be stored outside of digital computer system 2000. Those skilled in the relevant art will recognize that the logical connections shown in FIG. 20 are only some examples of establishing communications between computers, and other connections may also be used.
While digital computer system 2000 may generally operate automatically, an end user application interface 2020 may also be provided such that an operator can interact with digital computer system 2000 through different user interfaces 2048, including output devices, such as a monitor 2042, and input devices, such as a keyboard 2044 and a pointing device (e.g., mouse 2046). Monitor 2042 may be coupled to system bus 2010 via a video interface, such as a video adapter (not shown). Digital computer system 2000 can also include other output devices, such as speakers, printers, etc. Other input devices can also be used, including a microphone, joystick, scanner, etc. These input devices may be coupled to digital computer processor 2006 via a serial port interface that couples to system bus 2010, a parallel port, a game port, a wireless interface, a universal serial bus (“USB”) interface, or via other interfaces.
NIC 2040 may include appropriate hardware and/or software for interfacing with the elements of a quantum processor (not shown). In other embodiments, different hardware may be used to facilitate communications between digital computer system 2000 and a quantum processor. For example, digital computer system 2000 may communicate with a quantum processor via a direct electrical connection (e.g., via Universal Serial Bus, Firewire, or the like), a wireless connection (e.g., via a Wi-Fi® network), or an Internet connection.
Client computer system 2036 may comprise any of a variety of computing devices communicatively coupled to digital computer system 2000, and may include a client program 2090 configured to properly format and send problems directly or indirectly to server application 2022. Once digital computer system 2000 has determined a solution, server application 2022 may be configured to send information indicative of this solution back to client program 2090. Throughout this specification, the term “connectivity” is used to describe the maximum number of possible communicative coupling paths that are physically available (e.g., whether active or not) to communicably couple between individual qubits in a quantum processor without the use of intervening qubits. For example, a qubit with a connectivity of three is capable of communicably coupling to up to three other qubits without any intervening qubits. In other words, there are communicative paths available to three other qubits, although in any particular application less than all of those communicative paths may be employed. In a quantum processor employing coupling devices between qubits, this would mean a qubit having a connectivity of three is communicably coupleable via three coupling devices. Traditionally, the number of qubits in a quantum processor limits the size of problems that may be solved and the connectivity between the qubits in a quantum processor limits the complexity of the problems that may be solved.
The present systems and methods provide techniques for using adiabatic quantum computation and/or quantum annealing to perform factoring by decomposing the factoring problem into at least three component logic circuits, encoding the at least three component logic circuits into at least one discrete optimization problem, and solving the at least one discrete optimization problem via a quantum processor by performing adiabatic quantum computation and/or quantum annealing. Similar techniques for encoding logic circuits as discrete optimization problems are described in US Patent Publication 2011-0231462, which is incorporated by reference herein in its entirety.
The above description of illustrated embodiments, including what is described in the Abstract, is not intended to be exhaustive or to limit the embodiments to the precise forms disclosed. Although specific embodiments of and examples are described herein for illustrative purposes, various equivalent modifications can be made without departing from the spirit and scope of the disclosure, as will be recognized by those skilled in the relevant art. The teachings provided herein of the various embodiments can be applied to other systems, methods and apparatus of quantum computation, not necessarily the exemplary systems, methods and apparatus for quantum computation generally described above.
The various embodiments described above can be combined to provide further embodiments. All of the commonly assigned US patent application publications, US patent applications, foreign patents, foreign patent applications and non-patent publications referred to in this specification and/or listed in the Application Data Sheet, including but not limited to US Provisional Patent Application Ser. No. 61/187,987, filed Jun. 17, 2009 and entitled “Systems and Methods for Solving Computational Problems,” U.S. Provisional Patent Application Ser. No. 61/238,043, filed Aug. 28, 2009 and entitled “Systems and Methods for Solving Factoring Problems,” U.S. Provisional Patent Application Ser. No. 61/330,789, filed May 3, 2010 and entitled “Systems and Methods for Solving Computational Problems,”, US Patent Publication No. 2006-0225165 (now U.S. Pat. No. 7,533,068), US Patent Publication 2008-0176750, U.S. patent application Ser. No. 12/266,378 published as US Patent Publication 2009-0121215, PCT Patent Application Serial No. PCT/US09/37984 published as PCT Patent Publication 2009-120638, U.S. Pat. No. 7,135,701, PCT Patent Application Serial No. PCT/US2009/044537 published as PCT Patent Publication 2009-143166, US Patent Publication 2008-0215850, and US Patent Publication 2011-0231462 are incorporated herein by reference, in their entirety. Aspects of the embodiments can be modified, if necessary, to employ systems, circuits and concepts of the various patents, applications and publications to provide yet further embodiments.
The various problems to be solved may include problems which represent physical objects. For example, the various methods may solve problems related to geology using seismic data, for example used in oil exploration, predicting seismic activity or volcanology. Such may also be used in astronomy using information, for instance spectral information, collected via optical or radio telescopes. Such may also be use in physics or sub-atomic physics using information collected by various sensors associated with a particle collider or other piece of physics instrumentation. Such may further be used in performing analysis of actual or planned communications networks, using various measurements of network traffic, or for factoring prime numbers. Such may further be used in verification and validation of physical systems, such as hardware systems and/or software systems used in the operation of hardware systems. Various other practical problems representing physical objects may be solved.
These and other changes can be made to the embodiments in light of the above-detailed description. In general, in the following claims, the terms used should not be construed to limit the claims to the specific embodiments disclosed in the specification and the claims, but should be construed to include all possible embodiments along with the full scope of equivalents to which such claims are entitled. Accordingly, the claims are not limited by the disclosure.

## Claims

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.

2. The method of claim 1 wherein solving each respective discrete optimization problem using a quantum processor includes performing at least one of adiabatic quantum computation and quantum annealing.

3. The method of claim 1, further comprising mapping each respective discrete optimization problem to the quantum processor.

4. The method of claim 3 wherein the quantum processor comprises qubits and couplers, and wherein mapping each respective discrete optimization problem to the quantum processor includes, for each respective discrete optimization problem, programming the qubits and the couplers of the quantum processor in a configuration representing a problem Hamiltonian that corresponds to the discrete optimization problem.

5. A system to factor an N-bit integer p as a product of a pair of integers a and b, the system comprising:
at least one quantum processor;
a digital computer system including at least one non-transitory digital processor-readable medium which stores instructions that cause the at least one quantum processor to factor an N-bit integer p by:
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, bi) of the binary representations of a and b.

6. The system of claim 5 wherein the at least one quantum processor includes at least one quantum processor configured to perform adiabatic quantum computation or quantum annealing.

7. The system of claim 5 wherein the at least one quantum processor includes at least one superconducting quantum processor.

8. The system of claim 5 wherein the non-transitory processor-readable medium stores a discrete optimization module, and the instructions that cause the at least one quantum processor to factor an N-bit integer p are stored in the discrete optimization module.