6 ms·

Quantum Computing/Information researcher here. This article is largely garbage, the original (~2 month old) paper is surprisingly readable [0] and I suggest you

Quantum Computing/Information researcher here. This article is largely garbage, the original (~2 month old) paper is surprisingly readable [0] and I suggest you to check it out. Here's my $0.02: The efforts of the Google team is commendable in that they're trying to squeeze as much out of their noisy systems as possible until error correction is here (they need to, to justify their existence after all) and they are aware of the shortcomings of the paradigm. But personally I don't see anything useful coming out until error correction and number of qubits are improved many orders of magnitude to have fault tolerant QC. The jury is still out on their utility once realized; Shor's algorithm is an obvious one followed by quantum simulation algorithms that might benefit chemistry and fundamental physics, but it's not as big of a silver bullet as we thought before for simulation. Maybe someone can tell me what fast prime factorization is good for besides breaking encryption. Also IBM released a paper[1] recently making similar claims ("quantum advantage without complete error correction") which got obliterated by 2 back to back papers [2,3] that did what they did for much cheaper on a classical computer. [0]: https://arxiv.org/pdf/2304.11119.pdf https://arxiv.org/pdf/2304.11119.pdf [1]: https://www.nature.com/articles/s41586-023-06096-3 https://www.nature.com/articles/s41586-023-06096-3 [2]: https://arxiv.org/pdf/2306.14887.pdf https://arxiv.org/pdf/2306.14887.pdf [3]: https://arxiv.org/pdf/2306.16372.pdf https://arxiv.org/pdf/2306.16372.pdf

shawabawa3 3y ago
> Maybe someone can tell me what fast prime factorization is good for besides breaking encryption. Maybe someone can tell me what alchemy is good for besides turning lead into gold?
- Retric 3y ago
  Prime factorization only breaks a subset of crypto algorithms, it’s not that useful or game changing alone.
- NooneAtAll3 3y ago
  considering that the world is transitioning to post-quantum crypto... everyone moved from gold to digital currencies, pretty much
zerodensity 3y ago
Questing regarding error correction and logical qbits. From my very limited understanding logical qbits could mitigate some of the error but uses multiple physical qbits for every logical qbits. Has anyone created a quantum computer that has logical qbits? Say a small one with 16 physical 4 logical qbits quantum computer, or similar.
- cohomologo 3y ago
  No, but the quantum groups are making progress towards essentially making 1 logical qubit -- a common scheme uses a square grid of physical qubits, say with size 7x7, 8x8, 9x9, etc.. as a single logical qubit. This may seem like a moving target, but it is not. There is a specific, concrete error rate on the physical qubits, below which it is known that the logical qubits on increasingly large grids get _exponentially_ more accurate. Once the engineering achieves that noise level, logical qubits in the form of NxN grids where N~10-20 will ~eventually~ follow. I won't venture to predict how long, as building and controlling these grids of qubits while keeping the error rate low isn't easy. Could be years or decades.
klyrs 3y ago
> Maybe someone can tell me what fast prime factorization is good for besides breaking encryption. That untapped market of trillionaire hobby number theorists?
imchillyb 3y ago
> I don't see anything useful coming out until error correction and number of qubits are improved many orders of magnitude to have fault tolerant QC. Error correction and control are vital for any system to be reliable. Thankfully the ability to run simultaneously and vet against multiple outputs should overcome this fault for a time.
- fsh 3y ago
  This doesn't work because the success probability drops exponentially in the length of the algorithm. It is possible that any real application requires quantum error correction which has not been demonstrated in any meaningful way.
avsteele 3y ago
Grover's algorithm seems quite useful, though I'd guess it requires an enormous number of qubits (large unordered database) to be useful.
- typon 3y ago
  What class of actually useful algorithms are limited by unordered search?
erikaww 3y ago
I'm not educated on QC. But wouldn't Grover's algorithm be very useful? I believe it provides a sqrt(n) time search. For QC to be useful,it just needs to make common utilities very fast. I should look more into QC. It would be cool if it could speed all computation up. I understand there are algorithms that it could execute that a classical composer could not, but I wonder if it could eventually he like just faster hardware.
- bawolff 3y ago
  I think you have to scale very big before that starts to matter.
- fsh 3y ago
  According to a recent article [1], quadratic quantum speedups are very unlikely to outperform classical computers in any application. This is assuming very optimistic parameters for future quantum computers. Grover's algorithm is therefore not considered useful in practice. [1] https://doi.org/10.1145/3571725 https://doi.org/10.1145/3571725
- ted_dunning 3y ago
  Most general purpose computing is based on algorithms that are essentially O(n). What that means is that they are a constant times the cost of simply reading the input. Often, the computation is actually cheaper. Quantum computing might make some computations have a smaller theoretical constant, but it is almost certain that the practical constant ($/bit of input) will be much, much worse due to scale. Right now, only very specialized computations look like they will ever have any speedup. And even that is only maybe, in practice.
- pclmulqdq 3y ago
  To load those bits into your quantum computer, you need to spend O(n) time. Most practical searches are O(n).
  - bawolff 3y ago
    Not neccesarily, you can calculate them on the fly.
EvgeniyZh 3y ago
I don't agree. I do a bit of QC in my PhD, but my advisor works specifically on error mitigation, and from what I see, we'll soon (maybe a couple of years) be there: we'll have state-of-the-art simulations on quantum computer. There will be classical simulations that will improve on a specific claim, but eventually they'll die out. But even if it is not true, think how good can be QC without being good enough for quantum error correction. You're saying orders of magnitude improvements are needed to be able to do EC, but I'm sure useful and interesting things can be done with log(QV) of 100, only 5 times more than current record.
- deepburner 3y ago
  You're talking in very vague terms here, what does """interesting""" mean? Let me give you some numbers. Factorising RSA is order 10^6 logical qubits (and I'm being charitable here), simulating FoMoCo is around 10^7. The state of the art error correction is around (again, charitably) 10^3 physical qubits per logical qubit at the moment, that gives us 10^9-10^10 qubits necessary for the simplest quantum application. We're at order 100 right now. Peter Shot thinks that error correction can go down to 100 physical-per-logical, that's an order of magnitude shaved off there, but the algorithm itself is pretty basic, i don't see it getting any better there. Simulation algorithms have much better odds in seeing improvements as I think the gates used there are rather non-standard and have avenues for better gate compilation techniques.
  - EvgeniyZh 3y ago
    Well, I was talking specifically simulations of quantum systems (physical and chemical). Interesting is indeed vague, what I meant systems that people study outside of attempt to create a hard-to-simulate (classically) quantum system. Say, 2D Hubbard model or some 2D topological insulator. Optimization (VQE, QAOA and stuff like that) also is realizable on NISQ. I'm more sceptical about its usefulness but it is hard to say. Shor's algorithms is definitely outside of NISQ, I don't think anyone serious about QC thinks otherwise. From there to "no applications for NISQ" is a far fetch.
IAmGraydon 3y ago
Thanks for your input. Can we all take a moment to recognize what a rare and special corner of the internet HackerNews is? Here we have an article on a highly advanced topic and lo and behold a researcher in the field shows up to add clarity. In a mess of advertising and misinformation that makes up the modern internet, it’s really an island of knowledge and experience that I hope we all truly appreciate.

shawabawa3 3y ago

> Maybe someone can tell me what fast prime factorization is good for besides breaking encryption. Maybe someone can tell me what alchemy is good for besides turning lead into gold?

Retric 3y ago
Prime factorization only breaks a subset of crypto algorithms, it’s not that useful or game changing alone.
NooneAtAll3 3y ago
considering that the world is transitioning to post-quantum crypto... everyone moved from gold to digital currencies, pretty much

zerodensity 3y ago

Questing regarding error correction and logical qbits. From my very limited understanding logical qbits could mitigate some of the error but uses multiple physical qbits for every logical qbits. Has anyone created a quantum computer that has logical qbits? Say a small one with 16 physical 4 logical qbits quantum computer, or similar.

cohomologo 3y ago
No, but the quantum groups are making progress towards essentially making 1 logical qubit -- a common scheme uses a square grid of physical qubits, say with size 7x7, 8x8, 9x9, etc.. as a single logical qubit. This may seem like a moving target, but it is not. There is a specific, concrete error rate on the physical qubits, below which it is known that the logical qubits on increasingly large grids get _exponentially_ more accurate. Once the engineering achieves that noise level, logical qubits in the form of NxN grids where N~10-20 will ~eventually~ follow. I won't venture to predict how long, as building and controlling these grids of qubits while keeping the error rate low isn't easy. Could be years or decades.

klyrs 3y ago

> Maybe someone can tell me what fast prime factorization is good for besides breaking encryption. That untapped market of trillionaire hobby number theorists?

imchillyb 3y ago

> I don't see anything useful coming out until error correction and number of qubits are improved many orders of magnitude to have fault tolerant QC. Error correction and control are vital for any system to be reliable. Thankfully the ability to run simultaneously and vet against multiple outputs should overcome this fault for a time.

fsh 3y ago
This doesn't work because the success probability drops exponentially in the length of the algorithm. It is possible that any real application requires quantum error correction which has not been demonstrated in any meaningful way.

avsteele 3y ago

Grover's algorithm seems quite useful, though I'd guess it requires an enormous number of qubits (large unordered database) to be useful.

typon 3y ago
What class of actually useful algorithms are limited by unordered search?

erikaww 3y ago

I'm not educated on QC. But wouldn't Grover's algorithm be very useful? I believe it provides a sqrt(n) time search. For QC to be useful,it just needs to make common utilities very fast. I should look more into QC. It would be cool if it could speed all computation up. I understand there are algorithms that it could execute that a classical composer could not, but I wonder if it could eventually he like just faster hardware.

bawolff 3y ago
I think you have to scale very big before that starts to matter.
fsh 3y ago
According to a recent article [1], quadratic quantum speedups are very unlikely to outperform classical computers in any application. This is assuming very optimistic parameters for future quantum computers. Grover's algorithm is therefore not considered useful in practice. [1] https://doi.org/10.1145/3571725 https://doi.org/10.1145/3571725
ted_dunning 3y ago
Most general purpose computing is based on algorithms that are essentially O(n). What that means is that they are a constant times the cost of simply reading the input. Often, the computation is actually cheaper. Quantum computing might make some computations have a smaller theoretical constant, but it is almost certain that the practical constant ($/bit of input) will be much, much worse due to scale. Right now, only very specialized computations look like they will ever have any speedup. And even that is only maybe, in practice.
pclmulqdq 3y ago
To load those bits into your quantum computer, you need to spend O(n) time. Most practical searches are O(n).
- bawolff 3y ago
  Not neccesarily, you can calculate them on the fly.

EvgeniyZh 3y ago

I don't agree. I do a bit of QC in my PhD, but my advisor works specifically on error mitigation, and from what I see, we'll soon (maybe a couple of years) be there: we'll have state-of-the-art simulations on quantum computer. There will be classical simulations that will improve on a specific claim, but eventually they'll die out. But even if it is not true, think how good can be QC without being good enough for quantum error correction. You're saying orders of magnitude improvements are needed to be able to do EC, but I'm sure useful and interesting things can be done with log(QV) of 100, only 5 times more than current record.

deepburner 3y ago
You're talking in very vague terms here, what does """interesting""" mean? Let me give you some numbers. Factorising RSA is order 10^6 logical qubits (and I'm being charitable here), simulating FoMoCo is around 10^7. The state of the art error correction is around (again, charitably) 10^3 physical qubits per logical qubit at the moment, that gives us 10^9-10^10 qubits necessary for the simplest quantum application. We're at order 100 right now. Peter Shot thinks that error correction can go down to 100 physical-per-logical, that's an order of magnitude shaved off there, but the algorithm itself is pretty basic, i don't see it getting any better there. Simulation algorithms have much better odds in seeing improvements as I think the gates used there are rather non-standard and have avenues for better gate compilation techniques.
- EvgeniyZh 3y ago
  Well, I was talking specifically simulations of quantum systems (physical and chemical). Interesting is indeed vague, what I meant systems that people study outside of attempt to create a hard-to-simulate (classically) quantum system. Say, 2D Hubbard model or some 2D topological insulator. Optimization (VQE, QAOA and stuff like that) also is realizable on NISQ. I'm more sceptical about its usefulness but it is hard to say. Shor's algorithms is definitely outside of NISQ, I don't think anyone serious about QC thinks otherwise. From there to "no applications for NISQ" is a far fetch.

IAmGraydon 3y ago

Thanks for your input. Can we all take a moment to recognize what a rare and special corner of the internet HackerNews is? Here we have an article on a highly advanced topic and lo and behold a researcher in the field shows up to add clarity. In a mess of advertising and misinformation that makes up the modern internet, it’s really an island of knowledge and experience that I hope we all truly appreciate.