Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What You Shouldn't Know About Quantum Computers

arxiv.org

Post reply on HN
Print view View original

71–80 of 104 posts

Re: What You Shouldn't Know About Quantum Computers

#71

Post by naasking »

bawolff wrote: post #56
blamestross wrote: post #11

You have to get to page 25 before it starts being honest about the fact quantum computing is a con. Important Nuance: the research is real, the science is real, but the narrative being sold about the future of quantum computing to ensnare investors is not a reasonable prediction and is a con.

To be fair, that doesn't really distinguish it from the rest of the industry. I would say the same thing about AI and (especially) blockchain.

> I would say the same thing about AI

AI has commercial applications right now. What commercial application is there for quantum computing right now?

Re: What You Shouldn't Know About Quantum Computers

#72

Post by jessriedel »

NickC25 wrote: post #52
cwillu wrote: post #47

Earlier quoted context omitted.

A QC that can't run Shor's algorithm is not a QC, as much as D-Wave screams and stamps their feet that it's not fair.

I'm a complete layman when it comes to Quantum Computing, but I thought Shor's algorithm is effectively the most basic usecase example of Quantum Computers? I'm confused here.

There are extant non-general purpose quantum computers that solve super esoteric useless math problems specially designed to be easy on these primitive quantum computers but infeasible on any classical computer. (This is “quantum supremacy” aka “quantum advantage”.) Furthermore, we expect to develop slightly less primitive quantum computers in the medium-term that can solve maybe-interesting quantum simulation questions without having the capability to run Shor’s algorithm (at least on an interestingly large integers). So no, Shor’s algorithm is not the most basic use case. It’s just one of the cleanest to understand.

Re: What You Shouldn't Know About Quantum Computers

#73

Post by jessriedel »

tedunangst wrote: post #65
jessriedel wrote: post #36

Earlier quoted context omitted.

Co-author of the paper here. The “largest integer factored” metric is terrible for several reasons, which is well recognized by researchers and is why people rarely publish those sorts of claims any more. Without net-positive error correction, it’s basically a function of how low your error rate is and how many bits that allows you to compute on with low chance of error, but as soon as the error rate crosses the faul…

Predictions as to the first coprime factored after it has been achieved? Will they publish just rsa-1024, or drop a whole load of factors all at once, eliminate the whole field?

My non-confident impression is that when fault tolerance is first achieved it will still be somewhat expensive to add qubits, so the size of the largest integers that are factorizable will grow roughly like “quantum Moore’s law”. Like maybe they double qubit count every year or two, and I think the length (in digits) of the largest factorizable integer will scale like that, modulo a root or square. I could be confused though.

Re: What You Shouldn't Know About Quantum Computers

#74

Post by bawolff »

naasking wrote: post #71
bawolff wrote: post #56

Earlier quoted context omitted.

To be fair, that doesn't really distinguish it from the rest of the industry. I would say the same thing about AI and (especially) blockchain.

> I would say the same thing about AI AI has commercial applications right now . What commercial application is there for quantum computing right now?

D-wave managed to sell some devices. I'm not clear on what they could be useful for, but they still managed to sell them.

Re: What You Shouldn't Know About Quantum Computers

#75

Post by bawolff »

shagie wrote: post #63
bawolff wrote: post #54

Earlier quoted context omitted.

> I am skeptical. 36 years is a long time, but in the past 10 years there hasn't been much progress: 36 years ago we didn't even know shor's algorithm existed, and didn't know quantum computers could non-exponentially factor integers at all. So in a certain sense, we have made infinite progress in the last 36 years. Who knows what could happen in the next 36. More generally, i think making science predictions that fa…

https://youtu.be/6qD9XElTpCE > Hear the story of Shor's Algorithm, straight from the source, Peter Shor. Shor's part of the story starts in '81. Though, I generally agree with the it is hard to make predictions that far out. We've got the math to do some higher things, but we still don't have flying cars and fusion power.

Shor being alive in 1981 is not the same thing as saying shor's algorithm was discovered in 1981.

Re: What You Shouldn't Know About Quantum Computers

#77

Post by vlovich123 »

jessriedel wrote: post #72
NickC25 wrote: post #52

Earlier quoted context omitted.

I'm a complete layman when it comes to Quantum Computing, but I thought Shor's algorithm is effectively the most basic usecase example of Quantum Computers? I'm confused here.

There are extant non-general purpose quantum computers that solve super esoteric useless math problems specially designed to be easy on these primitive quantum computers but infeasible on any classical computer. (This is “quantum supremacy” aka “quantum advantage”.) Furthermore, we expect to develop slightly less primitive quantum computers in the medium-term that can solve maybe-interesting quantum simulation questi…

Is there any reason to believe a computer that can do Shor's algorithm is actually possible? There's a lot of freaking out trying to build QC-resistent assymetric encryption, but we don't actually know whether or not it's physically possible to build the requisite error corrections to make it feasible in the first place, right? Is there reason to believe that the physical reality of QM doesn't require exponentially more and more qbits for every logical qbit added to the system? Basically, is there any reason to believe that a QC capable of Shor's doesn't degrade to a space / time tradeoff for a classical computer when it comes to integer factorization?

Re: What You Shouldn't Know About Quantum Computers

#78

Post by shagie »

bawolff wrote: post #75
shagie wrote: post #63

Earlier quoted context omitted.

https://youtu.be/6qD9XElTpCE > Hear the story of Shor's Algorithm, straight from the source, Peter Shor. Shor's part of the story starts in '81. Though, I generally agree with the it is hard to make predictions that far out. We've got the math to do some higher things, but we still don't have flying cars and fusion power.

Shor being alive in 1981 is not the same thing as saying shor's algorithm was discovered in 1981.

The seeds of Shor's algorithm was when he went to a lecture on negative probability by Feynman in 1981 as a graduate student. Shor's part of the storm starts in 1981.

Re: What You Shouldn't Know About Quantum Computers

#79

Post by jessriedel »

vlovich123 wrote: post #77
jessriedel wrote: post #72

Earlier quoted context omitted.

There are extant non-general purpose quantum computers that solve super esoteric useless math problems specially designed to be easy on these primitive quantum computers but infeasible on any classical computer. (This is “quantum supremacy” aka “quantum advantage”.) Furthermore, we expect to develop slightly less primitive quantum computers in the medium-term that can solve maybe-interesting quantum simulation questi…

Is there any reason to believe a computer that can do Shor's algorithm is actually possible? There's a lot of freaking out trying to build QC-resistent assymetric encryption, but we don't actually know whether or not it's physically possible to build the requisite error corrections to make it feasible in the first place, right? Is there reason to believe that the physical reality of QM doesn't require exponentially m…

The strong expert consensus is that fault-tolerant quantum computation is physically possible and it’s just a challenging engineering problem. One key insight is the threshold theorems, which show that if you can build individual physical gates with error rate below a finite threshold (typically 0.1-1%), you can just stack these gates together and they simulate logical operations with logical error rates that can be made exponentially small.

https://en.wikipedia.org/wiki/Threshold_theorem

If it helps, there are plenty of historical analogies. Quantum-enhanced sensing took more than half a century between conception and practical use, but it is currently used daily at LIGO.

Re: What You Shouldn't Know About Quantum Computers

#80

Post by JanisErdmanis »

sebzim4500 wrote: post #43
JanisErdmanis wrote: post #23

Earlier quoted context omitted.

Quantum error correction produces logical qubits that have smaller nonzero error rate. Thus it needs to be applied repeatedly to achieve a necessary error rate to produce meaningful results. For Shor algorithm the error rate needs to decrease exponentially with the number of qubits. Thus even though IBM has a hundred qubits QCs they still only have managed to use five qubits to factorize a number 21.

>For Shor algorithm the error rate needs to decrease exponentially with the number of qubits I have never seen a result like that. Do you have a citation?

I have forgotten the source where I stumbled on the requirement for a qubit error rate to run the Shor algorithm. I would greatly value it if someone could put a key reference here.

A recent result considers a generic error model and a subclass for particular kinds of prime numbers [1]. The important result is $epsilon > cn^{−1/3}$ where epsilon represents qubit error rate and n number of bits in the factorised number. As $n = 2^N$ where N is a number of qubits, the result:

error_rate Therefore, the error rate must decrease exponentially with the number of logical qubits with which the computation is made.

[1]: https://arxiv.org/pdf/2306.10072

Post reply on HN