Quantum Period Finding with a Single Output Qubit - Factoring n-bit RSA with n/2 Qubits

Abstract

We study quantum period finding algorithms such as Simon, Shor, and Ekera-Hastad. For a periodic function $f$ these algorithms produce -- via some quantum embedding of $f$ -- a quantum superposition $\sum_x \vert x\rangle\vert f(x)\rangle$, which requires a certain amount of output bits that represent $\vert f(x)\rangle$. We show that we can lower this amount to a single output qubit by hashing $f$ down to a single bit. Namely, we replace the embedding of $f$ in quantum period finding circuits by 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 period finding algorithm in some $n$-bit function $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ our hashing technique reduces the required qubits from $2n$ down to $n+1$. For the Ekera-Hastad algorithm for factoring $n$-bit RSA our hashing reduces the required qubits from $(\frac 3 2 + o(1))n$ down to $(\frac 1 2 + o(1))n$.