dorsal/arxiv
View SchemaOn the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
| Authors | Jaikumar Radhakrishnan, Martin Roetteler, Pranab Sen |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0503114 |
| URL | https://arxiv.org/abs/quant-ph/0503114 |
| Journal | Proceedings 32nd International Conference on Automata, Languages, and Programming (ICALP 2005), Lisbon, Portugal, Springer LNCS, pp. 1399-1411, 2005 |
Abstract
The hidden subgroup problem (HSP) provides a unified framework to study problems of group-theoretical nature in quantum computing such as order finding and the discrete logarithm problem. While it is known that Fourier sampling provides an efficient solution in the abelian case, not much is known for general non-abelian groups. Recently, some authors raised the question as to whether post-processing the Fourier spectrum by measuring in a random orthonormal basis helps for solving the HSP. Several negative results on the shortcomings of this random strong method are known. In this paper however, we show that the random strong method can be quite powerful under certain conditions on the group G. We define a parameter r(G) for a group G and show that O((\log |G| / r(G))^2) iterations of the random strong method give enough classical information to identify a hidden subgroup in G. We illustrate the power of the random strong method via a concrete example of the HSP over finite Heisenberg groups. We show that r(G) = \Omega(1) for these groups; hence the HSP can be solved using polynomially many random strong Fourier samplings followed by a possibly exponential classical post-processing without further queries. The quantum part of our algorithm consists of a polynomial computation followed by measuring in a random orthonormal basis. This gives the first example of a group where random representation bases do help in solving the HSP and for which no explicit representation bases are known that solve the problem with (\log G)^O(1) Fourier samplings. As an interesting by-product of our work, we get an algorithm for solving the state identification problem for a set of nearly orthogonal pure quantum states.
{
"annotation_id": "4f280fcd-caaa-41df-ad7b-d41a8101f24b",
"date_created": "2026-03-02T18:02:17.155000Z",
"date_modified": "2026-03-02T18:02:17.155000Z",
"file_hash": "0e763fcfa4dba7822d0ede4a63253dda921e7e30061b5acee555a5f63a26288c",
"private": false,
"record": {
"abstract": "The hidden subgroup problem (HSP) provides a unified framework to study\nproblems of group-theoretical nature in quantum computing such as order finding\nand the discrete logarithm problem. While it is known that Fourier sampling\nprovides an efficient solution in the abelian case, not much is known for\ngeneral non-abelian groups. Recently, some authors raised the question as to\nwhether post-processing the Fourier spectrum by measuring in a random\northonormal basis helps for solving the HSP. Several negative results on the\nshortcomings of this random strong method are known. In this paper however, we\nshow that the random strong method can be quite powerful under certain\nconditions on the group G. We define a parameter r(G) for a group G and show\nthat O((\\log |G| / r(G))^2) iterations of the random strong method give enough\nclassical information to identify a hidden subgroup in G. We illustrate the\npower of the random strong method via a concrete example of the HSP over finite\nHeisenberg groups. We show that r(G) = \\Omega(1) for these groups; hence the\nHSP can be solved using polynomially many random strong Fourier samplings\nfollowed by a possibly exponential classical post-processing without further\nqueries. The quantum part of our algorithm consists of a polynomial computation\nfollowed by measuring in a random orthonormal basis. This gives the first\nexample of a group where random representation bases do help in solving the HSP\nand for which no explicit representation bases are known that solve the problem\nwith (\\log G)^O(1) Fourier samplings. As an interesting by-product of our work,\nwe get an algorithm for solving the state identification problem for a set of\nnearly orthogonal pure quantum states.",
"arxiv_id": "quant-ph/0503114",
"authors": [
"Jaikumar Radhakrishnan",
"Martin Roetteler",
"Pranab Sen"
],
"categories": [
"quant-ph",
"cs.ET"
],
"journal_ref": "Proceedings 32nd International Conference on Automata, Languages,\n and Programming (ICALP 2005), Lisbon, Portugal, Springer LNCS, pp. 1399-1411,\n 2005",
"title": "On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group",
"url": "https://arxiv.org/abs/quant-ph/0503114"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4158c404-0459-4ef2-aa4c-438aa33fe3cb",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}