Practical Period Finding on IBM Q – Quantum Speedups in the Presence of Errors
share
We implemented Simon's quantum period finding circuit for functions F_2^n →F_2^n with period s⃗∈F_2^n up to n=7 on the 14-qubit quantum device IBM Q 16 Melbourne. Our experiments show that with a certain probability τ(n) we measure erroneous vectors that are not orthogonal to s⃗. While Simon's algorithm for extracting s⃗ runs in polynomial time in the error-free case τ(n)=0, we show that the problem of extracting s⃗∈F_2^n in the general setting 0 ≤τ(n) ≤1/2 is as hard as solving LPN (Learning Parity with Noise) with parameters n and τ(n). Hence, in the error-prone case we may not hope to find periods in time polynomial in n. However, we also demonstrate theoretically and experimentally that erroneous quantum measurements are still useful to find periods faster than with purely classical algorithms, even for large errors τ(n) close to 1/2.
READ FULL TEXT