Quantum algorithms for a set of group theoretic problems

DOI10.1142/S012905411550015XzbMATH Open1322.68078arXivquant-ph/0408150OpenAlexW2243810228MaRDI 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)

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.

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

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

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)

Cites Work

• Quantum theory, the Church–Turing principle and the universal quantum computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum complexity of testing group commutativity
• On the Power of Quantum Computation
• Fast Monte Carlo algorithms for permutation groups
• Quantum algorithms for algebraic problems
• Quantum computation of zeta functions of curves
• Solvable black-box group problems are low for PP
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• Hidden Translation and Translating Coset in Quantum Computing

Cited In (7)

• Theoretical Computer Science
• The hidden subgroup problem and MKTP
• Quantum algorithms for fixed points and invariant subgroups
• Title not available (Why is that?)
• Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
• 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)