The Hidden Subgroup Problem for Universal Algebras

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

Author name not available (Why is that?)

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

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 (5)

• Finding hidden Borel subgroups of the general linear group
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• Title not available (Why is that?)
• Hidden constructions in abstract algebra. VI: The theorem of Maroscia and Brewer {\&} Costa
• The hidden subgroup problem and permutation group theory

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)