dorsal/arxiv
View SchemaQuantum Algorithms for Simon's Problem Over General Groups
| Authors | Gorjan Alagic, Cristopher Moore, Alexander Russell |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0603251 |
| URL | https://arxiv.org/abs/quant-ph/0603251 |
| Journal | Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2007 |
Abstract
Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Z_2^n provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. In this paper, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m_1, ..., m_n) in G^n from an oracle f with the property that f(x) = f(xy) iff y equals m or the identity. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G^n, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form G^n have a simple product structure, they share important representation-theoretic properties with the symmetric groups S_n, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called ``standard method'' requires highly entangled measurements on the tensor product of many coset states. Here we give quantum algorithms with time complexity 2^O(sqrt(n log n)) that recover hidden involutions m = (m_1, ..., m_n) in G^n where, as in Simon's problem, each m_i is either the identity or the conjugate of a known element k, and there is a character X of G for which X(k) = -X(1)$. Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the ``missing harmonic'' approach of Moore and Russell. These are the first nontrivial hidden subgroup algorithms for group families that require highly entangled multiregister Fourier sampling.
{
"annotation_id": "919810fb-1310-48a9-b79b-72a75bbf3a2f",
"date_created": "2026-03-02T18:02:26.465000Z",
"date_modified": "2026-03-02T18:02:26.465000Z",
"file_hash": "8807f7d765fbf1ec00b6745ad8042664c15ab34a22c7436145004430b5ee8840",
"private": false,
"record": {
"abstract": "Daniel Simon\u0027s 1994 discovery of an efficient quantum algorithm for solving\nthe hidden subgroup problem (HSP) over Z_2^n provided one of the first\nalgebraic problems for which quantum computers are exponentially faster than\ntheir classical counterparts. In this paper, we study the generalization of\nSimon\u0027s problem to arbitrary groups. Fixing a finite group G, this is the\nproblem of recovering an involution m = (m_1, ..., m_n) in G^n from an oracle f\nwith the property that f(x) = f(xy) iff y equals m or the identity. In the\ncurrent parlance, this is the hidden subgroup problem (HSP) over groups of the\nform G^n, where G is a nonabelian group of constant size, and where the hidden\nsubgroup is either trivial or has order two. Although groups of the form G^n\nhave a simple product structure, they share important representation-theoretic\nproperties with the symmetric groups S_n, where a solution to the HSP would\nyield a quantum algorithm for Graph Isomorphism. In particular, solving their\nHSP with the so-called ``standard method\u0027\u0027 requires highly entangled\nmeasurements on the tensor product of many coset states. Here we give quantum\nalgorithms with time complexity 2^O(sqrt(n log n)) that recover hidden\ninvolutions m = (m_1, ..., m_n) in G^n where, as in Simon\u0027s problem, each m_i\nis either the identity or the conjugate of a known element k, and there is a\ncharacter X of G for which X(k) = -X(1)$. Our approach combines the general\nidea behind Kuperberg\u0027s sieve for dihedral groups with the ``missing harmonic\u0027\u0027\napproach of Moore and Russell. These are the first nontrivial hidden subgroup\nalgorithms for group families that require highly entangled multiregister\nFourier sampling.",
"arxiv_id": "quant-ph/0603251",
"authors": [
"Gorjan Alagic",
"Cristopher Moore",
"Alexander Russell"
],
"categories": [
"quant-ph"
],
"journal_ref": "Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2007",
"title": "Quantum Algorithms for Simon\u0027s Problem Over General Groups",
"url": "https://arxiv.org/abs/quant-ph/0603251"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "73d62158-b5da-486f-bd14-769d6a2686b1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}