Quantum Computing Since Democritus Lecture 3: Gödel, Turing, and Friends
Gödel, Turing, and Friends. Another whole course compressed into one handwaving lecture. (This will be a recurring theme.)
Gödel, Turing, and Friends. Another whole course compressed into one handwaving lecture. (This will be a recurring theme.)
Follow
Comment #1 September 27th, 2006 at 2:54 pm
One of the best predictors of success in mathematical logic is having an umlaut in your name.
Does this mean you’re changing your name to Scött?
Comment #2 September 27th, 2006 at 4:05 pm
Just curious: why does viewing quantum mechanics as an “intermediate” between discrete theories and continuous theories require the Hilbert space to be finite-dimensional?
Comment #3 September 27th, 2006 at 4:24 pm
Does this mean you’re changing your name to Scött?
No, he’s changing it to Scoẗẗ.
Comment #4 September 27th, 2006 at 4:44 pm
Does this mean you’re changing your name to Scött?
No, because I’m not a logician.
Comment #5 September 27th, 2006 at 4:49 pm
James: If the Hilbert space is continuous, then we just get the quantum analogues of classical continuous theories (such as field theories), with all of the associated drawbacks from my perspective.
If the Hilbert space has countably infinite dimension, then we’re in a better situation (though one still might be able to pose questions whose answers depend on AC or CH — I’d have to think about that).
Comment #6 September 27th, 2006 at 5:27 pm
Actually, it is a precept of mathematical physics that all reasonable Hilbert spaces are separable (have a countable Hilbert basis), even if they arise in quantum field theory or string theory.
Of course there is also the more elementary remark that a Hilbert space may look “countinuous” but still have a countable basis. For instance L^2(R) (square-integrable functions on the reals) has a basis consisting of exp(-x^2/4)*poly(x), where poly(x) is a Hermite polynomial.
Comment #7 September 27th, 2006 at 5:49 pm
Greg: That’s really interesting — thanks! I guess what you’re saying is that, if we consider wavefunctions of (say) a single particle on the real line, then it’s unphysical to measure in the “obvious basis,” consisting of all |x> where x is a real number. (Even though these vectors do correspond to legitimate probability distributions, namely the singleton distributions!) Instead we should only consider measurements in a countable basis, like Gaussians times Hermite polynomials, and wavefunctions that can be written in that basis. Incidentally, can the “singleton function,” f(x)=infinity if x=0 and f(x)=0 otherwise, be written as a linear combination of those basis vectors?
My next question would be this. If we do consider the Aleph0-dimensional Hilbert space of square-integrable functions on the real line, are there natural questions about that space whose truth or falsehood depends on AC or CH?
Comment #8 September 27th, 2006 at 6:25 pm
Greg: That’s really interesting — thanks! I guess what you’re saying is that, if we consider wavefunctions of (say) a single particle on the real line, then it’s unphysical to measure in the “obvious basis,” consisting of all |x> where x is a real number.
The real answer, of course, is that {|x>} isn’t a basis of L^2(R). In fact, it isn’t even a subset of L^2(R), because |x> is not normalizable. That doesn’t stop physicists from talking about things like |x> or its Fourier dual (a plane wave). What they mean is an idealized limit of a sequence of states that does exist in L^2.
Also, to answer your question, each |x> can be written as a divergent sum (or integral) of honest elements of L^2. Also, {|x>} works as a kind of pseudobasis, in that elements of L^2 are expressible as integrals over them, provided that the multiplier in the integrand is a square-integrable function. (If you think about it, it’s a tautology.)
The Hilbert space with basis {|x>} is the space of square-summable superpositions of point states. The understandable wisdom of mathematical physics is that if that is the Hilbert space that you really want, then your train of thought has probably hopped the rails.
Now, you sort-of asked what is good or bad about the position operator as a measurement if it doesn’t have any eigenvectors. (An operator like this is officially called “continuous spectrum”.) The answer is that the realistic measurement is a POVM approximation. This is what POVMs were invented for.
If we do consider the Aleph0-dimensional Hilbert space of square-integrable functions on the real line, are there natural questions about that space whose truth or falsehood depends on AC or CH?
The first thought that comes to mind is the Hahn-Banach theorem and related. I would have to think a bit to come up with a specific example. But I have the feeling that “convenient” or “interesting” are inevitably better words than “natural” for any connection between physics and AC. (Even more so CH.)
Comment #9 September 27th, 2006 at 6:43 pm
Now, you sort-of asked what is good or bad about the position operator as a measurement if it doesn’t have any eigenvectors. (An operator like this is officially called “continuous spectrum”.) The answer is that the realistic measurement is a POVM approximation. This is what POVMs were invented for.
I see — so the relevant POVM would return (say) the position smeared by Gaussian noise. Then even though the measurement result is a real number, it has only finite mutual information with the wavefunction, provided the wavefunction is bounded within a finite interval. (Indeed, this is true even if the wavefunction is a point function.)
Comment #10 September 27th, 2006 at 7:15 pm
Turing’s first result is the existence of a “universal” machine: a machine whose job is to simulate any other machine described via symbols on the tape. In other words, programmable computers can exist.
I don’t see how this is ‘in other words’, we have known about programmable computers at least since Babbage and furthermore one could create a non–Turing complete machine which could be programmed to accomplish the examples which follow the above qoute.
Comment #11 September 27th, 2006 at 7:25 pm
anonymous: Babbage and Lovelace certainly had the idea for a programmable computer, but as far as I know they didn’t prove their machine was universal. (Indeed in order to prove that, they would’ve first needed the notion of a computable function.)
The examples that follow were just that: examples. If you really want to nitpick, I suppose they can all be implemented by a finite automaton, since presumably any “real” program only addresses a bounded amount of memory.
Comment #12 September 27th, 2006 at 7:28 pm
When we consider infinte dimensional spaces we have to be careful when we speak of a basis. For a finite dimensional vector space a basis is simply the thing we learn about in linear algebra, i.e. a finite set of vectors such that every other vector has a unique representation as a linear combination of these vectors.
For an infinite dimensional vector space there are two kinds of bases. First the algebraic, or Hamel, basis. A basis of this kind has the quite strong property that every element in the space can be given as a finite linear combination of elements from the basis. Such a basis must of course be infinite, and few spaces have them.
There is also the Schauder basis. A Schauder base can represent every element of a normed space as an infinite linear combination of basis elements, in the sense that the difference between the linear combination and the original vector is zero in the given norm. A suitable finite truncation of the linear combination gives a good approximation of the element in the norm.
One tricky thing about Schauder bases for function spaces, such as the Fourier basis for L^2, is that even for continuous functions the series can diverge at an everywhere dense set of points, which has measure zero. You can also get different results just by rearranging the order of summation.
In some way I guess one might want to avoid some of these patological behaviours in physics, one way or another.
Comment #13 September 27th, 2006 at 7:34 pm
Not to reopen that argument, but are CS types wrong that QC has much of the flavor of analog computation? I think not. The observations may be discrete, but manipulating their probability is most decidedly an analog operation.
Our digital computations can be treated as such because the nonlinearities in MOSFETs allow us to regenerate an adequate approximation of a digital state. QM, of course, is linear. The billion-dollar question is whether the nonlinearity of measurement is good enough to allow us to repeatedly regenerate a good enough approximation of the state probabilities and phases that the computation itself succeeds. Many people are convinced that it is; I’ve been through the math enough times to be comfortable with how it works on paper, but there are still things about, for example, how accurate the basis we measure in is in the physical world that nag at me.
And the QFT is a most decidedly analog computation (before measurement), where the rotation angles are small and the interference between terms that gives us the final state we want is analog. The question is whether QEC is enough to keep this process on track, and what the behavior is with imperfect gates. Barenco, Ekert, Fowler, and others have all investigated this issue, but I admit to still having lingering doubts.
So, in the end, I don’t think the question of whether quantum computation is analog should be either asked or dismissed lightly. I think it tells us something very profound, and ultimately will prove to involve quite deeply issues of the real world.
P.S. I bit my tongue on the university issue, since that is a very long and involved argument on society and the role of educational institutions, but suffice it to say that in Japan, it is more than just a simple test score that determines which university you attend (indeed, it can be effectively decided as early as preschool). As is inevitable anywhere, many factors, including your socio-economic background, determine everything from your level of accomplishment to your self-image and ambitions. Once you get to the actual test, yes, numerical results are what count, but how did you get there? It may surprise you, but acceptance rates at even the best universities may be 50% or more, no doubt because of self-selection: if you’re not the right “type” for a particular university, you don’t apply.
But that’s a long conversation, and should be in another forum. I’m reading a book of Whitehead’s on education, a set of lectures he gave in the 1910s and 20s. It’s fascinating, profound in places and quaint in others. Some day I’ll post about it on my blog.
Comment #14 September 27th, 2006 at 7:47 pm
Scott: I see — so the relevant POVM would return (say) the position smeared by Gaussian noise. Then even though the measurement result is a real number, it has only finite mutual information with the wavefunction, provided the wavefunction is bounded within a finite interval.
Right. Although I should have said that there is alternative approximation to measuring x which is just a plain old Hermitian operator (with point spectrum). Namely, you chop R into short intervals, which you could call “buckets”, and just measure which bucket has the particle.
However, if you want a translationally invariant approximation, then you really do need a POVM.
Comment #15 September 27th, 2006 at 7:54 pm
Scott, you seem to being equating universality with programmability, suggesting that if a machine isn’t universal it cannot be programmable. This seems a strange definition of programmable to me and I think liable to confuse beginners.
‘In other words, programmable computers can exist’
My point was we already knew they could exist since Babbage gave an example. If you don’t equate universality with programmability it is irrelevant if his example was universal or not.
I apologise for not being clear the first time round.
Comment #16 September 27th, 2006 at 7:59 pm
For an infinite dimensional vector space there are two kinds of bases. First the algebraic, or Hamel, basis. A basis of this kind has the quite strong property that every element in the space can be given as a finite linear combination of elements from the basis. Such a basis must of course be infinite, and few spaces have them.
All of this is technically correct or almost correct, but in my view this is a bit more doctrinaire functional analysis than necessary.
By the axiom of choice, every vector space has an algebraic basis. What you mean is a countable algebraic basis. It is not true that “few” spaces have them. No infinite-dimensional Banach spaces whatsoever have them. However, vector spaces in algebra, for example polynomial rings, do have countable algebraic bases.
Another remark is that an algebraic basis is a special case of a topological basis, when the vector space in question has the discrete topology. The terminology “Hamel” and “Schauder” is peculiar to functional analysis, and makes it sound like algebraic bases aren’t topological bases. But this is wrong.
A Schauder base can represent every element of a normed space as an infinite linear combination of basis elements, in the sense that the difference between the linear combination and the original vector is zero in the given norm.
In the sense that the linear combination in question is a convergent series, which is obviously what you always want.
One tricky thing about Schauder bases for function spaces, such as the Fourier basis for L^2, is that even for continuous functions the series can diverge at an everywhere dense set of points, which has measure zero.
Right, a Fourier series in the Hilbert space L^2(circle) may not converge in the topology of pointwise convergence. However, it does always does converge in the supremely more relevant L^2 topology. The lesson for functional analysis is that you should be very careful when you hop between topologies on a vector space. (Or parts of it; the pointwise topology is not even defined on all of L^2.) The lesson for most of quantum mechanics and quantum information theory is to stick to the Hilbert space and its best topology.
Comment #17 September 27th, 2006 at 7:59 pm
rdv:
And the QFT is a most decidedly analog computation (before measurement), where the rotation angles are small
In implementing QFT, you don’t have to perform the rotations whose angles are below some epsilon. Precisely because these rotations are so small, omitting them can have only a negligible effect on the output.
(That QFT requires exponentially-small rotations is one of the most common misconceptions I’ve encountered…)
More generally, we know universal quantum computing is possible provided the error per qubit per time step is below a constant. To me, this makes it hard to argue that, as a formal model of computation, quantum computing is “analog.”
Of course, whether the formal model corresponds to reality is a different question — one that I took up in the other post.
Comment #18 September 27th, 2006 at 8:05 pm
Scott, you seem to being equating universality with programmability, suggesting that if a machine isn’t universal it cannot be programmable. This seems a strange definition of programmable to me and I think liable to confuse beginners.
Thanks! I changed the text to clarify this.
Comment #19 September 27th, 2006 at 8:21 pm
Greg — I’ve always been perplexed about the physical reasons for assuming separability. Do you know of any such reason?
Michael Nielsen
Comment #20 September 27th, 2006 at 8:24 pm
It’s a shame that, after proving his Completeness Theorem, Gödel never really did anything else of note.
We will see if Scott will *ever* do anything that is truly of note.
Comment #21 September 27th, 2006 at 8:26 pm
I’m very much aware of the approximate QFT work and the argument that you can ignore the low-order parts of the computation — but most certainly not of the result. But that doesn’t change the fact that the basic method of interfering states correctly to get the desired end state out of the QFT requires that the analog amplitudes of the states be managed to certain, relatively high, analog fidelity.
The two papers of which I am aware that are most relevant to my concerns are Barenco et al. and Fowler and Hollenberg. One evaluates a large-R approximation, the other a small-R approximation, and they get very different results for the scaling of the success probability on imperfect systems. Austin has been very good about answering my questions, and I have partially reproduced his results, so I think I understand where they are coming from, but I reserve the right to have reservations :-).
At any rate, I stand by statement that the analog/discete argument is actually non-trivial, and is a window into important insight on both the nature of computation and the possibility of building adequately robust real-world machines. I’m an engineer; I want to build and use one of these things :-).
Comment #22 September 27th, 2006 at 8:30 pm
Greg — I’ve always been perplexed about the physical reasons for assuming separability. Do you know of any such reason?
I am not expert on this question, but I think that the idea is that the world would be such a large stage that most actors would never see each other. Given the uncountable orthonormal basis, only countably many amplitudes of any normalized state would be non-zero. This suggests that most of the model is formal and that all of the physics is in some separable subspace.
Or another thing that might happen is that time evolution is too discontinuous to have a Hamiltonian. Take the Hilbert space that I mentioned above, where each |x> is a true basis vector. Then the particle which is in state |t> at time t may look like it follows a continuous path, but it doesn’t. In effect, it is a misalignment between formalism and intended physics. I think that any continuous path of normalized states has to lie in a separable subspace of the Hilbert space.
Comment #23 September 27th, 2006 at 9:22 pm
We will see if Scott will *ever* do anything that is truly of note.
LOL — you didn’t get the joke?! As the rest of the paragraph explains, the Completeness Theorem was just a warmup to the Incompleteness Theorem…
Comment #24 September 27th, 2006 at 9:30 pm
rdv: The relevant results in the two papers you linked to follow immediately from more general considerations. (Gates with miniscule effects can always be omitted, not just in the special case of QFT.) See Bernstein-Vazirani and Aharonov-Ben-Or.
Comment #25 September 27th, 2006 at 9:38 pm
As the rest of the paragraph explains, the Completeness Theorem was just a warmup to the Incompleteness Theorem…
I feel sorry for Gödel. It’s really frustrating to just contradict your old work.
Comment #26 September 27th, 2006 at 9:49 pm
Greg: Thanks for the comment.
Anonymous says:
“We will see if Scott will *ever* do anything that is truly of note.”
Presumably anonymous’s modus operandi at parties is to attend in disguise, publicly insult the host (after quoting them entirely out of context), and then to run away. Classy.
Michael Nielsen
Comment #27 September 27th, 2006 at 10:21 pm
Sigh. We’re talking past each other, so I suppose I should just pack it in, since I don’t really need to continue to up my Public Denseness Demonstration Quotient (PDDQ).
You’re satisfied with the mathematical proof that QC works. I won’t be satisfied until I have seen it work — or, better yet, made it work. Count me with Babbage, rather than Wollaston or Davy.
I’ve read the papers you cite. They’re important, seminal work, and very reassuring. Likewise, I have read a large stack of papers on quantum error correction. But as an engineer, I find a more recent paper by Steane to be one of the most exciting and important papers around, because it analyzes with care how to best build a real system — and I suspect that particular paper would put you to sleep.
[Up until now there have been two main classes of people in QC — theorists and experimentalists. Of course, there are many types of each, including theorists up where you are and theorists trying to figure out how to build the best superconducting qubit. People keep trying to put me in one category or the other. But I am in the vanguard (led by Mark Oskin) of a third type of critter — computer systems people working on QC; I’m an architect and engineer. If you evaluate me based on how you evaluate theorists, I will always rate poorly. We will have more in common with the experimentalists than the theorists up where you are, but the experimentalists look at me like I’m insane when I talk about thousands to millions of qubits.
Every time you say something has been “proven”, we will look at each other uncomfortably and recall the difficulty we had getting the right eye shape on the oscilloscope, or getting the interrupt handler right, or getting it all to fit in memory without swapping, or fitting enough wires into one place as we try to make your theories actually work. Expect more people like me in the future :-).]
In short, I find an argument that something has been proven, and that everything else is just engineering details, to be unsatisfying.
Comment #28 September 27th, 2006 at 10:39 pm
The bits of your lectures that I’ve read so far are great fun, Scott. (I’ve been skimming some bits.)
If you haven’t already covered it, I think Rice’s theorem is great fun, and would fit right in. The fact that you can’t decide _any_ black box property at all (no universal debugger!) strikes me as amazingly cool. You could just about make the proof a problem for the class.
Michael Nielsen
Comment #29 September 27th, 2006 at 10:42 pm
I have enormous respect for the people trying to build quantum computers. I would never ask that they be judged by the same standards as theorists.
All I ask is that we clearly distinguish between two questions: (1) whether quantum computing is an analog model of computation, and (2) whether the model corresponds to physical reality. I was discussing the first question, not the second one.
Comment #30 September 27th, 2006 at 10:44 pm
Thanks, Mike! Unfortunately, we already finished computability…
Comment #31 September 27th, 2006 at 11:39 pm
I know that Scott doesn’t need this quibble from me. Even so, technically speaking, experimental QC is more about whether quantum computation can be a technological reality, rather than physical reality. Whether it is physical reality is somewhere between theory and experiment. If you completely believe quantum probability, then it is almost strictly a theory question, and the answer is probably yes.
On that note, rdv is rather conflating the technological question, about which Scott spoke well, with the theoretical question or science question of whether QC is possible in principle. It is hard to be sure unless you actually make one. However, the pro-QC people seem to be winning the “realistic in principle” debate so far. They have a lot of interesting things to say, while the dwindling anti-QC camp has made little progress in years.
In particular, the position that QC is a form of analogue computation has been dead for years. If quantum computers cannot be built, it certainly won’t be for that reason.
In a way, it’s a shame that the debate is so one-sided. There is presently some significant barrier to making quantum computers, but the barrier has no theoretical characterization. If it did, maybe we could surmount it faster.
Comment #32 September 28th, 2006 at 12:39 am
Greg: “There is presently some significant barrier to making quantum computers, but the barrier has no theoretical characterization. If it did, maybe we could surmount it faster.”
I think optical quantum computing is a case where this strategy has born dividends. There was a theoretical barried (linear optics can be simulated classically) which was made precise, and which has driven a great deal of research aimed at surmounting the barrier, with considerable success.
(My colleage Andrew White has an amusing graph showing how the resources required to quantum compute optically have dropped over the years, due to theoretical advances. If theory continues on track, we should soon be able to quantum compute with lightbulbs and shaving mirrors. Either that, or the graph will saturate…)
Michael Nielsen
Comment #33 September 28th, 2006 at 1:15 am
If theory continues on track, we should soon be able to quantum compute with lightbulbs and shaving mirrors.
Hey, that’s the way that I quantum compute. Or at least, the way that I write papers. Sometimes when I am following some routine, maybe I’m shaving, a lightbulb goes on in my head.
Comment #34 September 28th, 2006 at 6:00 am
Greg:
I mostly agree with your comments on what I wrote. The important condition countable went missing there. However while it is true that no infinite dimensional Banach space has a countable algebraic basis it is also true that few infinte dimensional vector spaces have them, which is what I stated. In order to construct an example just take all finite linear combinations of some countably infinite set of vectors. If one looks at a space of this kind as a normed space it will necessarily be incomplete and thus not a Banach space.
I agree that this is most likely more functional analysis than needed here. My point is rather that if one looks at infinte dimensional spaces, even the separable ones, in general there is a lot of things which one need to be careful about. But in spite of this people have been able to use the often heuristic calculational techniques of quantum theory with great success, and there is probably a good reason for this. Either the underlying physics constrains things to lie in nicely behaved parts of the spaces used, or they might not even be infinte dimensional, just of extremely large dimension.
Another lesson here is probably that I should treat posts like this like I do my email: Reading right before going to bed is safe, writing can lead to all sorts of nonsense.
Comment #35 September 28th, 2006 at 8:01 am
Maybe it’s because I’m in the Volume B camp, but I still find the Turing machine a pretty ugly construction that is mainly of historical interest. Lambda-calculus, on the other hand, pops up in a lot of places nowadays—mainly in programming language syntax and semantics, but also in concurrency theory and mechanized theorem proving.
Not only is Church’s approach to computability more natural to the mathematically inclined, but it also tends to produce more productive programmers. Why speak of infinite tapes and machine heads when all you need is a lambda and a dot?
Comment #36 September 28th, 2006 at 11:54 am
I think the usual reason we only consider separable Hilbert spaces in quantum physics is the Stone-von Neumann theorem.
It says (roughly) that in a separable Hilbert space there can be only one representations of a given dynamics together with the canonical commutation relations, up to unitary equivalence. The different representations are like Heisenberg’s matrix mechanics and the Schrodinger equation: different representations that lead to all the same predictions with a nice 1-1 mapping between them.
In a non-separable Hilbert space the theorem is not true and there may be representations giving non-unitarily equivalent theories, and therefore different predictions. I’m not an expert, this situation is commonly referred to as an “enormous mess”.
Comment #37 September 28th, 2006 at 12:30 pm
Why speak of infinite tapes and machine heads when all you need is a lambda and a dot?
Blech! Blech! Blech! Well … to each his own. 🙂
Comment #38 September 28th, 2006 at 8:41 pm
Well… the thing about PHD work being too similar to master thesis is probably a joke, but I would like to know if it’s entirely made up or have something real behind it, like the guy really said that joking, or said something you were mocking here.
Comment #39 September 28th, 2006 at 10:11 pm
Well… the thing about PHD work being too similar to master thesis is probably a joke
No, it’s not. It was (I believe) in John Dawson’s Gödel biography.
Comment #40 September 29th, 2006 at 2:30 pm
It is also true that few infinte dimensional vector spaces have [countable algebraic bases], which is what I stated.
I am not sure what you mean by “few”. Of course, none of them are Banach space. However, virtualy all infinite-dimensional vector spaces that I encounter when I study algebra, or algebraic geometry, do have countable bases. I have in mind polynomial algebras, other finitely generated algebras, the Virasoro algebra (or any other countably generated algebra), Verma modules, Harish-Chandra modules, Vassiliev spaces, etc.
Of course, there is no natural, rigorously defined measure on the class of all vector spaces that would let you say that “few” or “most” of them have any particular property. But you can look at what actually appears across mathematics. I don’t know that it is even fair to say that few vector spaces studied by analysts have countable algebraic dimension, since analysts do commonly look at dense subspaces of topological vector spaces of this type. Maybe the fair statement is that when analysts study countable-dimension vector spaces, they almost always have uncountable topological completions. That might almost work as a definition of analysis!
Comment #41 October 3rd, 2006 at 2:53 pm
Really enjoyable lecture Scott. Thanks.
Comment #42 October 4th, 2006 at 2:02 pm
anonymous: You’re welcome!