Quantum Supremacy Measure

A Quantum Supremacy Measure is a computing measure which demonstrates that a programmable quantum device can solve a problem that classical computers practically cannot.

• See: Quantum Computing, Computational Complexity Theory, Time Complexity, Quantum Circuit.

---

---

References

2020

• (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/quantum_supremacy Retrieved:2020-1-14.
  • In quantum computing, quantum supremacy is the goal of demonstrating that a programmable quantum device can solve a problem that classical computers practically cannot (irrespective of the usefulness of the problem). The term quantum eclipse is also suggested by Kevin Tian and Ewin Tang . By comparison, the weaker quantum advantage is the demonstration that a quantum device can solve a problem merely faster than classical computers. Conceptually, this goal involves both the engineering task of building a powerful quantum computer and the computational-complexity-theoretic task of finding a problem that can be solved with current technology and has a believed superpolynomial speedup over the best known or possible classical algorithm for that task. The term was originally popularized by John Preskill but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's (1980) and Richard Feynman's (1981) proposals of quantum computing. Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov, D-Wave's specialized frustrated cluster loop problems, and sampling the output of random quantum circuits. Like factoring integers, sampling the output distributions of random quantum circuits is believed to be hard for classical computers based on reasonable complexity assumptions. Google previously announced plans to demonstrate quantum supremacy before the end of 2017 by solving this problem with an array of 49 superconducting qubits. However, as of early January 2018, only Intel has announced such hardware. In October 2017, IBM demonstrated the simulation of 56 qubits on a conventional supercomputer, increasing the number of qubits needed for quantum supremacy. In November 2018, Google announced a partnership with NASA that would “analyze results from quantum circuits run on Google quantum processors, and ... provide comparisons with classical simulation to both support Google in validating its hardware and establish a baseline for quantum supremacy.” Theoretical work published in 2018 suggests that quantum supremacy should be possible with a "two-dimensional lattice of 7x7 qubits and around 40 clock cycles" if error rates can be pushed low enough. On June 18, 2019, Quanta Magazine suggested that quantum supremacy could happen in 2019, according to Neven's law. On September 20, 2019, the Financial Times reported that "Google claims to have reached quantum supremacy with an array of 54 q[u]bits out of which 53 were functional, which were used to perform a series of operations in 200 seconds that would take a supercomputer about 10,000 years to complete". On October 23, Google officially confirmed the claims. IBM responded by suggesting some of the claims are excessive, and suggested that it could take 2.5 days instead of 10,000 years.

---