|
| related topics |
| {algorithm, log, probability} |
| {group, space, representation} |
| {let, theorem, proof} |
| {measurement, state, measurements} |
| {state, states, entangled} |
| {state, algorithm, problem} |
| {vol, operators, histories} |
| {states, state, optimal} |
|
On the impossibility of a quantum sieve algorithm for graph isomorphism:
unconditional results
Cristopher Moore, Alexander Russell, Piotr Sniady
abstract: It is known that any quantum algorithm for Graph Isomorphism that works
within the framework of the hidden subgroup problem (HSP) must perform highly
entangled measurements across \Omega(n \log n) coset states. One of the only
known models for how such a measurement could be carried out efficiently is
Kuperberg's algorithm for the HSP in the dihedral group, in which quantum
states are adaptively combined and measured according to the decomposition of
tensor products into irreducible representations. This ``quantum sieve'' starts
with coset states, and works its way down towards representations whose
probabilities differ depending on, for example, whether the hidden subgroup is
trivial or nontrivial.
In this paper we show that no such approach can produce a polynomial-time
quantum algorithm for Graph Isomorphism. Specifically, we consider the natural
reduction of Graph Isomorphism to the HSP over the the wreath product S_n\wr
Z_2. Using a recently proved bound on the irreducible characters of S_n, we
show that no algorithm in this family can solve Graph Isomorphism in less than
e^{\Omega(\sqrt{n})} time, no matter what adaptive rule it uses to select and
combine quantum states. In particular, algorithms of this type can offer
essentially no improvement over the best known classical algorithms, which run
in time e^{O(\sqrt{n \log n})}.
- oai_identifier:
- oai:arXiv.org:quant-ph/0612089
- categories:
- quant-ph math.RT
- comments:
- An earlier preprint, quant-ph/0609138, gave versions of these results
which were conditional on a group-theoretic conjecture. This version provides
unconditional results
- doi:
- 10.1145/1250790.1250868
- arxiv_id:
- quant-ph/0612089
- journal_ref:
- In: STOC '07: Proceedings of the thirty-ninth annual ACM symposium
on Theory of computing, pages 536-545, New York, NY, USA, 2007. ACM Press
- created:
- 2006-12-12
- updated:
- 2007-04-07
Full article ▸
|
|
| related documents |
| 0504067v3 |
| 9907020v2 |
| 0410042v1 |
| 0403140v2 |
| 0304131v1 |
| 0408150v2 |
| 0010034v1 |
| 9802040v2 |
| 0607148v3 |
| 0504083v2 |
| 0008059v3 |
| 0210077v1 |
| 0510185v1 |
| 9702028v1 |
| 0610235v2 |
| 0703220v1 |
| 0612052v2 |
| 0703061v1 |
| 0612210v3 |
| 0703179v2 |
| 0701054v1 |
| 0611125v1 |
| 0702155v3 |
| 0701198v1 |
| 0612033v1 |
|