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