Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1809.07442 · Nature

Quantum computational supremacy

Aram W. Harrow, Ashley Montanaro

Published Sep 1, 2017• 872 citations
arXivHTMLPDF
DOI
10.1038/nature23458

Related papers

The Road to Quantum Computational Supremacy

Cristian S. Calude, Elena Calude

arXiv:1712.01356•Springer proceedings in mathematics & statistics•Jan 1, 2020•23 citations

Quantum Supremacy and the Advancements in Quantum Computing

Rajit Nair, Ramgopal Kashyap, Preeti Sharma Nair

Lecture notes in networks and systems•Jan 1, 2026•0 citations

Quantum Supremacy: computational complexity and applications

P. Roushan

Bulletin of the American Physical Society•Mar 5, 2020•2 citations

The Argument against Quantum Computers, the Quantum Laws of Nature, and Google's Supremacy Claims

Gil Kalai

My 2018 lecture at the ICA workshop in Singapore dealt with quantum computation as a meeting point of the laws of computation and the laws of quantum mechanics. We described a computational complexity argument against the feasibility of quantum computers: we identified a very low-level complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explained why it would allow neither good-quality quantum error-correction nor a demonstration of "quantum supremacy," namely, the ability of quantum computers to make computations that are impossible or extremely hard for classical computers. We went on to describe general predictions arising from the argument and proposed general laws that manifest the failure of quantum computers. In October 2019, "Nature" published a paper describing an experimental work that took place at Google. The paper claims to demonstrate quantum (computational) supremacy on a 53-qubit quantum computer, thus clearly challenging my theory. In this paper, I will explain and discuss my work in the perspective of Google's supremacy claims.

arXiv:2008.05188•Aug 12, 2020•19 citations

Fundamentals of Quantum Computing, Quantum Supremacy, and Quantum Machine Learning

Kamaljit I. Lakhtaria, Vrunda Gadesha

When we aim to demonstrate that a programmable quantum device can solve complex problems which cannot be addressed by classic computers, this fundamental goal is known as quantum supremacy. This concept has changed every fundamental rule of computation. In this chapter, the detailed concept of quantum computing and quantum supremacy is explained along with various open source tools and real-time applications of this technology. The major base concepts, quantum computing, the difference between classical and quantum computer on physical level, programing quantum device, and the experiment-quantum supremacy are explained conceptually. This chapter also includes an introduction of the tools Cirq and OpenFermion plus the applications like quantum simulation, error mitigation technique, quantum machine learning, and quantum optimization, which are explained with illustrations.

Advances in information security, privacy, and ethics book series•Jan 1, 2021•0 citations

Quantum Computational Leverage

Peter P. Rohde

Cambridge University Press eBooks•Sep 9, 2021•0 citations
My 2018 lecture at the ICA workshop in Singapore dealt with quantum computation as a meeting point of the laws of computation and the laws of quantum mechanics. We described a computational complexity argument against the feasibility of quantum computers: we identified a very low-level complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explained why it would allow neither good-quality quantum error-correction nor a demonstration of "quantum supremacy," namely, the ability of quantum computers to make computations that are impossible or extremely hard for classical computers. We went on to describe general predictions arising from the argument and proposed general laws that manifest the failure of quantum computers. In October 2019, "Nature" published a paper describing an experimental work that took place at Google. The paper claims to demonstrate quantum (computational) supremacy on a 53-qubit quantum computer, thus clearly challenging my theory. In this paper, I will explain and discuss my work in the perspective of Google's supremacy claims.
When we aim to demonstrate that a programmable quantum device can solve complex problems which cannot be addressed by classic computers, this fundamental goal is known as quantum supremacy. This concept has changed every fundamental rule of computation. In this chapter, the detailed concept of quantum computing and quantum supremacy is explained along with various open source tools and real-time applications of this technology. The major base concepts, quantum computing, the difference between classical and quantum computer on physical level, programing quantum device, and the experiment-quantum supremacy are explained conceptually. This chapter also includes an introduction of the tools Cirq and OpenFermion plus the applications like quantum simulation, error mitigation technique, quantum machine learning, and quantum optimization, which are explained with illustrations.