Researchers Prove Quantum Computers Are More Powerful Than Classical Computers

https://motherboard.vice.com/amp/en_us/article/evw93z/researchers-finally-proved-quantum-computers-are-more-powerful-than-classical-computers?__twitter_impression=true

by Osiris30 • 8 years ago

75 27 8 years ago

motherboard.vice.com

camillomiller2• 8 years ago

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• 8 years ago

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

quickthrower2• 8 years ago

It sounds like a cross between a Bond and Bourne movie.

camillomiller2• 8 years ago

It’s still time well spent!

kakaorka• 8 years ago

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

abdullahkhalids• 8 years ago

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• 8 years ago

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

wolfgke4• 8 years ago

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.

krastanov2• 8 years ago

While t Hooft is a genius, this particular work of his is not taken very seriously by most researchers.

omazurov• 8 years ago

https://arxiv.org/abs/1704.00690

utopcell• 8 years ago

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 ?

213• 8 years ago

Grover is sqrt(n) versus n, this paper says for their problem is 1 (constant depth) versus log n:

In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit

chowells• 8 years ago

Only if you assume that the classical counterparts of it are optimal. There's no proof of that.

adamnemecek2• 8 years ago

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

krastanov2• 8 years ago

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).

adamnemecek2• 8 years ago

I’m well aware. I just don’t think that we’ve given analog error correction good enough of a shake.

anon4738383• 8 years ago

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• 8 years ago

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).

skeptic_69• 8 years ago

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

Researchers Prove Quantum Computers Are More Powerful Than Classical Computers

Related Stories