DLOG ⊆ BQP

Inclusion · quantum setting · Shor97, BL95

Statement

A polynomial-time quantum algorithm computes discrete logarithms in ${\mathbb{Z}}_p^{\ast }$ — Shor97. The algorithm extends to every group whose operation is efficiently computable on unique encodings, elliptic-curve groups included — BL95. The decision version of DLOG (given $(\mathbb{G},g,h,t)$, decide whether some $x\le t$ satisfies $g^x=h$) is therefore in BQP.

Sketch

For $h=g^x$ in a group of order $r$, the function $f(a,b):=g^a{h}^{-b}$ on ${\mathbb{Z}}_r^2$ is constant exactly on the cosets of $\{(a,b):a\equiv bx\mathrm{mod}r\}$. Fourier sampling over ${\mathbb{Z}}_r^2$ returns $(c,d)$ with $d\equiv -cx(\mathrm{mod}r)$, and $x=-d{c}^{-1}\mathrm{mod}r$ whenever $c$ is invertible — Shor97.