This paper examines both a quantum, and highly related quantum inspired algorithm based on an instantaneous quantum quench. Since this algorithm uses a transverse field (single bit flip) driver, the quantum algorithm may be regarded as a continuous time quantum walk on a hypercube, with a phase related to the energy for each corner of the hypercube. The classical algorithm is a `de-quantized’ version of the quantum algorithm. Importantly this paper does not focus on finding the single most optimal solution to an optimisation problem, but rather good (or at least `pretty good’) solutions, and provides rigorous bounds for the performance of the classical algorithm on the solution quality, in addition to valuable insights into the quantum algorithms including plausible conjecture for a similar bound.

The fact that this paper focuses on approximate optimisation which can be done using individual rapid quenches, rather than algorithms with long runtimes which find the absolutely most optimal solution, makes it different and more relevant to practical computing than much of the work which has been done so far, which has a strong focus on the adiabatic limit (see for example [1,2,3,4,5]). The reason that this work has more relevance to practical computing stems from the runtime of the algorithm. In this paper the author considers runtimes which scale, at worst, polynomially with the size of the problem, but most analysis is done for constant runtime. On the other hand, unless P=NP, the runtime for an algorithm which succeeds almost always (such as an adiabatic algorithm) $must$ have an exponentially long runtime. Since the system is expected to remain coherent throughout the runtime, an adiabatic algorithm has much more stringent hardware requirements (exponentially scaling coherence time), whereas the quantum algorithm proposed here has more achievable requirements (polynomial or constant coherence time).

While rapid quenches are less studied than the adiabatic limit, there has been some work done in this direction. An example of such work is [6], which showed numerically that multiple rapid quenches can be superior to a single long quench at solving optimisation problems. However, the work presented here has several important differences, for one it considers instantaneous quenches, for which the adiabatic principle cannot be applied (and therefore another explanation must be found for how the algorithm solves problems as discussed in the next paragraph), and secondly, it is an analytical study, whereas to the best of my knowledge all other studies of rapid quenches to date have been numerical.

As the paper states, the mechanism by which the quantum quenches considered in this paper obtains approximate solutions is a consequence of energy conservation. Since the total energy is the sum of the expectation value of the driver and problem Hamiltonian, and the initial state of the driver Hamiltonian is its ground state, the expectation value of the problem Hamiltonian must decrease with time evolution. This mechanism was independently realized and discussed in [7], which was a numerical study of the same algorithm including studies on very similar problems. The papers appeared on the ar$\chi$iv within weeks of each other and the numerical analysis in [7] and this paper nicely complement each other. Because of the similar subject matter of these two works, I highlight where they complement each other in the next paragraph.

It is first worth highlighting the difference between the two works, beyond the obvious observation that this work is theoretical and [7] is numerical. These studies consider slightly different problems, the MAX-K-LIN-2 problem considered in this paper only allows $\{-1,0,1\}$ couplings and restricts the degree of each variable to be $D$, whereas the Sherrington-Kirkpatrick spin glass considered in [7] allows (two body) coupling between all nodes, with real valued couplings. Secondly, while this paper focuses on approximation, [7] focuses on finding the exact solution to an optimisation problems by statistically sampling over repeated runs. In both studies however suggest that continuous time quantum walks perform substantially better than random guessing, and in the case of [7] better than unstructured Grover like search. Furthermore, both studies find that performance of the quantum algorithm depends on the structure of the problem. The constants in the conjectured bound for the quantum algorithm can depend strongly (exponentially) on $K$, this fact is likely related to difference in behaviour between correlated and uncorrelated energy landscapes found in [7]. Highly uncorrelated energy landscapes, such as unstructured search, require high order terms (and hence correspond to large $K$), [7] found that the rapid quench algorithm was not effective on this kind of problem, consistent with the exponential vanishing of terms with increasing $K$.

This paper makes a large step in the right direction for understanding realistic continuous time quantum algorithms which will, by necessity, be far from the adiabatic limit, and therefore require novel theory to understand, and also provides an interesting quantum inspired algorithm. While this paper is a step in the right direction there is still much to be done to understand this regime, in particular, as the author suggests in the conclusion, understanding non-adiabatic, but non-instantaneous, quenches.

► BibTeX data

► References

Cited by

This View is published in Quantum Views under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.