A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

By Greg Kuperberg. SIAM journal on computing (Print), 2003

371 citations recorded by the source corpus.

We present a quantum algorithm for the dihedral hidden subgroup problem (DHSP) with time and query complexity $2^{O(\sqrt{\log\ N})}$. In this problem an oracle computes a function $f$ on the dihedral group $D_N$ which is invariant under a hidden reflection in $D_N$. By contrast, the classical query complexity of DHSP is $O(\sqrt{N})$. The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins as usual with a quantum character transform, which in the case of $D_N$ is essentially the abelian quantum Fourier transform. This yields the name of a group representation of $D_N$, which is not by itself useful, and a state in the representation, which is a valuable but indecipherable qubit. The algorithm proceeds by repeatedly pairing two unfavorable qubits to make a new qubit in a more favorable representation of $D_N$. Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/43809e75c048ff3973b333d0070464c20508a6cb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2005, background): “ Introduction Since Shor’s breakthrough discovery in 1994 [28], quantum algorithms with an exponential speedup over the best known classical algorithms have been shown for a number of problems (e.g., [10, 30, 15, 22]). All these problems and algorithms share some common features: the problems are gr”
New lattice based cryptographic constructions (2003, background): “No efficient solution to the HSP on the dihedral group is known.The best known algorithm is due to Kuperberg [ 18 ] and runs in subexponential time 2O(”
CSIDH: An Efficient Post-Quantum Commutative Group Action (2018, methodology): “Bonnetain and Schrottenloher [6] determine (quantum) query complexities for breaking CSIDH under the assumption that the quantum memory can be made very large, which implies that Kuperberg’s faster algorithms would be applicable.”
Quantum computation vs. firewalls (2013, background): “Researchers have been trying consistently since then to attack the non-Abelian version of the problem but with only very limited success [70–72].”
Post-quantum cryptography (2008, neutral): “We do not describe isogeny-based cryptography [20, 21, 22], for example, and we do not discuss Kuperberg’s algorithm [23].”
Classical hardness of learning with errors (2013, background): “The latter would be a major progress in quantum algorithms, yet is not entirely unreasonable; in fact, a 2 O ( √ n ) -time quantum algorithm for a somewhat related quantum task was discovered by Kuperberg [Kup05] (see also [Reg02]).”