3 ms·

> whether there exist computational problems for which classical computers demonstrate exponential growth in time complexity, but quantum computers show sub-exp

> whether there exist computational problems for which classical computers demonstrate exponential growth in time complexity, but quantum computers show sub-exponential growth. > It remains unclear whether even this is possible "Quantum supremacy" by this definition has already been experimentally demonstrated, and it's not a high bar to meet. Like saying that if I let go of a feather in a windy area and measure how long it takes to fall to the ground with a stopwatch, that is "feather drop timing supremacy" because I have solved the problem of determining how long the feather takes to fall easily, while a classical computer would need to do complex physics simulations to get the same result. What is hard and interesting is to find a useful computational problem for which quantum computers are much better than classical ones.

krastanov 4y ago
I think you are having a relatively common misunderstanding. Indeed, just having some analog process run itself is a boring example of "supremacy". https://www.smbc-comics.com/comic/2013-07-19 https://www.smbc-comics.com/comic/2013-07-19 A "useful" computation is indeed the important final proof of supremacy. But intermediary results of "programmable" but useless computation is a pretty amazing achievement on its own, and it is not just "an analog process running itself". The distinction is described quite well here and it really matters to computational complexity theory https://scottaaronson.blog/?p=5460 https://scottaaronson.blog/?p=5460
andrewla 4y ago
I agree that this is the problem that we are effectively trying to solve. The problem with the feather analogy is that there's an initial condition problem that is basically unresolvable. Replicating them in such a way that the result of physically dropping the feather is identical between runs of this computer is far beyond intractable, much less representing them in such a way that you can compare the output of a classical computer in this regard. The NMR results from factoring 15 [1] are incredibly fascinating. Here the quantum computer is just a molecule, and using NMR we can get a precise view of the initial conditions and the time evolution. We're just asking the molecule to molecule itself and measuring the outcome. This unfortunately does not appear to scale, so it's impossible to say if we are demonstrating quantum supremacy, but the experimental design blows my mind. [1] https://cryptome.org/shor-nature.pdf https://cryptome.org/shor-nature.pdf

krastanov 4y ago

I think you are having a relatively common misunderstanding. Indeed, just having some analog process run itself is a boring example of "supremacy". https://www.smbc-comics.com/comic/2013-07-19 https://www.smbc-comics.com/comic/2013-07-19 A "useful" computation is indeed the important final proof of supremacy. But intermediary results of "programmable" but useless computation is a pretty amazing achievement on its own, and it is not just "an analog process running itself". The distinction is described quite well here and it really matters to computational complexity theory https://scottaaronson.blog/?p=5460 https://scottaaronson.blog/?p=5460

andrewla 4y ago

I agree that this is the problem that we are effectively trying to solve. The problem with the feather analogy is that there's an initial condition problem that is basically unresolvable. Replicating them in such a way that the result of physically dropping the feather is identical between runs of this computer is far beyond intractable, much less representing them in such a way that you can compare the output of a classical computer in this regard. The NMR results from factoring 15 [1] are incredibly fascinating. Here the quantum computer is just a molecule, and using NMR we can get a precise view of the initial conditions and the time evolution. We're just asking the molecule to molecule itself and measuring the outcome. This unfortunately does not appear to scale, so it's impossible to say if we are demonstrating quantum supremacy, but the experimental design blows my mind. [1] https://cryptome.org/shor-nature.pdf https://cryptome.org/shor-nature.pdf