Skip to content

Beyond quadratic speedups in exact combinatorial optimization

Overview

The discovery of Grover's algorithm [1] (later generalized to amplitude amplification) has long been the source of enthusiasm that quantum algorithms can be advantageous for combinatorial optimization, as it leads to quadratic asymptotic speedups for many concrete end-to-end search problems in this area. However, resource estimates indicate that early and intermediate-term fault-tolerant devices will fail to deliver practical advantages when the available speedup is only quadratic, due to intrinsic overheads of quantum computation compared to classical computation (see, e.g., [2, 3]). Thus, identifying whether beyond-quadratic speedups are available is of principal importance for identifying end-to-end practical advantages in combinatorial optimization. Despite the fact that Grover's algorithm is optimal in the black-box (unstructured) setting, superquadratic speedups could be possible when the combinatorial optimization problem has a certain structure that can be better exploited by a quantum algorithm than a classical algorithm.

Unfortunately, many proposals that could conceivably deliver superquadratic speedups lack rigorous theoretical performance guarantees. This includes the quantum adiabatic algorithm and variational quantum algorithms such as the quantum approximate optimization algorithm (QAOA) [4], which is typically formulated to give approximate solutions, but at higher cost could also be used to find exact solutions. Limited analytic and numerical work provides some evidence (e.g. [5, 6]) that QAOA could outperform a vanilla application of Grover's algorithm to the \(k\)-\(\mathsf{SAT}\) problem, but provides no definitive conclusion on the matter. Alternatively, a line of work in [7, 8] studies a different algorithm (related in certain aspects to the quantum adiabatic algorithm) and provide rigorous running time guarantees that slightly surpass Grover's algorithm.

However, while these algorithms may have a speedup over Grover's algorithm, this does not entail a superquadratic speedup over the best classical algorithm, which can often exploit structure in other ways to do much better than exhaustive search. Overall, it remains a wide open question whether quantum algorithms can provide superquadratic speedups for useful problems in exact combinatorial optimization.

Actual end-to-end problem(s) solved

Combinatorial optimization problems ask to find which solution is optimal among a finite set of possible candidates. Here, we stick to binary optimization on \(n\) bits, where the universe of possible candidates are bit strings \(z = (z_1,z_2,\ldots,z_n) \in \{1,-1\}^n\). The input to the problem is a compact description of some cost function \(C: \{1,-1\}^n \rightarrow \mathbb{R}\), and the desired output is the string \(z^*\) for which \(C\) is minimized. Let \(E^* = C(z^*)\) denote the optimal value of the cost function. For simplicity we assume \(z^*\) is unique and \(E^*\) is known ahead of time.1

Concrete examples can be formed by choosing the function \(C(z)\) to be a low-degree polynomial in the bits of \(z\). For example, if \(C\) is a degree-2 polynomial in \(z\), this is a Quadratic Unconstrained Binary Optimization (\(\mathsf{QUBO}\)) problem. If furthermore every term of \(C\) has degree exactly 2 (no degree-1 or constant terms) and every coefficient is either \(0\) or \(1\), then the problem is equivalent to a \(\mathsf{MAX}\)-\(\mathsf{CUT}\)problem. Finally, if \(C\) is the sum of terms of the form

\[\begin{equation} z_az_bz_c + z_az_b+z_az_c +z_bz_c + z_a+z_b+z_c \qquad \text{where}\qquad z_a,z_b,z_c \in \{z_1,-z_1,z_2,-z_2,\ldots,z_n,-z_n\} \end{equation}\]

then the problem is equivalent to a \(\mathsf{MAX}\)-3-\(\mathsf{SAT}\) instance, where the optimal solution represents the bit string that satisfies the most clauses of a satisfiability formula written in conjunctive normal form, where each clause involves three variables (this is easily generalized from \(\mathsf{MAX}\)-3-\(\mathsf{SAT}\) to \(\mathsf{MAX}\)-\(k\)-\(\mathsf{SAT}\)).

For a fixed instance \(C\), the quantum algorithms must find \(z^*\) with high probability over measurement outcomes. If it does so for every \(C\) chosen from some class of problem, we say it succeeds in the worst case. Alternatively, we can consider ensembles of instances chosen from some class of problem; if for a large fraction of instances from the ensemble, the algorithm finds \(z^*\) with high probability, then we say the algorithm succeeds in the average case.2 A commonly considered average-case ensemble is the Sherrington–Kirkpatrick (SK) model [9], defined as

\[\begin{equation} C(z) = \sum_{i=1}^n\sum_{j=i+1}^n J_{ij} z_i z_j \quad \text{where}\quad J_{ij} \sim \mathcal{N}(0,1), \end{equation}\]

where the coefficients \(J_{ij}\) are drawn randomly from a standard Gaussian distribution \(\mathcal{N}(0,1)\). The SK model is relevant in spin-glass theory, and can be generalized to higher-degree interactions, where it is referred to as the \(p\)-spin model [10]. Another ensemble is the random \(\mathsf{MAX}\)-\(k\)-\(\mathsf{SAT}\) ensemble, where \(\mathsf{MAX}\)-\(k\)-\(\mathsf{SAT}\) instances are generated by choosing each clause uniformly at random with some fixed clause-to-variable ratio (see, e.g., [11]).

Dominant resource cost/complexity

A vanilla application of Grover's algorithm to binary optimization problems achieves \(\mathcal{O}^*(2^{0.5n})\) running time, where notation \(\mathcal{O}^*(2^{an})\) is shorthand for \(\mathrm{poly}(n)2^{an}\). We cover three approaches to solving binary optimization problems on a quantum computer that have some potential to improve upon this running time. Note that all of these algorithms require polynomial (in fact, linear \(\mathcal{O}\left( n \right)\)) space. However, their running time is expected to scale exponentially in \(n\).

  • First, we consider variational quantum algorithms, using the QAOA [4] as a representative. These algorithms are typically studied as efficient (polynomial-time) quantum algorithms that produce approximate solutions, i.e. strings \(z \neq z^*\) for which \(C(z)\) is small, but not optimal. However, they may also be viewed as exact algorithms, since, if repeated a sufficient number of times, they eventually produce the exactly optimal \(z^*\). The QAOA fixes a depth parameter \(p\) and variational parameters \(\gamma = (\gamma_1,\ldots,\gamma_p)\) and \(\beta = (\beta_1,\ldots,\beta_p)\) (sometimes these are set to some fixed instance-independent value, and sometimes they are variationally updated on subsequent repetitions of the algorithm). The QAOA starts in the \(n\)-qubit equal superposition state \(\ket{+}\) and implements alternating rounds of rotations about the diagonal cost function \(C\) and a "mixing" operator \(X = \sum_i X_i\), where \(X_i\) denotes the Pauli-\(X\) gate about qubit \(i\). The state produced by QAOA is thus given by
    \[\begin{equation} \ket{\psi_{\gamma,\beta}} = e^{-i\beta_p X}e^{-i\gamma_p C}\ldots e^{-i\beta_2 X}e^{-i\gamma_2 C}e^{-i\beta_1X}e^{-i\gamma_1 C}\ket{+}\,. \end{equation}\]

    If one makes a computational basis measurement of \(\ket{\psi_{\gamma,\beta}}\), one obtains \(z^*\) with probability \(|\braket{z^*}{\psi_{\gamma,\beta}}|^2\). The expected number of repetitions required to obtain \(z^*\) is the inverse of this probability, and this running time can be quadratically sped up by performing amplitude amplification on top of the QAOA protocol; thus, the QAOA unitary is applied \(\mathcal{O}\left( |\braket{z^*}{\psi_{\gamma,\beta}}|^{-1} \right)\) times. Implementing the QAOA unitary typically requires only \(p \cdot \mathrm{poly}(n)\) gates, as each of the rotations about \(X\) and \(C\) are efficient to implement. For hard combinatorial optimization problems such as typical \(\mathsf{MAX}\)-\(k\)-\(\mathsf{SAT}\) instances, the expectation is that the total running time required will be exponential. If the depth \(p\) is chosen to be constant or even \(\mathrm{poly}(n)\), the dominant cost will come from the \(\mathcal{O}\left( |\braket{z^*}{\psi_{\gamma,\beta}}|^{-1} \right)\) repetitions required to amplify the \(\ket{z^*}\) state. Alternatively, one can reduce the number of repetitions needed to \(\mathcal{O}\left( 1 \right)\) at the expense of taking \(p\) to be very large (at least exponentially large in \(n\)); indeed, for sufficiently large \(p\), the QAOA can be viewed as a Trotterized simulation of the adiabatic algorithm [4]. There is some analytic evidence that the QAOA may outperform Grover's algorithm at finding the exact solution for constant \(p\) in certain cases. Reference [5] studied the QAOA applied to hard (i.e. near the satisfiability threshold) \(k\)-\(\mathsf{SAT}\) instances with instance-independent choice of \(\gamma\), \(\beta\) for constant \(p\), and developed an analytic formula for the expected success probability \(|\braket{z^*}{\psi_{\gamma,\beta}}|^2\) averaged over random instance in the limit \(n \rightarrow \infty\). This formula was evaluated numerically and suggested for example that the average success probability behaves as \(2^{-0.33n}\) for \(p=10\) on \(8\)-\(\mathsf{SAT}\). One might be tempted to declare that this implies an overall average running time of \(\mathcal{O}^*(2^{0.33n/2})\), substantially better than Grover, but such a conclusion is not analytically supported as the average of the inverse probability can be much larger than the inverse of the average probability. Nevertheless, it provides intriguing evidence in favor of such a conclusion. Further numerical evidence that QAOA may be effective as an exact algorithm was provided in [6], which numerically assessed the performance of QAOA on instances of the Low Autocorrelation Binary Sequences (LABS) problem up to \(n=40\), although compared to the best classical heuristic solver, the advantage appeared to be subquadratic. - Second, we consider the quantum adiabatic algorithm [12, 13]. The standard approach, as applied to binary optimization problems, is to start in the state \(\ket{+}\) and evolve by a Hamiltonian that interpolates along a path \(H(s)\) parameterized by \(s \in [0,1]\), given by

    \[\begin{equation} \label{eq:adiabatic_interpolation} H(s) = (1-s)(-X) + s C\,. \end{equation}\]

    It is important to note that the ground state of \(H(0)\) is \(\ket{+}\) and the ground state of \(H(1)\) is \(\ket{z^*}\). This evolution can be simulated on a fault-tolerant gate-based quantum computer using Hamiltonian simulation, and its running time is dominated by the inverse of the minimum spectral gap \(\Delta_{\min}\) of \(H(s)\). That is, the gate complexity to run the algorithm and produce \(\ket{z^*}\) scales as at least \(\Delta_{\min}^{-1}\) and possibly a larger power of \(\Delta_{\min}^{-1}\). Much numerical work has been done on the performance of the adiabatic algorithm on small instances of combinatorial optimization problems, but it generally lacks analytical guarantees. The expectation is that \(\Delta_{\min}\) will be exponentially small [14, 15, 16] in \(n\) (or worse, see, e.g., [17, 18]), meaning the running time of the algorithm is exponentially large, but it remains possible that it surpasses the \(\mathcal{O}^*(2^{0.5n})\) running time of Grover's algorithm in some cases, and could in principle deliver a superquadratic speedup. - Third, we consider the short-path algorithm studied in [7, 19, 20] and a dual version of the algorithm studied in [8]. The goal of these algorithms was to be able to provide a rigorous guarantee that the algorithm can find \(z^*\) in time \(2^{(0.5-c)n}\) for some value of \(c>0\). Similar to the adiabatic algorithm, the short-path algorithm also considers a single-parameter family of Hamiltonians

    \[\begin{equation} H(s) = (1-s) f_X\left(-\frac{X}{n}\right) + s f_Z\left(\frac{C}{|E^*|}\right)\label{eq:short_path} \end{equation}\]

    where \(f_X, f_Z: \mathbb{R} \rightarrow \mathbb{R}\) are monotonic filter functions, and each term \(X/n\) and \(C/|E^*|\) are normalized to have minimum value \(-1\). The idea of the short-path algorithm is to, rather than evolve smoothly from \(s=0\) to \(s=1\), perform a pair of discrete "jumps." The first jump goes from the ground state \(\ket{+}\) at \(s=0\) to the ground state \(\ket{\psi_b}\) of an intermediate point with \(s=b\). The second jump goes from \(\ket{\psi_b}\) to the ground state \(\ket{z^*}\) at \(s=1\). The jumps are accomplished with quantum phase estimation (or more advanced versions utilizing the quantum singular value transformation) of the Hamiltonian \(H_b\) combined with amplitude amplification. The running time of the algorithm is [8, Theorem 1]

    \[\begin{equation} \label{eq:short_path_runtime} \mathrm{poly}(n) \cdot \frac{1}{\Delta} \cdot \left(\frac{1}{|\braket{+}{\psi_b}|} + \frac{1}{|\braket{\psi_b}{z^*}|}\right)\,, \end{equation}\]

    where \(\Delta\) is the spectral gap of the Hamiltonian \(H(b)\). The \(\Delta^{-1}\) factor comes from the need to perform phase estimation at \(\mathcal{O}\left( \Delta \right)\) resolution to successfully prepare \(\ket{\psi_b}\), and the two additive inverse overlap terms represent the number of rounds of amplitude amplification for the first and second jumps, respectively. In [7], filter functions \(f_X(x) = x^K\) for odd integers \(K\) (e.g. \(K=3\)) and \(f_Z(x) = x\) were chosen, and \(b\) was chosen close to 1, such that the first term of Eq. \(\eqref{eq:short_path}\) could be viewed as a small perturbation of the second term. If \(C\) is an instance of \(\mathsf{MAX}\)-\(\mathsf{E}k\)-\(\mathsf{LIN2}\), i.e. if it is a polynomial for which all monomials are degree exactly \(k\), then it was shown that certain conditions on the spectral density of \(C\) near the optimal cost value imply sufficient analytic control of \(\Delta\) and the other parameters in Eq. \(\eqref{eq:short_path_runtime}\) such that the algorithm runs in time \(\mathcal{O}^*(2^{(0.5-c)n})\) for \(c > 0\). However, it remained unclear when these conditions were met. Inspired by [7], [8] proposed using the filter functions \(f_X(x) = x\) and \(f_Z(x) = \min(0,(x+1-\eta)/\eta)\) for a fixed choice of \(\eta \in [0,1]\), and chose a value of \(s\) close to 0 (rather than close to 1). In this sense, the algorithm in [8] is dual to that of [7]. These modifications allowed additional statements to be proved. For example, it was unconditionally shown that the algorithm solves \(k\)-\(\mathsf{SAT}\) (whether or not a formula has a fully satisfiable solution) in time \(\mathcal{O}^*(2^{(0.5-c)n})\) for a (small) constant \(c > 0\), and that the same is true for typical instances of the SK model and its higher-body generalization (\(p\)-spin model), a polynomial speedup over Grover's algorithm and superquadratic advantage over classical exhaustive search.

Existing error corrected resource estimates

Reference [21] compiled resource estimates for various primitive tasks related to combinatorial optimization. For example, it estimated that for an \(n=512\) instance of the SK model, implementing a single QAOA step \(e^{-i\beta_j X}e^{-i\gamma_j C}\) would require \(577\) logical qubits and \(5.0 \times 10^5\) Toffoli gates. A similar estimate would hold for performing a single step of adiabatic evolution with a first-order product formula. The total logical estimate for finding \(z^*\) would be the product of the depth of the circuit and any number of repetitions / rounds of amplitude amplification. An error-corrected estimate could then be computed for a specific fault-tolerant architecture. Without knowing the number of repetitions, it is hard to give precise estimates, but a rough attempt was made in [3] for different speedup factors. There, under different possible assumptions on the amount of classical parallelism available, a breakeven point was estimated for different possible polynomial speedups (quadratic, cubic, quartic). It was found that with a quartic speedup, the breakeven point could be reasonable (on the order of seconds to hours) even assuming the availability of classical parallelism.

Caveats

There are several caveats. The most salient one is that for most of the algorithms above, there is no provable beyond-Grover advantage. Meanwhile, in the case of [8], the size of the provable beyond-Grover advantage is miniscule. The prospect of these algorithms is thus left to extrapolations from numerical simulations carried out at very small instance sizes and speculation based on physical principles.

A second important caveat is that to deliver practical superquadratic speedups, the performance of the quantum algorithm needs to be compared to the best classical algorithm, which is often substantially better than the \(\mathcal{O}^*(2^n)\) running time of exhaustive enumeration. For example, \(3\)-\(\mathsf{SAT}\) problems are classically solvable in \(\mathcal{O}^*(2^{0.39n})\) time [22].

Along these lines, a third caveat is the existence of classical "Quantum Monte Carlo" algorithms (see, e.g., [23, 24, 25, 26, 27]), which can, under certain conditions, classically simulate the quantum algorithms described above. This is because the Hamiltonians in Eqs. \(\eqref{eq:adiabatic_interpolation}\) and \(\eqref{eq:short_path}\) are stoquastic Hamiltonians, defined by the property that their off-diagonal matrix elements are non-positive (when written in the computational basis). Stoquasticity implies that the ground state of the Hamiltonian can be written such that all amplitudes are non-negative real numbers [28], meaning that these Hamiltonians avoid the so-called "sign problem" enabling the potential application of Quantum Monte Carlo techniques. To be clear, it remains possible that quantum algorithms for these combinatorial optimization problems involving stoquastic Hamiltonians can evade classical simulation—indeed, superpolynomial oracle separations have been shown between classical computation and adiabatic quantum computation restricted to stoquastic paths [29, 30]—but it is something to keep in mind when designing algorithms based on stoquastic Hamiltonians.

A final caveat is that the quantum algorithms described here are typically not amenable to parallelization, although in principle QAOA could be parallelized if one opts not to use amplitude amplification (resulting in worse asymptotic complexity). This lies in stark contrast to many classical optimization algorithms for exact combinatorial optimization which are highly parallelizable, a feature that can be exploited to significantly reduce the runtime of these classical algorithms on high-performance computers, making achieving practical quantum advantage more difficult [3].

Comparable classical complexity and challenging instance sizes

For many binary optimization problems, there exist classical algorithms that exploit the structure of the problem to perform significantly better than exhaustive search. For example, the best 3-\(\mathsf{SAT}\) algorithm runs in time \(\mathcal{O}^*(2^{0.39n})\) and in general \(k\)-\(\mathsf{SAT}\) can be solved in time \(2^{(1-\Omega(1/k))n}\) [22]. This running time suggests the solution will be impractical once \(n\) is on the order of 100. The algorithm analyzed in [22] is designed for the worst case, and is likely not the best practical algorithm for typical instances. For random instances, the hardness of \(k\)-\(\mathsf{SAT}\) depends sensitively on the clause-to-variable ratio \(\alpha\). Remarkably, heuristic algorithms can succeed at finding a satisfiable solution for typical instances with thousands or even tens of thousands of variables even very close to the satisfiability threshold \(\alpha_c\) where most instances become unsatisfiable (e.g., [31]). However, these algorithms are expected to fail sufficiently close to the satisfiability threshold and in the worst case.

Similarly, the SK model admits a classical branch-and-bound algorithm guaranteed to run in time \(2^{0.45n}\) (for a large fraction of instances) and likely better than that in practice [32]. However, once the interaction degree becomes larger than 2, the problem becomes significantly harder. The branch-and-bound algorithm is not known to generalize to the \(p\)-spin model, and for \(p \geq 3\) there is no known classical algorithm that provably achieves \(2^{(1-c)n}\) for any constant \(c\) (although it has not garnered much attention, see [8]). Similarly, in contrast to \(k\)-\(\mathsf{SAT}\), the \(\mathsf{MAX}\)-\(k\)-\(\mathsf{SAT}\) problem (i.e. the version of the problem that asks for the optimal assignment even if it does not satisfy all the clauses) only has a \(\mathcal{O}^*(2^{(1-c)n})\) time algorithm for \(k=2\), and, notably, this algorithm requires exponential space [33].

Speedup

As there are generally no rigorous running time guarantees for the quantum algorithms, the speedup cannot be estimated. However, it is worth emphasizing that for hard combinatorial optimization problems, the speedup could be superquadratic, but it is not expected to be superpolynomial.

The rigorous results of [8] establish a beyond-Grover running time, but the only case in which the speedup is beyond quadratic when compared with the best known classical algorithm is the \(p\)-spin model with \(p \geq 3\) (here, the comparison benefits from little work on classical algorithms for the problem).

NISQ implementation

The QAOA approach is amenable to NISQ implementation (assuming one opts not to apply amplitude amplification on top of it), since the quantum circuit one needs to implement is fairly shallow depth. In this case, the effect of uncorrected errors in the NISQ device may degrade the performance (and require more repetitions to extract the optimal bit string \(z^*\)). Similarly, on a NISQ quantum annealer [34, 13], one could run a noisy version of the quantum adiabatic algorithm and repeat until finding the optimal bit string \(z^*\).

Outlook

For quantum computers to be impactful for exact combinatorial optimization, one of two things must occur: (1) great advancements to the expected underlying clock speeds of quantum hardware and the overheads of fault-tolerant quantum computing, or (2) the development of quantum algorithms that go significantly beyond the quadratic speedup provided by Grover's algorithm. On the one hand, ideas have been proposed that could potentially deliver such a speedup, but on the other hand, in all cases there are no provable guarantees, or the provable guarantees are very small. Much more attention must be devoted to studying these quantum algorithms and developing new ones if we are to leverage them into actual practical advantages, especially given the extensive amount of work developing sophisticated classical algorithms for these problems.

Bibliography

  1. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing (STOC), 212–219. 1996. arXiv: https://arxiv.org/abs/quant-ph/9605043. doi:10.1145/237814.237866.

  2. Earl Campbell, Ankur Khurana, and Ashley Montanaro. Applying quantum algorithms to constraint satisfaction problems. Quantum, 3:167, 2019. arXiv: https://arxiv.org/abs/1810.05582. doi:10.22331/q-2019-07-18-167.

  3. Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum, 2(1):010103, 3 2021. arXiv: https://arxiv.org/abs/2011.04149. doi:10.1103/PRXQuantum.2.010103.

  4. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv: https://arxiv.org/abs/1411.4028, 2014.

  5. Sami Boulebnane and Ashley Montanaro. Solving boolean satisfiability problems with the quantum approximate optimization algorithm. arXiv: https://arxiv.org/abs/2208.06909, 2022.

  6. Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, and Marco Pistoia. Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. arXiv: https://arxiv.org/abs/2308.02342, 2023.

  7. M. B. Hastings. A short path quantum algorithm for exact optimization. Quantum, 2:78, 7 2018. arXiv: https://arxiv.org/abs/1802.10124. URL: https://doi.org/10.22331/q-2018-07-26-78, doi:10.22331/q-2018-07-26-78.

  8. Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão. Mind the gap: achieving a super-grover quantum speedup by jumping to the end. In Proceedings of the 55th ACM Symposium on the Theory of Computing (STOC), 1131–1144. New York, NY, USA, 2023. Association for Computing Machinery. arXiv: https://arxiv.org/abs/2212.01513. URL: https://doi.org/10.1145/3564246.3585203, doi:10.1145/3564246.3585203.

  9. David Sherrington and Scott Kirkpatrick. Solvable model of a spin-glass. Physical Review Letters, 35(26):1792, 1975. doi:10.1103/PhysRevLett.35.1792.

  10. B. Derrida. Random-energy model: limit of a family of disordered models. Physical Review Letters, 45:79–82, 7 1980. URL: https://link.aps.org/doi/10.1103/PhysRevLett.45.79, doi:10.1103/PhysRevLett.45.79.

  11. Don Coppersmith, David Gamarnik, MohammadTaghi Hajiaghayi, and Gregory B. Sorkin. Random max sat, random max cut, and their phase transitions. Random Structures & Algorithms, 24(4):502–545, 2004. Earlier version in *SODA'03*, arXiv: https://arxiv.org/abs/math/0306047. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20015, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20015, doi:10.1002/rsa.20015.

  12. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv: https://arxiv.org/abs/quant-ph/0001106, 2000.

  13. Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90:015002, 1 2018. arXiv: https://arxiv.org/abs/1611.04471. doi:10.1103/RevModPhys.90.015002.

  14. Sergey Knysh and Vadim Smelyanskiy. On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm. arXiv: https://arxiv.org/abs/1005.3011, 2010. doi:10.48550/arXiv.1005.3011.

  15. A. P. Young, S. Knysh, and V. N. Smelyanskiy. First-order phase transition in the quantum adiabatic algorithm. Physical Review Letters, 104:020502, 1 2010. arXiv: https://arxiv.org/abs/0910.1378. URL: https://link.aps.org/doi/10.1103/PhysRevLett.104.020502, doi:10.1103/PhysRevLett.104.020502.

  16. Itay Hen and A. P. Young. Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. Physical Review E, 84:061152, 2011. arXiv: https://arxiv.org/abs/1109.6872. URL: https://link.aps.org/doi/10.1103/PhysRevE.84.061152, doi:10.1103/PhysRevE.84.061152.

  17. Boris Altshuler, Hari Krovi, and Jérémie Roland. Anderson localization makes adiabatic quantum optimization fail. Proceedings of the National Academy of Sciences, 107:12446–12450, 2010. arXiv: https://arxiv.org/abs/0912.0746. doi:10.1073/pnas.1002116107.

  18. Dave Wecker, Matthew B. Hastings, and Matthias Troyer. Training a quantum optimizer. Physical Review A, 94:022309, 2016. arXiv: https://arxiv.org/abs/1605.05370. doi:10.1103/PhysRevA.94.022309.

  19. Matthew B Hastings. Weaker assumptions for the short path optimization algorithm. arXiv: https://arxiv.org/abs/1807.03758, 2018. doi:10.48550/arXiv.1807.03758.

  20. M. B. Hastings. The short path algorithm applied to a toy model. Quantum, 3:145, 5 2019. arXiv: https://arxiv.org/abs/1901.03884. URL: https://doi.org/10.22331/q-2019-05-20-145, doi:10.22331/q-2019-05-20-145.

  21. Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush. Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum, 1(2):020312, 11 2020. arXiv: https://arxiv.org/abs/2007.07391. doi:10.1103/PRXQuantum.1.020312.

  22. Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick. Faster \(k\)-sat algorithms using biased-ppsz. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 578–589. New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3313276.3316359.

  23. Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B Meyer, and Peter Shor. Quantum adiabatic algorithms, small gaps, and different paths. Quantum Information and Computation, 2009. arXiv: https://arxiv.org/abs/0909.4766. doi:10.26421/QIC11.3-4-1.

  24. Sergey Bravyi. Monte carlo simulation of stoquastic hamiltonians. Quantum Information and Computation, 15:1122–1140, 2015. arXiv: https://arxiv.org/abs/1402.2295. doi:10.26421/QIC15.13-14-3.

  25. Michael Jarret, Stephen P. Jordan, and Brad Lackey. Adiabatic optimization versus diffusion monte carlo methods. Physical Review A, 94:042318, 10 2016. arXiv: https://arxiv.org/abs/1607.03389. URL: https://link.aps.org/doi/10.1103/PhysRevA.94.042318, doi:10.1103/PhysRevA.94.042318.

  26. Elizabeth Crosson and Aram W. Harrow. Simulated quantum annealing can be exponentially faster than classical simulated annealing. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), volume, 714–723. 2016. arXiv: https://arxiv.org/abs/1601.03030. doi:10.1109/FOCS.2016.81.

  27. Elizabeth Crosson and Samuel Slezak. Classical simulation of high temperature quantum ising models. arXiv: https://arxiv.org/abs/2002.02232, 2020. doi:10.48550/arXiv.2002.02232.

  28. Sergey Bravyi and Barbara Terhal. Complexity of stoquastic frustration-free hamiltonians. SIAM Journal on Computing, 39(4):1462–1485, 2010. arXiv: https://arxiv.org/abs/0806.1746. doi:10.1137/08072689X.

  29. Matthew B. Hastings. The power of adiabatic quantum computation with no sign problem. arXiv: https://arxiv.org/abs/2005.03791, 2020.

  30. András Gilyén, Matthew B. Hastings, and Umesh Vazirani. (sub)exponential advantage of adiabatic quantum computation with no sign problem. In Proceedings of the 53rd ACM Symposium on the Theory of Computing (STOC), STOC 2021, 1357–1369. New York, NY, USA, 2021. Association for Computing Machinery. arXiv: https://arxiv.org/abs/2011.09495. URL: https://doi.org/10.1145/3406325.3451060, doi:10.1145/3406325.3451060.

  31. Raffaele Marino, Giorgio Parisi, and Federico Ricci-Tersenghi. The backtracking survey propagation algorithm for solving random k-sat problems. Nature Communications, 7(1):12996, 2016. arXiv: https://arxiv.org/abs/1508.05117. doi:10.1038/ncomms12996.

  32. Ashley Montanaro. Quantum speedup of branch-and-bound algorithms. Physical Review Research, 2(1):013056, 2020. arXiv: https://arxiv.org/abs/1906.10375. doi:10.1103/PhysRevResearch.2.013056.

  33. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2):357–365, 2005. Earlier version in ICALP'04. URL: https://www.sciencedirect.com/science/article/pii/S0304397505005438, doi:10.1016/j.tcs.2005.09.023.

  34. Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Physical Review E, 58:5355–5363, 11 1998. arXiv: https://arxiv.org/abs/cond-mat/9804280. URL: https://link.aps.org/doi/10.1103/PhysRevE.58.5355, doi:10.1103/PhysRevE.58.5355.

  1. This assumption can often be relaxed at the expense of at most \(\mathrm{poly}(n)\) overhead, e.g., by iterating over all possible values \(E^*\) might take, which fall within a \(\mathrm{poly}(n)\) size range when the cost function consists of only \(\mathrm{poly}(n)\) constant size (integer) terms. ↩

  2. A more typical definition of the average-case complexity of an algorithm is the expected runtime required for it to find the solution \(z^*\), averaged over both choice of instance and internal algorithmic randomness (i.e., classical coin flips or quantum measurement outcomes). This definition is related to the convention we follow, but it is more coarse grained as it does not distinguish between the two types of randomness, the latter of which can be boosted by repetition. ↩