Quantum algorithms for Simon's problem over nonabelian groups

DOI10.1145/1644015.1644034MaRDI QIDQ2930295zbMATH OpenOpenAlexWikidataFDO

Authors Gorjan Alagic, Cristopher Moore, Alexander Russell

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

hidden subgroup problemquantum algorithms

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Z_2^n provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. In this paper, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m_1, ..., m_n) in G^n from an oracle f with the property that f(x) = f(xy) iff y equals m or the identity. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G^n, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form G^n have a simple product structure, they share important representation-theoretic properties with the symmetric groups S_n, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called ``standard method requires highly entangled measurements on the tensor product of many coset states. Here we give quantum algorithms with time complexity 2^O(sqrt(n log n)) that recover hidden involutions m = (m_1, ..., m_n) in G^n where, as in Simon's problem, each m_i is either the identity or the conjugate of a known element k, and there is a character X of G for which X(k) = -X(1)$. Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the ``missing harmonic approach of Moore and Russell. These are the first nontrivial hidden subgroup algorithms for group families that require highly entangled multiregister Fourier sampling.

Recommendations

• Quantum algorithms for Simon's problem over general groups
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• The Symmetric Group Defies Strong Fourier Sampling
• Normal subgroup reconstruction and quantum computation using group representations
• The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts

Cited in

(10)

• Deterministic polynomial-time quantum algorithms for Simon's problem
• A fusion algorithm for solving the hidden shift problem in finite abelian groups
• Quantum Fourier transform over symmetric groups -- improved result
• Quantum and classical query complexities for generalized Simon's problem
• Quantum algorithms for Simon's problem over general groups
• An efficient quantum algorithm for some instances of the group isomorphism problem
• Hidden symmetry detection on a quantum computer
• The Symmetric Group Defies Strong Fourier Sampling
• scientific article; zbMATH DE number 1303028 (Why is no real title available?)
• Two remarks on the vectorization problem

This page was built for publication: Quantum algorithms for Simon's problem over nonabelian groups

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