Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0303041 · Annual Symposium on Foundations of Computer Science

Quantum search of spatial regions

Scott Aaronson, Andris Ambainis

Published Mar 2, 2004• 128 citations
arXivHTMLPDF

Abstract

Can Grover's quantum search algorithm speed up search of a physical region - for example a 2D grid of size /spl radic/n x /spl radic/n? The problem is that /spl radic/n time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time 0(/spl radic/n) for d /spl ges/ 3, or 0(/spl radic/n log/sup 3/ n) for d = 2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks; a generalized algorithm that works for any graph with good expansion properties, not just hypercubes; and relationships among several notions of locality for unitary matrices acting on graphs. As an application of our results, we give an 0(/spl radic/n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Hoyer and de Wolf and matches a lower bound of Razborov.

DOI
10.1109/sfcs.2003.1238194

Related papers

On the Quantum Query Complexity of Local Search in Two and Three Dimensions

Xiaoming Sun, Andrew Chi-Chih Yao

The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d ges 5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2is Omega(nfrac12 - delta), and that for the 3-dimensional grid [n]3is Omega(n1 - delta), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (2004) (based on Ambainis' adversary method (2003) for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemeridi (1965), Bose and Chowla (1962-63), and Halasz (1977) from combinatorial number theory, as well as less familiar probability tools like Esseen's inequality

Annual Symposium on Foundations of Computer Science•Oct 1, 2006•10 citations

Spatial Search by Nonlinear Quantum Walk

David A. Meyer, Thomas G. Wong

Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size $Θ(N)$, for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.

quant-pharXiv:2606.01403•Jun 2, 2026•0 citations

A note on quantum lower bounds for local search via congestion and expansion

Simina Brânzei, Nicholas Recker

We consider the quantum query complexity of local search as a function of graph geometry. Given a graph $G = (V,E)$ with $n$ vertices and black box access to a function $f : V \to \mathbb{R}$, the goal is find a vertex $v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in E$, using as few oracle queries as possible. We show that the quantum query complexity of local search on $G$ is $Ω\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)$, where $g$ is the vertex congestion of the graph. For a $β$-expander with maximum degree $Δ$, this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Brânzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of $Ω\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)$. This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of $O\bigl( n^{\frac{1}{3}} \bigr)$ for such graphs.

arXiv:2412.13345•Dec 17, 2024•0 citations

Quantum lower bounds for the collision and the element distinctness problems

Yaoyun Shi

Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).

arXiv:quant-ph/0112086•Annual Symposium on Foundations of Computer Science•Jun 26, 2003•100 citations

Spatial search by quantum walk

Andrew M. Childs, Jeffrey Goldstone

Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of $N$ items laid out in $d$ spatial dimensions can be searched in time of order $\sqrt{N}$ for $d>2$, and in time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$ for $d=2$. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that $\sqrt{N}$ speedup can also be achieved on the hypercube. We show that full $\sqrt{N}$ speedup can be achieved on a $d$-dimensional periodic lattice for $d>4$. In $d=4$, the quantum walk search algorithm takes time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$, and in $d<4$, the algorithm does not provide substantial speedup.

arXiv:quant-ph/0306054•Physical Review A•Aug 23, 2004•726 citations

Quantum Search on the Spatial Grid

Falk, Matthew

This paper explores Quantum Search on the two dimensional spatial grid. Recent exploration into the topic has devised a solution that runs in O(sqrt(n*ln(n))). This paper explores a new algorithm that gives promise for the O(sqrt(n)) result that is the lower bound off of the grid.

arXiv:1303.4127•Mar 18, 2013•11 citations
Can Grover's quantum search algorithm speed up search of a physical region - for example a 2D grid of size /spl radic/n x /spl radic/n? The problem is that /spl radic/n time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time 0(/spl radic/n) for d /spl ges/ 3, or 0(/spl radic/n log/sup 3/ n) for d = 2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks; a generalized algorithm that works for any graph with good expansion properties, not just hypercubes; and relationships among several notions of locality for unitary matrices acting on graphs. As an application of our results, we give an 0(/spl radic/n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Hoyer and de Wolf and matches a lower bound of Razborov.
The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d ges 5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2is Omega(nfrac12 - delta), and that for the 3-dimensional grid [n]3is Omega(n1 - delta), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (2004) (based on Ambainis' adversary method (2003) for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemeridi (1965), Bose and Chowla (1962-63), and Halasz (1977) from combinatorial number theory, as well as less familiar probability tools like Esseen's inequality
Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size Θ(N)Θ(N)Θ(N), for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph G=(V,E)G = (V,E)G=(V,E) with nnn vertices and black box access to a function f:V→Rf : V \to \mathbb{R}f:V→R, the goal is find a vertex vvv that is a local minimum, i.e. with f(v)≤f(u)f(v) \leq f(u)f(v)≤f(u) for all (u,v)∈E(u,v) \in E(u,v)∈E, using as few oracle queries as possible. We show that the quantum query complexity of local search on GGG is Ω(n34g)Ω\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)Ω(g​n43​​), where ggg is the vertex congestion of the graph. For a βββ-expander with maximum degree ΔΔΔ, this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Brânzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of Ω(n14log⁡n)Ω\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)Ω(logn​n41​​). This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of O(n13)O\bigl( n^{\frac{1}{3}} \bigr)O(n31​) for such graphs.
Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).
Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of NNN items laid out in ddd spatial dimensions can be searched in time of order N\sqrt{N}N​ for d>2d>2d>2, and in time of order Npoly(logN)\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)N​poly(logN) for d=2d=2d=2. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that N\sqrt{N}N​ speedup can also be achieved on the hypercube. We show that full N\sqrt{N}N​ speedup can be achieved on a ddd-dimensional periodic lattice for d>4d>4d>4. In d=4d=4d=4, the quantum walk search algorithm takes time of order Npoly(logN)\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)N​poly(logN), and in d<4d<4d<4, the algorithm does not provide substantial speedup.