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.
arXiv comments
To appear in: Hemmo, Meir and Shenker, Orly (eds.) Quantum, Probability, Logic: Itamar Pitowsky's Work and Influence, Springer, Nature (2019), forthcoming
Journal reference
in: M. Hemmo, and O. Shenker,(eds.) Quantum, Probability, Logic: Itamar Pitowsky's Work and Influence, Springer(2020),pp. 399-422
Linked by 6 identifiable commenters in 6 comments across 6 threads, from Oct 2019 to Dec 2024. Found in 1 HN submission from Aug 2019 to Aug 2019. Open submission discussions.
In 2019 you asserted [1] that attempts of creating distance-5 surface code will fail. Do you think you were wrong? If so, what was your mistake and why do you think you made it? If not, what's the problem with the Google's results? Have your estimations of feasibility of quantum…
What does homeopathy need to move forward? What does perpetual motion machinery need to move forward? This is not totally fair; it is possible given certain independence assumptions. But they are likely not physically realizable. It is almost certain that even within our…
Here's a well-informed argument to that end: https://arxiv.org/abs/1908.02499 and a nuanced lay-opinion by the same author: https://gilkalai.wordpress.com/2022/05/26/waging-war-on-quan...
jlokier has explained this beautifully and in more detail than I would have known how. I will just add one thing: basically Quantum Supremacy is yet another test of QM. As long as quantum supremacy could not be demonstrated, there remained a possibility that QM was wrong in this…
Many commenters are comparing this to the time sharing era of classical computing. There is an important difference here: we knew that classical computers were useful at the time, even though many people failed to predict that they would become millions of times cheaper and…
I couldn't disagree with you more. The "author" you are referring to is: https://en.wikipedia.org/wiki/Gil_Kalai He is a multi-award winner, internationally recognized researcher with several dozen publications on mathematics and computer science. > The author raises points in…
In 2019 you asserted [1] that attempts of creating distance-5 surface code will fail. Do you think you were wrong? If so, what was your mistake and why do you think you made it? If not, what's the problem with the Google's results? Have your estimations of feasibility of quantum…
EvgeniyZhView on HNParent context