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>

By admin