On the complexity of the hidden subgroup problem

DOI10.1142/S0129054113500305MaRDI QIDQ5168412zbMATH OpenOpenAlexFDO

Authors Yong Zhang, S. Fenner

Publication date 4 July 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054113500305

zbMATH Keywords

computational complexityhidden subgroup problemquantum computing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68)

Recommendations

• On the Complexity of the Hidden Subgroup Problem
• The quantum query complexity of the hidden subgroup problem is polynomial
• The hidden subgroup problem and permutation group theory
• The hidden subgroup problem for universal algebras
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations

Cites work

• A nonadaptive NC checker for permutation group intersection
• A note on the graph isomorphism counting problem
• Designing programs that check their work
• Efficient checkers for number-theoretic computations
• 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 algorithms for algebraic problems
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Rapid solution of problems by quantum computation
• The Complexity of Decision Versus Search
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• The quantum query complexity of the hidden subgroup problem is polynomial

Cited in

(22)

• The hidden subgroup problem and post-quantum group-based cryptography
• Deterministic algorithms for the hidden subgroup problem
• Quantum dual adversary for hidden subgroups and beyond
• The hidden subgroup problem and MKTP
• The quantum query complexity of the hidden subgroup problem is polynomial
• Sample complexity of hidden subgroup problem
• The hidden subgroup problem and permutation group theory
• On the Complexity of the Hidden Subgroup Problem
• For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets
• Quantum measurements for hidden subgroup problems with optimal sample complexity
• Hidden translation and orbit coset in quantum computing
• Optimal measurements for the dihedral hidden subgroup problem
• Quantum Computation and Lattice Problems
• The hidden subgroup problem for universal algebras
• Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
• How hard is deciding trivial versus nontrivial in the dihedral coset problem?
• A hidden number problem in small subgroups
• Hidden symmetry subgroup problems
• The one-way communication complexity of subgroup membership
• Complexity bounds on some fundamental computational problems for quantum branching programs.
• Two remarks on the vectorization problem
• The dihedral hidden subgroup problem

This page was built for publication: On the complexity of the hidden subgroup problem

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