Received: June 13, 2004
Published: July 13, 2005
DOI: 10.4086/toc.2005.v001a004
Abstract: [Plain Text Version]
Can Grover's algorithm speed up search of a physical region---for example a 2-D grid of size (√n)×(√n)? The problem is that (√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(√n) for d≥3, or O((√n)log5/2n) 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(√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.