3 ms·
Where does that estimate come from? My (basic) understanding is that, in order to find the factorization of a composite N, Shor's algorithm requires an amount o
by MzxgckZtNqX5i 8y ago
Where does that estimate come from?
My (basic) understanding is that, in order to find the factorization of a composite N, Shor's algorithm requires an amount of qubits (let call it q) such that N^2 =< 2^q =< 2N^2.
Right now RSA is at most at 4096 bits, so q=8192 could be enough.
- abdullahkhalids 8y agoFor building a quantum computer a distinction is made between logical qubits and physical qubits. The physical qubits correspond 1-to-1 with the underlying physical media i.e. each electron spin makes one physical qubit. The physical qubits have a lot of noise, so can't be used directly to do computation. Instead you do error correction on many (3 to millions or more) physical qubits to make one logical qubit that is noise free. These logical qubits are then used to do the actual computation. Your estimate of q=8192 is for logical qubits. The actual physical qubits will realistically go to millions, unless some really fundamental breakthroughs are made.
- throwawaymath 8y agoIf you'd like a specific, authoritative citation confirming what the other responder is saying, read the National Academies 2019 report on QC.