A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
Open accessThe DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Abstract
We present a quantum algorithm for the dihedral hidden subgroup problem (DHSP) with time and query complexity $2^{O(\sqrt{\log\ N})}$. In this problem an oracle computes a function f on the dihedral group $D_N$ which is invariant under a hidden reflection in $D_N$. By contrast, the classical query complexity of DHSP is $O(\sqrt{N})$. The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins as usual with a quantum character transform, which in the case of $D_N$ is essentially the abelian quantum Fourier transform. This yields the name of a group representation of $D_N$, which is not by itself useful, and a state in the representation, which is a valuable but indecipherable qubit. The algorithm proceeds by repeatedly pairing two unfavorable qubits to make a new qubit in a more favorable representation of $D_N$. Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Linear Representations of Finite Groups
Serre, J.-P. (1977) · Graduate Texts in Mathematics · doi:10.1007/978-1-4684-9458-7 · Cited by 2,350
On the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295
Noise-tolerant learning, the parity problem, and the statistical query model
Blum, A., Kalai, A., & Wasserman, H. (2003) · Journal of the ACM · doi:10.1145/792538.792543 · Cited by 598
A sieve algorithm for the shortest lattice vector problem
Ajtai, M., Kumar, R., & Sivakumar, D. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380857 · Cited by 558
Quantum measurements and the Abelian Stabilizer ProblemPreprint
Kitaev, A. (1995) · arXiv (Cornell University) · Cited by 510
Babai, L., & Luks, E. M. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808746 · Cited by 410
Hopcroft, J., Paul, W., & Valiant, L. (1977) · Journal of the ACM · doi:10.1145/322003.322015 · Cited by 253
Quantum computation of Fourier transforms over symmetric groups
Beals, R. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258548 · Cited by 191
Quantum Computation and Lattice Problems
Regev, O. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539703440678 · Cited by 188
A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial SpacePreprint
Regev, O. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0406151 · Cited by 167
On Quantum Algorithms for Noncommutative Hidden Subgroups
Ettinger, M., & Høyer, P. (2000) · Advances in Applied Mathematics · doi:10.1006/aama.2000.0699 · Cited by 166
Normal subgroup reconstruction and quantum computation using group representations
Hallgren, S., Russell, A. C., & Ta‐Shma, A. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335392 · Cited by 133
Quantum mechanical algorithms for the nonabelian hidden subgroup problem
Grigni, M., Schulman, L., Vazirani, M., & Vazirani, U. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380769 · Cited by 121
EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
Ivanyos, G., Magniez, F., & Sántha, M. (2003) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054103001996 · Cited by 95
Quantum algorithms for element distinctness
Buhrman, H., Durr, C., Heiligman, M., Hoyer, P., Magniez, F., Santha, M., & de Wolf, R. (2002) · Proceedings 16th Annual IEEE Conference on Computational Complexity · doi:10.1109/ccc.2001.933880 · Cited by 93
EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
MOSCA, M., & ZALKA, C. (2004) · International Journal of Quantum Information · doi:10.1142/s0219749904000109 · Cited by 65
QUANTUM ALGORITHMS FOR SOME HIDDEN SHIFT PROBLEMS
van Dam, W., Hallgren, S., & Ip, L. (2002) · Cited by 59
Generic quantum Fourier transforms
Moore, C., Rockmore, D. N., & Russell, A. C. (2004) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/982792.982910 · Cited by 40
Cited by
Bernstein, D. J., & Lange, T. (2017) · Nature · doi:10.1038/nature23461 · Cited by 1,242
“We do not describe isogeny-based cryptography [20, 21, 22], for example, and we do not discuss Kuperberg’s algorithm [23].”
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
Classical hardness of learning with errors
Brakerski, Z., Langlois, A., Peikert, C., Regev, O., & Stehlé, D. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488680 · Cited by 627
CSIDH: An Efficient Post-Quantum Commutative Group Action
Castryck, W., Lange, T., Martindale, C., Panny, L., & Renes, J. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-03332-3_15 · Cited by 481
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Metadata
- Authors
- Kuperberg, G.
- Venue
- SIAM Journal on Computing
- Published
- 2005-01
- Volume
- 35
- Issue
- 1
- Pages
- 170-188
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2057065544
- Cited by
- 347
- References
- 21
- FWCI
- 18.89
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.