|
Friday, December 4, 2009 |
|
|
|
|
Quantum property testing for sparse graphs |
|
|
In property testing, the goal is to determine whether an object has a certain
property or is far from having that property. Many properties of graphs can be
tested very quickly, even classically; for example, one can decide whether a graph
is connected or far from connected in constant time, independent of the size of
the graph. However, Goldreich and Ron showed that testing bipartiteness or
expansion of n-vertex graphs requires at least about sqrt(n) queries. By
derandomizing classical property testing algorithms and applying quantum
techniques for collision finding, we show that these problems can be solved in
only about n^{1/3} steps on a quantum computer. Whether quantum algorithms might
offer an exponential speedup for testing graph properties remains an interesting
open question. |