3 ms·

> Let’s remember that it took Google 53 qubits to create an application that could accomplish a supercomputer function. If we want to explore new applications t

> Let’s remember that it took Google 53 qubits to create an application that could accomplish a supercomputer function. If we want to explore new applications that go beyond today’s supercomputers, we’ll need to see system sizes that are orders of magnitude larger. Although the current order of magnitude (10s of qubits) are sufficient (on paper) for doing certain tasks faster than supercomputers of today, we need to go to 100-1000 qubits order for error-corrected results. Maintaining coherence for long enough to be able to do useful calculations in 10s of qubits has still been a challenge, let alone the designs for 100s of qubits.

andrewla 4y ago
> Let’s remember that it took Google 53 qubits to create an application that could accomplish a supercomputer function. If we want to explore new applications that go beyond today’s supercomputers, we’ll need to see system sizes that are orders of magnitude larger. And it turns out that Google didn't even do that. Further research [1] has indicated that the suspected case of quantum supremacy was not valid, as the problem can be solved classically without a supercomputer. So we have yet to see a demonstration of quantum supremacy from an NISQ system. [1] https://gilkalai.wordpress.com/2022/08/06/ordinary-computers-can-beat-googles-quantum-computer-after-all/ https://gilkalai.wordpress.com/2022/08/06/ordinary-computers...
- edgyquant 4y ago
  What are the odds quantum algorithms end up as a no true Scotsman (but without the fallacy) where everyone found turns out to have some classical workaround/solution?
  - andrewla 4y ago
    I think this is a likely outcome, and it's a reason why we should be continuing research into so-called "post-quantum" cryptosystems. Where there exists a low-cost quantum computing algorithm, it seems possible that there is a similarly low-cost probablistic algorithm. Randomized and probablistic algorithms are in my opinion the most important area for future development in computer science. One hope is that the vocabulary and syntax of quantum computing can be used to create classical probablistic simulations directly that will result in solving all but the most combinatorially explosive cases of various problems.
    - krastanov 4y ago
      No, it really does not seem like a likely outcome. There are way too many small "coincidences" that point to a substantial separation between complexity classes like BQP and BPP. On the other hand, it is indeed incredibly exciting to see all the progress in derandomization of classical probabilistic algorithms and de-quantization of some quantum algorithms (in particular, all the initial ideas in quantum machine learning). Also, it seems most computational complexity theorists do not believe probabilistic algorithms (BPP) are more powerful than deterministic ones (P), and the details of this process of de-randomization are absolutely fascinating. E.g. how we found a deterministic prime-testing algorithm after decades of relying on the random ones. Or deterministic algorithms for creation of expander graphs. There is no equivalent to such derandomization techniques in the quantum case. Quantum and classical probabilities are just too different. Also, post-quantum cryptosystems have very little to do with finding classical counterparts of quantum algorithms.
  - krastanov 4y ago
    If that happens, that would be absolutely monumental discovery, not just for CS, but for fundamental physics. I am a researcher working on building quantum computer hardware. If the whole premise of my career vanishes one day because Computational Complexity theorists find a way to prove that BQP as a complexity class is not more powerful than BPP, I would be *happier* than if I successfully build a quantum computer (although I probably would need to find a different job at that point). Such a discovery would shatter our understanding of the physical world and of abstract mathematics.
    - edgyquant 4y ago
      Yep this is what I expected but am not a physicist nor work on quantum computers. Thanks.
  - bawolff 4y ago
    I think the odds are 0 in general, but perhaps higher for many actually "useful" algorithms. Take grover's algorithm (basically find an item in a list or bruteforce something in O(sqrt(n)) time). The current best classical algorithm to bruteforce something is try every possibility, taking about n/2 guesses on average. The quantum version takes O(sqrt(n)). We are never going to be able to bruteforce with a normal computer faster than guessing all possibilities.
    - tsimionescu 4y ago
      Second edit: I just realized I am completely wrong in what I'm saying below. Grover's algorithm is indeed optimal, and there is no equivalent classical algorithm that can finish as fast. However, this has nothing to do with BPP vs BQP, since it is not doing any kind of exponential speed up - both Grover's algorithm and classical search are polynomial time algorithms. While this seems very likely, it has not yet been proven that unstructured search (the problem that Grover's algorithm solves) can't be solved by a probabilistic Turing machine in the same complexity with the same error bounds (that is, it's not proven that BPP != BQP). So even if this seems intuitively obvious, it has eluded any proof so far - which I think is interesting in itself. Edit: wording
      - bawolff 4y ago
        We are only talking about a polynomial speed up, so i dont think bqp vs bpp is relavent.
        tsimionescu 4y ago
        Yes, apologies, you are completely right and I amended my comment.
- krastanov 4y ago
  It is indeed incredibly exciting when better classical algorithms are found. But if Google were using 10 more qubits, then that classical algorithm would have failed. That is at the root of supremacy experiments: a minor increase in the number of qubits leads to exponential difficulty in classically faking the result. And that type of push-and-pull will continue for another few years until we have a "useful" example of supremacy. That does not de-value the current technology demonstrators that are paving the way.
  - andrewla 4y ago
    > But if Google were using 10 more qubits, then that classical algorithm would have failed That's a big maybe -- the paper that describes the classical algorithm indicates that they achieved significantly higher fidelity than that reported by the Sycamore paper, so it's unclear if the quantum computer was even giving valid results at more than 12-14 qubits.

andrewla 4y ago

> Let’s remember that it took Google 53 qubits to create an application that could accomplish a supercomputer function. If we want to explore new applications that go beyond today’s supercomputers, we’ll need to see system sizes that are orders of magnitude larger. And it turns out that Google didn't even do that. Further research [1] has indicated that the suspected case of quantum supremacy was not valid, as the problem can be solved classically without a supercomputer. So we have yet to see a demonstration of quantum supremacy from an NISQ system. [1] https://gilkalai.wordpress.com/2022/08/06/ordinary-computers-can-beat-googles-quantum-computer-after-all/ https://gilkalai.wordpress.com/2022/08/06/ordinary-computers...

edgyquant 4y ago
What are the odds quantum algorithms end up as a no true Scotsman (but without the fallacy) where everyone found turns out to have some classical workaround/solution?
- andrewla 4y ago
  I think this is a likely outcome, and it's a reason why we should be continuing research into so-called "post-quantum" cryptosystems. Where there exists a low-cost quantum computing algorithm, it seems possible that there is a similarly low-cost probablistic algorithm. Randomized and probablistic algorithms are in my opinion the most important area for future development in computer science. One hope is that the vocabulary and syntax of quantum computing can be used to create classical probablistic simulations directly that will result in solving all but the most combinatorially explosive cases of various problems.
  - krastanov 4y ago
    No, it really does not seem like a likely outcome. There are way too many small "coincidences" that point to a substantial separation between complexity classes like BQP and BPP. On the other hand, it is indeed incredibly exciting to see all the progress in derandomization of classical probabilistic algorithms and de-quantization of some quantum algorithms (in particular, all the initial ideas in quantum machine learning). Also, it seems most computational complexity theorists do not believe probabilistic algorithms (BPP) are more powerful than deterministic ones (P), and the details of this process of de-randomization are absolutely fascinating. E.g. how we found a deterministic prime-testing algorithm after decades of relying on the random ones. Or deterministic algorithms for creation of expander graphs. There is no equivalent to such derandomization techniques in the quantum case. Quantum and classical probabilities are just too different. Also, post-quantum cryptosystems have very little to do with finding classical counterparts of quantum algorithms.
- krastanov 4y ago
  If that happens, that would be absolutely monumental discovery, not just for CS, but for fundamental physics. I am a researcher working on building quantum computer hardware. If the whole premise of my career vanishes one day because Computational Complexity theorists find a way to prove that BQP as a complexity class is not more powerful than BPP, I would be *happier* than if I successfully build a quantum computer (although I probably would need to find a different job at that point). Such a discovery would shatter our understanding of the physical world and of abstract mathematics.
  - edgyquant 4y ago
    Yep this is what I expected but am not a physicist nor work on quantum computers. Thanks.
- bawolff 4y ago
  I think the odds are 0 in general, but perhaps higher for many actually "useful" algorithms. Take grover's algorithm (basically find an item in a list or bruteforce something in O(sqrt(n)) time). The current best classical algorithm to bruteforce something is try every possibility, taking about n/2 guesses on average. The quantum version takes O(sqrt(n)). We are never going to be able to bruteforce with a normal computer faster than guessing all possibilities.
  - tsimionescu 4y ago
    Second edit: I just realized I am completely wrong in what I'm saying below. Grover's algorithm is indeed optimal, and there is no equivalent classical algorithm that can finish as fast. However, this has nothing to do with BPP vs BQP, since it is not doing any kind of exponential speed up - both Grover's algorithm and classical search are polynomial time algorithms. While this seems very likely, it has not yet been proven that unstructured search (the problem that Grover's algorithm solves) can't be solved by a probabilistic Turing machine in the same complexity with the same error bounds (that is, it's not proven that BPP != BQP). So even if this seems intuitively obvious, it has eluded any proof so far - which I think is interesting in itself. Edit: wording
    - bawolff 4y ago
      We are only talking about a polynomial speed up, so i dont think bqp vs bpp is relavent.
      - tsimionescu 4y ago
        Yes, apologies, you are completely right and I amended my comment.
krastanov 4y ago
It is indeed incredibly exciting when better classical algorithms are found. But if Google were using 10 more qubits, then that classical algorithm would have failed. That is at the root of supremacy experiments: a minor increase in the number of qubits leads to exponential difficulty in classically faking the result. And that type of push-and-pull will continue for another few years until we have a "useful" example of supremacy. That does not de-value the current technology demonstrators that are paving the way.
- andrewla 4y ago
  > But if Google were using 10 more qubits, then that classical algorithm would have failed That's a big maybe -- the paper that describes the classical algorithm indicates that they achieved significantly higher fidelity than that reported by the Sycamore paper, so it's unclear if the quantum computer was even giving valid results at more than 12-14 qubits.