Re: Is Intel exceptionally unsuccessful as an architecture designer?

On 19/09/2024 12:59, Terje Mathisen wrote:

David Brown wrote:

On 19/09/2024 09:44, Niklas Holsti wrote:

On 2024-09-19 2:47, Lawrence D'Oliveiro wrote:

On Wed, 18 Sep 2024 20:09:53 GMT, Anton Ertl wrote:
>

He mentioned that several physics breakthroughs
are needed for quantum computing to become useful.

>
The biggest one would be getting around the fundamental problem that you
can’t get something for nothing.

>
>
Stupid argument. Look at the effort and tech it takes to make quantum computers... that is not "nothing".
>
>

The promise of an exponential increase in computing power for a linear
increase in the number of processing elements sounds very much like
“something for nothing” under another name, wouldn’t you say?

>
>
No, it is exploiting the very non-intuitive nature of quantum entanglement to create an exponential number of collective states of a linear number of elements. Medieval arguments about "nothing" vs "something" don't work there.
>

>
Quantum computing certainly gives you some tricks that are hard to replicate with classical computers.  (And of course some quantum effects are impossible to replicate classically, but those are not actually computations.)
>
But it is still ultimately limited in many ways.  Landauer's principle about the minimal energy costs of calculations applies equally to quantum calculations.
>
The practical limitations for quantum computers are far more significant.  Roughly speaking, when you entangle more states at once, you need tighter tolerances to maintain coherence, which translates to lower temperatures, higher energy costs, and lower times to do your calculations.  And to be useful, you need large numbers of qubits, which again makes maintaining coherence increasingly difficult.
>
I'm sure that there will be breakthroughs that improve some of this, but I am not holding my breath - I don't believe quantum computers will ever be cost-effective for anything but a few very niche problems.  Currently they have only beat classical computers in tasks that involve simulating some quantum effects.  That's a bit like noticing that soap bubble computers are really good at solving 2D minimal energy surface problems.
>
Remember, the current record for Shor's algorithm is factorising 21 into 3 x 7.  Factorising 35 is still beyond current engineering levels.
>

  From my recent reading, it seems like factoring 21 (5 bits) requires at least 5+10=15 bits all staying entangled, plus a number of additional bits for error correction. I'm guessing you also need some extra bits/redundancy in order to successfully read out the results?

This was done with a quantum computer designed specifically for that one task, and simplified with the knowledge of the answer.  Even then, these machines just give you a result that /might/ be the correct answer - you have to check it externally to be sure.  (Of course for integer factorisation, checking a possible answer is a lot easier than finding plausible answers.)

 Getting to at the very least 3K entangled bits in order to speed up RSA 1024 decryption will certainly be out of the question for the remainder of my professional career, and most probably also the rest of my life.
 

According to someone on the internet (that ever-reliable source of information), an n-bit integer takes 2n + 2 fully entangled qubits and 448.n³.log(n) gates.  For 1024-bit RSA, that's 2050 logical qubits and about 5×10e12 gates.    For the common default size of 2048-bit RSA, it's 4098 logical qubits and 4.2×10e13 gates.
Then you need the quantum error correction in addition.  I am not at all convinced that I understand the details here or if I am applying them correctly, but I think that for larger systems you need perhaps 1000 physical qubits per logical qubit.
So for your 1024-bit RSA, your need a 2 million qubit monster with all 2000 logical qubits fully entangled (most quantum computers today with more than a few tens of qubits are not fully entangled - 51 fully entangled qubits was the biggest I read about).  And you need to keep it coherent for 72n³ cycles - 72 gigacycles - for the algorithm.  Top speeds today are 1.4 MHz, with perhaps 4 MHz being practically feasible, assuming only two-qubit gates are needed.  That gives 5.4 hours, without considering the extra time delays of the quantum error correction (which I'm sure are very significant).  Current coherence time records are measured in microseconds or perhaps milliseconds.  (Some other types of quantum computers have longer coherence times, but correspondingly slower cycle speeds.)
So using Shor's algorithm to break 1024-bit RSA requires a scaling of 20,000 in qubit counts and 20,000,000 in coherence time and/or cycle speed.  Moving to the common high-security size of 4096-bit adds another factor of 64 to each of these, and RSA easily scales much higher than that.
I don't believe any of us need to worry about quantum computers breaking RSA for a while yet.
(Of course someone might come up with a new algorithm, either classical or quantum, that changes the game.)