Noisy Quantum Gates Spoil Shor's Factorization Attack

kodlu

6/15/24, 2:12 AM

Update:

In Lipton and Regan's blog, Scott Aaranson and Craig Gidney have commented that the results are not unexpected and also not a deal-breaker in that dealing with this type of noise is already part of the way QC is implemented, including the use of physical measures as well as error correction for making quantum computing work.

Original Question:

An interesting recent paper by Jin-Yi Cai is suggesting that even slightly noisy quantum gates render Shor's algorithm unable to factor $N=pq.$ The author thanks a group of researchers including Shor, Aho, Boneh, Gacs, Galil, Levin, Lipton, Rivest, Sipser, and Valiant in the acknowledgements section for insightful comments.

Abstract:

We consider Shor’s quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) 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 from a well-defined set of primes of positive density. We further prove that with probability $1 − o(1)$ over random prime pairs $(p, q),$ Shor’s factoring algorithm does not factor numbers of the form $pq,$ with the same level of random noise present.

Some observations:

It seems that slightly noisy quantum computers cannot factor $pq$ if $p,q$ have what the author calls the Fouvry property (Theorem 2). A prime $p$ has this property if the largest prime in the prime factorization of $(p-1)$ is $>p^{2/3}$. This criterion is obeyed by strong primes (used for RSA) as well as Sophie Germain primes.

It seems that randomly chosen primes from primes of a given bitlength (Theorem 3) are also not factorable by Shor.

Do these results, if upheld, imply that there is a separation between choosing classically strong $p,q$ and Shor-resistant $p,q$, in some sense? Note that the results seem to be asymptotic in nature.

The author says that he has similar work on discrete logarithms to appear soon.

Non-Expert Question:

Does this result imply a kind of unity between quantum and classical strength of RSA? It seems that (if I haven't misinterpreted) if strong primes are chosen for optimizing RSA against classical attacks, then slightly noisy quantum gates are enough to foil Shor.

Any other comments welcome.

134

0 + 2

factoring

quantum-cryptanalysis

shors-algorithm

DannyNiu

6/15/24, 6:50 AM

It's a strong consensus right now (don't police me like a citation-demanding Wikipedian), that CRQC is not mature yet. I personally feel that, the effort to construct one and run Shor's algo is as difficult as that of constructing a classical computer and run GNFS or Pollard's rho, at least for 5 years from now on.

garfunkel

6/16/24, 2:41 PM

@Turbo: Why do you call Scott's comment cryptic? In the first paragraph he states that Cai finally (in the sense that nobody before invested the work in proving an expected result) actually proved that error correction is indeed required, if the quantum operations are not free of noise. In the second paragraph he criticizes Cai for mixing this technical result with the personal opinion that quantum mechanics does not quite correctly model reality.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Noisy Quantum Gates Spoil Shor's Factorization Attack

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.