Field
The present methods generally relate to solving computational problems using a quantum processor via a compressed sensing technique.
Superconducting Qubits
There are many different hardware and software approaches under consideration for use in quantum computers. One hardware approach employs integrated circuits formed of superconducting material, such as aluminum and/or niobium, to define superconducting qubits. Superconducting qubits can be separated into several categories depending on the physical property used to encode information. For example, they may be separated into charge, flux and phase devices. Charge devices store and manipulate information in the charge states of the device; flux devices store and manipulate information in a variable related to the magnetic flux through some part of the device; and phase devices store and manipulate information in a variable related to the difference in superconducting phase between two regions of the phase device.
Many different forms of superconducting flux qubits have been implemented in the art, but all successful implementations generally include a superconducting loop (i.e., a “qubit loop”) that is interrupted by at least one Josephson junction. Some embodiments implement multiple Josephson junctions connected either in series or in parallel (i.e., a compound Josephson junction) and some embodiments implement multiple superconducting loops.
Quantum Processor
A quantum processor may take the form of 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. A superconducting quantum processor may also employ coupling devices (i.e., “couplers”) providing communicative coupling between qubits. Further detail and embodiments of exemplary quantum processors that may be used in conjunction with the present methods are described in U.S. Pat. Nos. 7,533,068, 8,008,942, US Patent Publication 2008-0176750, US Patent Publication 2009-0121215, and PCT Patent Publication 2009-120638 (now US Patent Publication 2011-0022820).
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 s 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 methods, 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. Nos. 7,135,701 and 7,418,283.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 than classical annealing. 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 a hard problem. 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 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 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.
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.