Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: David Brown <david.brown@hesbynett.no>
Newsgroups: comp.arch
Subject: Re: Is Intel exceptionally unsuccessful as an architecture designer?
Date: Thu, 19 Sep 2024 16:15:09 +0200
Organization: A noiseless patient Spider
Lines: 114
Message-ID: <vchble$jie1$1@dont-email.me>
References: <memo.20240913205156.19028s@jgd.cix.co.uk>
 <vcd3ds$3o6ae$2@dont-email.me>
 <2935676af968e40e7cad204d40cafdcf@www.novabbs.org>
 <2024Sep18.074007@mips.complang.tuwien.ac.at> <vcds4i$3vato$1@dont-email.me>
 <2024Sep18.220953@mips.complang.tuwien.ac.at> <vcfopr$8glq$3@dont-email.me>
 <ll232oFs6asU1@mid.individual.net> <vcgr9d$gndp$2@dont-email.me>
 <vch06v$hq45$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 19 Sep 2024 16:15:10 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c725ff283502bbf48b983059d00c1d0e";
	logging-data="641473"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1945a8otm0VfNXM2ogDXeo2e3MsiV3Xp1I="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.11.0
Cancel-Lock: sha1:5jEukaWSe2MaKKRa81a4+OK2csI=
Content-Language: en-GB
In-Reply-To: <vch06v$hq45$1@dont-email.me>
Bytes: 6891

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.)