A Little Noise Makes Quantum Factoring Fail

Gödel’s Lost Letter and P=NP 2023-06-14

Jin-Yi Cai is one of the top theory experts in the world. Both Ken and I have had the pleasure to work with him and interact with him over the years. We have discussed some of his previous work here and here.

Today we will talk about his new work on quantum computing.

Quantum Factoring

Peter Shor invented the quantum algorithm for finding the prime factors of an integer in 1994.

This is one of the great algorithms of all time. It shows at least in theory that quantum algorithms can be much more efficient than classical algorithms. The algorithm shows that the integer factorization problem can be efficiently solved on an idealized quantum computer and is consequently in the complexity class ${\mathsf{BQP}}$ . This is almost exponentially faster than the most efficient known classical factoring algorithm.

Quantum Factoring Possible?

Is it practically feasible to use Shor’s factoring method to break RSA? This leads to a major question:

Can cryptography survive quantum methods?

A paper by Daniel Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta titled “Post-Quantum RSA” is a key one. They consider further systems including elliptic curve cryptography (ECC) and say:

The conventional wisdom among researchers in post-quantum cryptography is that quantum computers will kill RSA and ECC but will not kill hash-based cryptography, code-based cryptography, lattice-based cryptography, or multivariate- quadratic-equations cryptography. … Shor’s algorithm easily breaks RSA as used on the Internet today. The question is whether RSA parameters can be adjusted so that all known quantum attack algorithms are infeasible while encryption and decryption remain feasible.

See also this. A 2019 paper by Craig Gidney and Martin Ekerå argues that implementations of Shor on 2,048-bit integers ${N}$ is within reach of current technology using noisy qubits—needing only some millions of them. However, this presumes an error-free implementation of the Quantum Fourier Transform (QFT). They say:

Note furthermore that when we analyze the success probabilities of Shor’s algorithms, and the various derivatives, we assume the use of an ideal QFT even though the implemented QFT is technically an approximation.

Quantum Factoring Impossible?

Now enter Jin-Yi. He has a new paper that says:

We consider Shor’s quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for rotation 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 chosen from a set of primes of positive density.

Jin-Yi essentially is saying that quantum algorithms fail to break RSA in the presence of noisy gates. He argues that they will not be able to work when quantum gates are not perfect.

This seems to contradict the previous section. Can it be that quantum algorithms break RSA in theory, but are not practically realizable? See these three recent discussions.

To our knowledge, this is the first hard-and-fast negative result about Shor’s algorithm. Let’s take a closer look.

Angles on Shor’s Algorithm

Given ${N = pq}$ to factor, Shor’s algorithm starts by choosing ${a}$ relatively prime to ${N}$ . The algorithm extends the domain of the function ${f(x) = a^x \pmod{N}}$ to all ${x < M}$ where ${M = 2^m}$ , ${m = 2n}$ , and ${2^n}$ is the next power of ${2}$ after ${N}$ , so that ${M \approx N^2}$ . The quantum engine of Shor’s algorithm has just two main components:

A routine that computes the quantum state

$\displaystyle \Phi = \frac{1}{\sqrt{M}}\sum_x |x\rangle|f(x)\rangle.$

Put another way without the Dirac angle-bracket notation, ${\Phi}$ is a state of ${m+n}$ qubits that has equal nonzero amplitude only on those components ${xy}$ where ${y = f(x)}$ .
The QFT (or its inverse) on ${m}$ qubits.

Quantum gates of the form ${R_k = \begin{bmatrix} 1 & 0 \\ 0 & \omega_k \end{bmatrix}}$ where ${\omega_k = \exp(\frac{2\pi i}{2^k})}$ , when controlled from another qubit, are used in the “textbook” way to compute the QFT. The diagram with ${m=4}$ suffices for the general pattern:

source

For all but a few small values of ${k}$ , the rotation angle in ${R_k}$ is tinier than theoretical minimum units of space, let alone the smallest precision of angular or spatial resolution we have achieved in experiments such as LIGO. Call a circuit family using ${R_k}$ for unbounded ${k}$ “idealistic.”

Donald Coppersmith showed that Shor’s algorithm still works if ${R_k}$ is replaced by the identity operator for ${k > b}$ , where the threshold ${b}$ equals ${c\log_2 n}$ for a constant ${c}$ slightly above ${1}$ . The resulting circuits are still “idealistic” but at least not exponentially so. Coppersmith’s analysis is referenced in Shor’s original paper but not expounded further there.

Jin-Yi shows that Shor’s and Coppersmith’s circuits cannot tolerate a natural kind of noise that operates close to Coppersmith’s level of scaling. It stands concretely against any asymptotic claims of power via Shor’s algorithm that involve idealistic circuits. At the end we will discuss its implications also for circuits that implement Shor’s algorithm without using ${R_k}$ gates.

The Noise

Call ${C}$ a Shor circuit if it uses controlled ${R_k}$ gates to compute the QFT (or its inverse) and can be sampled by a classical procedure ${{\cal A}}$ to infer the period ${\rho}$ of ${f(x) = a^x \pmod{N}}$ in ${n^{O(1)}}$ expected time.

Jin-Yi’s noise operation has parameters ${\epsilon}$ and ${b'}$ and maps a Shor circuit ${C}$ to a distribution of circuits ${\tilde{C}}$ defined as follows: For each controlled ${R_k}$ gate in ${C}$ with ${k \geq b'}$ (alternatively, ${k = b'}$ ), replace it by

$\displaystyle \tilde{R_k} = \begin{bmatrix} 1 & 0 \\ 0 & \tilde{\omega} \end{bmatrix}\quad\text{where}\quad \tilde{\omega} = \exp\left(\frac{2\pi i(1 + r\epsilon)}{2^k}\right)$

with the same control qubit and with an independent draw of Gaussian noise ${r \sim {\cal N}(0,1)}$ . The echo of Coppersmith’s “ ${b}$ ” is on purpose, because he establishes the following fact, which we first state loosely:

Provided ${b' + \log_2(1/\epsilon) \sim \frac{1}{3}(\log_2 n)}$ , the circuits ${\tilde{C}}$ lose the Shor property, meaning that ${{\cal A}}$ sampling ${\tilde{C}}$ cannot find ${\rho}$ .

This says that the noise range brushes against the Coppersmith upper bound for the precision needed to implement Shor’s algorithm. Since ${k}$ is exponentiated, one can say that noise on the order of the cube of the precision needed for Shor’s algorithm is enough to destroy it.

The estimates in the paper allow replacing ${\frac{1}{3}}$ by ${\frac{1}{2+\delta}}$ with greater attention to additive constants, so lower noise approaching the square root of the Coppersmith precision suffices to destroy the Shor property. This may be improvable to almost linear. Exactly what does the noise attack? That’s next.

Long Periods

The noise most strongly affects cases ${N = pq}$ where ${p-1}$ and ${q-1}$ have a large prime factor. The most extreme such case is ${\frac{p - 1}{2} = p'}$ being prime. Then ${p'}$ is called a Sophie Germain prime. Ironically, ${p = 2p'+1}$ is called a “safe prime” but those are the most unsafe under Jin-Yi’s noise.

It remains unknown whether infinitely many Sophie Germain primes exist, despite the quest winning a Tony Award and Pulitzer Prize. But a less-heralded property suffices. Étienne Fouvry proved in 1985 that the set of primes ${p}$ for which ${p - 1}$ has a factor ${p' > p^{2/3}}$ is not only infinite, but has positive density in the set of primes. It follows that cases ${N = pq}$ where both ${p}$ and ${q}$ have this “Fouvry property” have positive density among products of two primes. There can be only one prime factor ${p' > p^{2/3}}$ , likewise ${q' > q^{2/3}}$ .

The upshot for such ${p}$ and ${q}$ is that most ${a}$ have exponentially long periods ${\rho}$ modulo ${N}$ . The geometric sums that concentrate amplitudes on multiples of ${\rho}$ in the ideal situation, when the circuit is sampled via quantum measurement, have norm-squared proportional to ${\rho}$ . In the noisy situation, such length maximizes the perturbative effect of the noise so as to level out the amplitude. This destroys the ability to infer ${\rho}$ .

We cut a few corners in the statements of Jin-Yi’s theorems, but they are reasonably close and the paper has full details. They hold also under the ${k = b'}$ variant and with-or-without removing controlled ${R_k}$ gates for ${k > b'}$ .

Theorem 1 Asymptotically as ${n \rightarrow \infty}$ , if ${N = pq}$ is an ${n}$ -bit product of two Fouvry primes, and ${b' + \log(1/\epsilon) < \frac{1}{3}\log_2 n - \Theta(1)}$ , then the probability that ${{\cal A}(\tilde{C})}$ infers ${\rho}$ is exponentially small.

Theorem 2 Asymptotically as ${n \rightarrow \infty}$ , for all but a vanishing fraction of ${n}$ -bit primes and with ${b' + \log(1/\epsilon) < \frac{1}{3}\log_2 n - \Theta(1)}$ , the probability over ${a}$ and noisy ${\tilde{C}}$ that ${{\cal A}(\tilde{C})}$ infers ${\rho}$ is exponentially small.

Theorem 2, whose proof is in the paper’s appendix, says that Shor’s algorithm fails to survive the noise in all but a vanishing fraction of instances. It applies also under certain restrictions of the primes, such as ${p}$ and ${q}$ both being congruent to 3 modulo 4. Theorem 1 gives a substantial explicit set of cases ${N = pq}$ on which the algorithm fails.

How General Is This?

The theorems are carefully stated in terms of the period-inferencing component of Shor’s algorithm. And they are asymptotic. They do not rule out:

possible quantum improvements on input sizes in the finite range of conceivable practical crypto;
quantum circuits ${D}$ that might factor by other means; nor
that error correction might restore the Shor property.

In particular, they do not define a general-purpose noise model that could apply to any quantum circuit ${D}$ .

Now we discuss two means to implement Shor’s algorithm without using gates beyond ${R_3}$ :

The Hadamard gate ${H}$ , the controlled-not gate CNOT, and the gate ${T = R_3}$ form a complete set that (by the Solovay-Kitaev theorem) can feasibly approximate the state produced by any feasible quantum circuit plus QFT. Then the minimum angle of any individual operation is ${\pi/8}$ .
The Hadamard and Toffoli gates form a universal set in the weaker sense of encoding real and imaginary parts of quantum amplitudes separately. This suffices to compute the factoring function via polynomial-size circuits using only real entries.

Idea 1 may only mask the issue, insofar as the resulting circuits must still approximate angles down to Coppersmith’s unboundedly small magnitude ${2^{-b}}$ . Both ${H}$ and ${T}$ are rotations of the Bloch sphere of periods 2 and 8, respectively. As such, each may be exactly physically realizable, along with their controlled versions and CNOT in higher-dimensional Bloch spheres.

However, ${H}$ and ${T}$ together generate an infinite subgroup of SU(2). The group has members that rotate through arbitrarily small angles. Jin-Yi says in his speculative concluding section:

It is true that using a fixed finite set of rotations of reasonable angles such as ${\pi/8}$ along various axes can compose to rotations of arbitrarily small angles. But my view is just that these compositional rules as specified by the group SU(2) must not be exact for physical reality.

Most in particular, let ${A = HT}$ . If ${A}$ can be exactly realized, then any power ${AA}$ , ${AAA}$ , … should be. But the angle of ${A}$ is not a rational multiple of ${\pi}$ , so the powers alone form an infinite state space and include arbitrarily tiny rotations. Please see Jin-Yi’s paper for other context and justifications on these points, plus related contentions by Mikhail Dyakonov.

The circuits in idea 2 cannot approximate any (feasible) quantum state metrically, but they can emulate Shor’s algorithm using only ${0}$ and ${\pi}$ as “angles.” They may, however, still involve quantum states with filigrees beyond physically realizable precision. In the coda to our own textbook, we speculate this already for the deterministic “functional superposition” component of Shor’s algorithm.

All this and more was discussed already twenty-plus years ago in the “Sure/Shor separator” debate. The difference now is having Jin-Yi’s new work as a linchpin for the skeptical side. Non-robustness to noise in the “Coppersmith range” may be a wider phenomenon than his current results show.

In his last paragraph, Jin-Yi argues that quantum computing makes a fundamental departure from Alan Turing’s condition that primitive steps are finite and fixed independent of the data size ${n}$ . He mentions the free use of SU(2) but his point may apply as well to the step of placing a Toffoli gate anywhere in an ${n}$ -qubit quantum circuit. This point is separate from issues of noise models, about which we have heard much from Gil Kalai including recently.

Open Problems

The issue is simple: Can quantum algorithms be made to work in the presence of gates that are making errors at Jin-Yi’s scaling? The obvious interesting open question is: As in classical computation, can we build circuits that can handle errors? See this and this on error-free computation.

This seems to be a wonderful question. Will the new results reshape debates on quantum computing and the polynomial Church-Turing thesis, or are they subsumed in matters already recently much discussed?