21
$\begingroup$

Google recently announced that they have achieved "Quantum Supremacy": "that would be practically impossible for a classical machine."

Does this mean that they have definitely proved that BQP ≠ BPP ? And if that is the case, what are the implications for P ≠ NP ?

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ They have sampled from a random quantum circuit, which is suspected to be outside of $\mathrm{NP}$, based on theoretical work of others. They have not "definitely proved that $\mathrm{BQP}\ne\mathrm{BPP}$;" however, they have thrown down a gauntlet regarding the Extended Church-Turing Thesis $\endgroup$
    – Mark Spinelli
    Oct 23, 2019 at 16:05
  • $\begingroup$ @MarkS since this is not a decision problem, in what sense can one say the problem is P, NP, BQP etc.? $\endgroup$
    – user1936752
    Oct 23, 2019 at 16:32
  • 1
    $\begingroup$ @user1936752, well, a single solution - sample only one output $n$-bit string from a random quantum circuit of depth $m$, wherein the probability (amplitude squared) of the sampled string is greater than $1/2^n$ - is still likely a hard problem. See, for example, this question. You are right though - this is getting away from the OP. Can you ask another? Google's results challenge the hypothesis that it is physically impossible to build a scalable QC. $\endgroup$
    – Mark Spinelli
    Oct 23, 2019 at 18:18
  • 1
    $\begingroup$ @AlexKinman The Extended Church-Turing Thesis implies that all computational models have the same efficiency as those of a probabilistic Turing machine. A quantum computer (most likely) does not have the same efficiency as a probabilistic Turing machine. Google built a quantum computer, and showed that they performed a task in a manner orders of magnitude - indeed asymptotically faster - than a probabilistic Turing machine. There is no statement that Google performed a task that is formally undecidable - only that they asymptotically more efficient. $\endgroup$
    – Mark Spinelli
    Oct 25, 2019 at 1:59
  • 1
    $\begingroup$ @MarkS thanks. Now it makes sense. I was assuming that the Extended Church Turing thesis was the same as the Church–Turing–Deutsch principle, now I understand the difference. $\endgroup$
    – Alex Kinman
    Oct 25, 2019 at 3:13

2 Answers 2

Reset to default
16
$\begingroup$

Google's paper/results are kind of sideways to questions in computational complexity about the relation between $\mathrm{BPP}$ and $\mathrm{BQP}$ (and even further from questions about whether $\mathrm{P}\ne\mathrm{NP}$). It's more as if Google relies on the hypothesis that $\mathrm{BPP}\ne\mathrm{BQP}$ as evidence that their quantum computer performs a task many orders of magnitude faster than a classical computer could.

Google performed a sampling task on their quantum computer, that they have strong theoretical reasons to believe is not easily performed on a classical computer. If we say that these complexity classes live in some idealized platonic universe, then Google's results don't shed any light about the difficulty of proving whether or not they are equal to one another - because Google's paper assumes that they are not equal to one another.

What Google's paper does do, is provide evidence that the hypothesis that "a probabilistic Turing machine can efficiently simulate any realistic model of computation" is incorrect. They have prepared and maintained coherence of a state of their choosing in a Hilbert space of dimension $2^{53}$. As Aaronson argues, is akin to the Wright Flyer providing evidence that "heavier-than-air human-controlled powered flight is impossible" is incorrect.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @Mark S, How have Google's paper managed to provide evidence against the hypothesis that "a probabilistic Turing machine can efficiently simulate any realistic model of computation"? Pl. share relevant logic or parts of paper which show such evidence. $\endgroup$
    – Ashish
    Oct 24, 2019 at 11:47
  • 1
    $\begingroup$ @Ashish It's an interesting question about whether or how one can conclude that random circuit sampling helps invalidate the Extended Church-Turing Thesis (ECT) - I claim it does, but that seems separate from the OP's, which appears to be more along the lines of whether or how random circuit sampling helps validate that $\mathrm{BQP}\ne\mathrm{BPP}$ - I claim it doesn't. However, if you were to formally ask here a well-phrased question about random circuit sampling and the ECT, it might be well-received. $\endgroup$
    – Mark Spinelli
    Oct 24, 2019 at 13:38
  • 1
    $\begingroup$ @Ashish I don't know if I understand your question properly. let me try, since Random Circuit Sampling (RCS) is #P-hard (see here: arxiv.org/pdf/1803.04402.pdf) So, it is hard classically, and there is an efficient algorithm to compute it in quantum. RCS can be computed with few quibts, so it is very good candidate problem to put it in 'quantum supremacy' experiment. Assume that all complexity classes are hold, then by Google experiment, we know that ECT is no longer a true statement; since probabilistic TM cannot simulate RCS in best classical computer (this is a counterexample.) $\endgroup$
    – YOUSEFY
    Oct 29, 2019 at 10:09
3
$\begingroup$

Paraphrasing some tweets on the matter earlier, the result is rather underwhelming because it plays on a discrepancy between what they mean by quantum supremacy (QS) and what people tend to think QS means.

What I find most people think QS is supposed to mean, and what I assumed it meant until a month or so ago, was that there exists a computable problem (in the CTT sense of computation) and an actual quantum computer, such that, at some scales, the problem is tractable on the quantum computer but intractable on all classical computers.

The problem the Google QC folks have demonstrated is not computation in the CTT sense. It is a physical process of sampling that involves computations as part of the process, and as with any physical process, it can be simulated approximately by computation. They have good reason to believe (proof? I'm not sure but it should reasonably be assumed true by default anyway) that computation to similate the process is going to be intractably slow. This is not surprising at all. It's a fundamental consequence of quantum mechanics that lots of physical processes will have that property.

That's not to say it's entirely uninteresting. There are likely useful applications of the sampling problem they implemented, and as I understand it, it provides examples of large classes of physical systems which are not amenable to efficient computational simulation. But it has nothing to do with whether or how soon a QC will be able to compete with a (classical, CTT) computer solving computable problems.

Improve this answer
$\endgroup$
19
  • 3
    $\begingroup$ I wouldn't say it's "underwhelming". What they mean by quantum supremacy is exactly what everyone in the community means with the term, and pretty much the kind of result that people (people working on the field I mean) expected from them. Also, they do solve a "computational problem", only it's a "sampling problem", which is a type of problem unfamiliar to many. Also, there are computational complexity results underlying the claim of hardness of solving this problem classically $\endgroup$
    – glS ♦
    Oct 24, 2019 at 9:35
  • 3
    $\begingroup$ I guess by "CTT" you mean "Church-Turing thesis". What do you mean exactly with "computation in the CTT" sense? That it's not a decision problem? $\endgroup$
    – glS ♦
    Oct 24, 2019 at 11:37
  • 2
    $\begingroup$ @R.. - Your answer seems to challenge whether or not sampling from a random quantum circuit qualifies as computation. Although this may be asked and answered as a separate question, it's not clear whether your answer addresses the OP's question: "Does this mean that they have definitely proved that BQP ≠ BPP ? And if that is the case, what are the implications for P ≠ NP ?" $\endgroup$
    – Mark Spinelli
    Oct 24, 2019 at 12:15
  • 5
    $\begingroup$ @R.. but results about sampling problems do tell you about what you call "CTT" complexity classes. For example, if you can classically solve the sampling problem of simulating a boson sampling device, then it has been proven (up to some reasonable cc assumptions) that the polynomial hierarchy collapses at the third level. Similar results hold for simulating random circuits, see e.g. Bouland et al. $\endgroup$
    – glS ♦
    Oct 24, 2019 at 15:37
  • 3
    $\begingroup$ It could be okay to say that serious supremacy requires deterministic output. However, Google's experiment is much closer to CS theory than just that physical systems can be hard to simulate. A system may be hard to simulate when it has too much state (like water flow) or when we don't know its dynamic (like neutron stars). But the dynamics of the Sycamore chip is totally nailed down, and its state is only 53 qubits, which is a lot like just 53 bits. Instead, Sycamore is serious evidence of a different regime of computational complexity. $\endgroup$
    – Greg Kuperberg
    Oct 31, 2019 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.