These seem to be much stronger claims than were made last time this was discussed:
”””While our processor takes about 200 seconds to sample one instance of the quantum circuit 1 million times, a state-of-the-art supercomputer would require approximately 10,000 years to perform the equivalent task.”””
”””Quantum processors based on superconducting qubits can now perform computations in a Hilbert space of dimension 2^53 ≈ 9 × 10^15, beyond the reach of the fastest classical supercomputers available today. To our knowledge, this experiment marks the first computation that can only be performed on a quantum processor. Quantum processors have thus reached the regime of quantum supremacy. We expect their computational power will continue to grow at a double exponential rate: the classical cost of simulating a quantum circuit increases exponentially with computational volume, and hardware improvements will likely follow a quantum-processor equivalent of Moore’s law [52, 53], doubling this computational volume every few years. To sustain the double exponential growth rate and to eventually offer the computational volume needed to run well-known quantum algorithms, such as the Shor or Grover algorithms [19, 54], the engineering of quantum error correction will have to become a focus of attention.
The “Extended Church-Turing Thesis” formulated by Bernstein and Vazirani [55] asserts that any “reasonable” model of computation can be efficiently simulated by a Turing machine. Our experiment suggests that a model of computation may now be available that violates this assertion. We have performed random quantum circuit sampling in polynomial time with a physically realized quantum processor (with sufficiently low error rates), yet no efficient method is known to exist for classical computing machinery. As a result of these developments, quantum computing is transitioning from a research topic to a technology that unlocks new computational capabilities. We are only one creative algorithm away from valuable near-term applications.”””
Yes, quantum supremacy disproves the extended church-turing thesis (Bernstein-Vazirani). This thesis states that any computation that can be computed efficiently can be computed efficiently with a classical computer (ie a Turing machine).
ECT thesis means that quantum computers will never be able to compute something significantly faster that classical ones.
However, technically, google haven't proved yet quantum supremacy since they just did the classical calculation using the best known classical algorithm. And there is no proof that there is no significantly better algorithm.
But this not a serious objection, no one thinks that there is an exponentially better way of classically simulating quantum computers.
> However, technically, google haven't proved yet quantum supremacy
To be absolutely clear, an experiment (or a set of replicated experiments) can't prove quantum supremacy. Quantum supremacy is a statement about about the asymptotic behavior of quantum and classical computers, and obviously, a finite set of data points cannot prove anything about asymptotes.
What these experiments are doing are gathering evidence against the extended Church-Turing thesis - in the same way other experiments are used to gather evidence in favor of/against general relativity or some other physical theory.
The proof of quantum supremacy within the framework of the currently accepted laws of physics (quantum theory), has to be a mathematical proof. Currently, we have no idea how to construct such a proof.
”””While our processor takes about 200 seconds to sample one instance of the quantum circuit 1 million times, a state-of-the-art supercomputer would require approximately 10,000 years to perform the equivalent task.”””
”””Quantum processors based on superconducting qubits can now perform computations in a Hilbert space of dimension 2^53 ≈ 9 × 10^15, beyond the reach of the fastest classical supercomputers available today. To our knowledge, this experiment marks the first computation that can only be performed on a quantum processor. Quantum processors have thus reached the regime of quantum supremacy. We expect their computational power will continue to grow at a double exponential rate: the classical cost of simulating a quantum circuit increases exponentially with computational volume, and hardware improvements will likely follow a quantum-processor equivalent of Moore’s law [52, 53], doubling this computational volume every few years. To sustain the double exponential growth rate and to eventually offer the computational volume needed to run well-known quantum algorithms, such as the Shor or Grover algorithms [19, 54], the engineering of quantum error correction will have to become a focus of attention.
The “Extended Church-Turing Thesis” formulated by Bernstein and Vazirani [55] asserts that any “reasonable” model of computation can be efficiently simulated by a Turing machine. Our experiment suggests that a model of computation may now be available that violates this assertion. We have performed random quantum circuit sampling in polynomial time with a physically realized quantum processor (with sufficiently low error rates), yet no efficient method is known to exist for classical computing machinery. As a result of these developments, quantum computing is transitioning from a research topic to a technology that unlocks new computational capabilities. We are only one creative algorithm away from valuable near-term applications.”””