Skip to content

Search algorithms à la Grover

Overview

Grover's search algorithm [1], and its generalizations, such as amplitude amplification, are essential sources of quantum speedups. A straightforward application of Grover search in the spirit of optimization is quantum minimum finding [2] that finds the minimizer of a function on a given set of elements with a quadratic speedup, and its natural generalization analogous to amplitude amplification can be found in [3].

As search is a very generic primitive, Grover's algorithm is extremely widely applicable and it can speed up many subroutines especially in algorithms for combinatorial optimization. In the early days of quantum computing, a plethora of such applications were found, and the list still keeps growing. We list a few such representative applications that demonstrate how Grover's algorithm may be applied to speed up combinatorial optimization.

Actual end-to-end problem(s) solved

The goal is to solve a search problem, i.e., decide whether there is an element among a set of objects that satisfies some criterion, and if there is such an object, find one. Many combinatorial optimization problems are fundamentally search problems; a notable class of examples are graph problems, such as finding a maximal independent set, a \(k\)-coloring, a lowest weight Hamiltonian cycle (called the traveling salesperson problem), or the shortest path between two vertices.

For conceptual clarity, here, we focus on the prototypical Boolean satisfiability problem, i.e., \(\mathsf{SAT}\) solving: given a Boolean formula in the so-called conjunctive normal form, decide whether it has a satisfying Boolean assignment (and if so, find one). A formula in this form consists of some constraints (called clauses) each containing the logical AND of some variables or their negation (called literals). We denote the number of Boolean variables by \(n\), while the total number of literals of the formula by \(\ell\) (counted with multiplicity).

Dominant resource cost/complexity

If there are at least \(m\) marked elements among \(N\) possible ones, then the search problem can be solved with high probability by using \(\mathcal{O}\left( \sqrt{N/m} \right)\) Grover iterations. Each Grover iteration requires generating a uniform superposition over the \(N\) elements starting from the all \(0\) state, and to check whether an element is marked (in superposition), which can be implemented with gate cost \(\mathcal{O}\left( \ell+n \right)\). If the formula is satisfiable then there is at least one solution, thus \(\mathcal{O}\left( \sqrt{2^n} \right)\) Grover iterations suffice, giving an overall complexity of \(\mathcal{O}\left( (\ell+n)\sqrt{2^n} \right)\).

In some applications, it is useful to consider a generalization of Grover search, amplitude amplification, which enables working with an arbitrary prior distribution on the elements, unlike Grover's algorithm which effectively uses a uniform prior. The relevance of this extension can be seen through the example of 3-\(\mathsf{SAT}\), which is a restricted version of \(\mathsf{SAT}\) where each clause has at most 3 literals. A clever application of amplitude amplification described by Ambainis [4] for solving 3-\(\mathsf{SAT}\) more efficiently uses Schöning's algorithm [5] and thus generates a nontrivial prior distribution on the solutions.

The complexity of amplitude amplification is similar to that of Grover's search in general. If \(\ket{\psi}\) is the quantum state representing the prior distribution, so that measuring the state yields a marked element with probability at least \(p\), then \(\mathcal{O}\left( \sqrt{1/p} \right)\) "Grover iterations" suffice to find a marked element with high probability. The algorithm requires preparing the initial state \(\ket{\psi}\) and then each iteration consist of a reflection \(2\ketbra{\psi}{\psi}-I\) around \(\ket{\psi}\) and checking whether an element is marked (in superposition). The former reflection can be implemented with two uses of the circuit that prepares \(\ket{\psi}\) from the all \(0\) state, and a reflection about the all \(0\) state.

Existing error corrected resource estimates

There are several studies on the resource estimation of Grover-type (sub)quadratic speedups. Due to the wide range of these problems, we do not focus on explicit gate counts on any particular problem/implementation variant, but rather list some prominent articles and illustrate their findings on a high level [6, 7, 8, 9, 10, 11]. Unfortunately, these recent studies revealed that quadratic or smaller speedups alone are unlikely to be useful probably even in the medium term, unless the large overheads of fault-tolerant quantum computing schemes can be greatly reduced. For example, [7] concluded that even if there is some reasonable advantage in quantum gate counts for solving the constraint satisfaction problems that they consider, the classical computation supporting the fault-tolerant quantum computation actually annihilates the speedup in practice. They state that "Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. \(\ldots\) However, the number of physical qubits used is extremely large, \(\ldots\) In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques." The most recent of the above quoted papers [11] estimates that getting a quantum advantage via a quadratic speedup requires at least a month-long computation already if each iteration contains at least one floating-point operation. The situation looks more promising for cubic and quartic speedups, but unfortunately such improvements seem to require techniques beyond Grover search.

Caveats

Grover originally described his result as "A fast quantum mechanical algorithm for database search" [1]. If we work in the circuit model of quantum computation, then strictly speaking Grover search gives a slowdown for database search, as every Grover iteration needs to "touch" every element in the database. If we anyway need to touch all \(N\) elements in the database, then the best we can do is to simply go over every element in linear time \(\mathcal{O}\left( N \right)\). Grover's search circuit in this case would have gate complexity \(\widetilde{\mathcal{O}}\left( N^{3/2} \right)\), clearly worse than sequentially going through the entire dataset.

In the database scenario, we can only recover the quadratic speedup if we assume that we can use a quantum random access memory (QRAM), with constant (or logarithmic) cost for each database query. The analogous assumption regarding ordinary RAM is often made in classical computer science, simply because RAM calls are cheap in practice. However, since a RAM call should be able to touch every bit of the database, from a circuit complexity perspective a RAM call must have gate cost at least \(N\). On the other hand, this task can be parallelized very well, so with appropriate hardware it is reasonable to count a RAM call to have (time) complexity \(\log(N)\). While QRAM can also be implemented with a quantum circuit of \(\mathcal{O}\left( \log(N) \right)\) depth, a similar accounting might not be fair in the case of QRAM if error correction is necessary, especially if one implements the entire QRAM circuit in a fault-tolerant fashion.

However, Grover's algorithm can provide a quadratic speedup without extra hardware assumptions when the elements of the list that we search over can be easily generated and checked "on the fly." For example, in the case of \(\mathsf{SAT}\), we search over the \(2^n\) possible truth assignments, yet we can easily check whether an individual assignment is satisfactory by simply substituting the assignment into the formula and evaluating the resulting Boolean expression.

Comparable classical complexity

For the unstructured search problem, exhaustive search is essentially the best that can be done, with a running time \(\sim\ell \cdot 2^n\). Of course, \(\mathsf{SAT}\) seems to be far from unstructured, but under the Strong Exponential-Time Hypothesis [12, 13] the best classical algorithm for \(\mathsf{SAT}\) has running time \(2^{n-o(n)}\).

A similar argument holds for the generalized problem considered in the setting of amplitude amplification: if we have some prior distribution, we can classically find a marked element by sampling from this distribution about \(\sim \frac{1}{p}\) times. Since unstructured search is a special case of this problem, we cannot hope for a better classical algorithm in general.

Speedup

The speedup is quadratic in terms of the number of required iterations if we compare to corresponding naive classical algorithms. It can be shown that this speedup is optimal in the black-box query model [14]. Moreover, we do not expect that there would be a bigger than quadratic speedup in gate complexity [15] in the general (non-black-box) case.

Outlook

We have discussed how Grover search provides a quadratic speedup for \(\mathsf{SAT}\), and how amplitude amplification yields a quadratic speedup for 3-\(\mathsf{SAT}\). Grover's algorithm can be used as a subroutine in several other combinatorial optimization problems as well, e.g., related to graphs. In the literature, these problems are most often studied in the query model, therefore here we also only discuss their speedup in terms of query complexity. Since these are (sub)quadratic speedups, we know that the fault-tolerant resource estimates will be unfavorable anyway, as discussed above.

For example, the problem of finding the shortest paths from a single source \(s\) in graph \(G=(V,E)\) to all other vertices \(v\in V\) can be solved using Dijkstra's algorithm in time \(\mathcal{O}\left( |E|+|V|\log|V| \right)\) if the graph is provided with its adjacency list (and with query complexity \(\mathcal{O}\left( |E| \right)\)), whereas the quantum query complexity of this problem is \(\widetilde{\Theta}(\sqrt{|V||E|})\) [16]. The paper [16] determines the query complexity of several other graph problems such as deciding graph connectivity and strong connectivity as well as finding the minimum-weight spanning tree. For all of these problems, there is a similar moderate (sub)quadratic quantum speedup.

One graph problem that is often mentioned in connection to quantum computation is the (in)famous traveling salesperson problem. However, for this problem, the best provable speedup is only subquadratic. The naive classical problem runs in time \(n!\), and Grover's algorithm offers a quadratic speedup over it. Unfortunately, the best classical algorithm uses dynamic programming and runs in time \(2^n\). Ambainis et al. [17] showed how to obtain a speedup over this algorithm by combining classical precalculation with recursive applications of Grover's search resulting in time complexity \(\widetilde{\mathcal{O}}\left( 1.817^n \right)\) assuming that QRAM calls have unit costs. Considering the overheads coming from the implementation of QRAM and fault tolerance, the traveling salesperson problem seems to be one of the least likely candidates to achieve a practical quantum speedup.

Finally, let us mention quantum walk algorithms, which can also be viewed as a generalization of Grover's search. However, quantum walks are more distant relatives of Grover's search and can only be applied in more specific settings. They can be used for proving many nontrivial speedups in query complexity, however the resulting algorithms are often not practical due to high space and/or gate complexity overheads, as is the case for the prototypical Element Distinctness problem. The query reduction is moderate \(N^2\rightarrow N^{4/3}\) in the number of elements \(N\), but the corresponding quantum algorithm [18] unfortunately uses a QRAM consisting of about \(\sim N^{4/3}\) registers.

There are nevertheless more practical quantum walk algorithms applicable, e.g., to speed up backtracking algorithms [19, 20, 21, 22], which are among the most successful and widely used classical heuristics for solving \(\mathsf{SAT}\) instances in practice. The quantum algorithm can achieve an essentially quadratic speedup compared to its classical backtracking variant. This approach is applicable to the traveling salesperson problem in the special case that the graph has degree at most 4 [23]. For resource estimates see the earlier quoted reference [6]. A further extension of this algorithm is applicable to branch-and-bound algorithms [24, 25], and in some cases yields running times that are substantially better than what we know can be achieved by naively using Grover's algorithm. For example, it can find exact ground states for most instances of the Sherrington–Kirkpatrick model [26] in time \(\mathcal{O}\left( 2^{0.226n} \right)\) [24], which means about a quadratic speedup compared to classical methods. Branch-and-bound-based speedups can also be applied to solve mixed-integer programs, which includes certain formulations of the portfolio optimization problem [25].

There is a plethora of other applications of quantum search speedups, ranging from machine learning [27] to dynamical programming solutions of other NP-hard problems [17], which we do not discuss here for length constraints and due to discouraging resource estimates for (sub)quadratic quantum speedups.

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. Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv: https://arxiv.org/abs/quant-ph/9607014, 1996.

  3. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum sdp-solvers: better upper and lower bounds. Quantum, 4:230, 2020. Earlier version in FOCS'17. arXiv: https://arxiv.org/abs/1705.01843. doi:10.22331/q-2020-02-14-230.

  4. A. Ambainis. Quantum search algorithms. SIGACT News, 35(2):22–35, 6 2004. arXiv: https://arxiv.org/abs/quant-ph/0504012. doi:10.1145/992287.992296.

  5. Uwe Schöning. A probabilistic algorithm for k-sat and constraint satisfaction problems. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), volume, 410–414. 1999. doi:10.1109/SFFCS.1999.814612.

  6. 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.

  7. 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.

  8. 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.

  9. Chris Cade, Marten Folkertsma, Ido Niesen, and Jordi Weggemans. Quantifying grover speed-ups beyond asymptotic analysis. arXiv: https://arxiv.org/abs/2203.04975, 2022.

  10. Chris Cade, Marten Folkertsma, Ido Niesen, and Jordi Weggemans. Quantum algorithms for community detection and their empirical run-times. arXiv: https://arxiv.org/abs/2203.06208, 2022.

  11. Torsten Hoefler, Thomas Häner, and Matthias Troyer. Disentangling hype from practicality: on realistically achieving quantum advantage. Commun. ACM, 66(5):82–87, 2023. doi:10.1145/3571725.

  12. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001. doi:https://doi.org/10.1006/jcss.2001.1774.

  13. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, 75–85. Springer Berlin Heidelberg, 2009. doi:10.1007/978-3-642-11269-0\_6.

  14. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997. arXiv: https://arxiv.org/abs/quant-ph/9701001. doi:10.1137/S0097539796300933.

  15. Harry Buhrman, Subhasree Patro, and Florian Speelman. A framework of quantum strong exponential-time hypotheses. In Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS), volume 187, 19:1–19:19. 2021. doi:10.4230/LIPIcs.STACS.2021.19.

  16. Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006. Earlier version in ICALP'04. arXiv: https://arxiv.org/abs/quant-ph/0401091. doi:10.1137/050644719.

  17. Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. Quantum speedups for exponential-time dynamic programming algorithms. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1783–1793. SIAM, 2019. arXiv: https://arxiv.org/abs/2104.14384. doi:10.1137/1.9781611975482.107.

  18. Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007. Earlier version in FOCS'04. arXiv: https://arxiv.org/abs/quant-ph/0311001. doi:10.1137/S0097539705447311.

  19. Ashley Montanaro. Quantum-walk speedup of backtracking algorithms. Theory of Computing, 14(15):1–24, 2018. arXiv: https://arxiv.org/abs/1509.02374. doi:10.4086/toc.2018.v014a015.

  20. Andris Ambainis and Martins Kokainis. Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. In Proceedings of the 49th ACM Symposium on the Theory of Computing (STOC), 989–1002. 2017. arXiv: https://arxiv.org/abs/1704.06774. doi:10.1145/3055399.3055444.

  21. Michael Jarret and Kianna Wan. Improved quantum backtracking algorithms using effective resistance estimates. Physical Review A, 97(2):022337, 2018. arXiv: https://arxiv.org/abs/1711.05295. doi:10.1103/PhysRevA.97.022337.

  22. Simon Martiel and Maxime Remaud. Practical implementation of a quantum backtracking algorithm. In Alexander Chatzigeorgiou, Riccardo Dondi, Herodotos Herodotou, Christos Kapoutsis, Yannis Manolopoulos, George A. Papadopoulos, and Florian Sikora, editors, SOFSEM 2020: Theory and Practice of Computer Science, 597–606. Cham, 2020. Springer International Publishing. arXiv: https://arxiv.org/abs/1908.11291. doi:10.1007/978-3-030-38919-2\_49.

  23. Alexandra E. Moylett, Noah Linden, and Ashley Montanaro. Quantum speedup of the traveling-salesman problem for bounded-degree graphs. Physical Review A, 95:032323, 3 2017. arXiv: https://arxiv.org/abs/1612.06203. URL: https://link.aps.org/doi/10.1103/PhysRevA.95.032323, doi:10.1103/PhysRevA.95.032323.

  24. 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.

  25. Shouvanik Chakrabarti, Pierre Minssen, Romina Yalovetzky, and Marco Pistoia. Universal quantum speedup for branch-and-bound, branch-and-cut, and tree-search algorithms. arXiv: https://arxiv.org/abs/2210.03210, 2022.

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

  27. Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum nearest-neighbor algorithms for machine learning. Quantum Information and Computation, 15(3&4):318–358, 2015. arXiv: https://arxiv.org/abs/1401.2142. doi:10.26421/QIC15.3-4.