4 ms·
Researchers Prove Quantum Computers Are More Powerful Than Classical Computers
- camillomiller 8y agoIn 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 8y agoDamn. And I just spent 10 minutes trying to explain quantum supremacy to 6 year old.
- quickthrower2 8y agoIt sounds like a cross between a Bond and Bourne movie.
- mrhappyunhappy 8y agoComing to theater near you.
- camillomiller 8y agoIt’s still time well spent!
- mishurov 8y agoI wonder whether it is possible to exploit quantum superposition between measurements as a some sort of an activation function for deep learning for instance. It would be wonderful to discover the uses of the quantum gates beyond the current experience such as Shor's algorithm.
- kakaorka 8y agoI don't think there are many doubts that quantum computers are more powerful than classical in specific areas, or am I wrong?
- abdullahkhalids 8y agoIt 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 8y agoThis isn't even a real-world example. It's yet another circuit on paper.
- wolfgke 8y agoIf 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 https://link.springer.com/book/10.1007%2F978-3-319-41285-6 Simply read section 5.8.
- krastanov 8y agoWhile t Hooft is a genius, this particular work of his is not taken very seriously by most researchers.
- wolfgke 8y ago> While t Hooft is a genius, this particular work of his is not taken very seriously by most researchers. As I wrote: this work is controversial. For a very positive review, see for example > https://physicstoday.scitation.org/doi/10.1063/PT.3.3629 https://physicstoday.scitation.org/doi/10.1063/PT.3.3629 According to 't Hooft himself (source: https://physicstoday.scitation.org/do/10.1063/PT.6.4.20170711a/full/ https://physicstoday.scitation.org/do/10.1063/PT.6.4.2017071...) "The response [by fellow researchers] has been very mixed. Many other researchers are clearly very skeptical. They should be, because there are important unanswered questions. Others have expressed their interest and support. What concerns me is that I haven’t yet found colleagues who completely understand my approach. And also, of course, I don’t know what they say behind my back.".
- omazurov 8y agohttps://arxiv.org/abs/1704.00690 https://arxiv.org/abs/1704.00690
- utopcell 8y agoIs 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 ?
- 21 8y agoGrover 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 8y agoOnly if you assume that the classical counterparts of it are optimal. There's no proof of that.
- 21 8y agoFor Groover algorithm, which is applied to the problem of search you can prove that there is no classical algorithm faster than O(N) - looking at each item in the worst case scenario.
- wolfgke 8y ago> For Groover algorithm, which is applied to the problem of search you can prove that there is no classical algorithm faster than O(N) - looking at each item in the worst case scenario. Assuming that you cannot "look into the black box of the oracle" (i.e. we are only allowed to use a given oracle to evaluate an item at an index).
- 21 8y agoYou still have the case of a list of perfect random numbers. There is nothing in the box then.
- adamnemecek 8y agoEveryone talks about qubit quantum computers but I'm really souped for continuous variable quantum computers. https://en.wikipedia.org/wiki/Continuous-variable_quantum_information https://en.wikipedia.org/wiki/Continuous-variable_quantum_in...
- krastanov 8y agoThis 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).
- adamnemecek 8y agoI’m well aware. I just don’t think that we’ve given analog error correction good enough of a shake.
- hexane360 8y agoWhy don't we start with classical systems then?
- anon4738383 8y agoTo 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 8y agoWell 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 8y agoI don't understand why you would publish this in nature instead of FOCs/STOC