Quantum Computing Since Democritus

by Scott Aaronson

Written by noted quantum computing theorist Scott Aaronson, this book takes readers on a tour through some of the deepest ideas of maths, computer science and physics. Full of insights, arguments and philosophical perspectives, the book covers an amazing array of topics. Beginning in antiquity with Democritus, it progresses through logic and set theory, computability and complexity theory, quantum computing, cryptography, the information content of quantum states and the interpretation of quantum mechanics. There are also extended discussions about time travel, Newcomb's Paradox, the anthropic principle and the views of Roger Penrose. Aaronson's informal style makes this fascinating book accessible to readers with scientific backgrounds, as well as students and researchers working in physics, computer science, mathematics and philosophy.

Genres: Science, Physics, Computer Science, Philosophy, Nonfiction, Mathematics, History

370 pages, Paperback

First published February 26, 2013

About the author

http://en.wikipedia.org/wiki/Scott_Aa...

Reviews

[Gwern · Rating 4 out of 5]

Moved to gwern.net.

[Robb Seaton · Rating 4 out of 5]

This reads a bit like, "Hey, I'm Scott Aaronson and here's my perspective on a bunch of topics," which -- don't get me wrong -- is entertaining because Scott has an, uh, impressive intellectual batting average. He's managed to glean a fair bit of insight about the sort of topics that mathematicians would call philosophy and philosophers would call mathematics.

The book suffers from lack of a really cohesive theme, though, which is what we're all chasing, right? Some beautiful, consistent theory that unites everything, and the book doesn't offer that.

[Jason · Rating 4 out of 5]

"You can't actually build a working computer whose radius is more than 20 billion light years or whatever. It's depressing, but true." -- Scott Aaronson (*)

(* - What causes a sad for Scott Aaronson may differ from most people)

I'm going to likely re-read this one some time later when I find all the bits of cerebellum which squirted out my ears. After finishing this book I had a revelation about my favorite intellectual hobby; Quantum mechanics and computational complexity have a lot of interesting thought experiments which involve suicide. I'm still sitting with what that correlation is really about.

[Alireza · Rating 4 out of 5]

It took me a long time to finish this book, mainly because I had to re-read some chapters several times; and even now I cannot claim I understand nearly 20% of it.

This book is a fascinating bridge between physics, computer science, and philosophy. As a CS student I've been exposed to many of the presented ideas before, but I couldn't comprehend the same material when it was written by Scott. Maybe it was presented at a higher level, or maybe I'm plainly stupid. Now imagine the times when I was reading about something for this first time in his book.

I used to be a skeptic about the the nature of quantum physics, believing that everything can, at worse, be modelled as a system with latent, unobservable, variables. Now I'm convinced that the quantum physics offers an entirely different perspective.

This book answered many of the questions I've been wondering about for the past few years. Questions that you can't simply ask from a philosopher, physicist, or computer scientist alone.

I would probably read this book sometime in the distant future, hoping that I can learn more from it.

The overall experience of this book, is as if you're hanging out with an intelligent friend who's enthusiastically explaining the topics you both enjoy. And what better experience can you hope for?

[Alex Zakharov · Rating 5 out of 5]

If you follow quantum computing at all, you are no doubt familiar with Scott Aaronson. He is not a physicist or a hard-core programmer or an engineer - his chief contributions are in the field of computational complexity (theoretical computer science). He runs the premier quantum computing blog (“shtetl optimized”), and it is the variant of his algorithm that Google used to achieve quantum supremacy a few months ago. Aaronson even managed to collaborate with the great Leonard Susskind to tease out a hypothesized relationship between gravity, entropy and growth of quantum information modeled within the AdS/CFT correspondence.

As such “Quantum Computing since Democritus” is first and foremost a theoretical computer science text, and I must warn you that by no means does it qualify as a “popular science” book. His coverage of Probability, Turing Machines, NP-Completeness, Randomness, Cryptography, Proofs, Unitary Transformations, Quantum States, and a myriad of Complexity Classes start out at the undergraduate computer science level and rapidly escalate. I’m not unfamiliar with many of these subjects, yet a depressingly sizeable chunk of the text was borderline incomprehensible to me.

Nonetheless, I couldn’t put the book down – many reviewers hated Aaronson’s often hoi polloi style and rather eccentric humor, but how else would you present a fairly technical text to a non-practitioner? If you can make people laugh while they are guided through a proof showing that oracle-powered BQP is contained in PP you deserve a medal!

As a bonus, there are few chapters in the second half of the book that deal with Free Will, Consciousness, Time Travel, and Anthropic Principle. Arguably all these subjects have been beaten to death and then some, yet Aaronson manages to wrap them up into a computational complexity blanket and give them an utterly fresh polish. Anyway, this is not a light read, but if you have technical background and a penchant for minor masochism, it could be a very rewarding one!

[Michelle Victora · Rating 3 out of 5]

I LOVED the intro to this book. Almost lol'ed but I was in an airport while reading it. Was really excited, thought it was a perfect fit for me b/c it advertised itself as somewhere BETWEEN pop science and a textbook. As in, still entertaining and light, but also requiring a fair bit of math/physics understanding. I bet the book would be good for someone who had TAKEN a quantum computing/info class like the one Aaronson taught to produce these lecture notes. Unfortunately, even though I broadcast myself as quantum computing-knowledgeable, I'm actually still a bonehead when it comes to group theory and all the complexity classes.

So a lot of the chapters went straight over my head, and while I DO think I might use this book as a guide to go back and study more if I DO want to learn more about all these things... I bet I won't. I guess the further I get away from my physics experience, the more I have to realize I'm probably not motivated to go back and learn all the complex math I didn't actually take for the PhD.

I do highly recommend reading the intro, though. It'll probably make you want to read the book :D

[Mingyuan Zhang · Rating 5 out of 5]

Good read if you skip over things you don’t understand

There are a lot of concepts discussed in this book. I made the mistake trying to understand every definition and every proof. For the first few chapter, it was really painful. As soon as you are willing to accept some of the things are too hard to understand, and skip those, you will find this a very thought provoking and enjoyable book.

[Martin Brochhaus]

I don't think I can rate this, as I am way too stupid to fully understand even a single paragraph in this book.

It's damn funny, though, that's for sure.

But I have no idea who the target audience is. This was a lecture? Students were supposed to digest this? HOW? These students were all Stephen-Hawkings-level geniuses or what?

[Ben · Rating 1 out of 5]

I had a difficult time with this. I don't recommend it unless you are already familiar with quantum mechanics, quantum computing, and complexity theory/more compsci than me. In many cases I felt that I would have preferred reading selected chapters of a straight QC book, some review articles, and Bostrom. Some pretty great sections - his interpretations on Quantum, fantastical arguments - I may go back to it after reading something less sketched out to get his insights.

[Alex Telfar · Rating 4 out of 5]

This style of writing it perfect! Amusing, fascinating and technical. This is certainly the first textbook I have laughed out loud to.

I love Scott's perspective on computation and it's connection to physics. I was fascinated by the connection between probability theory and quantum mechanics.

Overall Scott just seems to have a great thought process. Critical, playful and balanced.

[Daniel · Rating 5 out of 5]

Substantially challenging, though I'm hardly the ideal audience, which I suspect is somebody actively studying computer engineering[1] either at an elite or grad school level. The math isn't hard, exactly; it's more a question of applied logic than math per se, but anytime equations are deployed as liberally as this, there's a hurdle in shifting my (and only mine?) brain from prose/philosophy mode (which is equally a component) to computation/recognition and back, sometimes several times per page.

What is genuinely excellent about it, should one feel like digging in, is that it demonstrates the boundaries of quantum computing and can help one get a handle on current crytpto-concerns versus (groundless) crypto-panic. It also nicely demilits how far quantum computing is likely to get in my remaining career in adjacent industries. Answer: not particularly far.

Also, sometimes it is funny[2]. Aaronson is clearly quite bright.

Here's a pull quote: "It's easier than the Knuth."
_________________________

[1] I'm very glad I bought it instead of renting it, as it took 164 days and I was reading at least a couple of pages most nights.

[2] Check the highlights for samples.

[Victor · Rating 4 out of 5]

I HAVE NOT FINISHED THIS BOOK.

I read up to the quantum section at which point I was only understanding 10% of the material. The parts I did read were fantastic. Aaronson is a joy to read. His enthusiasm for the field is obvious and contagious.

This is a hard book. I read each page at least twice, and many proofs far more than that. The proofs given are short and elegant. Godels incompleteness theorem is proved in a page while it occupies multiple chapters in Godel, Escher, Bach. You need to really think to understand anything at all.

I plan on finishing this book after taking a formal course in quantum mechanics. This book convinced me to take courses in quantum mechanics and complexity theory.

[Vlad · Rating 4 out of 5]

I found Quantum Computing Since Democritus from a reference in chapter 14 ('Quantum and Post-Quantum') in Serious Cryptography: A Practical Introduction to Modern Encryption, which I'd recommend reading if you're interested in a quick high-level treatment of the implications of QC on cryptography.

[Darnell]

The author begins with self-deprecating jokes about his book having a tiny target audience, and he seems to be right. It assumes you have a deeper math background than I do, isn't particularly accessible, and when I managed to fully grasp sections I didn't find them particularly rewarding.

[Vikrant Varma · Rating 2 out of 5]

Aaronson has a breezy and lucid explanation style reminiscent of Feynman, and I found his first few chapters on set theory and basic complexity riveting. I wasn't able to understand 80% of the book though -- he starts off by explaining what numbers are and then very quickly assumes you already know quantum mechanics. I found the qualitative conclusions interesting anyway - a testament to his engaging prose.

Worth reading if you've studied QM, early sections are enjoyable even with undergrad level maths.

Also see Gwern's excellent review:
https://www.goodreads.com/review/show...

[Odo · Rating 4 out of 5]

3.5/5.0

[Steve Abreu · Rating 5 out of 5]

Without a doubt my favorite textbook.

[Kendall Zhu]

Skimmed over the mathy parts. Still a fun read. Aaronson just seems like a solid thinker to me. I came to him originally for his paper "Why Philosophers Should Care About Computational Complexity" which is just so so so true.

[Infinite Jen · Rating 5 out of 5]

PHYS666: Quantum Computing Democritus’ Willybits With Q-Bits.

Miskatonic University, Fall 2006 Tuesdays and Thursdays, as the moon shines on the luminiferous ether.

Fhtagn! Building, 2nd floor seminar room (ECCF2125)

Instructor: Jen “Keep it in the circus” Kumiko.

Office hours: via astral projection (Original NFT Diploma of Dr. Herbert West MD required)

Description: When I force your incredulous, novitiate asses into the Stygian depths of your arcane edification, your physiology, by the primal edicts of lizard logic, will move in a kind of autonomic atavism of death ballet, characterized by arms moving rapidly up and down and legs going to and fro, which experienced Lifeguards have come to call “climbing the ladder”. This knowledge will do little to keep you from hyperventilating as your grimacing mug is aggressively cropped by the tenebrous fuck-podge of disparate concepts which comprise the heavy, unstable nucleus of this course, until your screaming image dissolves to a white dot in the center of an undeflected electron beam exciting the phosphors in the front tube of a cathode ray television as the voltage drops. A high concentration of mathematical and philosophical problems that predate quantum computing (i.e. the measurement problem, P versus NP, the existence of secure cryptography, the Humean problem of induction, or the possibility of closed time-like curves) combined with the strong hand which rises from the grave to grip the wheel (i.e. my giant man-handibles) palming your face like a parasitic life form freshly emerged from a Xenomorph egg, triggers the need to take a deep breath of semi-reliable communal sense-making. In the first breath, copious amounts of axiomatic prestidigitation are inhaled, you see this future lesson:

Obscenely tall Asian woman futilely attempting to hotbox an e-cigarette in poorly ventilated faculty bathroom. Concerned student ejects pontifical detritus from face-hole about the risks of vaping which are transmitted via telepathy to agitated percipient who flings mango flavored pen into the toilet and storms off toward the offending concern-troll, crepuscular vestments fluttering. Irate witch bursts through door in the manner of Cosmo Kramer, issues a: “Hello class.” Followed by a violent physical gesture alloyed with the following incantation: “Hot Spacho!” An eldritch death curse first uttered by Samuel Jackson in infamous Capital One Fondue TV Spot. Reducing student to a toxic puddle of anaerobic bacteria excrement.

“You’ll wanna be extremely careful about breathing that in. Anywhoo! Enough pussydicking around. Let's see some axioms for set theory. I'll state the axioms in Muggle; converting them to first-order logic is left as an exercise for you daft coonts”

Empty Set: There exists an empty set.

Extensionality: If two sets have the same members then they're equal.

Pairing: For all sets x,y there exists a set {x,y}.

Union: For all sets x, there exists a set equal to the union of all sets in x.

Existence of Infinite Sets: There exists a set x that contains the empty set and that contains y∪{y} for every y∈x.

Power Set: For all sets x there exists a set consisting of the subsets of x.

Replacement (for every function A): For all sets x, there exists a set {A(y) | y∈x}.

Foundation: All nonempty sets x have a member y such that for all z, either z∉x or z∉y.

(This is a technical axiom, whose point is to rule out sets like {{{{...}}}}.)

“These axioms -- called the Zermelo-Fraenkel axioms -- are the foundation for basically all of math. So I thought you should see them at least once in your life.”

As these concepts perpetrate inexpressible acts of Corpus Callosium Paizuri betwixt the moist hemispheres of your brain, the larynx usually closes, preventing Propositional Tautologies, Modus Ponens, Equality Rules, Change of Variables, Quantifier Elimination, Quantifier Addition, and Quantifier Rules from reaching the lungs. However, you will soon lose consciousness and, as your neural funhouse is inundated with spirit molecules, you will lurch forward in time once more to apprehend a punitive lesson doled out many months hence:

Giant Hāfu Scandinasian Death Eater eye-bones motley assemblage of feckless undergrads, impatiently tapping out the beat of - Garbage: Only Happy When It Rains - with her wand and foot. “Well?” She says. To which a timid ginger replies: “That was my mother. She says that gran has passed away…” Eliciting a swish of robes and a shrieking, verbal catalyst, “Holy Hand Grenade of Antioch!” Resulting in effulgent luminosity and commensurate seismic upheaval, with the freckled, crestfallen student at the epicenter. She is never seen again.

“So what's the real result? It's that there's a basic problem, called the halting problem, that no program can ever solve. The halting problem is this: we're given a program, and we want to decide if it ever halts. Of course we can run the program for a while, but what if the program hasn't halted after a million years? At what point should we give up?”

“One piece of evidence that this problem might be hard is that, if we could solve it, then we could also solve many famous unsolved math problems. For example, Goldbach's Conjecture says that every even number 4 or greater can be written as a sum of two primes. Now, we can easily write a program that tests 4, 6, 8, and so on, halting only if it finds a number that can't be written as a sum of two primes. Then deciding whether that program ever halts is equivalent to deciding the truth of Goldbach's Conjecture.”

“But can we prove there's no program to solve the halting problem? This is what Turing does. His key idea is not even to try to analyze the internal dynamics of such a program, supposing it existed. Instead he simply says, suppose by way of contradiction that such a program P exists. Then we can modify P to produce a new program P' that does the following.”

“Given another program Q as input, P' runs forever if Q halts given its own code as input, or halts if Q runs forever given its own code as input. Now we just feed P' its own code as input. By the conditions above, P' will run forever if it halts, or halt if it runs forever. Therefore P' -- and by implication P -- can't have existed in the first place.”

“Homework Assignment: Let BB(n), or the "nth Busy Beaver number," be the maximum number of steps that an n-state Turing machine can make on an initially blank tape before halting. (Here the maximum is over all n-state Turing machines that eventually halt.) Prove that BB(n) grows faster than any computable function.”

“Let S = 1/BB(1) + 1/BB(2) + 1/BB(3) + ... Is S a computable real number? In other words, is there an algorithm that, given as input a positive integer k, outputs a rational number S' such that |S-S'|<1/k?”

The spasm relaxes, allowing the following epochs to enter the lungs and disrupt the surfactant: Late Turingzoic, Dawn of the Asymptotic Age, The Cook-Levin Asteroid; extinction of the Diagonalosaurs, The Karpian Explosion, Early Cryptozoic, Randomaceous Era, Eruption of Mt. Razborudich; extinction of the Combinataurs, Invasion of the Quantodactyls, Derandomaceous Era, causing the alveoli to collapse and prevent life-giving oxygen from being diffused into tissues and inducing one final vision:

“But why would Schrödinger be interested in this dialogue? Well, Schrödinger was interested in a lot of things. He was not an intellectual monogamist (or really any kind of monogamist). But one reason he might've been interested is a certain equation he was involved with, which you've probably heard about.”

i dψ/dt = Hψ

“Actually, let me write it in a more correct form.”

|ψt+1⟩ = U |ψt⟩

“What is this equation? Well, maybe you have to add a few details to it -- like the physics -- but once you do, it describes the evolution of a quantum pure state. For any isolated region of the universe that you want to consider, this equation describes the evolution in time of the state of that region, which we represent as a normalized linear combination - a superposition - of all the possible configurations of elementary particles in that region. So you can think of this equation as the sophisticated, modern version of Democritus's "atoms and the void." And as we all know, it does pretty well at the atoms and the void part.”

“The part where it maybe doesn't do so well is the "from us you take your evidence" part. Where's the "us"? Remember, the equation describes a superposition over all possible configurations of particles. So, I don't know -- are you in superposition? I don't feel like I am!”

“Incidentally, one thing I'm not going to do in this class is try to sell you on some favorite interpretation of quantum mechanics. You're free to believe any interpretation your conscience dictates. (What's my own view? Well, I agree with every interpretation to the extent it says there's a problem, and disagree with every interpretation to the extent it claims to have solved the problem!)”

“Anyway, just like we can classify religions as monotheistic and polytheistic, we can classify interpretations of quantum mechanics by where they come down on the "putting-yourself-in-coherent-superposition" issue. On the one side, we've got the interpretations that enthusiastically sweep the issue under the rug: Copenhagen and its Bayesian and epistemic grandchildren. In these interpretations, you've got your quantum system, you've got your measuring device, and there's a line between them. Sure, the line can shift from one experiment to the next, but for any given experiment, it's gotta be somewhere. In principle, you can even imagine putting other people on the quantum side, but you yourself are always on the classical side. Why? Because a quantum state is just a representation of your knowledge -- and you, by definition, are a classical being.”

“But what if you want to apply quantum mechanics to the whole universe, including yourself? The answer, in the epistemic-type interpretations, is simply that you don't ask that sort of question! Incidentally, that was Bohr's all-time favorite philosophical move, his WWF piledrive: "You're not allowed to ask such a question!"

“On the other side we've got the interpretations that do try in different ways to make sense of putting yourself in superposition: many-worlds, Bohmian mechanics, etc.”

“Now, to hardheaded problem-solvers like ourselves, this might seem like a big dispute over words -- why bother? I actually agree with that: if it were just a dispute over words, then we shouldn't bother! But as David Deutsch pointed out in the late 1970's, we can conceive of experiments that would differentiate the first type of interpretation from the second type. The simplest experiment would just be to put yourself in coherent superposition and see what happens! Or if that's too dangerous, put someone else in coherent superposition. The point being that, if human beings were regularly being put into superposition, then the whole business of drawing a line between "classical observers" and the rest of the universe would become untenable.”

“But alright -- human brains are wet, goopy, sloppy things, and maybe we won't be able to maintain them in coherent superposition for 500 million years. So what's the next best thing? Well, we could try to put a computer in superposition. The more sophisticated the computer was -- the more it resembled something like a brain, like ourselves -- the further up we would have pushed the 'line' between quantum and classical. You can see how it's only a minuscule step from here to quantum computing.”

While breathing has ceased, the heart usually continues to beat, but at an accelerated rate. Before stopping, it may progress to a stage of fibrillation. Once breathing and the heart stops, you will emerge from this experience a newly born factotum. There will be no concept orthogonal enough that you cannot correlate them with your big dick (and vulva, respectively) interdisciplinary energies.

Prerequisites: Mathematical maturity, some previous exposure to quantum computing, the will to master unforgivable curses.

Responsibilities: Crush your enemies.

Suggested Readings:

Democritus (from Stanford Encyclopedia of Philosophy)

David Deutsch, Quantum theory as a universal physical theory (unfortunately, can only be accessed from within the university). Pages 32-37 describe the notorious thought experiment. See also Chapter 1 of Minds, Machines, and the Multiverse by Julian Brown.

Alan Turing, On Computable Numbers

Alan Turing, Computing Machinery and Intelligence

Roger Penrose, The Emperor's New Mind

Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach (free draft available on the web)

Lucien Hardy, Quantum theory from five simple axioms

[Caroline · Rating 2 out of 5]

Reading this book consisted of two types of experiences. Either I was reading something I already knew, or I was completely lost.

Okay, that’s not quite true. I learned a few things, like some foundational parts of complexity theory. But overall I found the book poorly written and hard to follow. Early on, I tried looking up all the stuff I didn’t understand on Wikipedia, and I learned a lot that way. (Yeah, the explanations in this book were on average less clear than Wikipedia articles on the topic. It’s that bad.) And then I went back to the book to see why I hadn’t been able to understand it. Sometimes mathematical statements phrased in “plain English” had tripped me up by the ambiguity of natural language. Reminder: mathematical notation was invented for a reason. Other times, there were two (non-obviously) equivalent definitions of some concept. Aaronson would give definition A, then state a result that follows easily from definition B, then summarize the proof just as if he had given definition B to begin with. No wonder I couldn’t follow! Bad editing, perhaps?

After a while, he moved on to topics where it was less obvious what Wikipedia article to read, and also I was getting sick of reading a series of Wikipedia articles instead of a book. Instead of giving up, I decided to just finish without slowing down for the parts that didn’t make sense. As a reward, I got to experience one of the worst takes on free will I’ve ever seen. Aaronson says, “I’ve often heard the argument that... either our actions are determined by something, or else they’re not determined by anything, in which case they’re random. In neither case can we ascribe them to ‘free will.’ For me, the glaring fallacy in the argument lies in the implication Not Determined => Random. If that were correct, then we couldn’t have complexity classes like NP - we could only have BPP.” He doesn’t explain what he means by this, but I think he means the verification string in NP problems is neither determined by the algorithm nor a random string? But look, that string came from an existential quantifier (there exists a verification string v such that...), which I would argue is a type of determinism. And even if it’s considered some third type of origin, I would really like to see a detailed account of how free will derives from existential quantifiers. Needless to say, none was given.

[Amar Pai · Rating 3 out of 5]

Not casual reading... but seemed worthwhile. I need to come back to this when I have more time and patience. It was too deep for me this time around. Couple of takeaways from skimming:

* quantum physics = what happens when you allow negative probabilities, and use a '2-norm' instead of '1-norm'. using 2-norm, all probabilities for an event = all points at a distance of 1 from origin. probability is an amplitude, can be positive or negative.

* quantum computing != 'try all possibilities at once'. instead, what you get is a quadratic speedup over traditional computing. why? because you're using 2-norm instead of 1-norm. if you imagine probability of choosing a 'correct' number from range 1-N, each time you pick you have a 1/N chance. w/ 2-norm it's a 1/sqrt(N) chance. admittedly i have no idea what i'm even saying here, but it made sense when he said it

* new complexity classes related to quantum computing

* something about many worlds?

I dunno. It's an interesting book, definitely a way of looking at quantum physics that I hadn't come across before. He's basically like 'forget physics let's treat quantum theory as a layer between physics and math, it's like the OS that other physical theories run on..."

qubit = bit using a 2-norm ????

I would've kept the book longer but it's overdue and someone else has a hold on it. Maybe should just buy it. Though it will just sit next to all the other math books I've bought optimistically thinking 'someday I'll read this for real'.

[Fulmenius · Rating 4 out of 5]

Признаюсь, где-то после начала обсуждения доказательств с нулевым разглашением я окончательно перестал понимать, что происходит, и более-менее въехал обратно только ближе к концу книги. Надеюсь, я перечитаю её позже, с большим объёмом знаний по теоретической информатике, и тогда смогу извлечь из неё больше пользы.

Не рекомендуется людям, не знакомым хотя бы с основами квантовой механики (на уровне вводного учебника, а не популярных лекций) и матлогики - не поймёте вообще ничего. Книга и без того написана не слишком методично, что усугубляется кривым переводом. Главы в середине книги и вовсе, вероятно, невозможно понять без предварительного знакомства с обсуждаемым в них предметом в объёме ун��верситетского курса.

С другой стороны, всё действительно очень и очень интересно, даже если квантовая информатика - не ваша специальность. Надеюсь, что после прочтения я получил хотя бы приблизительное представление о том, чем всё-таки занимаются специалисты по теории вычислительной сложности (а заодно о том, откуда Юдковский взял свою концепцию путешествий во времени для решения NP-полных задач, хе-хе-хе)

[Roberto Rigolin F Lopes · Rating 5 out of 5]

Damn, quantum computers may use parallel universes to speed up our calculations. How cool is that? We just need to figure out how to build such computers; we have no idea but the theoretical foundations have been evolving furiously. Even Democritus would be thrilled to know that our knowledge of the universe is setting the boundaries of our computational powers. And Scott does a great job scaring the hell out of us running through the resulting complexity bestiary. Not sure how brave you are, but I bet you will buy some books and read some papers while facing these quantum beasts. But that's what great teachers are supposed to do with their damn good books.

[Zarathustra Goertzel · Rating 5 out of 5]

This was a great book. There were so many topics covered in detail that I've been meaning to get around to. (fortunately without full mathematical rigor, lest the book be far, far longer and less approachable). You'll get your quantum information theory and computing, but you'll get even more complexity theory. You'll also get insights on other topics (free will, time travel, cosmology, etc.) and how they are related to complexity and quantum theory.

Definitely recommended to anyone who doesn't mind some math.

[Thomas · Rating 1 out of 5]

I read half this book and realized it is not for me. I am not sure who this book is for, aside from the author.

[Andrej · Rating 3 out of 5]

Reads like an only lightly edited version of Aaronson's university lectures, with dorky jokes and everything. However, this is not a textbook. Rather than explaining everything, the book leaves (explicitly) a lot of work for the reader. Unfortunately, I didn't have time or inclination to reproduce dozens of mathematical proofs that the book alluded to, without going through them in sufficient detail. If there was a particular teaching goal, I missed it. In my view, the book mostly summarized Aaronson's published papers and his opinions about many things. This is less of a problem than it sounds because Aaronson's work encompasses an incredibly large scope.

I liked the occasional lucid parts and the fact that the author never stops asking questions. For example, I finally understood why amplitudes in quantum physics are complex numbers and not something else. This is something that ordinary physics textbooks often gloss over. I also liked connections between different fields and theories. For example, have you ever asked yourself how would the many worlds interpretation of quantum mechanics look like if decoherence worked differently? Finally, I loved deep insights that really make you think. For example, did you know that if both the many worlds interpretation is true and the world is ultimately discrete (maybe at the scale of the Planck length), the bifurcated parallel worlds will eventually run out of "space" (Hilbert space, of course) and start interfere with each other?

What I didn't like were lengthy parts about different complexity classes. I understand that Aaronson is a computational complexity theorist, but for me, as a lay person, it wasn't immediately clear why I should care about whether the SZK class is contained in the BQP class, and what the relationship between P# and P#P is. It'd be great to see some connection to the real-world algorithms. Another thing I disliked was the disdain shown to the theories and fields that the author wasn't into. I guess it was supposed to be funny, but, for me, it only exemplified insularity of some academics.

[Charles Daney · Rating 4 out of 5]

This is a really great read. But it isn't an introductory book on the subject. It's not an easy slog, except for someone who already knows the subject somewhat. Think of its challenge like the effort required of a reasonably fit climber to summit the Matterhorn. Thousands attempt that during a summer. Yet perhaps only about a third of them get all the way. (But don't worry. Failed attempts to grasp all the book's details are quite unlikely to be fatal.)

I give only 4 stars out of 5, but not only because of the difficulty. The most recent edition was published in 2013, so now there probably are more important details of the story than told here. Besides that, the title is a little misleading. Quantum computing isn't the main topic, and there's not much in the book about either constructing quantum computers or programming them. Finally, one aspect of the difficulty is that keeping track of the logic in the book's explanations requires careful attention. And another aspect is the sheer number of scientific fields that are drawn on for examples.

The book's real subject is the P vs. NP problem. Reading the book provides a very good idea of what that's all about, even if you don't quite get all the details. So for anyone who's seriously curious about scientific topics (especially mathematics or computing theory), this is a good read.

A "problem" in this context is, for example, determining whether a whole number is a prime number, i. e. one whose only exact divisors are 1 and the number itself. That would seem to be a simple enough matter, since all that's necessary is to try dividing a given number by each prime number that's not greater than the square root of N. If you want to determine whether N is prime, there are "only" approximately (√N)/log(N) primes to test. But the testing process is laborious if all the divisions required are done. So for a computer to do the necessary steps, many separate operations are required. The question here is whether this problem is of type P, which is the type of problem that a fast computer can theoretically solve in a reasonable amount of time. Although mathematicians have considered questions of divisibility for over 2000 years, only in 2004 was it proven that testing whether a given number is prime is actually of type P. Yet primality testing of very large numbers (thousands of digits) is still too much work for even the fastest digital supercomputers now to handle in a reasonable time.

A similar problem is finding two factors of a very large nonprime integer. It's of extreme practical importance, because there are several cryptography techniques involving "public keys" that are the strongest known and require factoring very large numbers that have two large prime factors. Encryption isn't just something that spies have to deal with, because it's vital for ensuring the secrecy of computer passwords and anything else that needs to be kept secret when transmitted through the Internet. No known factoring algorithm on a classical computer is of type P. But there's actually a fairly simple process ("Shor's algorithm") for a quantum computer to factor numbers. So if a suitable quantum computer can really be built, secrecy on the Internet could be a thing of the past.

Then what, exactly, is meant by determining whether a process (technically called an "algorithm") is of type P or NP? Problems of type P and NP are called "complexity classes". The exact definitions of these and other complexity classes (of which Aaronson has cataloged at least 545 different types) are quite technical. But P is fairly easy to describe. Another classical sort of problem that's been extensively studied is called the "traveling salesman problem". Suppose a salesman has to visit N different cities in a particular area. The problem is how to find the absolutely shortest path that the salesman could take to visit each city exactly once. In order for that problem to be of type P, a digital computer would have to perform a number of steps that is no more than a polynomial in N of degree k for some positive integer k.

The definition of the class NP is more complicated. It's still unknown (and seems extremely hard to figure out) whether P and NP are actually the same. For sure, any problem in the class P is also in NP. What isn't known is whether there are problems that are in NP but definitely not in P. The traveling salesman problem is conjectured to be in NP but not P. But there's no proof of that yet. If the conjecture were true, P must be a smaller class than NP. It's known that some problems are not even in NP. In fact, there are problems known that definitely can't be resolved at all, with any type of computer - because any proposed algorithm might run forever without stopping. (That's called the "halting problem".)

Here's what makes reading the book so demanding: Aaronson describes dozens of complexity classes - each subtly different from the others - out of the roughly 545 he's now cataloged. They're mostly all identified by labels, such as BPP or BQP. It's pretty hard to keep track of all of them. Some aren't even in the fairly complete index. And if P = NP, then most are actually the same.

Now, all of this may seem like esoteric issues that are of interest mainly to computer scientists and mathematicians. However, Aaronson ties them in with a dozen or more scientific fields. Surprisingly, resolving questions in a variety of fields depends on whether the problem can be reduced to one in P. Naturally, some of the main topics are part of computer science. These include complexity theory, artificial intelligence, machine learning, information theory, and cryptography. Of course, some mathematical topics are relevant to computer science and have been for a long time. These include mathematical logic, set theory, probability theory, statistics, and abstract algebra. Readers who don't have at least an acquaintance with some of these will have a difficult time following the story.

Naturally, some exposure to quantum theory is desirable, since "quantum computing" is right there in the title. Indeed, the strange ways in which quantum objects behave are central to how quantum computers function. Surprisingly, however, there are also connections with other branches of physical science as seemingly distant as cosmology, general relativity, and black holes. What's the connection with the rest of the book? It's basically a matter of information theory, and therefore with probability theory and "entropy". Although these topics aren't essential for understanding the main themes, readers who lack exposure to them will have difficulty when the topics are discussed.

Aaronson provides a tongue-in-cheek "review" of his book on the first page of the preface, to give potential readers an idea of what they're in for. The very first sentence avers that the book "is a candidate for the weirdest book ever published by Cambridge University Press." It's quite a trip, if you're up for it.

[Jumax9 · Rating 4 out of 5]

Empiezo diciendo que cogí este libro de la biblioteca de la universidad pensando que iba sobre otra cosa distinta y acabé dejándolo de parte ("ya le echaré un ojo, que parece interesante") hasta que se me ha acabado el plazo para devolverlo y me lo he leído prácticamente en un par de sentadas.
El libro trata sobre complejidad computacional y del papel de los ordenadores cuánticos en ese campo (lo cogí porque por el título pensaba que sería una revisión histórica). El libro es más complejo (jeje) de lo que uno puede digerir si no tiene conocimientos previos de cuántica y teoría de grupos pero está escrito de maravilla. Lo empecé a principios de semana pensando "seguramente no entienda una mierda" (porque de "computational complexity" 0 patatero) y sin embargo me lo he acabado teniendo una idea bastante más intuitiva de P, NP y todo el lio de siglas que se trae.
Siglas que olvidaré en las próximas dos o tres horas (ya siento cómo se desvanecen de mi memoria) pero al final es como aprender un idioma, tener una idea sobre las bases es ya una gran ventaja.

Cuatro sobre cinco porque a veces se vuelve loco y se cree que me voy a poner a demostrar teoremas en esta economía.

tl;dr: cogí el libro un poco a voleo pensando que era sobre la historia de la computación cuántica y me he encontrado con una explicación fantástica sobre un tema que me interesaba pero que nunca me había atrevido a tocar.

[Prakash Yadav · Rating 4 out of 5]

Spanning over Physics, Mathematics and Computer Science, this book is an excellent overview of the computing complexity as it is understood today. It starts like any other popular science book, with the historical and philosophical background for a complete perspective. It then introduces fairly simple undergraduate topics but very soon catapults into the quagmire of theoretical complexity classes and quantum mechanics. Every conjecture or proof is provided a link that the reader can visit to read more upon. Simpler derivations are left to the "non-lazy" reader. Penrose like Lucid conjectures are not entertained, only proofs and sincere effort of pure theoretical rigour of complexity theory. Add some randomness and dimensions to P and NP and we have so many more complexity classes that English grammar has no longer Alphabets for. AM, BQP, BQP(CTC), PostBQP, BPP, PostBPP, BPPpath, PPQ, CMA, AC, AC0, AM, QAM, QIP, QMA, QMAM, the list is just endless. Its like for every paper collapsing two classes together, there are 10 introducing new complexity classes, scaring the delicate physicist with subscripts and postscripts to classes they are already confused about. One has to admire Aaronson for sticking to the theoretical rigours in his popular science book. To be honest the latter portions of the book were way too technical for casual reading, I got the gist but I will not be able to explain if your cocktail-napkin-algorithm is in Bounded-Error Quantum Polynomial class.

[Ruben · Rating 2 out of 5]

When I asked a coworker about a book on quantum computing, he recommended this book. Unfortunately it turned out this was not a book I was looking for. This book is based on the author's lecture in 2006 with a few more additional contents. I was not a target audience, and with my very stale mathematical knowledge I couldn't understand majority of the contents.

This book is almost entirely about complexity theory, which is the author's main study area. The author skims through many topics from mathematical fundamentals to basic computing complexity all the way up to quantum complexity theory. The author even manages to explain quantum mechanics detached from physical experiments, which I actually found rather interesting. But there is not much about practical aspects of quantum computing, e.g. how logic gates can be constructed or concrete execution steps of calculation.

I can't help feeling this book was written to showcase the author's (then) latest researches to those who already have a solid understanding of complexity theory and quantum computing. Some people may like the author's colloquial writing style, but starting a sentence with "dude" doesn't make it any easier to understand. I need to look for another book on quantum computing.