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.
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 ?
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.
>
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).
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:
According to 't Hooft himself (source: 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.".
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".
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).
I 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.
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.
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).
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.
Damn. And I just spent 10 minutes trying to explain quantum supremacy to 6 year old.
It sounds like a cross between a Bond and Bourne movie.
Coming to theater near you.
It’s still time well spent!
https://arxiv.org/abs/1704.00690
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 ?
Only if you assume that the classical counterparts of it are optimal. There's no proof of that.
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.
> 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).
You still have the case of a list of perfect random numbers. There is nothing in the box then.
But perfect random numbers cannot be evaluated by an algorithm. Evaluating the black box/oracle must be done in a run of Grovers's algorithm.
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
I don't think there are many doubts that quantum computers are more powerful than classical in specific areas, or am I wrong?
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.
While t Hooft is a genius, this particular work of his is not taken very seriously by most researchers.
> 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
According to 't Hooft himself (source: 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.".
Controversial is not the same as “not taken seriously”. It’s really fringe.
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".
This isn't even a real-world example. It's yet another circuit on paper.
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...
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).
I’m well aware. I just don’t think that we’ve given analog error correction good enough of a shake.
Why don't we start with classical systems then?
I don't understand why you would publish this in nature instead of FOCs/STOC
I 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.
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.
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).