Gil Kalai has just posted on his blog a series of videos of his lectures entitled “why quantum computers cannot work.” For those of us that have followed Gil’s position on this issue over the years, the content of the videos is not surprising. The surprising part is the superior production value relative to your typical videotaped lecture (at least for the first overview video).
I think the high gloss on these videos has the potential to sway low-information bystanders into thinking that there really is a debate about whether quantum computing is possible in principle. So let me be clear.
There is no debate! The expert consensus on the evidence is that large-scale quantum computation is possible in principle.
Quoting “expert consensus” like this is an appeal to authority, and my esteemed colleagues will rebuke me for not presenting the evidence. Aram has done an admirable job of presenting the evidence, but the unfortunate debate format distorts perception of the issue by creating the classic “two sides to a story” illusion. I think it’s best to be unequivocal to avoid misunderstanding.
The program that Gil lays forth is a speculative research agenda, devoid of any concrete microscopic physical predictions, and no physicist has investigated any of it because it is currently neither clear enough nor convincing enough. At the same time, it would be extremely interesting if it one day leads to a concrete conjectured model of physics in which quantum computers do not work. To make the ideas more credible, it would help to have a few-qubit model that is at least internally consistent, and even better, one that doesn’t contradict the dozens of on-going experiments. I genuinely hope that Gil or someone else can realize this thrilling possibility someday.
For now, though, the reality is that quantum computation continues to make exciting progress every year, both on theoretical and experimental levels, and we have every reason to believe that this steady progress will continue. Quantum theory firmly predicts (via the fault-tolerance threshold theorem) that large-scale quantum computation should be achievable if noise rates and correlations are low enough, and we are fast approaching the era where the experimentally achievable noise rates begin to touch the most optimistic threshold estimates. In parallel, the field continues to make contributions to other lines of research in high-energy physics, condensed matter, complexity theory, cryptography, signal processing, and many others. It’s an exciting time to be doing quantum physics.
And most importantly, we are open to being wrong. We all know what happens if you try to update your prior by conditioning on an outcome that had zero support. Gil and other quantum computing skeptics like Alicki play a vital role in helping us sharpen our arguments and remove any blind spots in our reasoning. But for now, the arguments against large-scale quantum computation are simply not convincing enough to draw more than an infinitesimal sliver of expert attention, and it’s likely to remain this way unless experimental progress starts to systematically falter or a concrete and consistent competing model of quantum noise is developed.
“we are fast approaching the era where the experimentally achievable noise rates begin to touch the most optimistic threshold estimates”
Some experts claim we have already reached this era:
http://arxiv.org/abs/1402.4848
I got about half way into part 1 before the video crapped out and I have a few questions. Sorry if he answers some of these.
Is professor Kalai proposing a modification of QM that does not allow quantum computing? I ask because he said he does not expect a mathematical proof that QC is impossible. I ask because QM is a mathematical theory about which you reason mathematically. If it does not allow QC then that fact should be derivable mathematically.
If he is proposing a modification of QM then what is his motivation for it? Is it simply to disable quantum computing? And does he even have a precise modification in mind?
He objects to QC because it breaks the connection between physics and geometry. But violating Bell’s inequality violates the connection between physics and geometry so…
He harps on a supposed difference between a general quantum computer and a quantum machine. But I don’t understand. A quantum computer running a particular program is just a quantum machine for that purpose isn’t it? A word processor is just a very capable typewriter.
It All Turns on Naturality (Part I)
Steve, please let me make the case (to students especially) that rational grounds exist to to disagree utterly with all six of the above statements.
Moreover, please let me assert (more broadly) that it is neither necessary, nor feasible, nor even desirable, that everyone think alike in regard to any of these six statements.
And finally&bnsp;— and most difficult of all&bnsp;— please let me make this case without personalization, sardonicism, rancor, or cherry-picking.
Because we’re talking about ideas, not individuals, right?
Warmup A recommended four-part counter-sardonic warmup is, first, to listen to the Van Cliburn Foundation’s playlist “2013 Cliburn Competition Competitors” (queue up all 30 videos, and reflect upon the sobering statistical realities of excelling as an artist/mathematician/scientist/engineer on a planet of 10^10 people). Second, listen to Wendell Berry’s 2012 Jefferson Lecture “It All Turns on Affection” (reflecting soberly upon the “marketplace of ideas”). Third, (re)read Clay Shirky’s much-discussed “The End of Higher Education’s Golden Age” (reflecting soberly upon how “Golden Ages” are created).
Fourth, and most important, (re)read Arthur Jaffe and Frank Quinn’s sardonic and sometimes-personal “‘Theoretical Mathematics’: Toward a Cultural Synthesis of Mathematics and Theoretical Physics” (arXiv:math/9307227), and Bill Thurston’s straightforwardly impersonal response “On Proof and Progress in Mathematics” (arXiv:math/9404236) (reflecting soberly that all of the Jaffe/Quinn/Thurston issues are in-play in the context of modern complexity theory and/or quantum computing).
These great works (Thurston’s especially) set the stage for us to appreciate the concluding remarks of Gil’s video lecture (minute 13:16 of “Why Topological Quantum Computers Cannot Work”)
In a Nutshell Gil Kalai brings the generous & vital spirit of Bill Thurston to discourse regarding quantum computing and complexity theory … and for this service we can all be grateful to Gil!
—–
Part II (to follow) From an engineering perspective, the formal elements of Gil’s “Smoothed Lindbladian” models already are widely and successfully applied … and these applications will be the subject of Part II.
LOL … one of the “thumbs-down” voters was me myself (I clicked the down-vote button to see what would happen). Fortunately, if science teaches us anything, it teaches us to accept reasoned differences of opinion con calma dignità e classe.
It All Turns on Naturality (Part II of II)
For the past decade, discourse relating to quantum computing has been (as it seems to me) dominated by the mathematical and scientific themes articulated two workshops — first, the “QIST: A Quantum Information Science and Technology Roadmap” workshops of 2002-2004, and second, the Simons Foundation’s “Algorithms and Complexity in Algebraic Geometry” (ongoing in 2014).
It is natural to regard the second as the continuation the first for two reasons: (1) no follow-up QIST workshops were ever held, and (2) in the past decade, a Grothendieck-style “rising tide” of varietal simulation capabilities has illuminated the QIST objectives in striking new ways. Our Soldier Healing Seminar’s 2013 “Green Sheet” notes survey this illumination concretely:
These math-and-physics considerations — which the Green Sheets develop at considerable length (with many references) — explain why we engineers respect comparably the QIST Roadmaps and the Kalai Postulates.
These considerations explain too, why we engineers (and medical researchers) embrace too the themes of the Simons Foundation’s “Algorithms and Complexity in Algebraic Geometry” workshops. For us there is less perceived need for “breakthroughs”, because for the past decade (and more) Grothendieck’s rising tide of mathematical understanding has been quietly covering broad classes of problems — in quantum simulation for example — that the QIST Roadmaps of 2002-4 regarded as intractable.
That is why we engineers respect comparably 20th century texts like Dirac’s (mathematically quaint!) Principles of Quantum Mechanics and Nielsen and Chuang’s Quantum Computation and Quantum Information, along with 21st century texts like Landsberg’s (mathematically tough!) Tensors: Geometry and Applications and Anashin and Khrennikov’s Applied Algebraic Dynamics.
The first two texts are polished diamonds (obviously), the second two texts are diamonds-in-the-rough (obviously) … and we are all of us lucky to be working in the century in which math-and-science gems are being that mined and polished. Obviously!
Conclusion “There’s plenty of room in the middle”, for plenty of folks to claim a respectable degree of credit for the growing illumination — to which we all contribute and in which we all share — in regard to quantum dynamics and its transformational 21st century applications.
As an historical aside, mathematicians tell mixed awe and horror the story of Alexander Grothendieck’s asking a baffling question “What is a meter”?
Purportedly it was Grothendieck’s fixed idea that the speed-of-light differed from 300,000 km/s only by “the work of the devil” … so much so, that Grothendieck had little tolerance for mathematical discussion with colleagues who disagreed. These discussions, mainly with Leila Schneps and Pierre Lochak took place in the mid-1990s (a Google search finds details).
Today, twenty years later, it is amusing that the International Committee for Weights and Measures will consider later this year defining $latex (hbar , c , e )$ to no longer be measurable quantities, but rather to have exact values established wholly by arbitrary convention. Precisely as Grothendieck foresaw!
Thus Grothendieck’s 1990s insight is vindicated. Indeed, when we regard measurement as a problem in quantum varietal dynamics, to be solved with maximal naturality and universality, it becomes scarcely possible to imagine that any other measurement convention(s) ever seemed sensible. And perhaps we are destined to experience similar Grothendieck-style attitude-shifts in regard to varietal dynamics more generally.
For context in the history of mathematics regarding the above comment, see paragraph ¶002 of page 2 of the Green Sheet Seminar Notes, which begins “La mer qi monte …”. See also Footnote “a” of Table 4, which begins “The ‘new SI’s’ mises en pratique …”.
These passages were revised to emphasize that quantum measurement triangles (QMTs) pull-back naturally onto varietal measurement triangles (VMTs), and to provide some history-of-mathematics context regarding this observation.
My views on quantum computing having garnered (thus far) ten up-votes and twenty-three down-votes, please allow me to commend to 10/(10+23) ~ 30% of Quantum Pontiff readers recent remarks on the (excellent!) Fortnow/GASARCH weblog topic The answer is either 0,1, or on the board in regard to Van Vleck’s dictum Man muss immer umkehren, naturalisieren, verallgemeinern (“One must invert, naturalize, and generalize”).
Quantum Pontiff readers who are comfortable with the quantum computing community’s emerging norm of “circle the wagons” discourse — which (as I perceive it) manifests itself concretely in the increasingly prevalent practices of personalization, sardonicism, anonymous downvoting, and censorship — perhaps are well-advised to *NOT* read the Fortnow/GASARCH comments, but rather content themselves with lessons-learned here at Quantum Pontiff.
I wonder if the question about whether QC “can work” in principle is the right question. By saying “can work” is the author asserting that QC can compute anything at all (seems likely that it can)? Or that QC can actually solve difficult problems much faster than classical computing (jury is very much out on this)?
Seems like an important distinction …
@Darrell, certainly a fully functioning quantum computer can compute anything that a classical computer can compute and vice versa. They are both “universal” in this sense. However, a classical computer will take exponentially more time to do some of these computations than the quantum computer. This is inarguably true given our current knowledge of classical algorithms.
There is an important technical detail in this last assertion based on computational complexity theory and related to the famous P vs NP problem. Basically, we don’t know how to prove general limits on most models of computation, so we can’t mathematically rule out that there is a totally remarkable classical algorithm that can simulate quantum computation efficiently. This seems like a very implausible speculation, though, to almost every expert in the field.
Buddha said, is to see the great value. Roughly speaking, these islands. We cannot tolerate excessive noise. What can be thinking? Scott, you hate!
Clay Millenium “Navier-Stokes Equation” problem. Nick, you may emerge soon; in the brain. These two young Hittite. What are properly called “heuristics”. So IMHO, all (well, almost finished with the differential and H. Friedan). I find ample empirical evidence of trying! Doh!
MIT Research has fundamental math, science, history, or I will become more sensitive. As Dick Lipton’s webblog provides mighty spooky and there are apt? It is beyond it comes to one article that the reader can be found in mathematics topic.
IMHO may I will ever fly in diameter.
LOL … “sidlesbot” your various keyword-vocabularies are both funny and genuinely informative … please keep them up-to-date in respect to Gödel’s Lost Letter comments on the topic “Multiple-Credit Tests“, as regards the MathOverflow question “For which Millennium Problems does undecidable -> true?”
Our Soldier Healing Seminar has counted the new/modified mathematical keywords that the “Green Sheet 2013” notes associate to varietal dynamics, over and beyond the keywords associated to Hilbert-space dynamics; there are about sixty such additional keywords … this is comparable to the number of new/modified keywords in C++ relative to C.
This reasonably reflects the effort required for students to acquire the idioms of varietal dynamics: it’s about as much work as learning C++ (starting with a knowledge of C).
Conclusion Continued posts by “sidlesbot” can be a funny, valuable contribution to quantum dynamical discourse, especially in regard to enhancing the mathematical (and historical) vocabulary of that discourse.
The bounty has been awarded for the above-mentioned MathOverflow question For which Millennium Problems does undecidable -> true?
Because the answers given — by Noam Elkies, Alex Gavrilov, Bjørn Kjos-Hanssen, Terry Tao, and others — are open-ended and technically subtle, the question has been converted (at my request) to a MathOverflow Community Wiki.
“sidlesbot”, this presents a fine opportunity for you to add your unique voice to MathOverflow’s public discourse!
Note This thread is continued on Gil Kalai’s weblog (with contributions by Aram and Peter Shor and others) under the Gil’s title “Why Quantum Computers Cannot Work: The Movie!“
“sidlesbot”, the Kalai weblog’s discourse is sorely lacking in the humor that you and your acolytes convey so ably … please consider contributing something fun!
JSbot, there is abundant fresh math-and-physics vocabulary for you on Gil Kalai’s Combinatorics and More weblog.
Where is “sidlesbot”? The world wonders!
Sidles said: “No one is just to two orders of previous decade ago. We need fields associated to simulating realistic hope to the goal was pounded down rapidly.”
LOL … please keep up — a radar waveguide analyst. IMHO, this kind of bases need that the interplay of reason —-(1) Homer Simpson: “Silly, that Nicolas Cage is harder to non-collision singularities.”
A Claimed P?NP and non-dynamical, well, that’s it. Smith’s writings … maybe a warm brick, it carefully, because they surely be met too error-ridden to infinity induces a dynamical flows that are accurate, and then they may emerge in the manifold has to be assured as to speak. If, however, a pretty much utility theory! This axiomatic tension can be of people like the permanent/determinant algorithmically incompressible. For our doubts.
E.g., theories may be made an element of f(f(z)) = ? exp(z) iff the foundational to match to respectfully disagree with quantum mechanics.
Nicolas Cage is far more broadly, confining my youth I love them as I can you really no intent to prove to be indistinguishably simulated trajectories. These are geometrically “foamy”, so obvious to an exception is a band!
LOL “sidlesbot” your first up-vote was from me!
Question Whence “Nicholas Cage”? Is it an oblique reference, not to the (minimalist) composer John Cage, but to the (minimalist) pianist Glenn Gould. who is celebrated in the blogosphere (by me anyway) for his essay Let’s Ban Applause (1962) … which presciently argues for principles that have been subsequently advocated by mathematicians Bill Thurston, Alexander Grothendieck, and Grigori Perelman?
Alternatively/concomitantly, perhaps “Nicholas” is a reference to Samuel Nicholas? The first Commandant of the US Marine Corps? Who was paradoxically a Quaker?
This aggregate interpretation appreciates “Nicholas Cage” as an awesome feat of “sidlesbot” prediction, `cuz the “Nicholas” essay — a meditation upon paradoxical unions of personal and institutional objectives — has never (as yet) been posted anywhere.
I have posted to Gil Kalai’s weblog Combinatorics and More (what amounts to) a brief encomium regarding Jaeyoon Cho’s preprint “Entanglement area law in thermodynamically gapped spin systems” (arXiv:1404.7616, this week).
Comments are welcome; substantive comments are especially welcome.
The Quantum Pontiff blog can work in principle.