The argument against quantum computers

DOI10.1007/978-3-030-34316-3_18MaRDI QIDQ5119671zbMATH OpenOpenAlexFDO

Authors Gil Kalai

Publication date 31 August 2020

Published in Jerusalem Studies in Philosophy and History of Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.02499

zbMATH Keywords

noise sensitivity and stabilityphysical Church-Turing thesisquantum computationquantum error-correction

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) General and philosophical questions in quantum theory (81P05) Quantum computation (81P68)

Abstract: We give a computational complexity argument against the feasibility of quantum computers. We identify a very low complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explain why it will allow neither good-quality quantum error-correction nor a demonstration of "quantum supremacy." Some general principles governing the behavior of noisy quantum systems are derived. Our work supports the "physical Church thesis" studied by Pitowsky (1990) and follows his vision of using abstract ideas about computation to study the performance of actual physical computers.

Recommendations

• The quantum computer puzzle
• Complexity-theoretic foundations of quantum supremacy experiments
• Quantum computing
• Quantum Complexity Theory
• Introduction to Special Section on Quantum Computation

Cites work

• R(4, 5) = 25
• A counterexample to Borsuk’s conjecture
• Correlation polytopes: Their geometry and complexity
• Error Correcting Codes in Quantum Theory
• scientific article; zbMATH DE number 1559533 (Why is no real title available?)
• Mathematics and computation. A theory revolutionizing technology and science
• Noise sensitivity of Boolean functions and applications to percolation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum computing: pro and con
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Resilient quantum computation: error models and thresholds
• Symplectic geometry of quantum noise
• The computational complexity of linear optics
• The quantum computer puzzle

Cited in

(6)

• Full key recovery side-channel attack against ephemeral SIKE on the cortex-M4
• The quantum computer puzzle
• Multilinear formulas and skepticism of quantum computing
• Complexity-theoretic foundations of quantum supremacy experiments
• Anti-heterotic computing
• Noise analysis for the sorkin and Peres tests performed on a quantum computer

This page was built for publication: The argument against quantum computers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5119671)