pdf icon
Volume 1 (2005) Article 4 pp. 47-79
Quantum Search of Spatial Regions
Received: June 13, 2004
Published: July 13, 2005
Download article from ToC site:
[PDF (331K)]    [PS (638K)]    [PS.GZ (186K)]
[Source ZIP]
Keywords: quantum computing, Grover search, amplitude amplification, quantum communication complexity, disjointness, lower bounds
ACM Classification: F.1.2, F.1.3
AMS Classification: 81P68, 68Q17

Abstract: [Plain Text Version]

Can Grover's algorithm speed up search of a physical region—for example a $2$-D grid of size $\sqrt{n}\times\sqrt{n}$? The problem is that $\sqrt{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 $O(\sqrt{n})$ for $d\geq3$, or $O(\sqrt {n}\log^{5/2}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 $O(\sqrt{n})$-qubit communication protocol for the disjointness problem, which improves an upper bound of Høyer and de Wolf and matches a lower bound of Razborov.