GROUPS AND PROBABILTY June 30–July 4, Budapest

Quantum algorithms for groups

Katalin Friedl & Gábor Ivanyos

MTA SZTAKI (Budapest)

BABAI-BEALS 1993

G a black box group without ”large” composition factors of Lie type ⇒

We can compute ”the structure” of G in polynomial time using oracles for

• computing and factoring |g| for g ∈ G

• solving discrete log in GL(𝔽_{p})

• testing memberhsip effectively in abelian subgroups of G

These tasks can be solved efficiently on quantum computers (if the encoding is unique).

HIDDEN SUBGROUP

Input:  G (finite) group,

f : G → S hiding H ≤ G:

∀x ∈ G, h ∈ H, f(x) = f(xh) and ∀x, y ∈ G, xH ≠ yH ⟹ f(x) ≠ f(y).

Output: Generators for H.

Examples:

Order finding: G = ℤ, f(z) = u^{z} (u from a group, e.g, from ℤ_{n}^{∗} for factoring n)

Discrete log: G = ℤ × ℤ, f(y, z) = u^{y}v^{−z},

(u, v from a group, want x: u^{x} = v) Abelian membership test: G = ℤ^{n} × ℤ

f(y_{1}, …, y_{n}, z) = u_{1}^{y_{1}} ⋯ u_{n}^{y_{n}} · v^{−z}, (want x_{1}, …, x_{n}: u_{1}^{x_{1}} ⋯ u_{n}^{x_{n}} = v)

Graph automorphisms: G = S_{n}, f(π) = graph Γ permuted by π

ABELIAN FOURIER TRANSFORM

|g⟩ ↦ \frac{1}{√|G|} _{χ∈G^{∗}}^{∑} χ(g)|χ⟩

_{g∈G}^{∑} α_{g}|g⟩

↓

\frac{1}{√|G|} _{χ∈G^{∗}}^{∑} _{g∈G}^{∑} α_{g}χ(g)|χ⟩

ABELIAN HIDDEN SUBGROUP

\frac{1}{√|G|} _{g∈G}^{∑} |g⟩ ⊗ |∗⟩

↓

\frac{1}{√|G|} _{g∈G}^{∑} |g⟩ ⊗ |f(g)⟩ =

= \frac{1}{√|G|} _{y}^{∑} _{h∈H}^{∑} |g_{y}h⟩ ⊗ |y⟩

↓ (Fourier)

\frac{1}{|G|} _{y}^{∑} _{χ∈G^{∗}}^{∑}(_{h∈H}^{∑} χ(g_{y}h))|χ⟩ ⊗ |y⟩ =

= \frac{|H|}{|G|} _{y}^{∑} \{ \begin{matrix}χ(g_{y}) & if χ_{|H} = 1 \\ 0 & otherwise \end{matrix} \} |χ⟩ ⊗ |y⟩

Noncommutative results:

HIDDEN SUBGROUP can be solved in quantum poly (log |G|)-time when

– G = ℤk 2 ≀ ℤ2 [Roetteler,Beth’98]

– H is normal and QFT _{G} is available

[Hallgren,Russell,Ta-Shma’00]

– H is normal and G involves no large composition factors of Lie type, e.g., G is solvable or G ≤ S_{n}

[Ivanyos,Magniez,Santha’01]

– ∩{N(H) : H ≤ G} is large

[Grigni,Schulman,Vazirani,Vazirani’01]

– G = ℤ_{p} ⋊ ℤ_{q} when q = \frac{p−1}{(log p)^{c}}

[Moore,Rockmore,Russell,Schulman’02]

– G = ℤ_{n} ⋊ ℤ_{2} + exponential postprocessing

[[Ettinger,Høyer’00]]

Friedl, Ivanyos, Magniez, Santha, Sen 2003, :

HIDDEN SUBGROUP can be solved in quantum poly (log |G|)-time when

– G is a solvable group of bounded length & – G′ has bounded exponent:

∃ constants c_{1}, c_{2} and subnormal subgroups

G′ = N_{0} ⊳ N_{1} ⋯ ⊳ N_{c_{1}−1} ⊳ N_{c_{1}} = {1} s.t.

N_{i−1}/N_{i} ≅ ℤ_{p_{i}}^{n_{i}} (p_{i} prime, p_{i} ≤ c_{2})

Example: triangle matrix groups of constant degree and constant characteristic

G ≤ ( \begin{matrix}𝔽_{q}^{∗} & 𝔽_{q} & 𝔽_{q} \\ 0 & 𝔽_{q}^{∗} & 𝔽_{q} \\ 0 & 0 & 𝔽_{q}^{∗} \end{matrix} )

(q = power of a fixed prime)

IDEA (illustration)

G ⊆ S_{Ω} , e.g, Ω = {graphs on n points } ω_{0}, ω_{1} ∈ Ω

∃g ∈ G s.t. ω_{1} = ω_{0}^{g}
⇕

\frac{1}{√|G|} ∑_{g∈G} |ω_{0}^{g}⟩ = \frac{1}{√|G|} ∑_{g∈G} |ω_{1}^{g}⟩

Otherwise ⟨\frac{1}{√|G|} ∑_{g∈G} |ω_{0}^{g}⟩, \frac{1}{√|G|} ∑_{g∈G} |ω_{1}^{g}⟩⟩ = 0

Two problems:

– testing equality of these states

– computing \frac{1}{√|G|} ∑_{g∈G} ω^{g} QUANTUM STATE EQUALITY TEST: Given (sufficiently many copies of) two quantum states (unit vectors) ψ_{1}, ψ_{2} s.t. either ψ_{1} = ψ_{2} or ⟨ψ_{1}, ψ_{2}⟩ = 0 decide which is the case

SWAP TEST:

|0⟩ ⊗ ψ_{1} ⊗ ψ_{2}
↓
\frac{1}{√2}(|0⟩ + |1⟩) ⊗ ψ_{1} ⊗ ψ_{2}
↓
\frac{1}{√2}(|0⟩ ⊗ ψ_{1} ⊗ ψ_{2} + |1⟩ ⊗ ψ_{2} ⊗ ψ_{1})

∼ HIDDEN SUBGROUP on ℤ_{2}, but ”quantum state valued”.

ORBIT SUPERPOSITION

\frac{1}{√|G|} ∑_{g∈G} |ω^{g}⟩ difficult

Easy: \frac{1}{√|G|} ∑_{g∈G} |g⟩ ⊗ ω^{g}

How to ”forget” |g⟩ from |g⟩ ⊗ |ω^{g}⟩? Assume that G is (semi-)regular and there is an efficient algorithm for finding g s.t. ω = ω_{0}^{g}:

U : |ω_{0}⟩|1⟩ ⊗ |ω_{0}^{g}⟩ ↦ |ω_{0}⟩|g⟩ ⊗ |ω_{0}^{g}⟩

Then:

\frac{1}{√|G|} ∑_{g∈G} |ω_{0}⟩ ⊗ |g⟩ ⊗ |ω^{g}⟩
↓ U^{−1}
\frac{1}{√|G|} ∑_{g∈G} |ω_{0}⟩ ⊗ |1⟩ ⊗ |ω^{g}⟩

HIDDEN TRANSLATION

∼ finding g from ω_{0}, ω_{0}^{g}

Given injective functions f_{0}, f_{1} on G s.t. either f_{1}(g) = f_{0}(ug) form some x or Range(f_{1}) ∩ Range(f_{0}) = 0, decide, which is the case and find u.

Remark. [Ettinger-Høyer’00]. For a finite abelian G HIDDEN TRANSLATION in G ⇔ HIDDEN SUBGROUP in G ⋊ ℤ_{2}.

Theorem. For prime p, HIDDEN TRANSLATION can be solved on ℤ_{p}^{n} by a quantum algorithm with query complexity O(p(n + p)^{p−1}) and time complexity (n + p)^{O(p)}.

The algorithm for HIDDEN TRANSLATION in ℤ_{p}^{n}: Part 1 (quantum)

Idea of [EH’00]: Apply QFT on the direct product ℤ_{p}^{n} × ℤ_{2}.

State:

\frac{1}{2p^{n}} _{x,y∈ℤ_{p}^{n}}^{∑} 1 ; ∑ ; b,c=0 ω_{p}^{x·y}(−1)^{bc}|y⟩ ⊗ |c⟩ ⊗ |f_{b}(x)⟩

Rewrite using the hidden translation:

\frac{1}{2p^{n}} _{x,y∈ℤ_{p}^{n}}^{∑} 1 ; ∑ ; c=0 (ω_{p}^{x·y} + ω_{p}^{(x+u)·y} (−1)^{c})|y⟩ ⊗ |c⟩ ⊗

|f_{0}(x)⟩

For all x, y the coeff. of |y⟩ ⊗ |1⟩ ⊗ |f_{0}(x)⟩ is:

\frac{1}{2p^{n}}ω_{p}^{x·y}(1 − ω_{p}^{y·u})

After observation:

Pr[output = (y, 1)] = \frac{1}{4p^{2n}} |1 − ω_{p}^{y·u}|^{2}. Properties of the output distribution:

– depends only on y · u

– for every (y, 1) observed: y ·u ≠ 0 mod p. Decision version: Decide if f_{1} is a translate of f_{0}: distinguish a distribution of the above type from the uniform one. Search for u is similar.

Part 2 (classical postprocessing)

We consider observed values of type (y, 1)

∃ hidden translation u ⟹ ∃ P ∈ 𝔽_{p}[x_{1}, …, x_{n}] deg P ≤ p − 1 P (y) = 0 for every observed (y, 1) P (x) = (x · u)^{p−1} − 1

disjoint ranges (uniform distr) + many observations y_{1}, …, y_{N} ⟹

P (y_{1}) = 0

⋮
P (y_{N}) = 0

with high probability a system of lin. eqn’s (in the coeff’s of P) with solution only 0.

Iterateting the HIDDEN TRANSLATION (and some variants) → a solution of the HIDDEN SUBGROUP in solvable G of constant length with G′ of constant exponent...

Remarks, Questions

Solution for HIDDEN TRANSLATION in ℤ_{p}^{n} is exponential in p: Is there a method polynomial in p (or even in log p)?

Is there a direct method for HIDDEN TRANSLATION in ℤ_{k}^{n}? For prime power k we know one. For k = 6 or k = 15???