Will a quantum computer perform a calculation by 2026 that is impossible for any classical supercomputer?

Resolves yes if before 2026 a peer-reviewed publication demonstrates a quantum computer performing a calculation that is proven to be impossible for any existing classical supercomputer.

Get Ṁ600 play money
Sort by:

Since complexity theorists haven't actually proved P != NP, this raises a question which I don't see answered below about what counts as "proof".

For example, there have been claims in the past that BosonSampling like experiments have produced results unsimulatable by classical computers, which have then been countered by other teams creating new algorithms to simulate those experiments. How long does a claim have to go unchallenged to count?

predicts NO

@BoltonBailey And this is why I have so many limit orders on NO. Every quantum supremacy paper immediately becomes a target for computational groups to beat it with more sophisticated methods. When IBM published their most recent supremacy demonstration, it was less than one week before a preprint was put on arXiv which simulated the system using a tensor network approach.

"Proven to be impossible" is a bit vague. As of current understanding - any quantum calculation can be performed by any classical computer, but there might be calculations that take an unreasonable time using classical computers - years, decades or even thousands of years. However, such calculations are still theoretically possible, though impractical.

@ProjectVictory I second this question. Additionally, what about approximations? Suppose that you stipulate that whatever classical calculation is done must actually completely with results. Then do you accept algorithms which only approximate the quantum result?

@Pykess What I had in mind is that it performs a calculation that would not be feasible on a classical computer, ie it would take longer than the lifetime of the universe to compute.

@GabeGarboden Okay, so then I re-ask my point about approximations. Do you require that the classical counterpart be exact? Or if it made approximations in order to complete the calculation in a reasonable amount of time, would that suffice?

@Pykess It does not have to be exact, as long as it's shown the classical computer cannot come to a reasonable approximation within a reasonable expected time.

@GabeGarboden Thanks for the clarifications!

More related questions