Quantum Period Finding Is Compression Robust

Abstract

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|x⟩|f(x)⟩$, which requires a certain amount of output qubits that represent $|f(x)⟩$. 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:\{F{\}}_2^n\to \{F{\}}_2^n$ our hashing technique reduces the required output qubits from $n$ down to $1$, and therefo