PaperlayerView exact revision on arXiv

Source-linked AI summary

Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem

Greg Kuperberg

arXiv:1112.3333v1quant-ph

TL;DR

The paper presents an improved Algorithm 4.4 for the setting involving f(x+s), where f and g are injective functions on Z/N. A collimation sieve combines phase-bearing qubits into larger qudits and uses partial measurements to obtain a qubit revealing hidden-shift parity. The modified Algorithm 4.4 uses quantum time and classical space 2^O(√n), and quantum space O(log n).

  • Problem

    The paper presents an improved Algorithm 4.4 for the setting involving f(x+s), where f and g are injective functions on Z/N.

    Source: §1 · p. 1

  • Method

    A collimation sieve combines phase-bearing qubits into larger qudits and uses partial measurements to obtain a qubit revealing hidden-shift parity.

    Source: §1 · p. 1

  • Results

    The modified Algorithm 4.4 uses quantum time and classical space 2^O(√n), and quantum space O(log n).

    Source: §4.6 · p. 9

  • Takeaways & Limitations

    With quantumly accessible classical memory, the algorithm offers trade-offs between classical space and time and quantum time.

    Source: §1 · p. 1, §5 · p. 9

    The authors report no quantum acceleration for the discussed lattice-problem instances, where classical sieve algorithms remain difficult to compete with.

    Source: §5 · p. 9

Abstract

from arXiv · show

We give an algorithm for the hidden subgroup problem for the dihedral group $D_N$, or equivalently the cyclic hidden shift problem, that supersedes our first algorithm and is suggested by Regev's algorithm. It runs in $\exp(O(\sqrt{\log N}))$ quantum time and uses $\exp(O(\sqrt{\log N}))$ classical space, but only $O(\log N)$ quantum space. The algorithm also runs faster with quantumly addressable classical space than with fully classical space. In the hidden shift form, which is more natural for this algorithm regardless, it can also make use of multiple hidden shifts. It can also be extended with two parameters that trade classical space and classical time for quantum time. At the extreme space-saving end, the algorithm becomes Regev's algorithm. At the other end, if the algorithm is allowed classical memory with quantum random access, then many trade-offs between classical and quantum time are possible.

1. INTRODUCTION

The paper presents an improved dihedral hidden subgroup and cyclic hidden shift algorithm, using little quantum space and allowing time–space trade-offs. It describes a collimation sieve and motivates hidden-shift algorithms through their connection to finding elliptic-curve isogenies.

1. INTRODUCTION

  • The improved algorithm uses exp(O(√log N)) classical space and O(log N) quantum space, and is faster than the earlier algorithm in a heuristic model.The earlier algorithm also required exp(O(√log N)) time, queries, and quantum space.Source: §1 · p. 1
  • Two adjustable parameters trade classical space and time against quantum time, and the algorithm can also use multiple hidden shifts.With quantum access to classical memory, the algorithm can use more classical space and time to reduce quantum time.Source: §1 · p. 1
  • The collimation sieve combines phase-bearing qubits into larger qudits, then uses partial measurements to produce a qubit whose measurement reveals the parity of the hidden shift.Its tree has O(√log N) stages and can be traversed depth first; storing a large qudit’s phase description requires eO(ℓ) classical space for dimension ℓ.Source: §1 · p. 1
  • An abelian hidden shift can encode an isogeny between isogenous ordinary elliptic curves, giving hidden-shift algorithms a potential application to finding such isogenies.The paper presents this connection as a new impetus to study the dihedral hidden shift problem.Source: §1 · p. 1

2. QUANTUM TIME AND SPACE

The section distinguishes serial and parallel notions of quantum time and introduces RAM models that separate classical and quantum memory and access. It argues for a RAM-type model and describes quantum access to classical memory.

2. QUANTUM TIME AND SPACE

  • Circuit depth measures parallel quantum time, while gate complexity measures serial quantum time; the latter is equivalent up to a constant factor to computation time on a specified RAM-type machine.The authors regard serial time as a reasonable cost model because gate operations are more expensive than simple memory multiplied by clock time.Source: §2 · p. 2
  • QRACM allows classical memory to be read in quantum superposition, whereas QRAQM allows quantum memory to be accessed in superposition.The section distinguishes four combinations of classical or quantum memory and classical or quantum access.Source: §2 · p. 2
  • The Brassard-Høyer-Tapp collision algorithm uses quantumly addressable classical memory to search for a collision after generating N^1/3 function values.Its stated time complexity is eO(N^1/3); the passage contrasts its large classical memory with Ambainis’ use of true quantum memory.Source: §2 · p. 2

2.1. Some rigor

  • The section formalizes RAM models that separate classical and quantum tapes and describes how quantum addressing applies operations to memory cells in superposition.It also outlines a simulation of quantum reads from classical memory by stepping through the tape.Source: §2.1 · pp. 2–3

3. HIDE AND SEEK

The section reviews the hidden subgroup framework and its states, then relates the dihedral hidden subgroup problem to hidden shifts. It presents multiple hidden shifts and proves a Fourier-mode measurement property used in that setting.

3.1. Hidden subgroups

  • For the usual hidden subgroup problem, the hiding function is constant on cosets and injective on the coset space; the algorithm can discard its output and work with the resulting input state.The resulting state is a uniform mixture over coset states, and the paper’s algorithms mainly use this state for the dihedral group.Source: §3.1 · p. 3
  • The weak Fourier measurement selects a representation block, and the state’s block-diagonal structure lets the algorithm condition on that block while discarding the function value.The row-space state is independent of the state carrying information about the hidden subgroup.Source: §3.1 · pp. 3–4

3.2. Hidden shifts

  • For a generalized dihedral group, the hard hidden subgroup case is a hidden reflection, equivalent to finding a shift between two injective functions on the abelian group [7].The paper also allows multiple hidden shifts, with known endomorphisms and injective functions related by the unknown shift; uniqueness requires a non-degeneracy condition.Source: §3.2 · p. 4
  • The new algorithm can use multiple hidden shifts, but the resulting acceleration is not dramatic.The paper notes that its earlier sieve did not work better for semidirect products with |K| > 2 than in the dihedral case.Source: §3.2 · p. 4
  • The input state is block diagonal across Fourier modes, and measuring a mode yields a uniformly random value.The proof uses translation invariance of the state and the map that discards the function output.Source: §3.2 · p. 4

4. THE ALGORITHM

The algorithm treats the hidden shift in a cyclic power-of-two setting, then combines phase vectors through collimation until measuring a qubit reveals the shift’s parity.

4.1. The initial and final stages

  • For simplicity, the algorithm is described for A = Z/N with N = 2^n, using a supply of states (4).The paper says the details could instead use any fixed base or N that is a product of small numbers; precise optimization for all N receives only brief treatment.Source: §4.1 · p. 5
  • The algorithm seeks only the hidden shift’s parity: measuring whether |ψ⟩ is |+⟩ or |−⟩ reveals it, after which the problem reduces to a hidden shift on Z/2n−1 and proceeds by induction [7].Source: §4.1 · p. 5

4.2. Combining phase vectors

  • Collimation produces increasingly favorable phase vectors, with pairwise phase-function differences divisible by many powers of 2, until the algorithm produces a state of length 2 and height 1 (not height 0).Source: §4.2 · pp. 5–6
  • Combining two height-h phase vectors creates a double-indexed vector of height h; measuring with parameter m produces a new phase vector of height h−m.The measurement is a projection onto the specified subset of indices.Source: §4.2 · p. 6
  • For the combination, the index set can be computed classically, the phase multiplier is the sum of the inputs’ multipliers, and the indices are reindexed.A subunitary operator is unitary on the subspace spanned by the reindexed set and annihilates vectors orthogonal to it.Source: §4.2 · p. 6
  • Collimation also applies to a list of phase vectors, with a collimation parameter m, to produce a new collimate state.Source: §4.2 · p. 6

1. Notionally form the phase vector

The collimation sieve recursively combines and partially measures phase vectors to produce a qubit whose measurement reveals the hidden shift’s parity. Its tree structure and adjustable parameters shape the algorithm’s space and time costs, with a modified version given a rigorous complexity bound.

4.3. The complexity of collimation

  • Collimation takes eO(ℓmax) classical time and O(ℓmax max(m, log ℓmax)) classical space with quantum access, while using O(log ℓmax) quantum space.The resource bounds are stated for collimation with r = 2; the proposition assumes QRACM.Source: §4.3 · p. 6
  • A phase vector’s quantum state fits in ⌈log2 ℓmax⌉ qubits, while its phase-multiplier table has O(ℓmax) entries of h bits each.The low m bits of each table entry are kept in quantum-access memory.Source: §4.3 · pp. 6–7
  • The classical work of collimation can be computed in eO(ℓ) time when the input phase-multiplier tables are already sorted.The construction sorts the combined table and stores forward and inverse bijections for renumbering.Source: §4.3 · p. 7

4.4. The outer algorithm

  • Collimation combines phase vectors and partially measures their phase multipliers, producing progressively aligned vectors in a recursive tree.The tree can be traversed depth-first, storing only one path to a leaf rather than the entire tree.Source: §4.4 · p. 8
  • The middle collimation sieve uses computational-basis permutations and measurements, between quantum Fourier-transform queries and a parity measurement.The resulting qubit can reveal the parity of the hidden shift.Source: §4.4 · p. 8

4.5. Heuristic analysis

  • The heuristic analysis estimates both quantum-plus-classical time and classical space, but does not prove the estimate or account for random fluctuations in the length estimate.With QRACM, extra classical space can be used to increase m and save quantum time; when space is minimized by keeping ℓ = 2, the algorithm reduces to Regev’s algorithm.Source: §4.5 · p. 8

4.6. A rigorous complexity bound

  • The modified algorithm uses quantum time and classical space 2^O(√n), and quantum space O(log n).The construction assumes n = m^2 and two hidden shifts.Source: §4.6 · pp. 8–9
  • The modified sieve bounds intermediate and final-stage success without assuming a uniform distribution of combined phase multipliers.For intermediate buckets, the chance of a bucket of length at least ℓ0 is at least 3/4, followed by at least 1/2 chance that trimming yields length ℓ0; at the final stage, the corresponding bounds are 3/4 and 2/3 for producing a qubit.Source: §4.6 · p. 9

5. CONCLUSIONS

Algorithm 4.4 can be superpolynomially faster than Regev’s algorithm in many parameter settings, but the authors report no quantum acceleration for the overlapping-state lattice instances. They also identify solving DHSP without meaningfully using representation theory as a feature worth exploring further.

5. CONCLUSIONS

  • Both the new and first algorithms run in 2^O(√log N) time, but asymptotic notation in the exponent can hide real performance differences.The authors also argue that polynomial accelerations matter in complexity theory.Source: §5 · p. 9
  • For many parameter settings, Algorithm 4.4 is superpolynomially faster than Regev’s; with exponentially more quantum time than classical space, it becomes Regev’s algorithm.Source: §5 · p. 9
  • For overlapping-state instances from Regev’s lattice-problem reduction, the authors have found no quantum acceleration, citing difficulty competing with classical sieve algorithms.They characterize the algorithms’ role as making DHSP roughly comparable to lattice problems on a quantum computer.Source: §5 · p. 9
  • Algorithm 4.4 solves DHSP without meaningfully staying within the group’s representation theory, prompting interest in non-representation methods for other hidden-structure problems.Source: §5 · p. 9
Loading 1112.3333v1…