So You Think Quantum Computing Is Bunk?

In this talk, I’ll take an unusual tack in explaining quantum computing to a broad audience. I’ll start by assuming, for the sake of argument, that scalable quantum computing is “too crazy to
work”: i.e., that it must be impossible for some fundamental physical reason. I’ll then investigate the sorts of radical additions or changes to current physics that we seem forced to contemplate in order to justify such an assumption. I’ll point out the many cases where such changes seem ruled out by existing experiments, or by no-go theorems such as the Bell Inequality. I’ll also mention two recent no-go theorems for so-called “epistemic” hidden-variable theories: one due to Pusey, Barrett, and Rudolph, the other to Bouland, Chua, Lowther, and myself. Finally, I’ll discuss my 2004 notion of a “Sure/Shor separator,” as well as the BosonSampling proposal [A.-Arkhipov 2011] and its recent experimental realizations—which suggest one possible route to falsifying the Extended Church-Turing Thesis more directly than by building a universal quantum computer.