We study quantum period finding algorithms such as Simon and Shor (and its

variants Eker{aa}-H{aa}stad and Mosca-Ekert). For a periodic function $f$

these algorithms produce — via some quantum embedding of $f$ — a quantum

superposition $sum_x |xrangle|f(x)rangle$, which requires a certain amount

of output qubits that represent $|f(x)rangle$. We show that one can lower this

amount to a single output qubit by hashing $f$ down to a single bit in an

oracle setting.

Namely, we replace the embedding of $f$ in quantum period finding circuits by

oracle access to several embeddings of hashed versions of $f$. We show that on

expectation this modification only doubles the required amount of quantum

measurements, while significantly reducing the total number of qubits. For

example, for Simon’s algorithm that finds periods in $f: mathbb{F}_2^n

rightarrow mathbb{F}_2^n$ our hashing technique reduces the required output

qubits from $n$ down to $1$, and therefore the total amount of qubits from $2n$

to $n+1$. We also show that Simon’s algorithm admits real world applications

with only $n+1$ qubits by giving a concrete realization of a hashed version of

the cryptographic Even-Mansour construction. Moreover, for a variant of Simon’s

algorithm on Even-Mansour that requires only classical queries to Even-Mansour

we save a factor of (roughly) $4$ in the qubits.

Our oracle-based hashed version of the Eker{aa}-H{aa}stad algorithm for

factoring $n$-bit RSA reduces the required qubits from $(frac 3 2 + o(1))n$

down to $(frac 1 2 + o(1))n$. We also show a real-world (non-oracle)

application in the discrete logarithm setting by giving a concrete realization

of a hashed version of Mosca-Ekert for the Decisional Diffie Hellman problem in

$mathbb{F}_{p^m}$, thereby reducing the number of qubits by even a linear

factor from $m log p$ downto $log p$.

Go to Source of this post

Author Of this post: <a href="http://arxiv.org/find/cs/1/au:+May_A/0/1/0/all/0/1">Alexander May</a>, <a href="http://arxiv.org/find/cs/1/au:+Schlieper_L/0/1/0/all/0/1">Lars Schlieper</a>