Join Log in
Score:4
avatar Crypto

Can you really ignore number of quantum processing steps needed for Shor's algorithm?

gs flag
Mikko Rantalainen

Answers to question RSA key length vs. Shor's algorithm suggest that e.g. 2048 bit RSA encryption would be trivially broken with 4099 qubit quantum computer using Shor's algorithm (best known implementation of the algorithm requiring 2n+3 qubits).

Is this really true? If I've understood correctly, the number of gates (logically quantum operations) needed would be around log(2^2048)^2×log(log(2^2048))×log(log(log(2^2048))) which is roughly 2.9×10⁷. Considering that not even classical computers can execute any operations with 2.9×10⁷ gates using single piece of input data it really doesn't make sense to assume that such a high number of gates could be operated by quantum computer in non-trivial time.

I would assume that for quantum computer to execute one step executing the Shor's algorithm would need to pass (logically) one input through all those gates which would be analogous to classical computer executing enough computer code to pass one 2048 bit input through 2.9×10⁷ gates. Because information cannot travel faster than speed of light and gates have non-zero dimensions, this cannot happen in trivial time. And if you use photons for qubits in the quantum computer, wavelength probably sets minimum dimensions for a gate regardless of manufacturing abilities.

And if you need any error correction between the gates, that will require extra space and hence increase latency, too.

In addition, if I've understood correctly, to actually factor big numbers with Shor's algorithm you need to use classical computer to generate a random guess and Shor's algorithm will then use that guess to maybe emit the data need to compute the factors. How many guesses on average you would actually need for factoring numbers used in 2048 bit RSA?

Has there been research about potential practical runtime of a big physical quantum computer trying to execute Shor's algorithm for factoring big numbers? Does that really support the interpretation that you can simply ignore the processing time regardless of the size of the numbers?

78
0 + 0
rsa
us flag
Sam Ginrich
According to my understanding we can solve problems with about 50 q-bits, not even a question of runtime. If you look up "measurement problem" in physics exchange, you might conclude, that even the problem definition is on schrödinger's cat.
0
Reply
jp flag
user253751
"not even classical computers can execute any operations with 2.9×10⁷ gates using single piece of input data"? What? Yes they can! In a couple of milliseconds!
0
Reply
jp flag
user253751
Perhaps the first quantum computer to do it won't be very fast, so maybe it'll take a week or a month or a year instead of a couple of milliseconds. That's still a lot faster than "forever"
0
Reply
gs flag
Mikko Rantalainen
@user253751 I agree that modern computers can execute operations working with 2.9×10⁷ gates in very short time by executing enough instructions in series. This directly follows because modern CPUs can run up to 5×10⁹ instructions per second per core. I meant that there are no SIMD instructions that can run with such high gate (transistor) count as a single operation which means that the serial execution of individual operations will be an important limiting factor.
0
Reply
Score:3
poncho avatar Crypto
my flag
poncho

I would assume that for quantum computer to execute one step executing the Shor's algorithm would need to pass (logically) one input through all those gates

You misunderstand what is being measured by 'gate operations. The Quantum Computer wouldn't have $2.9 \times 10^7$ gates (and all the data is set through that set of gates repeatedly).

Instead, the Quantum Computer would need to perform a total of $2.9 \times 10^7$ gate operations; obviously, there is no need to perform them all simultaneously (and in fact, with Shor's, we can't, both because of the no-cloning theorem prohibits generating copies of Qubits to send to independent gates, and for the more pragmatic reason that the inputs of some gate operations depend on previous gate operations).

As for how these $2.9 \times 10^7$ gate operations are mapped to hardware gates, well, it is quite unlikely that we will have $2.9 \times 10^7$ physical gates; some hardware gates are likely to be reused multiple times during the course of the computation (just like, when a classical computer performs an RSA operation, the same gates are reused to implement the various modular multiply operations).

And if you need any error correction between the gates, that will require extra space and hence increase latency, too.

Yes, we know; the $2.9 \times 10^7$ figure above reflects logical qubits; that would translate to some larger number of physical qubits - the size of the increase would depend on the quantum error correction code used (which would depend on, among other things, the actual error rate of the physical qubit operations).

How many guesses on average you would actually need for factoring numbers used in 2048 bit RSA?

With extremely high probability, one. The Quantum Computer finds the order of $g$ modulo $n$, that is, the value $x$ where $g^x \equiv 1 \bmod n$. Unless the order of $g$ with respect to both $p$ and $q$ (the prime factors) is anomalously small (which can be shown to happen only with tiny probability if $g$ was selected randomly), that value of $x$ can be used to quickly factor.

0 + 0
gs flag
Mikko Rantalainen
Great info! Could all of this be summarized as follows? Given a quantum computer with 4099 qubits, the 2048 bit RSA key can be broken with $2.9 \times 10^7$ gate operations and that sets the total computing time needed. The actual wall time needed is definited by the effective average instruction clock speed of this computer to execute those operations.
0
Reply
gs flag
Mikko Rantalainen
According to https://quantumcomputing.stackexchange.com/a/2404/18991 it seems that quantum computers could run around 5M operations per second so total computing time needed would be around only 6 seconds! So if the number of qubits can actually be increased to thousands without slowing down individual operations, then execution speed should be good enough to not be the limiting factor in practice.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.