Quantum Groundhog Day
Happy Groundhog Day! This doesn’t actually count as a holiday, but at the very least it is the one day each year that every American can devote to the contemplation of quantum physics. Can there be any bigger fun than that?
Well we hope the comments flying today in our own recent item on quantum computers are edifying as well as fun. This is the first of a series, but before it recurs we thought we’d summarize some of what has been said. We fear otherwise the pith may get “lost in translation,” as in a famous film with Bill Murray in a serious role, delivering an Oscar-nominated performance. Bill Murray charges a $100,000 speaking fee, which a bet posted here would just cover, so we should get serious too. Here goes…
Roadmap to Comments
Cristopher Moore of the Santa Fe Institute was the first to give an evaluation of Gil Kalai’s conjectures. He began with the position that given known theoretical results, arguing limitations on quantum computers (QC’s) entails arguing against quantum mechanics itself. His main request was to focus arguments on the underlying physics. Gil Kalai responded by positing some limits on QC’s that everyone might agree on, but not clearly so to Steve Flammia and Boaz Barak who joined in that thread, while John Sidles gave supplementary considerations and recalled a Theoretical Physics StackExchange thread opened last September by Kalai.
Barak then asked whether Gil’s conjectures intended to knock the power of down to the classical . Gil thought yes but this is not central yet. Gil then opened a second thread responding to Moore and Flammia. One point of contention became whether noise can really be separated from the main notion of physical process being analyzed, insofar as noise arises from the same ambit of physical processes. Sidles noted that “noise” in plasma physics has frustrated efforts at plus-rate fusion energy.
Physicist Robert Alicki, who was referenced in the post itself, then weighed in here and here with details on the physics underlying the objections to FTQC. Geordie Rose, CTO of D-Wave Systems, however, noted progress in building QC’s, though with criticism of the standard quantum circuit model by which the feasibility of QC’s is mainly argued.
Joe Fitzimmons then raised another fundamental point, namely that the logical extension of Gil’s objections would argue against classical (fault-tolerant) computation itself. Indeed this is the focus of the first of Aram Harrow’s three responses, which is still in process of editing. This included a concrete example creating maximally-entangled states that are subject only to classical bit-flip errors, which Aram’s post will give the standard name X to, which if substantiated would refute Gil’s 4th conjecture. Gil asked for more detail, which led also to some harmonizing discussion of the other conjectures.
Scott Aaronson then joined the fray, opining that Barak’s question needed critical focus. This culminated in the aforementioned $100,000 bet on whether any currently-unknown laws can be found to give
…a demonstration, convincing to me, that scalable QC is impossible in the physical world.
This echoes the way we originally framed the question.