The quantum query complexity of the hidden subgroup problem is polynomial

Abstract

We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log |G|) number of calls to the oracle. This is exponentially better than the best classical algorithm. However our quantum algorithm requires exponential time, as in the classical case. Our algorithm utilizes a new technique for constructing error-free algorithms for non-decision problems on quantum computers.

To appear in Information Processing Letters (IPL)

References in corpus (1)

• Quantum lower bounds for the collision and the element distinctness problems

Cited by in corpus (47)

• Quantum algorithms for algebraic problems
• Quantum Computer Systems for Scientific Discovery
• Quantum Copy-Protection and Quantum Money
• Optimal Control-Based Efficient Synthesis of Building Blocks of Quantum Algorithms Seen in Perspective from Network Complexity towards Time Complexity
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Quantum Algorithmic Measurement
• Symmetry Principles in Quantum Systems Theory
• The Hidden Subgroup Problem - Review and Open Problems
• Lower Bounds on Quantum Query Complexity
• Gradient Flows for Optimisation and Quantum Control: Foundations and Applications
• Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
• Quantum Computation Beyond the Circuit Model
• Quantum Computing: Lecture Notes
• Energy-Consumption Advantage of Quantum Computation
• The Symmetric Group Defies Strong Fourier Sampling: Part II
• The Significance of the $C$-Numerical Range and the Local $C$-Numerical Range in Quantum Control and Quantum Information
• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• Optimal measurements for the dihedral hidden subgroup problem
• On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
• Hidden Translation and Translating Coset in Quantum Computing
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits
• Applications of the Adversary Method in Quantum Query Algorithms
• Hidden Symmetry Subgroup Problems
• Quantum Complexity for Discrete Logarithms and Related Problems
• Query complexity of generalized Simon's problem
• On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems
• Normalizer Circuits and Quantum Computation
• Information compression via hidden subgroup quantum autoencoders
• Deterministic Algorithms for the Hidden Subgroup Problem
• Quantum Versus Classical Proofs and Advice
• Explicit Multiregister Measurements for Hidden Subgroup Problems
• Thermodynamic optimization of quantum algorithms: On-the-go erasure of qubit registers
• Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement
• Abelian Hypergroups and Quantum Computation
• Exponential speedups for quantum walks in random hierarchical graphs
• The central nature of the Hidden Subgroup problem
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• Quantum Measurements for Hidden Subgroup Problems with Optimal Sample Complexity
• Quantum pattern matching fast on average
• Quantum algorithm based on the $\epsilon$-random linear disequations for the continuous hidden shift problem
• On the Power of Non-Adaptive Learning Graphs
• On solving systems of random linear disequations
• Quantum Fourier Sampling is Guaranteed to Fail to Compute Automorphism Groups of Easy Graphs
• Finding hidden Borel subgroups of the general linear group
• Classical algorithms for Forrelation
• An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
• The dihedral hidden subgroup problem