19
$\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 ?

$\endgroup$
  • 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 S Oct 23 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 at 16:32
  • $\begingroup$ @user1936752 well, you could, for example, state the problem as a search problem, given a random quantum circuit on $n$ qubits of depth $m=O(poly\:n)$, search for output strings that have an average cross-entropy fidelity of greater than (some reasonable number more than 0). See, for example, comment #13 on shtetl-optimized $\endgroup$ – Mark S Oct 23 at 18:00
  • 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 S Oct 23 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 S Oct 25 at 1:59
15
$\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.

$\endgroup$
  • 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 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 S Oct 24 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 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.

$\endgroup$
  • 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 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 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 S Oct 24 at 12:15
  • 2
    $\begingroup$ @glS: Decision problems, computable functions, etc. are equivalent, so whichever form you like. Sampling is not even a function, much less a computable one. It's a physical process outside the scope of computing/functions. $\endgroup$ – R.. Oct 24 at 15:00
  • 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 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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