CS Theory Seminar: Shor's Quantum Algorithms Fail in the Presence of Noise (Jin-Yi Cai)

Abstract: We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. We prove that the algorithm does not factor integers of the form $pq$ when the noise exceeds a vanishingly small level in terms of $n$ --- the number of bits of the integer to be factored, where $p$ and $q$ are either a pair of random primes or from a well-defined set of primes of positive density.

Links to the papers proving these claims are given below.

The second paper is joint with Ben Young and proves the same result for Discrete Log.

I will also present some experimental results supporting the hypothesis that rotations of physical qubits are not infinitely accurate, which forms the basis of the noise model for the proof.

I will speculate whether quantum error correction can rescue the situation.

• https://link.springer.com/article/10.1007/s11432-023-3961-3
• https://dl.acm.org/doi/pdf/10.1145/3736421