The hidden subgroup problem for universal algebras

DOI10.1145/3373718.3394764MaRDI QIDQ5145678zbMATHOpenAlexWikidataFDO

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)

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

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)

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.

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

Cited in

(12)

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

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)