What do you think?
Rate this book
Квантовые вычисления со времен Демокрита (Quantum Computing since Democritus)
Написанная известным теоретиком в области квантовых вычислений Скоттом Ааронсоном, эта книга проведет вас через поразительное разнообразие тем, исследуя самые глубокие идеи математики, информатики и физики от теории множеств, вычислительной сложности, квантовых вычислений до интерпретации квантовой механики. Кроме того, вы познакомитесь с дискуссиями относительно путешествий во времени, парадокса Ньюкома, антропного принципа и взглядов британского физика и математика Роджера Пенроуза. Неформальный стиль Ааронсона делает эту поразительную книгу доступной для читателей с научной подготовкой, а также для студентов и исследователей, работающих
577 pages, Kindle Edition
First published February 26, 2013
517 people are currently reading
5624 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 30 of 105 reviews
March 13, 2014
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.
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.
May 19, 2013
"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.
(* - 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.
April 30, 2020
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!
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!
August 30, 2015
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?
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?
September 2, 2021
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
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
January 30, 2021
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.
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.
August 6, 2024
Ik mis toch de rode draad tussen de verzameling van gedachte experimenten. Het deel over PSPACE op zichzelf is wel 5 sterren waard.
October 8, 2023
Personally I found this book hard to read, both intellectually and for its lack of coherence. However, one thing I feel like I gained a lot (at least spiritually) is the sense of how "far ahead" Scott is thinking about the subject of (quantum) computational complexity at that time. Or really, more generally. It's to the point that I feel ashamed for knowing that I have a Ph.D. in physics and I probably know less physics than he does (in the appropriate domain of comparison - I probably know more quantum field theory or general relativity than he does in some respects).
There are too many things to say (good things) about this book, but a few things stuck (and unfortunately, none of them are about the technicality of the complexity classes):
1. The first is the "point of complexity classes". I tended to agree in the past that the polynomial vs exponential separation are pointless in practice, because polynomial computation scaling like n^10000 is impractical while those scaling like exp(0.0000001 n) may be useful. His answer was "practical" - the fact that in most problems of interests this pathological scenario hardly occurs (e.g., in practical algorithms) means that this is not a real worry, and if it turns out that this is "generic" then one should really -redefine- the correct complexity class to capture this "genericity" of the pathological thinking. After all, if this were generic, the right thing to do is not to define polynomial vs exponential separation -this way-.
2. I mentioned earlier that he very nicely viewed "quantum mechanics as probability theory with complex numbers and 2-norm". I think this is important, because even though quantum mechanics is a physical theory, the way we think about our universe (or even our experiments) can (and perhaps should) be separated from the empirical facts. This is particularly relevant for quantum computing: it is very counter-productive to think about physics first before thinking about computer science. The natural way to do quantum computing is to "take the rules" of quantum mechanics and build models of computation; then figure out how to set up the gates, circuits, preparation. It is pointless to think about these in terms of canonical commutation relations and Schrodinger equations. This also changes the way we do science.
3. The way the book is written is a bit inspiring for me, who has lost most interest in physics (but still am doing physics at this time of writing). The reason is because regardless of how "mechanical" your job is (material scientists, chemists, etc.), your goal is (at least subconsciously) to understand the world. As Scott put it himself in the preface, he finds this whole mess about "no one understands quantum mechanics" pointless because we are all trying to understand something. If something is against our intuition, our new theory/understanding/framework should -advise- us on how to correct those. He correctly pointed out that general relativity is precisely one such example: it may never be fully intuitive to us because our everyday lives are mostly Newtonian regime, but we -know- how to think about those. Accepting that quantum mechanics is "incomprehensible" defeats the purpose of doing physics. I struggle to find the purpose of tackling any questions in everything I see, but this book gave me a bit of hope that perhaps there is some way out of this rut.
4. Last but not least, at technical level I got a sense of how big the "complexity zoo" is, which is more than enough for my purpose (sadly I don't get enough details to appreciate them better). However, two subtopics stuck and I would like to know more just for the sake of it. The first is the notion of "learning": I think this has been employed in quantum many-body physics (shadow estimation stuff?), which is important because it exploits the very fact that we are limited in our capabilities to measure or learn something efficiently about physical systems. The second is about "proofs". The fact that proofs are computations are not itself unfamiliar to me (I mean, if you read a bit about incompleteness theorems or even about proof-assistants, this may not come as a surprise). The notion of interactive proofs, zero-knowledge proofs are all interesting to me. It is something you never realize possible until you read it; in fact, one may think that -probabilistic proofs- may be counter to what mathematicians call proofs. I think this is part of the story about famous complexity classes like (Q)MA. Either way, both topics feel like something I should "know" a bit more even if it is irrelevant for my work. Ah, actually, "randomness" was also interesting subject of the book that stuck - I mean, if a number looks random if you check it for as long as the age of the universe but is actually not, do you call it random?
Either way, I highly recommend this to people who are willing to burn (quite a bit of) brain cells to try to see what this person has to say about the world of complexity theory, quantum computing, and understanding the world in general. I think I lost in the forest 70% of the time, but I am glad I managed to get out with some harvests on my hand.
There are too many things to say (good things) about this book, but a few things stuck (and unfortunately, none of them are about the technicality of the complexity classes):
1. The first is the "point of complexity classes". I tended to agree in the past that the polynomial vs exponential separation are pointless in practice, because polynomial computation scaling like n^10000 is impractical while those scaling like exp(0.0000001 n) may be useful. His answer was "practical" - the fact that in most problems of interests this pathological scenario hardly occurs (e.g., in practical algorithms) means that this is not a real worry, and if it turns out that this is "generic" then one should really -redefine- the correct complexity class to capture this "genericity" of the pathological thinking. After all, if this were generic, the right thing to do is not to define polynomial vs exponential separation -this way-.
2. I mentioned earlier that he very nicely viewed "quantum mechanics as probability theory with complex numbers and 2-norm". I think this is important, because even though quantum mechanics is a physical theory, the way we think about our universe (or even our experiments) can (and perhaps should) be separated from the empirical facts. This is particularly relevant for quantum computing: it is very counter-productive to think about physics first before thinking about computer science. The natural way to do quantum computing is to "take the rules" of quantum mechanics and build models of computation; then figure out how to set up the gates, circuits, preparation. It is pointless to think about these in terms of canonical commutation relations and Schrodinger equations. This also changes the way we do science.
3. The way the book is written is a bit inspiring for me, who has lost most interest in physics (but still am doing physics at this time of writing). The reason is because regardless of how "mechanical" your job is (material scientists, chemists, etc.), your goal is (at least subconsciously) to understand the world. As Scott put it himself in the preface, he finds this whole mess about "no one understands quantum mechanics" pointless because we are all trying to understand something. If something is against our intuition, our new theory/understanding/framework should -advise- us on how to correct those. He correctly pointed out that general relativity is precisely one such example: it may never be fully intuitive to us because our everyday lives are mostly Newtonian regime, but we -know- how to think about those. Accepting that quantum mechanics is "incomprehensible" defeats the purpose of doing physics. I struggle to find the purpose of tackling any questions in everything I see, but this book gave me a bit of hope that perhaps there is some way out of this rut.
4. Last but not least, at technical level I got a sense of how big the "complexity zoo" is, which is more than enough for my purpose (sadly I don't get enough details to appreciate them better). However, two subtopics stuck and I would like to know more just for the sake of it. The first is the notion of "learning": I think this has been employed in quantum many-body physics (shadow estimation stuff?), which is important because it exploits the very fact that we are limited in our capabilities to measure or learn something efficiently about physical systems. The second is about "proofs". The fact that proofs are computations are not itself unfamiliar to me (I mean, if you read a bit about incompleteness theorems or even about proof-assistants, this may not come as a surprise). The notion of interactive proofs, zero-knowledge proofs are all interesting to me. It is something you never realize possible until you read it; in fact, one may think that -probabilistic proofs- may be counter to what mathematicians call proofs. I think this is part of the story about famous complexity classes like (Q)MA. Either way, both topics feel like something I should "know" a bit more even if it is irrelevant for my work. Ah, actually, "randomness" was also interesting subject of the book that stuck - I mean, if a number looks random if you check it for as long as the age of the universe but is actually not, do you call it random?
Either way, I highly recommend this to people who are willing to burn (quite a bit of) brain cells to try to see what this person has to say about the world of complexity theory, quantum computing, and understanding the world in general. I think I lost in the forest 70% of the time, but I am glad I managed to get out with some harvests on my hand.
December 5, 2016
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.
March 24, 2018
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.
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.
March 18, 2018
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.
August 28, 2023
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.
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.
August 25, 2025
Not the easiest read for sure. Not entirely useful (by a long shot). This mostly related to a class the author taught. He is dumping the stuff he’s an expert in and given a lot of thoughts, rather than organizing some materials to educate laymen in a difficult subject (quantum computing). There are some areas that are well explained. For example, he explains quantum mechanics almost completely devoid of physics and argue how using an axiomatic way of establishing probability amplitude can better orient you. In other areas, the book form is a poor match. For example, the chapter on set is very technical and the form is probably not the best to learn. Probably warrant revisits as a reader learns more in the subject area.
July 9, 2019
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.
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.
May 17, 2020
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.
Read
February 21, 2019The 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.
December 1, 2017
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...
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...
June 25, 2019
3.5/5.0
September 23, 2021
Without a doubt my favorite textbook.
July 21, 2025
An "introductory" book that is best read by first reading other introductory books on varying topics.
Should really be called "Computational Complexity Since Democritus."
Should really be called "Computational Complexity Since Democritus."
Read
June 26, 2023Skimmed 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.
December 18, 2020
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.
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.
July 31, 2014
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'.
* 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'.
March 31, 2022
Признаюсь, где-то после начала обсуждения доказательств с нулевым разглашением я окончательно перестал понимать, что происходит, и более-менее въехал обратно только ближе к концу книги. Надеюсь, я перечитаю её позже, с большим объёмом знаний по теоретической информатике, и тогда смогу извлечь из неё больше пользы.
Не рекомендуется людям, не знакомым хотя бы с основами квантовой механики (на уровне вводного учебника, а не популярных лекций) и матлогики - не поймёте вообще ничего. Книга и без того написана не слишком методично, что усугубляется кривым переводом. Главы в середине книги и вовсе, вероятно, невозможно понять без предварительного знакомства с обсуждаемым в них предметом в объёме университетского курса.
С другой стороны, всё действительно очень и очень интересно, даже если квантовая информатика - не ваша специальность. Надеюсь, что после прочтения я получил хотя бы приблизительное представление о том, чем всё-таки занимаются специалисты по теории вычислительной сложности (а заодно о том, откуда Юдковский взял свою концепцию путешествий во времени для решения NP-полных задач, хе-хе-хе)
Не рекомендуется людям, не знакомым хотя бы с основами квантовой механики (на уровне вводного учебника, а не популярных лекций) и матлогики - не поймёте вообще ничего. Книга и без того написана не слишком методично, что усугубляется кривым переводом. Главы в середине книги и вовсе, вероятно, невозможно понять без предварительного знакомства с обсуждаемым в них предметом в объёме университетского курса.
С другой стороны, всё действительно очень и очень интересно, даже если квантовая информатика - не ваша специальность. Надеюсь, что после прочтения я получил хотя бы приблизительное представление о том, чем всё-таки занимаются специалисты по теории вычислительной сложности (а заодно о том, откуда Юдковский взял свою концепцию путешествий во времени для решения NP-полных задач, хе-хе-хе)
June 15, 2019
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.
April 19, 2014
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.
Definitely recommended to anyone who doesn't mind some math.
October 23, 2023
Some of the best relatively accessible intro on quantum computing and very engaging to read :)
Introduce quantum mechanics, classical and quantum complexity sometimes with humor and giving intuitions.
Introduce quantum mechanics, classical and quantum complexity sometimes with humor and giving intuitions.
July 8, 2017
Really should have a title that represents the fact that this is a book about complexity theory. It's really only tangentially about quantum computing.
October 1, 2023
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
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
October 31, 2025
"Quantum Computing since Democritus" by Scott Aaronson appears to be a comprehensive book that covers various topics related to quantum computing, logic, set theory, computability and complexity theory, quantum mechanics interpretation, among others.
From the sections I've read, here are some key points I learned about quantum computing:
1. Quantum circuits and gates: The book introduces basic concepts such as qubits, quantum gates (e. g., Hadamard gate, CNOT gate), and quantum circuit architecture.
2. Quantum algorithms: Aaronson discusses various quantum algorithms like Shor's algorithm for factoring large numbers, Grover's algorithm for searching unsorted databases, and Simon's algorithm for solving problems with periodic solutions.
3. Quantum error correction: The book covers the basics of quantum error-correcting codes and their importance in building fault-tolerant quantum computers.
4. Quantum complexity theory: Aaronson discusses various measures of computational complexity, such as circuit depth, number of qubits, and time complexity, as well as their implications for understanding the power of quantum computers.
5. Quantum information theory: The book covers topics like entanglement, teleportation, and quantum cryptography.
6. Interpretations of quantum mechanics: Aaronson provides an overview of different interpretations of quantum mechanics, such as the Copenhagen interpretation, many-worlds interpretation, pilot-wave theory, and more.
What I liked the most about the book is its ability to present complex topics in a clear and engaging manner, making it accessible to both beginners and experts in the field. The author's extensive knowledge and passion for the subject are evident throughout the book.
What I found confusing at times was some of the more advanced mathematical concepts, such as set theory and category theory, which might be challenging for those without a background in mathematics. However, Aaronson provides enough context and explanations to help readers understand these topics.
I would like to explore more about quantum algorithms and their practical applications, as well as the current state of quantum computing hardware and its development.
Regarding factual checking, I am not a quantum computing expert, so it is best for me to leave that assessment to experts in the field. However, the book has been praised by many in the community for its accuracy and depth.
From the sections I've read, here are some key points I learned about quantum computing:
1. Quantum circuits and gates: The book introduces basic concepts such as qubits, quantum gates (e. g., Hadamard gate, CNOT gate), and quantum circuit architecture.
2. Quantum algorithms: Aaronson discusses various quantum algorithms like Shor's algorithm for factoring large numbers, Grover's algorithm for searching unsorted databases, and Simon's algorithm for solving problems with periodic solutions.
3. Quantum error correction: The book covers the basics of quantum error-correcting codes and their importance in building fault-tolerant quantum computers.
4. Quantum complexity theory: Aaronson discusses various measures of computational complexity, such as circuit depth, number of qubits, and time complexity, as well as their implications for understanding the power of quantum computers.
5. Quantum information theory: The book covers topics like entanglement, teleportation, and quantum cryptography.
6. Interpretations of quantum mechanics: Aaronson provides an overview of different interpretations of quantum mechanics, such as the Copenhagen interpretation, many-worlds interpretation, pilot-wave theory, and more.
What I liked the most about the book is its ability to present complex topics in a clear and engaging manner, making it accessible to both beginners and experts in the field. The author's extensive knowledge and passion for the subject are evident throughout the book.
What I found confusing at times was some of the more advanced mathematical concepts, such as set theory and category theory, which might be challenging for those without a background in mathematics. However, Aaronson provides enough context and explanations to help readers understand these topics.
I would like to explore more about quantum algorithms and their practical applications, as well as the current state of quantum computing hardware and its development.
Regarding factual checking, I am not a quantum computing expert, so it is best for me to leave that assessment to experts in the field. However, the book has been praised by many in the community for its accuracy and depth.
Displaying 1 - 30 of 105 reviews