Researchers Prove Quantum Computers Are More Powerful Than Classical Computers

[camillomiller]

In case anyone's wondering: this is not Quantum Supremacy, yet. Just theoretical proof of a quantum advantage of quantum calculators over binary computer for some specific subset of problems. Very interesting nonetheless.

[thechao]

Damn. And I just spent 10 minutes trying to explain quantum supremacy to 6 year old.

[omazurov]

https://arxiv.org/abs/1704.00690

[utopcell]

Is it the case that a logarithmic gap is shown for a specific problem ? Why is this a big deal ? Doesn't Grover's algorithm already demonstrate a sqrt(n) gap ?

[kakaorka]

I don't think there are many doubts that quantum computers are more powerful than classical in specific areas, or am I wrong?

[wolfgke]

If you believe in the Cellular Automaton Interpretation of Quantum Mechanics by the Nobel laureate Gerard 't Hooft (which is somewhat controversial among physicists), building a sufficiently large quantum computer will probably be impossible. His book is available for free:

> https://link.springer.com/book/10.1007%2F978-3-319-41285-6

Simply read section 5.8.

[abdullahkhalids]

It depends on what you mean by "doubts". In the strict mathematical proof sense, we don't know if quantum computers are more powerful than classical computers at any task. In other words, like many conjectures in complexity theory (like P!=NP), the statement BQP!=P is still a conjecture. But computer scientists have good reasons to think that these conjectures will be true, after many decades of grappling with these problems and failing to prove otherwise. Therefore, in this informal expert-feeling sense of the word, there are not many "doubts".

[stephengillie]

This isn't even a real-world example. It's yet another circuit on paper.

[adamnemecek]

Everyone talks about qubit quantum computers but I'm really souped for continuous variable quantum computers. https://en.wikipedia.org/wiki/Continuous-variable_quantum_in...

[krastanov]

This is more of a hardware implementation choice than anything else. On top of such hardware we are still going to implement "digital" systems of qubits (or qudits).

I work at the Yale Quantum Institute, and people here are some of the bigger proponents of continuous variable quantum hardware. It is a fascinating design choice, but the final goal is the same: make something error corrected and qubit-like.

The reason for this is that you need to switch to digital if you want to be able to scalably correct errors (there is no such thing as scalable analog error correction).

[skeptic_69]

I don't understand why you would publish this in nature instead of FOCs/STOC

[anon4738383]

To be clear, Turing complete is Turing complete... quantum or classical, they are both general purpose, eg, able to execute an instruction set operating on fixed-sized integers. Certainly there will be improvements on classical code using quantum algorithms, but those will be reasonably-simulatable on classical computers... implying that quantum computers aren't necessarily special in terms of functionality, only in potential runtime and, for now, restriction to special-purpose acceleration of some classical operations.

Certainly, quantum computers will be advantaged in terms of theoretical and, likely, practical runtime of algorithms and code compared to classical computers.

[hadsed]

Well i think that has a twinge of negativity to it. I think what people forget is how important simulating quantum physical/chemical systems is. That's a problem that is extremely intensive even with our large numbers of approximate algorithms on supercomputers. At the moment you need almost a PhD in both high performance computing and the science to get anywhere. But what if physicists and engineers could simulate a complex quantum chemistry experiment in a Mathematica notebook? I imagine it'll change industries (think about how many engineers there are now that are effective with basic off the shelf AI tech right now).