The quantum query complexity of the hidden subgroup problem is polynomial

DOI10.1016/J.IPL.2004.01.024MaRDI QIDQ2390280zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Mark Ettinger, Peter Høyer, 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

algorithmsquery complexityquantum computationhidden subgroups

Mathematics Subject Classification ID

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

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.

Recommendations

• On the complexity of the hidden subgroup problem
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Hidden symmetry subgroup problems
• The quantum query complexity of the abelian hidden subgroup problem

Cites work

• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Normal subgroup reconstruction and quantum computation using group representations
• On quantum algorithms for noncommutative hidden subgroups
• On the Power of Quantum Computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum computations: algorithms and error correction
• Quantum lower bound for the collision problem
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem

Cited in

(39)

• Algebraic Methods in Quantum Informatics
• Quantum algorithm design: techniques and applications
• Zero sum subsequences and hidden subgroups
• Shadow tomography of quantum states
• Quantum complexity for discrete logarithms and related problems
• On homomorphic encryption using abelian groups: classical security analysis
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• On the quantum complexity of the continuous hidden subgroup problem
• Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups
• Sample complexity of hidden subgroup problem
• Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem
• Hidden subgroup quantum algorithms for a class of semi-direct product groups
• Gradient flows for optimization in quantum information and quantum dynamics: foundations and applications
• Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to abelian cases
• Symmetry principles in quantum systems theory
• The quantum query complexity of the abelian hidden subgroup problem
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• Hidden symmetry subgroup problems
• Quantum mechanics on finite groups
• Query complexity of generalized Simon's problem
• Classical and quantum function reconstruction via character evaluation
• On the complexity of the hidden subgroup problem
• Automata, Languages and Programming
• Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
• Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
• Deterministic algorithms for the hidden subgroup problem
• The significance of theC-numerical range and the localC-numerical range in quantum control and quantum information
• On the Complexity of the Hidden Subgroup Problem
• Quantum algorithms for algebraic problems
• How a Clebsch-Gordan transform helps to solve the Heisenberg hidden subgroup problem
• On the power of non-adaptive learning graphs
• Quantum pattern matching fast on average
• Efficient quantum algorithm for identifying hidden polynomials
• An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups
• Control aspects of quantum computing using pure and mixed states
• Quantum measurements for hidden subgroup problems with optimal sample complexity
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Post-quantum security of the Even-Mansour cipher

This page was built for publication: The quantum query complexity of the hidden subgroup problem is polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390280)