Show Summary Details

Page of

PRINTED FROM the OXFORD RESEARCH ENCYCLOPEDIA, PHYSICS (oxfordre.com/physics). (c) Oxford University Press USA, 2020. All Rights Reserved. Personal use only; commercial use is strictly prohibited (for details see Privacy Policy and Legal Notice).

date: 27 October 2020

Adiabatic Quantum Computing and Quantum Annealingfree

  • Erica K. GrantErica K. GrantQuantum Computing Institute, Oak Ridge National Laboratory
  •  and Travis S. HumbleTravis S. HumbleQuantum Computing Institute, Oak Ridge National Laboratory

Summary

Adiabatic quantum computing (AQC) is a model of computation that uses quantum mechanical processes operating under adiabatic conditions. As a form of universal quantum computation, AQC employs the principles of superposition, tunneling, and entanglement that manifest in quantum physical systems. The AQC model of quantum computing is distinguished by the use of dynamical evolution that is slow with respect to the time and energy scales of the underlying physical systems. This adiabatic condition enforces the promise that the quantum computational state will remain well-defined and controllable thus enabling the development of new algorithmic approaches.

Several notable algorithms developed within the AQC model include methods for solving unstructured search and combinatorial optimization problems. In an idealized setting, the asymptotic complexity analyses of these algorithms indicate computational speed-ups may be possible relative to state-of-the-art conventional methods. However, the presence of non-ideal conditions, including non-adiabatic dynamics, residual thermal excitations, and physical noise complicate the assessment of the potential computational performance. A relaxation of the adiabatic condition is captured in the complementary computational heuristic of quantum annealing, which accommodates physical systems operating at finite temperature and in open environments. While quantum annealing (QA) provides a more accurate model for the behavior of actual quantum physical systems, the possibility of non-adiabatic effects obscures a clear separation with conventional computing complexity.

A series of technological advances in the control of quantum physical systems have enabled experimental AQC and QA. Prominent examples include demonstrations using superconducting electronics, which encode quantum information in the magnetic flux induced by a weak current operating at cryogenic temperatures. A family of devices developed specifically for unconstrained optimization problems has been applied to solve problems in specific domains including logistics, finance, material science, machine learning, and numerical analysis. An accompanying infrastructure has also developed to support these experimental demonstrations and to enable access of a broader community of users. Although AQC is most commonly applied in superconducting technologies, alternative approaches include optically trapped neutral atoms and ion-trap systems.

The significant progress in the understanding of AQC has revealed several open topics that continue to motivate research into this model of quantum computation. Foremost is the development of methods for fault-tolerant operation that will ensure the scalability of AQC for solving large-scale problems. In addition, unequivocal experimental demonstrations that differentiate the computational power of AQC and its variants from conventional computing approaches are needed. This will also require advances in the fabrication and control of quantum physical systems under the adiabatic restrictions.

Subjects

  • Quantum Physics

1. An Introduction to Quantum Computing

Quantum computing is a form of computation that explicitly uses quantum mechanical effects to process information, and a quantum computer is a device that implements these principles to solve computational problems. Quantum computers are distinguished by the use of the quantum states of a physical system to store information (Nielsen & Chuang, 2010). Unlike classical bits of information that are either 0 or 1, a quantum bit of information or qubit is a linear superposition of 0 and 1. Formally, qubits represent normalized vectors within a two-dimensional Hilbert space that can be visualized as points on the Bloch sphere shown in Figure 1. In particular, the opposing poles of the Bloch sphere correspond to the orthogonal states of a physical system while every point on the surface represents a valid linear superposition (Bengtsson & Zyczkowski, 2017).

Figure 1. The Bloch sphere is the geometric representation of a qubit ψ as a superposition of two orthogonal states. Every point on the surface of the sphere corresponds to valid qubit, whereas the states of a classical bit correspond only to the the north and south poles designed as |0 and |1, respectively. A qubit is specified by the complex-valued coefficients a and b, which may be defined in terms of the spherical coordinates θ and ϕ.

In general, interactions between quantum physical systems extend the principle of superposition across multiple qubits, and the joint quantum states prepared by these interactions will manifest as correlations in behaviors for the physical systems. Quantum states are said to be entangled when these composite behaviors cannot be separated into independent processes—the behavior of one system is directly dependent on the behavior of the other. Entanglement represents a fundamentally new type of correlation that cannot be reproduced within the context of classical physical theory (Horodecki et al., 2009). It is a hallmark of quantum mechanics and, consequently, quantum computing.

A quantum algorithm is a set of operations that prepares superposition and entanglement and transforms a quantum state. The quantum algorithms proposed for full-scale quantum computers are expected to provide significant speedups over best-in-class conventional methods for certain problems. For example, quantum computers are expected to efficiently simulate quantum mechanics, which would provide insights into the structure, properties, and behavior of systems with many particles or interactions (Feynman, 1982). Additional quantum-algorithmic results impact the development of new methods for optimization, unstructured search, integer factorization, systems of linear equations, and many other application areas (Nielsen & Chuang, 2010; Montanaxo, 2016). These potential performance gains continue to motivate the development of quantum computers and applications to practical problems.

The concept of a universal quantum computer formalizes how arbitrary computations can be performed (Deutsch, 1985) and enables a theory of quantum computational complexity (Bernstein & Vazirani, 1997). Prominent classes from conventional complexity theory are found to have distinct quantum analogues that categorize new classes of problems. Conceptual requirements for an abstract quantum computer provide criteria that guide experimental efforts to realize this technology and are often referred to as DiVincenzo Criteria (DiVincenzo, 2000).

Problem classes that are challenging to solve with conventional methods of computation are of specific interest for quantum computation. In particular, the class NP represents those decision problems with solutions that can be verified in polynomial time but are not known to be solved in polynomial time. As the size of the input problem grows, the conventional resources required to find a solution grow super-polynomially with respect to input size. Problems from the NP class arise in many notable applications such as cryptography (Wieschebrink, 2006), routing and scheduling (Lenstra & Kan, 1981), etc. Therefore, quantum computation is of interest for this class of problems. Adiabatic quantum computation is especially focused on NP optimization problems (NPO) that fall in the NP class but additionally must be a decision problem. Such problems fit naturally into AQC because their solution can be encoded in the ground state and translated into an Ising Hamiltonian in polynomial time (Lucas, 2014). Some example NPO problems that have been formulated for AQC include satisfiability problems (Hogg, 2003), finding cliques (Childs, Farhi, Goldstone, & Gutmann, 2000), and exact cover (Choi, 2010).

Experimental efforts to realize AQC and QA have used a variety of different quantum physical systems including the spin of individual electrons (Struck & Burkard, 2016), the polarization of single photons (Adami & Cerf, 1999), and the quantized magnetic flux in superconducting electronics (Devoret & Martinis, 2005). However, interactions between such quantum physical systems and the environment may generate entangled or correlated states that represent a loss of information to the uncontrolled surroundings. The coherence time quantifies the time scale over which information may reliably persist in the primary system and this sets a fundamental limit on how many operations can be performed. The development of well-characterized, reproducible qubits continues to be an active area of experimental research for the realization of noisy, intermediate-scale quantum computing devices (Preskill, 2018).

A quantum computing model defines how a quantum computer should operate. Several models have been developed to implement universal quantum computation with each being computationally equivalent but operationally distinct. The model of adiabatic quantum computing is described in detail below, while a summary of the prominent circuit model can be found elsewhere (Nielsen & Chuang, 2010). The choice of quantum computing model may be tailored to the intended purpose of a quantum computer as some models more efficiently express certain algorithms. In addition, limits on the controllability of a quantum physical system may also make certain computational models better suited.

2. Adiabatic Quantum Computing

Adiabatic quantum computing (AQC) is a model of computation that uses quantum-mechanical processes operating under adiabatic conditions. This model employs continuous-time evolution of a quantum state |ψ(t) from a well-defined initial value to compute a final observed value. The evolution is modeled by the Schrödinger equation

i|ψ(t)t=H(t)|ψ(t)(1)

operating in the presence of adiabatic changes to the governing Hamiltonian H(t) over the range t[0,T], where is Planck’s constant divided by 2π. AQC is computationally equivalent to all other quantum computing models, including the circuit and topological models, and it can efficiently solve any problem in BQP (Aharonov et al., 2008). However, AQC was originally proposed as a method for solving satisfiability problems (Farhi et al., 2000) and it has received attention for the simplicity by which combinatorial optimization problems can be cast in Hamiltonian forms (Lucas, 2014).

The principles of operation for AQC derive fundamentally from the adiabatic theorem, which states that a quantum mechanical system will remain in an instantaneous eigenstate of the Hamiltonian provided conditions on the internal energy and time scales are met (Born & Fock, 1928). In the simplest case, the adiabatic theorem requires:

1.

There exists an energy gap between the populated eigenstate and all other excited energy states.

2.

The evolution time must be sufficiently slow to suppress internal excitation.

The significance of these conditions may be illustrated through the example of a time-dependent Hamiltonian

H(t)=A(t)HA+B(t)HB(2)

where t[0,T] and T is the total evolution time. The time-dependent prefactors, in this context referred to as temporal schedules A(t) and B(t), control the interpolation of the initial and final Hamiltonians HA and HB, respectively, which represent self-adjoint linear operators acting over a Hilbert space of dimension N=2n with the integer n referring to the number of qubits. In particular, the schedules should be smooth and differentiable and they should satisfy the boundary conditions A(0)=1 and B(0)=0 while A(T)=0 and B(T)=1. The j-th instantaneous eigenstate ϕj(t) for H(t) is then defined as

H(t)|ϕj(t)=Ej(t)|ϕj(t)(3)

where {Ej(t):j=0toN1} is the instantaneous eigenspectrum of H(t). If the quantum state is prepared in the j-th energy eigenstate of H(0)=HA at time t=0, then it will remain in the j-th instantaneous eigenstate under Schrödinger evolution provided the adiabatic conditions are met. The adiabatic theorem promises that the quantum state at time T will then be the corresponding j-th energy eigenstate of H(T)=HB. The transformation from a known initial state to a final, potentially unknown state represents adiabatic quantum computation.

In practice, the instantaneous ground state of H(t) is typically chosen for the computation, and the initial Hamiltonian H(0) is selected to have a ground state that can be prepared directly. The energy spectrum gap between the quantum computational state and all other states must remain non-zero to ensure adiabatic evolution. Assuming the computational state is the ground state, the minimum spectral gap of H(t) is defined as

gmin=min0tTminj0[Ej(t)E0(t)](4)

where Ej(t) is any higher-lying energy state. The minimum spectral gap gmin sets a lower bound for the smallest internal energy scale that contributes to undesired coupling of the computational ground state to erroneous, higher-lying eigenstates. These transitions arise from diabatic quantum dynamics, with the most common example typified by Landau-Zener transitions (Zener, 1932). When the Hamiltonian changes quickly, there is a non-negligible probability for diabatic transitions that corrupt the computation. These transitions may be avoided by selecting the evolution time T to be much longer than the timescale set by the inverse of the spectral gap. Worst-case lower bounds for general Hamiltonian instances suggest T must scale as O(gmin3) (Jansen et al., 2007), while more restrictive settings can improve this to O(gmin2) (Elgart & Hagedorn, 2012).

A central concern for assessing the computational efficiency of AQC is determining how the adiabatic timescale T must grow as the size n increases. Generally, the spectral gap gmin will decrease as n increases, but the rate of this decrease greatly affects the time complexity of the computation. For example, assuming gminkn for some positive constant k, then the minimum time T needed to ensure the adiabatic condition would increase exponentially with problem size. This would indicate that an exponential increase in time is required to solve a general problem within the AQC model. Presently, theoretical estimates for how the minimum spectral gap scales with size are inconclusive for the general setting but may be developed for specific Hamiltonian models (see examples in Ref. (Albash & Lidar, 2018). Answering the general spectral, gap question appears to be computationally difficult, if not impossible (Cubitt et al., 2015). In addition, the choice of temporal interpolation strongly affects the instantaneous spectrum. Some specific instances of Hamiltonians have been found to support minimum computational times that are sub-exponential in n, provided a more general form of the temporal interpolation is employed (Roland & Cerf, 2002).

As noted above, the initial Hamiltonian H(0) should enable convenient preparation of the quantum state from which the computation begins. A frequently used Hamiltonian is the form

HA=inx^i(5)

where each term x^i represents the n-fold tensor product of n1 identity operators I and the Pauli operator x^ for the i-th qubit. The energy eigenstates and eigenvalues for this Hamiltonian can be analytically constructed while experimental methods for preparing those eigenstates have been developed (Farhi et al., 2000).

The final Hamiltonian H(T) encodes the problem to be solved by AQC as the prepared quantum state expresses the corresponding solution. The Hamiltonian complexity determines the types of problems that can be solved. For example, a Hamiltonian capable of expressing a sum of arbitrary 2-local interactions is QMA-complete, while solving the problem of a 2-local Ising Hamiltonian is NP-Complete (Kempe et al., 2006; Bravyi, Divincenzo, Oliveira, & Terhal, 2006). In particular, the latter Ising model provides a direct connection to a variety of computationally significant problems. Although the Ising model was originally developed to describe the physical pairwise interactions between the spins in a magnetic material, it has since been used to describe many other systems composed from interacting binary variables. A quantum mechanical version of the Ising Hamiltonian may be cast in the form

H=i,jJijz^iz^jjhjz^j+γ(6)

where hi represents a bias on qubit i, z^ is the z Pauli operator, γ is a constant, and Jij describes the coupling strength between qubits i and j. This formulation can be used to model a wide variety of combinatorial optimization problems (Lucas, 2014), in which they are reduced to finding the ground state of an appropriate Hamiltonian. We defer additional examples to the section “Combinatorial Optimization,” but we note that the type of Hamiltonian plays a prominent role in the problem complexity.

3. Quantum Annealing

Efforts to realize AQC using quantum physical systems are susceptible to non-ideal conditions that undermine the promise of the adiabatic theorem. This includes preparing pure quantum states that evolve under strictly adiabatic dynamics, a fundamental challenge in the control of quantum physical systems. A relaxation of the adiabatic condition is captured in the complementary computational heuristic of quantum annealing (QA), which accommodates physical systems operating at finite temperature and in open environments. Quantum annealing is a method for identifying the minimum of an objective function using an approach that is based on the principles of AQC but fails to meet its stringent requirements. Additional dynamical behaviors including stochastic dynamics may be present during the actual evolution of the quantum state (Kadowaki & Nishimori, 1998). This revokes the guarantee of remaining in the instantaneous eigenstate, though in practice it may be sufficiently close.

In practice, quantum annealing evolves a quantum state under the time-dependent Hamiltonian in Eq. (2). However, the dynamics may not be modeled as Schrödinger evolution. When the dynamics are insufficiently slow, the quantum state will mix with nearby energy eigenstates and the probability to observe the expected outcomes will be decreased. In addition, the non-zero temperature of operation for quantum annealing invalidates the pure state description. A statistical mixture of energy eigenstates is a more appropriate model for initialization of the computation. The mixture of the initial state depends on the local operating temperature as well as the energy splitting between levels used for the computational basis.

Analyzing the results from QA requires statistical sampling to build confidence in the observed outcome. The collected results may then be used in decision-making processes. For example, when the lowest energy eigenstate is the solution, higher energy states can be rejected. However, this comes at a cost that is proportional to the number rejected. In addition, QA lacks a guarantee that the sought-after solution will be included in the observed results. If the dynamics nearly satisfy the adiabatic condition, then the probability distribution should be concentrated at energies near the sought-after state.

Similar behaviors in performance are observed with several important methods of classical computation such as simulated annealing (SA). In simulated (thermal) annealing, the system state overcomes these energy barriers through random changes driven by temperature fluctuations (Heim et al., 2015). However, there is a probability for the system to get trapped in a local minimum if the temperature fluctuations are not sufficient to cross a high energy barrier. In SA, the energy landscape in static and thermal excitations drive dynamics. By contrast, QA changes the energy landscape to drive the system state toward the energetic minimum. QA can also exploit quantum tunneling through barriers.

Figure 2. At t=0, quantum annealing begins with a prepared state with uniform probability. During the annealing steps, the probability begins to concentrate at the minimums. The dynamics drive the probability toward the global minimum by final time T.

While QA is based on a more realistic model for the behavior of actual quantum physical systems, the possibility of non-adiabatic effects obscures a clear separation with conventional computing complexity. The use of quasi-adiabatic evolution of mixed quantum states in an open environment is typically characterized as a heuristic because it lacks many of the computational promises offered by AQC. This has led to empirical evaluations of the efficacy of QA for solving both real and synthetic problems with mixed results (Katzgraber et al., 2015; Weigel, Katzgraber, Machta, Hamze, & Andrist, 2015; King et al., 2015; Boixo et al., 2016; Denchev et al., 2016). In particular, it remains unclear how to best categorize the computational power of QA even under relatively well understood Hamiltonians. For example, a stoquastic Hamiltonian is defined to have only real, non-positive off-diagonal matrix elements in the standard basis representation (Bravyi et al. 2006). This restricted form captures the quantum transverse Ising Hamiltonian that underlies current experimental approaches to QA. Theoretical evidence indicates that stoquastic Hamiltonians are insufficient for universal adiabatic quantum computing when restricted to the ground state, but permitting excited-state evolution is found to remove this limitation (Jordan et al., 2010). By contrast, non-stoquastic Hamiltonians are found to be more expressive for universal quantum computing, but the size of the minimum energy gap for these Hamiltonian remains unclear in general (Albash & Lidar, 2018). Solving non-stoquastic Hamiltonians efficiently may be an important step toward universal AQC and enhancing solution quality using QA (Nishimori & Takada, 2017).

4. Hardware Implementations

Designing quantum computing hardware to implement either AQC or the QA heuristic requires time-dependent control of the Hamiltonian governing an array of quantum physical systems (Hauke et al., 2019). For computation, the hardware must also encode a relevant problem into the time-dependent Hamiltonian by programming interactions between the physical qubits and measuring the final prepared quantum state. The leading technology to demonstrate AQC is currently superconducting electronics but other systems have been proposed for similar purposes, for example, trapped ions (Zhang et al., 2018). A leading implementation of the QA heuristic is found in the recent family of processors produced by D-Wave Systems, which are based on a superconducting flux-qubit design (Bunyk et al., 2014).

4.1 Example: Superconducting Electronics

A wide variety of qubit designs are possible with many specific choices of superconducting electronics being developed to support the encoding of a two-level system through the use of Josephson junctions (Wendin, 2017). A Josephson junction is a nanoscale insulating layer on the superconducting loop that is a leading design choice for AQC/QA implementations (Johnson et al., 2011). Although electrons move freely on the surface of a superconductor with no resistance, electrons probabilistically tunnel through the Josephson junction to form a superposition of states and thus a two-level system. A flux qubit is an example that prepares a quantized magnetic flux (Johnson et al., 2011) in a superposition of states using a Josephson junction as shown in Figure 3. While in a superposition of states, external magnetic fields can be applied to change the potential energy landscape or “weight” of each qubit according to the adiabatic theorem. The qubits are also arranged in such a way that the magnetic field of each qubit is directly dependent on its surrounding qubits via magnetic interference. This magnetic coupling is analogous to entanglement and is mathematically identical for the purpose of quantum computation. After the evolution is complete (at final time T), superconducting quantum-interference devices (SQUID) which are inductively coupled to each qubit detect and read-out the magnetic field/state of each qubit (Jaklevic et al., 1964).

Figure 3. A flux-qubit design based on a compound Josephson junction in which counter-propagating currents induce a magnetic field. The flux qubit is encoded within the resulting magnetic flux while externally applied control biases tune the current (Johnson et al., 2011).

A key challenge that arises in building a scalable AQC/QA device using superconducting electronics is maximizing the connectivity of the physical elements. An ideal design would enable all-to-all connectivity between the physical elements that represent the qubits as this ensures the most direct form of interactions for encoding an arbitrary problem Hamiltonian. However, the two-dimensional plane in which superconducting circuit technology is typically fabricated imposes a physical restriction on the degree of connectivity that can be fabricated. Consequently, trade-offs in the physical design are required. Such limited connectivity may still enable encoding of an arbitrary Hamiltonian but at the expense of redundant encoding of logical variables as chains of (perfectly) correlated spins. The challenge of mapping this smaller, more densely connected graph into the limited connectivity of available hardware is known as minor embedding (Choi, 2008), and a wide variety of techniques have been developed for this pre-processing step (Klymko et al., 2014; Venturelli et al., 2015; Goodrich et al., 2018).

A second key challenge that arises for hardware implementations of AQC/QA is minimizing the noise arising from the environment and the applied control signals. In particular, design choices for the superconducting electronics can enable certain features of the physical system to be more or less resilient to noise in the electrical control signals used (Harris et al., 2010). For the flux-qubits that feature prominently in AQC/QA implementations, there is a known sensitivity to flux noise that arises from magnetic-field fluctuations within the electronic circuits; these may be due to direct noise in the applied electrical fields or induced noise in nearby conductors (Quintana et al., 2017). In either case, the precision with which the time-dependent evolution may be controlled is limited by such noise.

4.2 Hardware Controls

The control of AQC/QA hardware requires tuning the time-dependent Hamiltonian by which the physical system evolves. Methods for adjusting and tuning the initial and final Hamiltonian parameters as well as the interpolating time-dependent schedule are necessary to drive dynamics of problem-specific quantum states. These controls may be used to improve the performance of AQC or QA programs by adjusting the interpolation either to better approximate adiabatic evolution or refine the problem definition. There are several approaches including varying the rate at which the energy landscape evolves, tuning the parameters or weights in the formulation of the Hamiltonian (Choi, 2008; Pudenz, 2016), and adjusting the initial Hamiltonian. These controls determine the dynamics and can affect the quality of the solution as well as time to the solution.

As described by the adiabatic theorem in Section 2, Adiabatic Quantum Computing, the time T needed to ensure adiabatic evolution of the problem Hamiltonian is inversely proportional to the minimum energy gap gmin. Therefore, the shortest possible total T is dictated by gmin. This is based on the assumption that rate of evolution remains constant in time (Farhi et al., 2000). However, the total time T of a quantum computation via adiabatic evolution can be improved by applying the adiabatic condition locally to infinitesimal time intervals dt for H(t). As shown in Figure 4, the spectral gap changes over time and may only reach its minimum value in a very small region of the dynamics. Therefore, a more optimal schedule would account for the local spectral gap by increasing the rate of evolution when the energy gap widens and decreasing the rate of evolution when the energy gap narrows, as shown in Figure 5.

The advantages of local adiabatic evolution have been applied to an example of Grover’s search algorithm, which returns a sought-after value encoded into a target Hamiltonian (Roland & Cerf, 2002). Classically, this search problem takes on average N/2 queries, where N is the number of entries in the database. Grover’s algorithm for the circuit model of quantum computing was shown previously to obtain a quadratic speedup relative to the best classical method (Nielsen & Chuang, 2010). Roland and Cerf extended this analysis to AQC by showing a similar N speedup is possible when using local control of the schedule and an evolution time (Roland & Cerf, 2002)

T=π2εN(7)

for recovery error ε1. ε1.

Figure 4. The time-dependent energy eigenspectrum for the time-dependent Hamiltonian used an example of Grover’s search algorithm for AQC where s=tT is the position in the anneal schedule. Note that the spectral gap between the ground state and first excited state changes with time (Roland & Cerf, 2002).

Figure 5. The optimal local schedule for implementing Grover’s search using AQC accounts for the time-dependent behavior of the spectral gap shown in Figure 4 where s=tT is the position in the anneal schedule. This schedule tailors the dynamics to evolve more slowly near the minimum spectral gap at s=.5 and faster outside of this region.

To implement this sort of scheduling, there must be some understanding of how the energy landscape fluctuates in time, namely how the energy gap (g) changes. Therefore, gmin must be approximated for each time slice, dt. Knowing gmin for dt requires knowing the ground state and first excited state for all H(dt). However, there are some potentially powerful tricks that could approximate an evolution schedule prior to solving a problem. For instance, there may be similarities between problems that fall into various categories. Pre-processing methods could be used to sweep over parameters to find optimal controls, or sampling the energy landscape could reveal an optimal annealing schedule for a category of problems. There may also be key features of a problem that can be used to approximate an annealing schedule through machine-learning methods.

Another mechanism for improving total anneal time is to control the initial Hamiltonian. This was first suggested by Farhi et al. 2009 when they chose the initial Hamiltonian (HA) for a set of 3-SAT optimization problems known to have a very small gmin in the standard AQC model (Farhi et al., 2009).

HA=12i=1nci(1Xi)(8)

where ci is chosen to be 1/2 or 3/2 randomly and with equal probability. With this method, the energy landscape is modified such that there is a high probability to remove the narrow energy gap and get a larger gmin if the problem instance is solved many times with different randomly selected HA (Farhi et al., 2009). This method is attractive because problems can be solved quickly and globally without prior knowledge of the energy landscape. However, it can be difficult to know how many different HA to use for a particular problem instance to ensure that a solution close to the ground state is discovered.

Another strategy is to formulate the initial Hamiltonian such that its ground state is the best guess for the ground state of the problem Hamiltonian (Perdomo-Ortiz et al., 2011). If after running the problem some number of times, a lower energy state (enew) is discovered, enew is set as the new ground state of HA and the process is repeated. This can be very useful for problems where there is some prior intuition for what the answer might be; it is often referred to as the “warm-start approach.”

5. Applications

Several applications have been developed within the AQC model to take advantage of its explicit representation of optimization (McGeoch & Wang, 2013). Broadly, suitable combinatorial optimization may be found in diverse areas including unconstrained and constrained optimization (Hen & Spedalieri, 2016; Santoro & Tosatti, 2006; Dinneen et al., 2019; Bian et al., 2016), number theory and graph theory (Bian et al., 2013; Ushijima-Mwesigwa et al., 2017; Chapuis et al., 2019; Jiang et al., 2018), and machine-learning (Neven et al., 2008; Dridi & Alghassi, 2017; Mott et al., 2017; Adachi & Henderson, 2015). Extension of these ideas to specific application problems has also received significant attention (Feynman, 1982), (Neukaxt et al., 2017; Perdomo-Ortiz et al., 2012; Crispin & Syrichas, 2013; Rosenberg et al., 2016; Kalinin & Berloff, 2018; Marzec, 2016).

A second area of AQC applications is data analytics and, in particular, several applications have been developed to leverage QA to investigate probability distributions. Sampling from the prepared distribution provides a convenient method for calculating expectation values and other statistics. This data analytic technique forms the basis of many machine-learning methods (Mott et al., 2017; Adachi & Henderson, 2015; Deng & Yu et al., 2014; Schrock et al., 2017; Potok et al., 2018).

A third emerging application area is the simulation of quantum Hamiltonian models, which is an important focus of study for the physical sciences (e.g., in high-energy physics, chemistry, materials science, and biology). These applications sample the quantum state prepared by a model adiabatic process to estimate the physical features of quantum-mechanical systems (Harris et al., 2018; King et al., 2018; Xia et al., 2017).

5.1 Combinatorial Optimization

Optimization problems seek the best solution within a set of many candidates. They are often difficult to solve because the solution may not be obvious or it may not be easy to quickly search the candidates. Solvers for optimization problems have found a natural implementation within the AQC model that can be designed to follow evolution of the lowest energy state of a model Hamiltonian. By designing the model Hamiltonian to mimic an optimization problem, the preparation of a final quantum state can represent the solution to the original optimization problem. Moreover, AQC offers the promise that the solution is optimal when the adiabatic condition is met throughout the computation. The QA heuristic may also be used for optimization, but it does not guarantee that the optimal solution will be found.

The choice of the target Hamiltonian determines the type of optimization problems that can be solved using either AQC or QA. For example, currently available QA hardware relies on a target Hamiltonian that models an Ising Hamiltonian, as described in Eq. 6. A wide variety of problems have been reduced to the Ising form (Lucas, 2014; De las Cuevas & Cubitt, 2016). The Ising Hamiltonian itself is naturally related to quadratic unconstrained binary optimization (QUBO). The QUBO problem is formulated to find the minimum of a quadratic polynomial with binary variables, that is,

E(x)=i=1ncixi+i=1nj=1nQi,jxixj(9)

where x{0,1}, ci represents the linear term to be minimized, and Qij describes the quadratic interactions or correlations between variables. The conversion from QUBO to Ising form is performed by using the transformation of variable x{0,1} to spin s{1,1}. The classical spin variable can then be substituted by the corresponding quantum operator to achieve a quantum Ising Hamiltonian as defined by Eq. 6. A variety of different combinatorial optimization problems have been reduced to this form (Lucas, 2014). We briefly describe several examples below.

3-SAT. A satisfiability (SAT) problem determines whether an assignment for Boolean variables that satisfies a set of logical clauses exists. Such a problem arises in many practical applications including product model checking and verification, planning and protocols, structural design, etc (Biere et al., 2009). The well-known Cook-Levin theorem from computational complexity theory places the 3-SAT problem in the NP-Complete complexity class (Cook, 1971; Levin, 1973), where this variant is specialized to cases for which every clause has at most three variables. Moreover, 3-SAT provides a constructive means by which a variety of other problems can be shown to lie in the NP hierarchy (Karp, 1972). This includes the Ising problem introduced above, which was identified by Farhi et al. (2000) as an important step in solving 3-SAT within AQC.

When introducing AQC as a method for solving optimization problems, Farhi showed how AQC could be used to solve 3-SAT using a 3-local Hamiltonian

Hp=inHi(10)

where Hi is a k-local Hamiltonian corresponding to the i-th clause (Farhi et al., 2000). If the smallest eigenvalue of Hp is 0, then each clause of the problem is satisfiable. (Albash & Lidar, 2018).

Binary Integer Linear Programming. Binary Integer Linear Programming (BILP) is an NP-Hard problem that maximizes or minimizes an objective function subject to a series of constraints. Practical examples include portfolio optimization (Venturelli & Kondratyev, 2018; Rosenberg et al., 2016), scheduling, networking (Neukart et al., 2017), etc.

maxxiaixisuchthatibixi=c(11)

where ai and bi are variables, c is a hard constraint, and xi{0,1}. To solve this problem with AQC, it must transform into an unconstrained problem. The Ising Hamiltonian representation is given by

H=θ1ixiaiixiθ2(ixibixic)2(12)

where the hard constraint around c becomes an unconstrained penalty for any deviation around c and θ1 and θ2 are weights that balance the first and second terms of Eq. 12 during the maximization of the a parameters.

Graph Theory. Graphs are used to represent networks where each node is an object and the lines connecting each node represent the relationships between objects. Graph theory can be used to solve many NP-Hard optimization problems like set cover (Karp, 1972), graph partitioning (Fu & Anderson, 1986), and graph coloring (Jensen & Toft, 2011) and the NP-complete traveling-salesman problem (TSP) (Lawler, 1985). The TSP, for instance, aims to find the shortest route which hits all desired destinations. These problems have been mapped successfully to quantum annealing hardware (Lucas, 2014; Titiloye & Crispin, 2011; Martonak et al., 2004; Cao et al., 2016).

5.2 Machine Learning

Machine learning using AQC and QA-based methods has attracted significant interest for a number of applications. Broadly, machine learning infers correlations from data, and several different approaches have been developed for this purpose within the AQC model. This includes both supervised and unsupervised training methods, which cast training as a global optimization problem that may be reduced to finding the lowest-energy state of a corresponding Hamiltonian (Lloyd et al., 2013). Because QA is able to find a solution that is close-to-optimal within a large set of possibilities, there is interest in using this approach to either optimize or accelerate the training state of machine learning. As part of an unsupervised machine-learning algorithm, O’Malley et al. (2017) used quantum annealing to recognize facial-feature patterns.

In another application, quantum annealing has been used to train a Boltzmann machine used in classification methods. A Boltzmann machine is an artificial neural network with visual and hidden nodes that encode information in their weighted couplings (Hinton, 2014). Whereas general Boltzmann machines do not restrict connections between nodes, a restricted Boltzmann machine (RBM) only permits connections between nodes in different layers. In either model, the underlying network is expressed in terms of a Ising model that uses the spin variables as the nodes and the couplings to define connectivity (Biamonte et al., 2017). Quantum annealing with the Ising Hamiltonian can therefore be used with either type of Boltzmann machine to find the optimal weighted couplings. Training Boltzmann machines with AQC/QA has been tested experimentally (Potok et al., 2018; Liu et al., 2018).

5.3 Quantum Simulation

An emerging application area for AQC/QA is the simulation of condensed-matter systems, where quantum many-body effects are often critical to the behavior of the modeled material. Understanding the behavior of materials is a challenge because simulating quantum many-body systems on a classical computer is computationally expensive. As originally proposed by Feynman (Feynman, 1982), quantum computing offers a natural paradigm in which to both model and simulate these highly correlated materials. For example, a key problem for materials science is characterizing the energetic ground state of a material system; the formulation of AQC in terms of a target Hamiltonian provides a natural connection to this problem.

One approach to this materials science application is to use QA to simulate the magnetic phase transitions in an Ising Hamiltonian over a multidimensional lattice. This application prepares the ground state of the Ising Hamiltonian defined in Eq. 8 and then probes the prepared quantum state to recover the magnetization. By selecting the parameters for the Ising Hamiltonian, an expected phase of matter can be programmed and characterized. A recent demonstration validated the observed magnetization for different phases of a spin-glass system (Harris et al., 2018).

This approach may also be used to simulate quantum phase transitions provided the underlying Hamiltonian supports a model for such a system. For example, the Kosterlitz-Thouless (KT) phase transition can be simulated in a transverse Ising Hamiltonian over a square-octagonal lattice. The KT-phase transition arises from frustrations and quantum fluctuations within this model Hamiltonian, and QA-based simulations have been validated directly against classical simulations (King et al., 2018). The programmability of the target Hamiltonian enables simulation by quantum annealing to test many different model phases of matter.

6. Open Questions

Many prominent questions remain open about the expected physical and computational behavior of AQC. This includes clarification about how non-adiabatic effects impact the performance of quantum annealing devices as well as how the optimal run-time can be realized without prior knowledge of the underlying energy landscape (Quiroz, 2019; Marshall et al., 2019). The design, development, and demonstration of reliable and programmable adiabatic quantum computers also remains an open endeavor. The idealized setting for satisfying the adiabatic condition exactly has yet to be realized in practice, and robust models for describing non-adiabatic effects will require better characterization about the underlying physical systems. Existing demonstrations that relax the adiabatic condition have made remarkable progress in controllability of quantum annealing, but experimental evidence remains mixed on the computational performance. This is due mainly to the relatively small amount of data that can be processed by these devices, which is insufficient for best-in-class comparisons.

Further experimental investigations into computational scaling using larger capacity devices will help identify the significance of non-adiabatic effects. However, the scaling of adiabatic quantum computing to arbitrarily large capacities is likely to require methods for managing and correcting faults that arise from noise in the devices and errors in the controls. The principles of fault-tolerant operation are well defined within the context of the circuit model of quantum computation, where redundantly encoded quantum states are actively corrected in the presence of noise. These principles may also apply to AQC, but a complete theory of fault-tolerant adiabatic quantum computation has yet to be developed.

Assuming the engineering of scalable quantum devices is achieved, AQC can be expected to have a significant impact on computational science. Already the formal reduction of many combinatorial optimization problems to the Ising problem have made AQC an attractive model for a number of known applications. But AQC supports an even broader class of Hamiltonians, including those that are complete for BQP and QMA. And it remains to be seen how this can be leveraged for new methods of quantum computation.

References

  • Adachi, S. H., & Henderson, M. P. (2015). Application of quantum annealing to training of deep neural networks. arXiv preprint arXiv:1510.06356.
  • Adachi, S. H., & Henderson, M. P. (2015). Application of quantum annealing to training of deep neural networks. arXiv preprint arXiv:1510.06356.
  • Adami, C., & Cerf, N. J. (1999). Quantum computation with linear optics. In Quantum computing and quantum communications (pp. 391–401). New York, NY: Springer.
  • Aharonov, D., Van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2008). Adiabatic quantum computation is equivalent to standard quantum computation. SIAM Review, 50(4), 755–787.
  • Albash, T., & Lidar, D. A. (2018). Adiabatic quantum computation. Reviews of Modem Physics, 90(1), 015002.
  • Bengtsson, I., & Zyczkowski, K. (2017). Geometry of quantum states: an introduction to quantum entanglement. Cambridge, U.K.: Cambridge University Press.
  • Bernstein, E., & Vazirani, U. (1997). Quantum complexity theory. SIAM Journal on Computing, 26(5) 1411–1473.
  • Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017). Quantum machine learning. Nature, 549(7671), 195.
  • Bian, Z., Chudak, F., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A. (2016). Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. Frontiers in ICT, 3, 14.
  • Bian, Z., Chudak, F., Macready, W. G., Clark, L., & Gaitan, F. (2013, September). Experimental determination of ramsey numbers. Phys. Rev. Lett., 3, 130505.
  • Biere, A., Heule, M., & van Maaren, H. (2009). Handbook of satisfiability (Vol. 185 Frontiers in Artificial Intelligence and Applications). Fairfax, VA: IOS Press.
  • Boixo, S., Smelyanskiy, V. N., Shabani, A., Isakov, S. V., Dykman, M., Denchev, V. S., . . . Neven, H. (2016). Computational multiqubit tunnelling in programmable quantum annealers. Nature Communications, 7, 10327.
  • Born, M., & Fock, V. (1928). Beweis des adiabatensatzes. Zeitschrift fur Physik, 51(3), 165–180.
  • Bravyi, S., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2006). The complexity of stoquastic local Hamiltonian problems. ArXiv preprint quant-ph/0606140.
  • Bravyi, S., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2008). The complexity of stoquastic local Hamiltonian problems. Quantum Inform Comput, 8, 0361.
  • Bunyk, P. I., Hoskinson, E. M., Johnson, M. W., Tolkacheva, E., Al- Tomaxe, F., Berkley, A. J., . . . Przybysz, A. J. (2014). Architectural considerations in the design of a superconducting quantum annealing processor. IEEE Transactions on Applied Superconductivity, 24(4), 1–10.
  • Cao, Y., Jiang, S., Perouli, D., & Kais, S. (2016). Solving set cover with pairs problem using quantum annealing. Scientific Reports, 6, 33957.
  • Chapuis, G., Djidjev, H., Hahn, G., & Rizk, G. (2019, March). Finding maximum cliques on the d-wave quantum annealer. Journal of Signal Processing Systems, 91, 363–377.
  • Childs, A. M., Farhi, E., Goldstone, J., & Gutmann, S. (2000). Finding cliques by quantum adiabatic evolution. ArXiv preprint quant-ph/0012104.
  • Childs, A. M., Faxhi, E., Goldstone, J., & Gutmann, S. (2002). Finding cliques by quantum adiabatic evolution. Quantum Inform Comput, 2, 181.
  • Choi, V. (2008). Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Information Processing, 7, 193.
  • Choi, V. (2010). Adiabatic quantum algorithms for the np-complete maximum-weight independent set, exact cover and 3sat problems. ArXiv: 1004.2226v1.
  • Cook, S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on theory of computing (pp. 151–158). New York, NY: ACM.
  • Crispin, A., & Syrichas, A. (2013). Quantum annealing algorithm for vehicle scheduling. Manchester, U.K. In 2013 IEEE International Conference on Systems, Man, and Cybernetics (pp. 3523–3528). IEEE.
  • Cubitt, T. S., Perez-Garcia, D., & Wolf, M. M. (2015). Undecidability of the spectral gap. Nature, 528(7581), 207.
  • De las Cuevas. G., & Cubitt, T. S. (2016). Simple universal models capture all classical spin physics. Science, 351(6278), 1180–1183.
  • Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016, August). What is the computational value of finite-range tunneling? Phys. Rev. X, 6, 031015.
  • Deng, L., Yu, D. (2014). Deep learning: methods and applications. Foundations and Trends in Signal Processing, 7(3–4), 197, 387.
  • Deutsch, D. (1985). Quantum theory, the church-turing principle and the universal quantum computer. Proc. R. Soc. Lond. A, 400(1818), 97–117.
  • Devoret, M. H., & Martinis, J. M. (2005). Implementing qubits with superconducting integrated circuits. In Experimental aspects of quantum computing (pp. 163–203). Boston, MA: Springer.
  • Dinneen, M. J., Mahasinghe, A., & Liu, K. (2019, February). Finding the chromatic sums of graphs using a d-wave quantum computer. The Journal of Supercomputing, 75(8), 4811–4828.
  • DiVincenzo, D. P. (2000). The physical implementation of quantum computation. Fortschritte der Physik: Progress of Physics, 48(9–11), 771–783.
  • Dridi, R., & Alghassi, H. (2017). Prime factorization using quantum annealing and computational algebraic geometry. Scientific Reports, 7, 43048.
  • Elgart, A., & Hagedorn, G. A. (2012). A note on the switching adiabatic theorem. Journal of Mathematical Physics, 53(10), 102202.
  • Farhi, E., Goldstone, J., Gosset, D., Gutmann, S., Meyer, H. B., & Shor P. (2009). Quantum adiabatic algorithms, small gaps, and different paths. ArXiv:0909.4766v2.
  • Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000). Quantum computation by adiabatic evolution. ArXiv:quant-ph/0001106.
  • Feynman, R. P. (1982). Simulating physics with computers. International Journal of Theoretical Physics, 21(6–7), 467–488.
  • Fu, Y., & Anderson, P. W. (1986). Application of statistical mechanics to np- complete problems in combinatorial optimization. Journal of Physics A: Mathematical and General, 19(9), 1605.
  • Goodrich, T. D., Sullivan, B. D., & Humble, T. S. (2018). Optimizing adiabatic quantum program compilation using a graph-theoretic framework. Quantum Information Processing, 17(5), 118.
  • Harris, R., Johansson, J., Berkley, A. J., Johnson, M. W., Lanting, T., Han, S., . . . Rose, G. (2010, April). Experimental demonstration of a robust and scalable flux qubit. Phys. Rev. B, 81, 134510.
  • Harris, R., Sato, Y. A. Berkley, M. Reis, F. Altomare, M. Amin, K. Boothby, P. Bunyk, C. Deng, C. Enderud. (2018). Phase transitions in a programmable quantum spin glass simulator. Science, 361(6398), 162–165.
  • Hauke, R., Katzgraber, H. G., Lechner, W., Nishimori, H., & Oliver, W. D. (2019). Perspectives of quantum annealing: Methods and implementations. ArXiv:1903.06559.
  • Heim, B., Rpnnow, T. F., Isakov, S. V., & Troyer, M. (2015). Quantum versus classical annealing of Ising spin glasses. Science, 348(6231), 215–217.
  • Hen, I., & Spedalieri, F. M. (2016). Quantum annealing for constrained optimization. Physical Review Applied, 5(3), 034007.
  • Hinton, G. (2014). Boltzmann machines. In Encyclopedia of machine learning and data mining (pp. 1–7). Scholarpedia, 2(5), 1668.
  • Hogg, T. (2003). Adiabatic quantum computing for random satisfiability problems. Physical Review A, 67(2), 022314.
  • Horodecki, R., Horodecki, P., Horodecki, M., & Horodecki, K. (2009, June). Quantum entanglement. Reviews of Modern Physics, 81, 865–942.
  • Jaklevic, R., Lambe, J., Silver, A., & Mercereau, J. (1964). Quantum interference effects in Josephson tunneling. Physical Review Letters, 12(7), 159.
  • Jansen, S., Ruskai, M.-B., & Seiler, R. (2007). Bounds for the adiabatic approximation with applications to quantum computation. Journal of Mathematical Physics, 48(10), 102111.
  • Jensen, T. R., & Toft, B. (2011). Graph coloring problems (Vol. 39). Chichester, U.K.: John Wiley.
  • Jiang, S., Britt, K. A., McCaskey, A. J., Humble, T. S., & Kais, S. (2018). Quantum annealing for prime factorization. Scientific Reports (Nature Publisher Group), 8, 1–9.
  • Johnson, M. W., Amin, M. H., Gildert, S., Lanting, T., Hamze, F., Dickson, N., . . . Bunyk, P. (2011). Quantum annealing with manufactured spins. Nature, 473(7346), 194.
  • Jordan, S. R., Gosset, D., & Love, R. J. (2010). Quantum-Merlin-Arthur- complete problems for stoquastic Hamiltonians and Markov matrices. Physical Review A, 81(3), 032331.
  • Kadowaki, T., & Nishimori, H. (1998). Quantum annealing in the transverse Ising model. Physical Review E, 58(5), 5355.
  • Kalinin, K. P., & Berloff, N. G. (2018). Blockchain platform with proof- of-work based on analog Hamiltonian optimisers. ArXiv:1802.10091.
  • Karp, R. M. (1972). Reducibility among combinatorial problems. In Raymond E. Miller, James W. Thatcher, & Jean D. Bohlinger (Eds.), Complexity of computer computations (pp. 85–103). Boston, MA: Springer.
  • Katzgraber, H. G., Hamze, F., Zhu, Z., Ochoa, A. J., & Munoz-Bauza, H. (2015). Seeking quantum speedup through spin glasses: The good, the bad, and the ugly. Physical Review X, 5(3), 031026.
  • Kempe, J., Kitaev, A., & Regev, O. (2006). The complexity of the local hamiltonian problem. SIAM Journal on Computing, 35(5), 1070–1097.
  • King, A. D., Carrasquilla, J., Ozfidan, I., Raymond, J., Andriyash, E., Berkley, A., . . . Poulin-Lamarre, G. (2018). Observation of topological phenomena in a programmable lattice of 1,800 qubits. Nature, 560, 456–460.
  • King, J., Yarkoni, S., Nevisi, M. M., Hilton, J. P., & McGeoch, C. C. (2015). Benchmarking a quantum annealing processor with the time-to-target metric. ArXiv:1508.05087.
  • Klymko, C., Sullivan, B. D., & Humble, T. S. (2014). Adiabatic quantum programming: Minor embedding with hard faults. Quantum Information Processing, 13(3), 709–729.
  • Lawler, E. L. (1985). The traveling salesman problem: A guided tour of combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics.
  • Lenstra, J. K., & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221–227.
  • Levin, L. A. (1973). Universal sequential search problems. Problemy Peredachi Informatsii, 9(3), 115–116.
  • Liu, J., Spedalieri, F., Yao, K.-T., Potok, T., Schuman, C., Young, S., . . . Chamka, G. (2018). Adiabatic quantum computation applied to deep learning networks. Entropy, 20(5), 380.
  • Lloyd, S., Mohseni, M., & Rebentrost, P. (2013). Quantum algorithms for supervised and unsupervised machine learning. ArXiv:1307.0411.
  • Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, 2, 5.
  • Marshall, J., Venturelli, D., Hen, I., & Rieffel, E. G. (2019). Power of pausing: Advancing understanding of thermalization in experimental quantum annealers. Physical Review Applied, 11(4), 044083.
  • Martonak, R., Santoro, G. E., & Tosatti, E. (2004). Quantum annealing of the traveling-salesman problem. Physical Review E, 70(5), 057701.
  • Marzec, M. (2016). Portfolio optimization: Applications in quantum computing. In Ionut Florescu, Maria C. Mariani, H. Eugene Stanley, & Frederi Viens (Eds.), Handbook of high-frequency trading and modeling in finance (pp. 73–106). Chichester, U.K.: John Wiley.
  • McGeoch, C. C., & Wang, C. (2013). Experimental evaluation of an adiabatic quantum system for combinatorial optimization. In Proceedings of the ACM International Conference on Computing Frontiers (p. 23). ACM, no. 23, (1–11), New York, NY.
  • Montanaxo, A. (2016). Quantum algorithms: An overview. NPJ Quantum Information, 2, 15023.
  • Mott, A., Job, J., Vlimant, J.-R., Lidar, D., & Spiropulu, M. (2017). Solving a higgs optimization problem with quantum annealing for machine learning. Nature, 550(7676), 375.
  • Neukart, F., Compostella, G., Seidel, C., Von Dollen, D., Yarkoni, S., & Parney, B. (2017). Traffic flow optimization using a quantum annealer. Frontiers in ICT, 4, 29.
  • Neukaxt, F., Compostella, G., Seidel, C., von Dollen, D., Yarkoni, S., & Parney, B. (2017). Traffic flow optimization using a quantum annealer. Frontiers in ICT, 4, 29.
  • Neven, H., Rose, G., & Macready, W. G. (2008). Image recognition with an adiabatic quantum computer: I. Mapping to quadratic unconstrained binary optimization. ArXiv.0804-4457.
  • Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information. (2nd ed.). Cambridge, U.K.: Cambridge University Press.
  • Nishimori, H., & Takada, K. (2017). Exponential enhancement of the efficiency of quantum annealing by non-stoquastic Hamiltonians. Frontiers in ICT, 4, 2.
  • O’Malley, D., Vesselinov, V. V., Alexandrov, B. S., & Alexandrov, L. B. (2017). Nonnegative/binary matrix factorization with a d-wave quantum annealer. ArXiv:1704-01605.
  • Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G., & Aspuru-Guzik, A. (2012). Finding low-energy conformations of lattice protein models by quantum annealing. Scientific Reports, 2, 571.
  • Perdomo-Ortiz, A., Venegas-Andraca, S. E., & Aspuru-Guzik, A. (2011). A study of heuristic guesses for adiabatic quantum computation. Quantum Information Processing, 10(1), 33–52.
  • Potok, T. E., Schuman, C., Young, S., Patton, R., Spedalieri, F., Liu, J., . . . Chakma, G. (2018). A study of complex deep learning networks on high-performance, neuromorphic, and quantum computers. ACM Journal on Emerging Technologies in Computing Systems (JETC), 14(2), 19.
  • Preskill, J. (2018, August). Quantum computing in the NISQ era and beyond. Quantum, 2, 79.
  • Pudenz, K. L. (2016). Parameter setting for quantum annealers. In 2016 IEEE high performance extreme computing conference (HPEC) (pp. 1-IEEE). Waltham, MA.
  • Quintana, C., Chen, Y., Sank, D., Petukhov, A., White, T., Kafri, D., . . . Campbell, B. (2017). Observation of classical-quantum crossover of 1/f flux noise and its paramagnetic temperature dependence. Physical Review Letters, 118(5), 057702.
  • Quiroz, G. (2019). Robust quantum control for adiabatic quantum computation. Physical Review A, 99(6), 062306.
  • Roland, J., & Cerf, N. J. (2002). Quantum search by local adiabatic evolution. Physical Review A, 65(4), 042308.
  • Rosenberg, G., Haghnegahdar, P., Goddard, P., Carr, P., Wu, K., & De Prado, M. L. (2016). Solving the optimal trading trajectory problem using a quantum annealer. IEEE Journal of Selected Topics in Signal Processing, 10(6), 1053–1060.
  • Santoro, G. E., & Tosatti, E. (2006). Optimization using quantum mechanics: Quantum annealing through adiabatic evolution. Journal of Physics A: Mathematical and General, 39(36), R393.
  • Schrock, J., McCaskey, A., Hamilton, K., Humble, T., & Imam, N. (2017). Recall performance for content-addressable memory using adiabatic quantum optimization. Entropy, 19(9), 500.
  • Struck, P. R., & Burkard, G. (2016). Spin quantum computing. Dordrecht, The Netherlands: Springer Netherlands, 2016.
  • Titiloye, O., & Crispin, A. (2011). Quantum annealing of the graph coloring problem. Discrete Optimization, 8(2), 376–384.
  • Ushijima-Mwesigwa, H., Negre, C. F. A., & Mniszewski, S. M. (2017). Graph partitioning using quantum annealing on the d-wave system. In Proceedings of the Second International Workshop on Post Moores Era Supercomputing (pp. 22–29). New York, NY: ACM.
  • Venturelli, D., & Kondratyev, A. (2019). Reverse quantum annealing approach to portfolio optimization problems. Quantum Machine Intelligence, 1(1–2), 17–30.
  • Venturelli, D., Mandra, S., Knysh, S., O’Gorman, B., Biswas, R., & Smelyanskiy, V. (2015). Quantum optimization of fully connected spin glasses. Physical Review X, 5(3), 031040.
  • Venturelli, D., & Kondratyev, A. (2019). Reverse quantum annealing approach to portfolio optimization problems. Quantum Machine Intelligence, 1(1-2), 17–30.
  • Katzgraber, H. G., Hamze, F., & Andrist, R. S. (2014). Glassy chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines. Physical Review X, 4(2), 021008.
  • Weigel, M., Katzgraber, H. G., Machta, J., Hamze, F., & Andrist, R. S. (2015). Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines. Physical Review X, 5(1), 019901.
  • Wendin, G. (2017). Quantum information processing with superconducting circuits: A review. Reports on Progress in Physics, 80(10), 106001.
  • Wieschebrink, C. (2006, July). Two NP-complete problems in coding theory with an application in code based cryptography. In 2006 IEEE International Symposium on Information Theory (pp. 1733–1737). IEEE.
  • Xia, R., Bian, T., & Kais, S. (2017). Electronic structure calculations and the Ising Hamiltonian. The Journal of Physical Chemistry B, 122(13), 3384–3395.
  • Zener, C. (1932). Non-adiabatic crossing of energy levels. Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character, 137(833), 696–702.
  • Zhang, J., Li, F.-G., Xie, Y., Wu, C.-W., Ou, B.-Q., Wu, W., & Chen, P.-X. (2018). Realizing an adiabatic quantum search algorithm with shortcuts to adiabaticity in an ion-trap system. Physical Review A, 98(5), 052323.