Quantum Annealing’s Ideal Form Is the Gate Model in Disguise

Table of ContentsIntroductionTwo machines that share nothing but a wordWhat “equally powerful” actually claimsA circuit can fake a slow meltTurning a movie into a mountain rangeThe obvious idea, and why it failsThe history stateBuilding the landscapeThe domino argumentWhy the movie must be evenly exposedFeynman’s movie projectorReading out the answerThe gap is the load-bearing beamWhy your quantum annealer still can’t run Shor’sWhy the AVKLLR proof earns its keepFurther reading

Introduction

In February 2007, at the Computer History Museum in Mountain View, a Canadian startup called D-Wave demonstrated what it billed as the world’s first commercially viable quantum computer. Sixteen qubits. A Sudoku puzzle solved live, by a processor that was actually sitting in Burnaby, British Columbia. The machine ran quantum annealing, and the announcement split its audiences: many physicists questioned whether the box was doing anything usefully quantum at all, while my clients asked a blunter question. I had been assessing quantum risk since 2000, when a European government engaged my firm to evaluate what quantum computers would eventually mean for national cryptographic infrastructure, and by that spring the question landing in my inbox was simple. Is this the machine that starts the countdown for RSA?

My working answer was no, and about the box itself I was right: Orion could not run Shor’s algorithm through any control D-Wave exposed, and no descendant of it has run Shor’s since. But my reasoning was wrong in a way that still delights me. I had argued from taxonomy: no gates, therefore not that kind of computer, therefore not on the road to breaking cryptography. The taxonomy turned out to be false. Three years earlier, Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev had proved, in “Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation” (a result I will call the AVKLLR proof, after t…