18
$\begingroup$

Many people are interested in the subject of quantum annealing, as an application of quantum technologies, not least because of D-WAVE's work on the subject. The Wikipedia article on quantum annealing implies that if one performs the 'annealing' slowly enough, one realises (a specific form of) adiabatic quantum computation. Quantum annealing seems to differ mostly in that it does not seem to presuppose doing evolution in the adiabatic regime — it allows for the possibility of diabatic transitions.

Still, there seems to be more intuition at play with quantum annealing than just "adiabatic computation done hastily". It seems that one specifically chooses an initial Hamiltonian consisting of a transverse field, and that this is specifically meant to allow for tunnelling effects in the energy landscape (as described in the standard basis, one presumes). This is said to be analogous to (possibly even to formally generalise?) the temperature in classical simulated annealing. This raises the question of whether quantum annealing pre-supposes features such as specifically an initial transverse field, linear interpolation between Hamiltonians, and so forth; and whether these conditions may be fixed in order to be able to make precise comparisons with classical annealing.

  • Is there a more-or-less formal notion of what quantum annealing consists of, which would allow one to point to something and say "this is quantum annealing" or "this is not precisely quantum annealing because [it involves some additional feature or lacks some essential feature]"?
  • Alternatively: can quantum annealing be described in reference to some canonical framework — possibly in reference to one of the originating papers, such as Phys. Rev. E 58 (5355), 1998 [freely available PDF here] — together with some typical variations which are accepted as also being examples of quantum annealing?

  • Is there at least a description which is precise enough that we can say that quantum annealing properly generalises classical simulated annealing, not by "working better in practise", or "working better under conditions X, Y, and Z", but in the specific sense in that any classical simulated annealing procedure can be efficiently simulated or provably surpassed by a noiseless quantum annealing procedure (just as unitary circuits can simulate randomised algorithms)?

$\endgroup$
6
$\begingroup$

I'll do my best to address your three points.

My previous answer to an earlier question about the difference between quantum annealing and adiabatic quantum computation can be found here. I'm in agreement with Lidar that quantum annealing can't be defined without considerations of algorithms and hardware.

That being said, the canonical framework for quantum annealing and the inspiration for the D-Wave is the work by Farhi et al. (quant-ph/0001106).

Finally, I'm not sure one can generalize classical simulated annealing using quantum annealing, again without discussing hardware. Here's a thorough comparison: 1304.4595.


Addressing comments:

(1) I saw your previous answer, but don't get the point you make here. It's fine for QA not to be universal, and not to have a provable performance to solve a problem, and for these to be motivated by hardware constraints; but surely quantum annealing is something independent of specific hardware or instances, or else it doesn't make sense to give it a name.

(2) You're linking the AQC paper, together with the excerpt by Vinci and Lidar, strongly suggests that QA is just adiabatic-ish evolution in the not-necessarily-adiabatic regime. Is that essentially correct? Is this true regardless of what the initial and final Hamiltonians are, or what path you trace through Hamiltonian-space, or the parameterisation with respect to time? If there are any extra constraints beyond "possibly somewhat rushed adiabatic-ish computation", what are those constraints, and why are they considered important to the model?

(1+2) Similar to AQC, QA reduces the transverse magnetic field of a Hamiltonian, however, the process is no longer adiabatic and dependent on the qubits and noise levels of the machine. The initial Hamiltonians are called gauges in D-Wave's vernacular and can be simple or complicated as long as you know the ground state. As for the 'parameterization with respect to time,' I think you mean the annealing schedule and as stated above this is restricted hardware constraints.

(3) I also don't see why hardware is necessary to describe the comparison with classical simulated annealing. Feel free to assume that you have perfect hardware with arbitrary connectivity: define quantum annealing as you imagine a mathematician might define annealing, free of niggling details; and consider particular realisations of quantum annealing as attempts to approximate the conditions of that pure model, but involving the compromises an engineer is forced to make on account of having to deal with the real world. Is it not possible to make a comparison?


The only relation classical simulated annealing has with quantum annealing is they both have annealing in the name. The Hamiltonians and process are fundamentally different.

$H_{\rm{classical}} = \sum_{i,j} J_{ij} s_i s_j$

$H_{\rm{quantum}} = A(t) \sum_{i,j} J_{ij} \sigma_i^z \sigma_j^z + B(t) \sum_i \sigma_i^x$

However, if you would like to compare simulated quantum annealing with quantum annealing, Troyer's group at ETH are the pros when it comes to simulated quantum annealing. I highly recommend these slides largely based on the Boxio et al. paper I linked above.

https://www.isi.edu/sites/default/files/top_level/events/aqc2014/day2-talk5-Troyer.pdf

(4) Your remark about the initial Hamiltonian is useful and suggests something very general lurking in the background. Perhaps arbitrary (but efficiently computable, monotone, and first differentiable) schedules are also acceptable in principle, with limitations only arising from architectural constraints, and of course also the aim to obtain a useful outcome?

I'm not sure what you're asking. Are arbitrary schedules useful? I'm not familiar with work on arbitrary annealing schedules. In principle, the field should go from high to low, slow enough to avoid a Landau-Zener transition and fast enough to maintain the quantum effects of qubits.

Related; The latest iteration of the D-Wave can anneal individual qubits at different rates but I'm not aware of any D-Wave unaffiliated studies where this has been implemented.

https://www.dwavesys.com/sites/default/files/14-1002A_B_tr_Boosting_integer_factorization_via_quantum_annealing_offsets.pdf

(5) Perhaps there is less of a difference between the Hamiltonians in QA and CSA than you suggest. $H_{cl}$ is clearly obtained from $H_{qm}$ for $A(t)=1,B(t)=0$ if you impose a restriction to standard basis states (which may be benign if $H_{qm}$ is non-degenerate and diagonal). There's clearly a difference in 'transitions', where QA seems to rely on suggestive intuitions of tunnelling/quasiadiabaticity, but perhaps this can be (or already has been?) made precise by a theoretical comparison of QA to a quantum walk. Is there no work in this direction?

$A(t)=1,B(t)=0$ With this schedule you're no longer annealing anything. The machine is just sitting there at a finite temperature so the only transitions you'll get are thermal ones. This can be slightly useful as shown by Nishimura et al. The following publication talks about the uses of a non-vanishing transverse field.

https://arxiv.org/abs/1605.03303

https://arxiv.org/abs/1708.00236

Regarding the relation of quantum annealing with quantum walks. It's possible to treat quantum annealing in this way as shown by Chancellor.

https://arxiv.org/abs/1606.06800

(6) One respect in which I suppose the hardware may play an important role --- but which you have not explicitly mentioned yet --- is the role of dissipation to a bath, which I now vaguely remember being relevant to DWAVE. Quoting from Boixo et al.: "Unlike adiabatic quantum computing [...] quantum annealing is a positive temperature method involving an open quantum system coupled to a thermal bath." Clearly, what bath coupling one expects in a given system is hardware dependent; but is there no notion of what bath couplings are reasonable to consider for hypothetical annealers?


I don't know enough about the hardware aspects to answer this, but if I had to guess, the lower temperature the better to avoid all the noise-related problems.


You say "In principle the field should go from high to low, slow enough to avoid a Landau-Zener transition and fast enough to maintain the quantum effects of qubits." This is the helpful thing to do, but you usually don't know just how slow that can or should be, do you?

This would be the coherence time of the qubits. The D-Wave annealing schedules are on the order of microseconds with T2 for superconducting qubits being around 100 microseconds. If I had to give a definitive definition of annealing schedule it would be 'an evolution of the transverse field within a length of time less than the decoherence time of the qubit implementation.' This allows for different starting strengths, pauses, and readouts of field strengths. It need not be monotonic.


I thought maybe dissipation to a bath was sometimes considered helpful to how quantum annealers work, when operating in the non-adiabatic regime (as it often will be when working on NP-hard problems, because we're interested in obtaining answers to problems despite the eigenvalue gap possibly being very small). Is dissipation not potentially helpful then?

I consulted with S. Mandra and while he pointed me to a few papers by P. Love and M. Amin, which show that certain baths can speedup quantum annealing and thermalization can help find the ground state faster.

https://arxiv.org/pdf/cond-mat/0609332.pdf


I think that maybe if we can get the confusion about the annealing schedules, and whether or not it the transition has to be along a liner interpolation between two Hamiltonians (as opposed to a more complicated trajectory), ...

$A(t)$ and $B(t)$ don't necessarily have to be linear or even monotonic. In a recent presentation D-Wave showed the advantages of pausing the annealing schedule and backwards anneals.

https://www.dwavesys.com/sites/default/files/mwj_dwave_qubits2018.pdf


Feel free to condense these responses however you'd like. Thanks.

$\endgroup$
  • $\begingroup$ Thanks --- I hope that we might be able to pin down some additional details though. (1) I saw your previous answer, but don't get the point you make here. It's fine for QA not to be universal, and not to have provable performance to solve a problem, and for these to be motivated by hardware constraints; but surely quantum annealing is something independent of specific hardware or instances, or else it doesn't make sense to give it a name. (cont'd) $\endgroup$ – Niel de Beaudrap Apr 4 '18 at 21:17
  • $\begingroup$ (2) Your linking the AQC paper, together with the excerpt by Vinci and Lidar, strongly suggests that QA is just adiabatic-ish evolution in the not-necessarily-adiabatic regime. Is that essentially correct? Is this true regardless of what the initial and final Hamiltonians are, or what path you trace through Hamiltonian-space, or the parameterisation with respect to time? If there are any extra constraints beyond "possibly somewhat rushed adiabatic-ish computation", what are those constraints, and why are they considered important to the model? (cont'd) $\endgroup$ – Niel de Beaudrap Apr 4 '18 at 21:20
  • 1
    $\begingroup$ Haven’t forgotten about this just been super busy. Will try to update tonight. $\endgroup$ – Andrew O Apr 6 '18 at 14:36
  • 1
    $\begingroup$ Sorry for the delay. Added some more info. $\endgroup$ – Andrew O Apr 8 '18 at 21:57
  • 1
    $\begingroup$ Addressed the remaining comments. $\endgroup$ – Andrew O May 16 '18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.