Quantum algorithms for a set of group theoretic problems

DOI10.1142/S012905411550015XzbMATH Open1322.68078OpenAlexW2243810228MaRDI QIDQ5261611FDOQ5261611

Authors Yong Zhang, S. Fenner

Publication date 6 July 2015

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

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

zbMATH Keywords

computational complexityquantum algorithmblack-box groups

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: We study two group theoretic problems, GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, in the setting of black-box groups, where DOUBLE COSET MEMBERSHIP generalizes a set of problems, including GROUP MEMBERSHIP, GROUP FACTORIZATION, and COSET INTERSECTION. No polynomial-time classical algorithms are known for these problems. We show that for solvable groups, there exist efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also study the decision versions of STABILIZER and ORBIT COSET, which generalizes GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, respectively. We show that they reduce to ORBIT COSET under certain conditions. Finally, we show that DOUBLE COSET MEMBERSHIP and DOUBLE COSET NONMEMBERSHIP have zero knowledge proof systems.

Recommendations

• Theoretical Computer Science
• Quantum algorithms for solvable groups
• Hidden translation and orbit coset in quantum computing
• Hidden translation and translating coset in quantum computing
• Quantum algorithms for Simon's problem over general groups

Cites work

• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• Fast Monte Carlo algorithms for permutation groups
• Hidden translation and translating coset in quantum computing
• 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 complexity of testing group commutativity
• Quantum computation of zeta functions of curves
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Solvable black-box group problems are low for PP

Cited in

(8)

• Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
• Quantum algorithms for solvable groups
• Theoretical Computer Science
• Quantum algorithms for fixed points and invariant subgroups
• scientific article; zbMATH DE number 7378343 (Why is no real title available?)
• The hidden subgroup problem and MKTP
• Quantum automata and algebraic groups
• Grover's algorithm and the secant varieties

This page was built for publication: Quantum algorithms for a set of group theoretic problems

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