Comments on some extra chapters were added at the end
This reading report will be much more favorable than the previous one, one on minds and machines.
Chapters 5, 6, 7 etc. are dedicated to the classes of problems that may be solved in a reasonable time. They are full of arguments showing that if one type of a problem may be solved [at all AND/OR with some limitations on time AND/OR with some limitations on memory AND/OR with some probability of success AND/OR with some secret hints etc.], then another type of a problem may be solved at all.
This leaves a network of classes of algorithmic problems that are not known to coincide. This network is a result of simplifications resulting from some known proofs – proofs demonstrating the equivalence of some classes etc. – which have been taken into account. There's a lot of mathematical arguments that I have only partially verified but it seems clear that they have no good reason to be wrong because the researchers doing them aren't stupid (they're rather rigorous mathematicians) and there aren't any real subtleties that would require some "special kinds of intelligence" behind conventional math skills and rigor.
As an introduction to complexity, it's a wonderful resource. But I don't plan to memorize all the things that are known about the classes and particular problems and algorithms; instead, I know a good source where some basic things may be found if needed. ;-)
The last pre-quantum chapter is dedicated to cryptography. You learn about various simple and hard codes; functions that are easy to compute but hard to invert; various proofs that various coding systems may be cracked in one way or another, with or without some extra information, with or without a quantum computer.
One of the holy grails of the chapter is the explanation of the RSA algorithm. You want to send some information – e.g. your credit card number – somewhere – e.g. to amazon.com (by the way, the company just decided to build its 1st-2nd largest European logistical center in Czechia, not Poland; the other one is in Germany) so that no one except for amazon.com may decode it. How is it done? Amazon.com picks random large prime integers \(p,q\) which may be done quickly and computes \(N=pq\). It sends just \(N\) to you. You don't know \(p,q\) yourself. Your computer computes \(x^3\mod N\) where \(x\leq N-1\) is an integer representing your secret message (or credit card number).
It's probably impossible to efficiently revert this exponentiation i.e. to compute the cubic root modulo \(N\) directly. It's also impossible to quickly enough find factors \(p,q\) of the composite number \(N\). It's probably impossible to compute \(x\) out of \(N\) and \(x^3\mod N\) even indirectly – such a task probably can't be done without the impossible tasks in the previous two sentences. However, amazon.com knows \(p,q\) as well and with this extra knowledge, it may calculate \(x\). For technical reasons, \(p-1\) and \(q-1\) shouldn't be multiples of three. Safe. Probably. Only you and amazon.com can know \(x\): you know it because you used it to calculate \(x^3\mod N\); amazon.com knows it because it's the only server that knows \(p,q\) which is probably needed to compute the cubic root.
There is a lot of stuff of this kind in the book and if you're interested in cryptography, the book is recommended to you. However, I want to say a few words about
The quantum mechanics operating system
There are lots of the "discrete bias" in the book; I will mention it again below. But I was impressed by Scott Aaronson's first approach to quantum mechanics because it largely agrees with mine – and some detailed uniqueness claims and arguments supporting them are almost exactly equivalent to my text arguing that quantum mechanics can't be any different.
So Aaronson says that the conventional undergraduate approach to teaching of quantum mechanics deals with lots of technicalities like differential equations and ends up viewing the new conceptual framework as an ultimate mystery. He takes a different approach – quantum mechanics is presented as a new generalization of the probability theory.
It is correctly said that there are just three frameworks that are worth considering: classical deterministic systems; classical probabilistic systems; and quantum mechanics. Arguments are given why quantum mechanics has to be based on squaring the (absolute values of the) amplitudes; why the complex numbers are the only right, "Goldilocks", number system for quantum mechanics (their being algebraically closed is also mentioned, much like the natural counting linked to the fact that complex representations of groups are the default ones); why operators have to be linear, and so on.
Some of the arguments are literally the same as mine. For example, the reason why the probabilities are given by the second power is explained by the fact that only for the exponents \(p=1\) and \(p=2\), one may find some unitary-like transformations of the probability amplitude vectors that preserve the norm and that are nontrivial i.e. more complicated than permutations with sign flips.
The unitary matrices are cleverly presented as the quantum answer to the stochastic matrices in classical physics. There isn't any other comparably interesting and nontrivial class of matrices with similar properties which is a part of the reason why classical and quantum physics are the only two frameworks to deal with probabilities in physics.
Of course, this introductory quantum chapter also discusses the cloning no-go theorem, tensor products, entangled states, and similarly basic notions, along with the quantum teleportation and even quantum money and other less rudimentary concepts in applied quantum physics (including references to some papers by Aaronson himself).
I don't really believe that there will be a single person who doesn't know quantum mechanics in advance but who will learn it from the book – the introduction to quantum mechanics in this chapter is arguably too concise – but I do think that it could be helpful to reorganize the teaching of quantum mechanics along these lines.
At the beginning, the author also says that quantum mechanics (the general postulates etc.) is "somewhere in between maths and physics in the hierarchy of scientific disciplines that continue with chemistry and biology". It's more physical than just maths and the ordinary probability theory in maths; but it's less physical than particular physical theories. It's an operating system on which particular physical models run as applications. I couldn't agree more.
Aaronson's computer-science bias only begins to emerge – at least I hope so – when he discusses what the actual applications are. So he apparently believes that all the applications, including those defining the fundamental laws of physics, should be of discrete nature which ain't the case. The quantum mechanical operating system perfectly allows the observables with continuous spectra and some operators of this kind are always needed to define the physical laws for the adults.
His flawed perception that bits, and not nats, are physically natural units of information and entropy is also imprinted in at least one characteristic error. The book doesn't avoid mathematical formulae and they're largely accurate. However, he applies the prime number theorem incorrectly to compute how many prime numbers with at most \(N\) bits are there. What do you think the result asymptotically is, including the right prefactors of order one? ;-)
Such annoying prefactors have to occur everywhere simply because \(2\) is an unnatural base for exponentials and logarithms much like a bit (and qubit) is an unnatural unit of information and entropy. But I am learning how to sharply separate these misconceptions of folks like Aaronson from the "operating system"-level of knowledge (including the quantum one) that they apparently understand correctly.
Quantum computers
Chapter 10 finally jumps at the inevitable union of computation and quantum mechanics, quantum computation. My intro to quantum computation is here. Sadly, one of several promising quantum computers that exist on Earth, one inside a diamond, was eaten by an 80-year-old grandma yesterday.
The author marvels that only in the 1990s, people started to ask which problems may be feasibly solved by computers allowed by Nature's being quantum mechanical. I also find it amazing that this branch of computer science wasn't born earlier.
He talks about the Hadamard gate etc. (replacing the universal NAND gate of classical computers), reasons why quantum computers may do everything that classical (even classical probabilistic) computers can do, and so on.
There are interesting two sections at the end of the chapter in which Aaronson debunks the super-naive "quantum computer as exponentially parallel classical computer" meme and the related misconceptions promoted largely by David Deutsch that quantum computation "proves the many worlds interpretation". Scott doesn't say as much as I did e.g. in this criticism of the many worlds but he does say certain things, for example that MWI can't say what is the preferred basis into which the world "splits" (it also can't say when and how etc. and the very claim that it does irreversibly split is wrong because at least in principle, there's always a nonzero chance of "reinterference").
The related idea that the "quantum computation is a massively parallel classical computation" is flawed and this big blunder may be illuminated in many ways. First of all, it's not true that the streams in the "massively parallel set of classical calculations within a quantum computer" are independent. Quite on the contrary, the result announced by a quantum computer depends on interference i.e. "collaboration" between these streams or "different histories".
Moreover, the textbook example of a problem you may want to massively speed up – the search of something in a database – can't be exponentially sped up by a quantum computer. Instead, Grover's algorithm only provides us with a power-law speedup. In fact, it's been proved before the algorithm was found that a faster quantum algorithm than the power ultimately realized by Grover's algorithm can't exist! As always, any attempt to sell quantum mechanics as some "kind of a classical theory" (whether it's parallel or not, whether it has hidden variables or not, whatever are its preferred observables etc.) may ultimately be proven deeply misguided. Quantum mechanics isn't classical, stupid.
Aaronson also extends his collection of classes of problems waiting for algorithms with classes that allow some/complete solution using a quantum computer. He reinterprets Feynman's path integral as the proof that one class belongs to another. That's what Feynman got his Nobel prize for, we learn. It's an amusing attempt of a computer scientist to "devour physics" but at least historically, it's completely wrong because Feynman shared their Nobel prize for QED, an application of his computational methods (including the path integral), not for the path integral itself (although his Nobel lecture essentially was mostly about the path integral).
Moreover, Aaronson only presented one particular application of Feynman's path integrals. Any physically meaningful question about a quantum system may be answered using Feynman's path integral which makes it kind of silly to associate this method with some "very special problems".
Chapter 11 is about Penrose, namely his opinions that G̦del-theorems-based reasoning can show that artificial intelligence is impossible and the human brain has some super-remarkable abilities (apparently exceeding any omniscient quantum computer or God you may think of) that can't be simulated. I agree with 100% of what Aaronson says here (why Penrose's arguments are ultimately irrational, illogical, unstable, not solving the original "problems", and wrong) Рand there's a lot he says.
Initially I thought that I would fully endorse every sentence of Chapter 12, one on decoherence and hidden variables. In the early passages, it says all the important right things. Decoherence is the right phenomenon that contains all the genuine processes people call "collapse" sometimes and its right description is the hopeless entanglement with the environment which converts quantum bits to effectively classical bits. It's irreversible and from some viewpoint, decoherence is just a new nearly equivalent way to describe the second law of thermodynamics. The reversal is as difficult as Pamela Anderson's attempts to regain privacy by targeting all the hard disks in the world that contain her photos – I liked this joke, indeed. ;-)
In the following sections about hidden variables, it lists most of the reasons why they're wrong – they only allow one to discuss measurements of particular observables (positions) but we need to predicts others and it's not possible to have classical "beable" states for all of them (Kochen-Specker theorem). Hidden-variables fundamentally violate relativity because they need superluminal communication to explain the correlations, whether or not it may be used in practice. Some important criticisms are omitted – like what happens with the insanely propagating, diluting pilot wave after the measurement or absorption of the particles etc.
However, the final "positive" sections on the hidden-variable theories have dramatically lowered my opinion about the chapter. He discusses "flow of oil", Schr̦dinger's, and Bohm's theories. Aaronson fails to notice that (and why) some of them are really equivalent to each other. He seems ignorant about the Bohmian and equivalent theories' history Рit was started by Louis de Broglie in 1927. Most importantly, he suddenly seems to forget all the right criticisms he previously raised: violations of relativity; need for privileged observables and bases, etc. So at the end, I think that the chapter is a rather eclectic mixture of "mutually contradicting but not confronted" right and wrong statements that suggest that Scott hasn't thought about these matters too carefully (despite his having published papers on hidden variables). I was also irritated by the criticism against the Bohmian hidden variables (which are really equivalent to the "flow of oil" when looked at properly) for their infinite dimension of the Hilbert space. Every realistic theory of the "real world" has an infinite-dimensional Hilbert space; this is surely not something one could use as a criticism (although the existence of discrete degrees of freedom such as the spin is another way to see the inadequacy of the hidden variable theories). Again, we see the limitations of a "discrete computer scientist" Aaronson here. Also, I don't believe that a reader who hasn't studied decoherence (or hidden variables) previously will learn what it is (or they are).
This reading report will be much more favorable than the previous one, one on minds and machines.
Chapters 5, 6, 7 etc. are dedicated to the classes of problems that may be solved in a reasonable time. They are full of arguments showing that if one type of a problem may be solved [at all AND/OR with some limitations on time AND/OR with some limitations on memory AND/OR with some probability of success AND/OR with some secret hints etc.], then another type of a problem may be solved at all.
This leaves a network of classes of algorithmic problems that are not known to coincide. This network is a result of simplifications resulting from some known proofs – proofs demonstrating the equivalence of some classes etc. – which have been taken into account. There's a lot of mathematical arguments that I have only partially verified but it seems clear that they have no good reason to be wrong because the researchers doing them aren't stupid (they're rather rigorous mathematicians) and there aren't any real subtleties that would require some "special kinds of intelligence" behind conventional math skills and rigor.
As an introduction to complexity, it's a wonderful resource. But I don't plan to memorize all the things that are known about the classes and particular problems and algorithms; instead, I know a good source where some basic things may be found if needed. ;-)
The last pre-quantum chapter is dedicated to cryptography. You learn about various simple and hard codes; functions that are easy to compute but hard to invert; various proofs that various coding systems may be cracked in one way or another, with or without some extra information, with or without a quantum computer.
One of the holy grails of the chapter is the explanation of the RSA algorithm. You want to send some information – e.g. your credit card number – somewhere – e.g. to amazon.com (by the way, the company just decided to build its 1st-2nd largest European logistical center in Czechia, not Poland; the other one is in Germany) so that no one except for amazon.com may decode it. How is it done? Amazon.com picks random large prime integers \(p,q\) which may be done quickly and computes \(N=pq\). It sends just \(N\) to you. You don't know \(p,q\) yourself. Your computer computes \(x^3\mod N\) where \(x\leq N-1\) is an integer representing your secret message (or credit card number).
It's probably impossible to efficiently revert this exponentiation i.e. to compute the cubic root modulo \(N\) directly. It's also impossible to quickly enough find factors \(p,q\) of the composite number \(N\). It's probably impossible to compute \(x\) out of \(N\) and \(x^3\mod N\) even indirectly – such a task probably can't be done without the impossible tasks in the previous two sentences. However, amazon.com knows \(p,q\) as well and with this extra knowledge, it may calculate \(x\). For technical reasons, \(p-1\) and \(q-1\) shouldn't be multiples of three. Safe. Probably. Only you and amazon.com can know \(x\): you know it because you used it to calculate \(x^3\mod N\); amazon.com knows it because it's the only server that knows \(p,q\) which is probably needed to compute the cubic root.
There is a lot of stuff of this kind in the book and if you're interested in cryptography, the book is recommended to you. However, I want to say a few words about
The quantum mechanics operating system
There are lots of the "discrete bias" in the book; I will mention it again below. But I was impressed by Scott Aaronson's first approach to quantum mechanics because it largely agrees with mine – and some detailed uniqueness claims and arguments supporting them are almost exactly equivalent to my text arguing that quantum mechanics can't be any different.
So Aaronson says that the conventional undergraduate approach to teaching of quantum mechanics deals with lots of technicalities like differential equations and ends up viewing the new conceptual framework as an ultimate mystery. He takes a different approach – quantum mechanics is presented as a new generalization of the probability theory.
It is correctly said that there are just three frameworks that are worth considering: classical deterministic systems; classical probabilistic systems; and quantum mechanics. Arguments are given why quantum mechanics has to be based on squaring the (absolute values of the) amplitudes; why the complex numbers are the only right, "Goldilocks", number system for quantum mechanics (their being algebraically closed is also mentioned, much like the natural counting linked to the fact that complex representations of groups are the default ones); why operators have to be linear, and so on.
Some of the arguments are literally the same as mine. For example, the reason why the probabilities are given by the second power is explained by the fact that only for the exponents \(p=1\) and \(p=2\), one may find some unitary-like transformations of the probability amplitude vectors that preserve the norm and that are nontrivial i.e. more complicated than permutations with sign flips.
The unitary matrices are cleverly presented as the quantum answer to the stochastic matrices in classical physics. There isn't any other comparably interesting and nontrivial class of matrices with similar properties which is a part of the reason why classical and quantum physics are the only two frameworks to deal with probabilities in physics.
Of course, this introductory quantum chapter also discusses the cloning no-go theorem, tensor products, entangled states, and similarly basic notions, along with the quantum teleportation and even quantum money and other less rudimentary concepts in applied quantum physics (including references to some papers by Aaronson himself).
I don't really believe that there will be a single person who doesn't know quantum mechanics in advance but who will learn it from the book – the introduction to quantum mechanics in this chapter is arguably too concise – but I do think that it could be helpful to reorganize the teaching of quantum mechanics along these lines.
At the beginning, the author also says that quantum mechanics (the general postulates etc.) is "somewhere in between maths and physics in the hierarchy of scientific disciplines that continue with chemistry and biology". It's more physical than just maths and the ordinary probability theory in maths; but it's less physical than particular physical theories. It's an operating system on which particular physical models run as applications. I couldn't agree more.
Aaronson's computer-science bias only begins to emerge – at least I hope so – when he discusses what the actual applications are. So he apparently believes that all the applications, including those defining the fundamental laws of physics, should be of discrete nature which ain't the case. The quantum mechanical operating system perfectly allows the observables with continuous spectra and some operators of this kind are always needed to define the physical laws for the adults.
His flawed perception that bits, and not nats, are physically natural units of information and entropy is also imprinted in at least one characteristic error. The book doesn't avoid mathematical formulae and they're largely accurate. However, he applies the prime number theorem incorrectly to compute how many prime numbers with at most \(N\) bits are there. What do you think the result asymptotically is, including the right prefactors of order one? ;-)
Such annoying prefactors have to occur everywhere simply because \(2\) is an unnatural base for exponentials and logarithms much like a bit (and qubit) is an unnatural unit of information and entropy. But I am learning how to sharply separate these misconceptions of folks like Aaronson from the "operating system"-level of knowledge (including the quantum one) that they apparently understand correctly.
Quantum computers
Chapter 10 finally jumps at the inevitable union of computation and quantum mechanics, quantum computation. My intro to quantum computation is here. Sadly, one of several promising quantum computers that exist on Earth, one inside a diamond, was eaten by an 80-year-old grandma yesterday.
The author marvels that only in the 1990s, people started to ask which problems may be feasibly solved by computers allowed by Nature's being quantum mechanical. I also find it amazing that this branch of computer science wasn't born earlier.
He talks about the Hadamard gate etc. (replacing the universal NAND gate of classical computers), reasons why quantum computers may do everything that classical (even classical probabilistic) computers can do, and so on.
There are interesting two sections at the end of the chapter in which Aaronson debunks the super-naive "quantum computer as exponentially parallel classical computer" meme and the related misconceptions promoted largely by David Deutsch that quantum computation "proves the many worlds interpretation". Scott doesn't say as much as I did e.g. in this criticism of the many worlds but he does say certain things, for example that MWI can't say what is the preferred basis into which the world "splits" (it also can't say when and how etc. and the very claim that it does irreversibly split is wrong because at least in principle, there's always a nonzero chance of "reinterference").
The related idea that the "quantum computation is a massively parallel classical computation" is flawed and this big blunder may be illuminated in many ways. First of all, it's not true that the streams in the "massively parallel set of classical calculations within a quantum computer" are independent. Quite on the contrary, the result announced by a quantum computer depends on interference i.e. "collaboration" between these streams or "different histories".
Moreover, the textbook example of a problem you may want to massively speed up – the search of something in a database – can't be exponentially sped up by a quantum computer. Instead, Grover's algorithm only provides us with a power-law speedup. In fact, it's been proved before the algorithm was found that a faster quantum algorithm than the power ultimately realized by Grover's algorithm can't exist! As always, any attempt to sell quantum mechanics as some "kind of a classical theory" (whether it's parallel or not, whether it has hidden variables or not, whatever are its preferred observables etc.) may ultimately be proven deeply misguided. Quantum mechanics isn't classical, stupid.
Aaronson also extends his collection of classes of problems waiting for algorithms with classes that allow some/complete solution using a quantum computer. He reinterprets Feynman's path integral as the proof that one class belongs to another. That's what Feynman got his Nobel prize for, we learn. It's an amusing attempt of a computer scientist to "devour physics" but at least historically, it's completely wrong because Feynman shared their Nobel prize for QED, an application of his computational methods (including the path integral), not for the path integral itself (although his Nobel lecture essentially was mostly about the path integral).
Moreover, Aaronson only presented one particular application of Feynman's path integrals. Any physically meaningful question about a quantum system may be answered using Feynman's path integral which makes it kind of silly to associate this method with some "very special problems".
Chapter 11 is about Penrose, namely his opinions that G̦del-theorems-based reasoning can show that artificial intelligence is impossible and the human brain has some super-remarkable abilities (apparently exceeding any omniscient quantum computer or God you may think of) that can't be simulated. I agree with 100% of what Aaronson says here (why Penrose's arguments are ultimately irrational, illogical, unstable, not solving the original "problems", and wrong) Рand there's a lot he says.
Initially I thought that I would fully endorse every sentence of Chapter 12, one on decoherence and hidden variables. In the early passages, it says all the important right things. Decoherence is the right phenomenon that contains all the genuine processes people call "collapse" sometimes and its right description is the hopeless entanglement with the environment which converts quantum bits to effectively classical bits. It's irreversible and from some viewpoint, decoherence is just a new nearly equivalent way to describe the second law of thermodynamics. The reversal is as difficult as Pamela Anderson's attempts to regain privacy by targeting all the hard disks in the world that contain her photos – I liked this joke, indeed. ;-)
In the following sections about hidden variables, it lists most of the reasons why they're wrong – they only allow one to discuss measurements of particular observables (positions) but we need to predicts others and it's not possible to have classical "beable" states for all of them (Kochen-Specker theorem). Hidden-variables fundamentally violate relativity because they need superluminal communication to explain the correlations, whether or not it may be used in practice. Some important criticisms are omitted – like what happens with the insanely propagating, diluting pilot wave after the measurement or absorption of the particles etc.
However, the final "positive" sections on the hidden-variable theories have dramatically lowered my opinion about the chapter. He discusses "flow of oil", Schr̦dinger's, and Bohm's theories. Aaronson fails to notice that (and why) some of them are really equivalent to each other. He seems ignorant about the Bohmian and equivalent theories' history Рit was started by Louis de Broglie in 1927. Most importantly, he suddenly seems to forget all the right criticisms he previously raised: violations of relativity; need for privileged observables and bases, etc. So at the end, I think that the chapter is a rather eclectic mixture of "mutually contradicting but not confronted" right and wrong statements that suggest that Scott hasn't thought about these matters too carefully (despite his having published papers on hidden variables). I was also irritated by the criticism against the Bohmian hidden variables (which are really equivalent to the "flow of oil" when looked at properly) for their infinite dimension of the Hilbert space. Every realistic theory of the "real world" has an infinite-dimensional Hilbert space; this is surely not something one could use as a criticism (although the existence of discrete degrees of freedom such as the spin is another way to see the inadequacy of the hidden variable theories). Again, we see the limitations of a "discrete computer scientist" Aaronson here. Also, I don't believe that a reader who hasn't studied decoherence (or hidden variables) previously will learn what it is (or they are).
Democritus on the QM operating system
![Democritus on the QM operating system]()
Reviewed by DAL
on
April 27, 2013
Rating:
No comments: