Scott Aaronsons underbara bok om kvantdatorberäkningar

Jag har nyss läst ut den unge briljante datalogen Scott Aaronsons bok Quantum Computing since Democritus från 2013, och jag rekommenderar den å det varmaste. Utöver att behandla teorin för kvantdatorberäkningar är den i minst lika hög grad en introduktion för den gren av teotetisk datalogi som benämns komplexitetsteori, och som studerar hur resurskrävande (i termer av exempelvis antal beräkningssteg eller mängden minnesutrymme) olika beräkningsproblem är, vanligtvis asymptotiskt då problemstorleken växer mot oändligheten. Komplexitetsteorin kan sägas handla om vilka problem som kan lösas effektivt, och till väldigt stor del är den uppbyggd kring den viktiga men infernaliskt svåra matematiska frågeställningen P kontra NP.¹ Till bokens rikedom bidrar de många utvikningar författaren gör till angränsande områden, som kvantmekanik, relativitetsteori (inklusive avsnitt om huruvida tidsresor är möjliga och vad det i så fall kan väntas ha för konsekvenser för komplexitetsteorin), sannolikhetsteori, kryptologi, antropiska resonemang à la Nick Bostrom, mänskligt medvetande (med precisa och lätt lustfyllda sågningar av John Searles och Roger Penroses respektive bidrag till området), kreationism, och det fantasieggande tankeexperiment som benämns Newcombs paradox och som jag skall återkomma till i morgondagens bloggpost. Mer än en gång ser sig Aaronson manad att leverera disclaimern att han inom fysiken blott är en amatör, men det står klart att i den mån detta överhuvudtaget är sant så är han en extraordinärt bildad sådan. Referensen till Demokritos - den grekiske filosof som verkade under 400- och 300-talen före Kristus och som införde atomteorin - är givetvis en anakronism av rang, men Aaronson begår den av goda skäl.

Genremässigt är boken, som ett slags lite egensinnigt mellanting mellan lärobok och populärvetenskap, en smula svårkategoriserad. Såsom akademiker med min huvudsakliga utbildning inte i datalogi men i ett annat matematiktungt STEM-ämne tror jag att jag har precis rätt sorts bakgrund för att få maximalt utbyte av boken. Det jag framför allt tar med mig från boken är vilket fantastiskt rikt tankebygge komplexitetsteorin utgör, med alla dess intrikata samband i den djungel av olika komplexitetsklasser (jämte ovan nämnda P och NP) som definierats. För mig fungerar också bokens originella stil utmärkt, men jag kan föreställa mig att en och annan läsare kan komma att reta sig på Aaronsons drivna jargong, där ironin sällan är långt borta. Smaka t.ex. på följande inledningsmening på det kapitel i vilket komplexitetsteorin först introduceras:

By any objective standard, the theory of computational complexity ranks as one of the greatest intellectual achievements of humankind - along with fire, the wheel, and computability theory. That it isn't taught in high schools is really just an accident of history. [s 44]

Eller följande inledning till kapitlet om kvantmekanik:

There are two ways to teach quantum mechanics. The first way - which for most physicists today is still the only way - follows the historical order in which the ideas were discovered. So, you start with classical mechanics and electrodynamics, solving lots of grueling differential equations at every step. Then you learn about the "blackbody paradox" and various strange experimental results, and the great crisis these things posed for physics. Next you learn a complicated patchwork of ideas that physicists invented between 1900 and 1926 to try to make the crisis go away. Then, if you're lucky, after years of study you finally get around to the central conceptual point: that nature is described not by probabilities (which are always nonnegative), but by numbers called amplitudes that can be positive, negative, or even complex.

Look, obviously the physicists had their reasons for teaching quantum mechanics this way, and it works great for a certain kind of student. But the "historical" approach also has disadvantages, which in the quantum information age becomes increasingly apparent. For example, I've had experts in quantum field theory - people who've spent years calculating path integrals of mind-boggling complexity - ask me to explain the Bell inequality to them, or other simple conceptual things like Grover's algorithm. I felt as if Andrew Wiles had asked me to explain the Pythagorean Theorem.

As a direct result of this "QWERTY" approach to explaining quantum mechanics - which you can see reflected in almost every popular book and article, down to the present - the subject acquired an unnecessary reputation for being complicated and hard. Educated people memorized the slogans - "light is both a wave and a particle," "the cat is neither dead nor alive until you look," "you can ask about the position or the momentum, but not both," "one particle instantly learns the spin of the other through spooky action-at-a-distance," etc. But they also learned that they shouldn't even try to understand such things without years of painstaking work.

The second way to teach quantum mechanics eschews a blow-by-blow account of its discovery, and instead starts directly from the conceptual core - namely, a certain generalization of probability theory to allow minus signs (and more generally, complex numbers). Once you understand that core, you can then sprinkle in physics to taste, and calculate the spectrum of whatever atom you want. This second approach is the one I'll be following here. [s 109-110]

Fotnot

1) Det som gör sambandet mellan komplexitetsteori och kvantdatorberäkningar särskilt hett är att ett kvantdatorgenombrott kan komma att utöka klassen av problem som vi kan lösa effektivt. Här finns dock utbredda vanföreställningar om hur radikal denna utökning kan väntas bli. Aaronson plockar ned dessa:

From reading newspapers, magazines, and so on, one would think a quantum computer could "solve NP-complete problems in a heartbeat" by "trying every possible solution in parallell," and then instantly picking the correct one.

Well, arguably that's the central misconception about quantum computing among laypeople. [s 145]

Och vad som kraftigt bidrar till denna "central misconception" är missförståndet att primtalsfaktorisering av stora heltal skulle vara ett NP-komplett problem. Det är visserligen sant att problemet tillhör NP, och att de snabbast kända klassiska (dvs icke-kvant) algoritmerna tar exponentiell tid på sig (något som, tack vare Shors algoritm, ett kvantdatorgenombrott skulle ändra på), men detta gör inte primtalsfaktorisering NP-komplett. Aaronson igen:

Over the course of my life, I must've met at least two dozen people who "knew" that factoring is NP-complete, and therefore that Shor's algorithm - since it lets us factor on a quantum computer - also lets us solve NP-complete problems on a quantum computer. Often these people were supremely confident of their "knowledge". [s 64-65]