dorsal/arxiv
View SchemaOn the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
| Authors | Cristopher Moore, Alexander Russell |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0609138 |
| URL | https://arxiv.org/abs/quant-ph/0609138 |
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 give strong evidence that no such approach can succeed 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. We show, modulo a group-theoretic conjecture regarding the asymptotic characters of the symmetric group, that no matter what rule we use to adaptively combine quantum states, there is a constant b > 0 such that no algorithm in this family can solve Graph Isomorphism in e^{b sqrt{n}} time. In particular, such algorithms are essentially no better than the best known classical algorithms, whose running time is e^{O(sqrt{n \log n})}.
{
"annotation_id": "d1a9a0f6-70c2-47f1-b645-f1f753890046",
"date_created": "2026-03-02T18:02:30.813000Z",
"date_modified": "2026-03-02T18:02:30.813000Z",
"file_hash": "a830c8dca56898998c75b5ebdb55dda112fb6a993adb5e03536166fd5d3d86f6",
"private": false,
"record": {
"abstract": "It is known that any quantum algorithm for Graph Isomorphism that works\nwithin the framework of the hidden subgroup problem (HSP) must perform highly\nentangled measurements across Omega(n log n) coset states. One of the only\nknown models for how such a measurement could be carried out efficiently is\nKuperberg\u0027s algorithm for the HSP in the dihedral group, in which quantum\nstates are adaptively combined and measured according to the decomposition of\ntensor products into irreducible representations. This ``quantum sieve\u0027\u0027 starts\nwith coset states, and works its way down towards representations whose\nprobabilities differ depending on, for example, whether the hidden subgroup is\ntrivial or nontrivial.\n In this paper we give strong evidence that no such approach can succeed for\nGraph Isomorphism. Specifically, we consider the natural reduction of Graph\nIsomorphism to the HSP over the the wreath product S_n \\wr Z_2. We show, modulo\na group-theoretic conjecture regarding the asymptotic characters of the\nsymmetric group, that no matter what rule we use to adaptively combine quantum\nstates, there is a constant b \u003e 0 such that no algorithm in this family can\nsolve Graph Isomorphism in e^{b sqrt{n}} time. In particular, such algorithms\nare essentially no better than the best known classical algorithms, whose\nrunning time is e^{O(sqrt{n \\log n})}.",
"arxiv_id": "quant-ph/0609138",
"authors": [
"Cristopher Moore",
"Alexander Russell"
],
"categories": [
"quant-ph",
"cs.CC",
"math.RT"
],
"title": "On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism",
"url": "https://arxiv.org/abs/quant-ph/0609138"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d5b5e554-a7eb-4577-a6b8-d5b1e7752f5e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}