[deepburner]

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

[1]: https://www.nature.com/articles/s41586-023-06096-3

[2]: https://arxiv.org/pdf/2306.14887.pdf

[3]: https://arxiv.org/pdf/2306.16372.pdf

[zerodensity]

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]

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.

[EvgeniyZh]

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]

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]

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.

[erikaww]

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.

[ted_dunning]

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.

[fsh]

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

[pclmulqdq]

To load those bits into your quantum computer, you need to spend O(n) time. Most practical searches are O(n).

[bawolff]

Not neccesarily, you can calculate them on the fly.

[zerodensity]

How so you mean calculating them on the fly? You need to at least load the data to perform operations on it.

[bawolff]

Grover's algorithm does not require you to load the data to be searched through if it can be generated instead. Grover's algorithm is not neccesarily searching through a list but searching through the output of a function. Sure if your function is an array index operator you need to load the underlying data, but many large search problems are not that.

[zerodensity]

That clears that up thanks.

[bawolff]

I think you have to scale very big before that starts to matter.

[avsteele]

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

[typon]

What class of actually useful algorithms are limited by unordered search?

[imchillyb]

> 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]

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.

[IAmGraydon]

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]

> 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]

Prime factorization only breaks a subset of crypto algorithms, it’s not that useful or game changing alone.

[NooneAtAll3]

considering that the world is transitioning to post-quantum crypto... everyone moved from gold to digital currencies, pretty much

[klyrs]

> Maybe someone can tell me what fast prime factorization is good for besides breaking encryption.

That untapped market of trillionaire hobby number theorists?