Quantum and classical dynamics in adiabatic computation

Adiabatic transport provides a powerful way to manipulate quantum states. By preparing a system in a readily initialized state and then slowly changing its Hamiltonian, one may achieve quantum states that would otherwise be inaccessible. Moreover, a judicious choice of final Hamiltonian whose ground state encodes the solution to a problem allows adiabatic transport to be used for universal quantum computation. However, the dephasing effects of the environment limit the quantum correlations that an open system can support and degrade the power of such adiabatic computation. We quantify this effect by allowing the system to evolve over a restricted set of quantum states, providing a link between physically inspired classical optimization algorithms and quantum adiabatic optimization. This perspective allows us to develop benchmarks to bound the quantum correlations harnessed by an adiabatic computation. We apply these to the D-Wave Vesuvius machine with revealing—though inconclusive—results.

Figure 1

Variational submanifold. In Eqs. (3) and (5), we consider dynamics that are continuously projected onto a variational submanifold of a certain degree of entanglement, captured by matrix product states of a particular Schmidt rank. Hamiltonian evolution will generally increase the degree of entanglement and coupling to a bath will counter this. The result is that the systems dynamics may be described semiclassically on an appropriate variational submanifold. When the degree of quantum entanglement captured by the variational manifold is insufficient, the projected evolution may deviate from the actual adiabatic evolution in the full Hilbert space.

Figure 2

Conditions for successful adiabatic computation. The boundary between successful and unsuccessful adiabatic computation forms a convex hull in a plot of (dissipation-limited) accessible fraction of Hilbert space versus sweep time. The minimum computation time $T^{*}$ occurs when all of the Hilbert space is accessible. The minimum fraction of Hilbert space for adiabatic computation is given by the horizontal asymptote at $f^{*}$. Schmidt rank is used as a discontinuous measure of the size of this accessible region in the present work. Contact with measures of computational complexity is made by dividing both axes into regions polynomial and exponential in the system size $N$. A quantum mechanically and classically easy calculation (I) can be performed in polynomial time with only a small fraction of the Hilbert space. A quantum mechanically easy, classically hard computation (II) can only be performed in a polynomial time using a large fraction of the Hilbert space.

Figure 3

Effects of temperature upon adiabatic computation. The boundary between successful and unsuccessful adiabatic computation becomes diffuse at finite temperature as the fluctuations render the adiabatic algorithm stochastic. Here, we modify the adiabatic success hull of Fig. 2 to include finite-temperature effects, sketching the boundary between successful and unsuccessful computation at three different temperatures: (a), (b), and (c). (a) At zero temperature the boundary is sharp except for the effects of zero-point fluctuations of the environment, which we assume small. At finite temperature, (b) and (c), the boundary is diffuse and the success probability increases smoothly from zero to one. Increasing sweep time increases exposure to noise and the width of crossover between success and failure increases. Crucially for attempts to determine the degree of quantum mechanics in an adiabatic computation, the change in success probability need not be monotonic either in changing sweep time [case (c)], or as a function of temperature [dashed line connecting curves (a)–(c)].

Figure 4

Success probability correlated with minimum Schmidt rank required for successful adiabatic computation. Histograms of number of problem instances versus D-Wave success probability. The data are divided into cohorts requiring different Schmidt rank for successful adiabatic computation. We show data for 500 instances of the one-dimensional chain. Problem instances with higher threshold Schmidt rank—and so more quantum according to Fig. 3—are more difficult to solve on the D-Wave Vesuvius machine.

Figure 5

Success probability compared with minimum sweep time required for successful adiabatic computation. Histograms of number of problem instances versus D-Wave Vesuvius success probability. The data are divided into cohorts requiring different sweep rates for successful adiabatic computation at Schmidt rank 2. We show data for 500 instances of the one-dimensional chain. Problem instances requiring longer sweeps—and so harder according to Fig. 3—are more difficult to solve on the D-Wave Vesuvius machine.

Figure 6

Annealing schedule of the D-Wave Vesuvius device in energy units where $h=1$. The horizontal dashed line corresponds to the operating temperature (18 mK) of the device. The large $A\left(0\right)/T$ value ensures that the initial state is the ground state of the transverse field Hamiltonian. The large $B\left(t_f\right)/T$ value ensures that thermal excitations are suppressed and that the final state reached is stable.

Figure 7

Connectivity of the D-Wave Vesuvius device. Five-hundred three flux qubits are usable. Nine qubits cannot be reliably calibrated and are not usable—these are shown disconnected from the other qubits. The highlighted couplers represent three different implementations of a 100-spin chain. The embeddings are randomly generated in order to average over the physical inhomogeneities of the chip.

Figure 8

Autocorrelation of data. Success probabilities for two halves of the collected data. The agreement between these is sufficient for the studies that we carry out.

Figure 9

Varying sweep time. Comparison between the success probabilities measured at two different values of the total annealing time $T_f$. There is a small reduction in success probability using the longer sweep time.

Figure 10

Embeddable 2-leg ladders. A general two-leg ladder is expected to provide a severe test of adiabatic computability. However, the constraint of embeddability on the Chimera graphs forbids connections on the links shown in light gray. The remaining links—shown in black—lead to problems that are easily solved by the D-Wave Vesuvius device. The ellipse indicates the combination of two spins into a four-level hyperspin over which matrix product states can be constructed.

Figure 11

Success probabilities for the two-leg ladder. Histograms of number of problem instances versus D-Wave success probability for instances of the two-leg ladder. In (a), the data are divided into cohorts requiring different Schmidt rank for successful adiabatic computation. In (b), the data are divided into cohorts requiring different sweep rates for successful computation at Schmidt rank 2. The two-leg ladder is considerably easier for the D-Wave Vesuvius machine to solve than the one-dimensional chain. There is no discernible correlation between success probability and either Schmidt rank or sweep time.