The quantum query complexity of the hidden subgroup problem is polynomial
From MaRDI portal
Publication:2390280
DOI10.1016/J.IPL.2004.01.024zbMATH Open1178.68268DBLPjournals/ipl/EttingerHK04arXivquant-ph/0401083OpenAlexW2044747430WikidataQ62039263 ScholiaQ62039263MaRDI QIDQ2390280FDOQ2390280
Authors: Mark Ettinger, Peter Høyer, Emanuel Knill 
Publication date: 21 July 2009
Published in: Information Processing Letters (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/quant-ph/0401083
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
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum computations: algorithms and error correction
- On the Power of Quantum Computation
- Quantum lower bound for the collision problem
- Title not available (Why is that?)
- On quantum algorithms for noncommutative hidden subgroups
- Normal subgroup reconstruction and quantum computation using group representations
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem
Cited In (37)
- How a Clebsch-Gordan transform helps to solve the Heisenberg hidden subgroup problem
- Deterministic algorithms for the hidden subgroup problem
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Quantum algorithm design: techniques and applications
- Shadow Tomography of Quantum States
- Efficient quantum algorithm for identifying hidden polynomials
- On the quantum complexity of the continuous hidden subgroup problem
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups
- Sample complexity of hidden subgroup problem
- Control aspects of quantum computing using pure and mixed states
- An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
- Quantum mechanics on finite groups
- On the Complexity of the Hidden Subgroup Problem
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- The significance of theC-numerical range and the localC-numerical range in quantum control and quantum information
- On homomorphic encryption using abelian groups: classical security analysis
- Zero sum subsequences and hidden subgroups
- An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups
- The quantum query complexity of the abelian hidden subgroup problem
- Quantum measurements for hidden subgroup problems with optimal sample complexity
- Algebraic Methods in Quantum Informatics
- Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to abelian cases
- Post-quantum security of the Even-Mansour cipher
- Automata, Languages and Programming
- ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM
- On the power of non-adaptive learning graphs
- Gradient flows for optimization in quantum information and quantum dynamics: foundations and applications
- Query complexity of generalized Simon's problem
- Quantum complexity for discrete logarithms and related problems
- Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
- Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem
- Quantum pattern matching fast on average
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- Classical and quantum function reconstruction via character evaluation
- Symmetry principles in quantum systems theory
- Quantum algorithms for algebraic problems
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)
