The hidden subgroup problem for universal algebras

DOI10.1145/3373718.3394764zbMATH Open1484.08002arXiv2001.11298OpenAlexW3103118845WikidataQ130928276 ScholiaQ130928276MaRDI QIDQ5145678FDOQ5145678

Authors:

Publication date: 21 January 2021

Published in: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no full solution has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, and classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.

Full work available at URL: https://arxiv.org/abs/2001.11298

Recommendations

• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• On the complexity of the hidden subgroup problem
• Hidden symmetry subgroup problems
• Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups
• Normal subgroup reconstruction and quantum computation using group representations

zbMATH Keywords

quantum computationuniversal algebraclone theoryhidden subgroup problemhidden kernel problem

Mathematics Subject Classification ID

Subalgebras, congruence relations (08A30) Operations and polynomials in algebraic structures, primal algebras (08A40)

Cited In (12)

• Finding hidden Borel subgroups of the general linear group
• Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian groups
• The hidden subgroup problem and MKTP
• Hidden symmetry subgroup problems
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• Title not available (Why is that?)
• Quantum Computation and Lattice Problems
• Harmonic analysis on finite groups, number theory and efficient quantum cryptographic algorithms.
• The hidden subgroup problem and post-quantum group-based cryptography
• Hidden constructions in abstract algebra. VI: The theorem of Maroscia and Brewer {\&} Costa
• The hidden subgroup problem and permutation group theory
• On the complexity of the hidden subgroup problem

This page was built for publication: The hidden subgroup problem for universal algebras

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