The quantum query complexity of the hidden subgroup problem is polynomial

DOI10.1016/j.ipl.2004.01.024zbMath1178.68268arXivquant-ph/0401083OpenAlexW2044747430WikidataQ62039263 ScholiaQ62039263MaRDI QIDQ2390280

Peter Høyer, Mark Ettinger, Emanuel Knill

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0401083

zbMATH Keywords

algorithmsquantum computationquery complexityhidden subgroups

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

The quantum query complexity of the abelian hidden subgroup problem, Quantum mechanics on finite groups, Post-quantum security of the Even-Mansour cipher, Control aspects of quantum computing using pure and mixed states, Sample complexity of hidden subgroup problem, On the Complexity of the Hidden Subgroup Problem, Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem, Zero sum subsequences and hidden subgroups, Algebraic Methods in Quantum Informatics, Shadow Tomography of Quantum States, Quantum algorithm design: techniques and applications, On the power of non-adaptive learning graphs, Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to abelian cases, Quantum pattern matching fast on average, Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems, ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM, GRADIENT FLOWS FOR OPTIMIZATION IN QUANTUM INFORMATION AND QUANTUM DYNAMICS: FOUNDATIONS AND APPLICATIONS, The significance of theC-numerical range and the localC-numerical range in quantum control and quantum information, Quantum algorithms for algebraic problems, Query complexity of generalized Simon's problem, Symmetry principles in quantum systems theory, Deterministic algorithms for the hidden subgroup problem, Quantum algorithms for learning symmetric juntas via the adversary bound, Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts

Cites Work

• Unnamed Item
• Normal subgroup reconstruction and quantum computation using group representations
• Quantum lower bound for the collision problem
• Quantum computations: algorithms and error correction
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• On the Power of Quantum Computation
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• On quantum algorithms for noncommutative hidden subgroups