Published: July 13, 2005

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