9
$\begingroup$

Quantum Annealing, (related questions Quantum Annealing, or hamiltonian related) is the process used in D-Waves' Quantum Annealer, in which the energy landscapes are explored, for different solutions, and by tuning a suitable Hamiltonian, zero in to a possible optimal solution to a problem. The process of Quantum Annealing reduces "transverse magnetic fields" in the Hamiltonian, in addition to other quantum effects like quantum tunnelling, entanglement, and superposition, which in turn all play a part in zeroing to a "valley" of a quantum mechanical wave function, where the "most likely" solution lies.

The process of Reverse Annealing, very briefly, is to use classical methods such as Simulated Annealing, to find a solution, and hone into a valley using Quantum Annealing. If the Hamiltonian used by the Quantum Annealer is already in a "valley", as it is being passed a solution in the first place -Does the D-Wave machine reach another "valley"( a better solution?) using the Hamiltonian passed to it, in the first place?

$\endgroup$

2 Answers 2

5
$\begingroup$

Until recently, D-Wave's quantum annealing devices always started from a uniform superposition over all $N$ qubits:

                                                $H_{initial} = |+\rangle_0 \otimes |+\rangle_1 ... \otimes |+\rangle_N$

where $|+\rangle_i = \frac{1}{\sqrt{2}} (|0\rangle_i + |1\rangle_i)$.

So let's suppose you already ran a few anneals with this setup and one of the low-energy results looks like a relatively good solution (some local optima) to your optimization problem. Until the very recent introduction of the reverse annealing feature, it was impossible to use this solution as input for the next anneal in order to explore the local space around that solution for bitstrings with even lower energy. Hence, reverse annealing allows us to initialize the quantum annealer with a known (classical) solution and search the state space around this local optima.

When exploring complicated (rugged) energy landscapes of optimization problems you need to balance the global exploration of the state space with the exploitation of local optima. In traditional (D-Wave) quantum annealing, we start with a high transverse field which then gets gradually decreased as you described in your question. D-Wave's quantum annealer was thereby performing a global search (due to a lot of quantum tunneling) at the beginning of the annealing schedule when the transverse field is strong. As the transverse field gets weaker, the search gets more and more local. In contrast, reverse annealing starts with a classical solution defined by the user, then gradually increases the transverse field (backward annealing) to then decrease the transverse field again (forward annealing).

This introduces the new parameter reversal distance which determines how far you want to anneal backward (how strong the transverse field should become). D-Wave published the following two plots in this D-Wave Whitepaper:

reversal distance plots

In the left plot you can see that reversal distance is a very important new hyperparameter since its value determines the probability of obtaining a new ground state (blue region). If the reversal distance is too low, you will get the same state you started with (red region) which would be useless. And of course if you reverse anneal for too long you essentially perform traditional quantum annealing and loose the information that you started with. Remember that too much transverse field means that we are performing global search again!

The right plot shows essentially the same thing by plotting Hamming distance against reversal distance and the probability of obtaining a new ground state. For your problem at hand, you want to find that sweet spot (maxima of the red curve). For large reversal distances we again see that we get solution strings that are far from our initial state in terms of Hamming distance.

All in all, reverse annealing is pretty new stuff and to the best of my knowledge there are no published papers about its effectiveness. In their Whitepaper, D-Wave claims the generation of 'new global optima up to 150 times faster than forward quantum annealing'.

$\endgroup$
2
$\begingroup$

A couple papers are out there on algorithms which can be constructed using reverse annealing, http://iopscience.iop.org/article/10.1088/1367-2630/aa59c4/meta and https://arxiv.org/abs/1609.05875 (it is worth pointing out previous somewhat related closed system work: https://link.springer.com/article/10.1007/s11128-010-0168-z). As far as experimental results, I think the only ones publicly visible at the time of writing are the white paper given in the previous post. However, there will be some new work presented at AQC 2018 (https://ti.arc.nasa.gov/events/aqc-18/) in late June and these talks are usually put online a few months after the conference.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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