Quantum Computing Since Democritus Lecture 10: Quantum Computing
You’ve waited for weeks. You’ve pestered me for it. Now here it is.
For those who liked my Shor’s algorithm post but are ready for the next level: brace yourself for BQP ⊆ PP, Recursive Fourier Sampling, and so much more. And for dessert, a brief discussion of quantum computing and the many-worlds interpretation.
Suggestions and bugfixes welcome; I’ll continue revising over the next few days as time permits.
Follow
Comment #1 February 28th, 2007 at 8:08 am
According to the multiverse theory, there should be a universe in which every flipped coins lies head up. Furthermore for a given day there should be a universe in which till then coins fall head up but from this day on number up. That would make a great headline.
Comment #2 February 28th, 2007 at 12:50 pm
How Simon’s problem can be reduced to a problem of finding a period? Just give a hint.
Comment #3 February 28th, 2007 at 12:52 pm
“Where was the number factored? Where did the computational resources needed to factor the number come from, if not from some sort of ‘multiverse’ exponentially bigger than the universe we see?”
It’s a good question. The preferred basis problem is also a good question, but of a different sort, since it doesn’t imply any “explanation” as to how the quantum computations would be physically carried out.
My recollection is that Deutsch expressly has said that computers in multiple universes “collaborate” to reach an answer, so I suspect that he wouldn’t disagree with your statement in that regard.
In any event, I don’t think this is an ultimately-meaningless debate. It’s important to think seriously about what quantum physics means with respect to the true nature of the world, because this leads to new knowledge. As you recently said, “. . . it matters that David Deutsch believes the many-worlds interpretation because that’s what led him to quantum computing.”
You say “[t]o me it’s sort of astounding that it took until the 1990’s for anyone to really seriously ask this question, given that all the tools for asking it were in place by the 1960’s or even earlier.” Although you were primarily referring to a more narrow question: what problems are efficiently solvable in the physical world, I think the same question is equally applicable to why interest in quantum computation made progress when it did.
Although Everett put the MWI forward in 1957, it wasn’t taken seriously by many as an “explanation” of the quantum formalism. Deutsch took it seriously.
Comment #4 February 28th, 2007 at 12:55 pm
Vasily: It’s not that Simon’s problem is reducible to period-finding; it’s that the two problems are similar. With Simon’s problem, instead of finding a hidden period, you want to find a hidden XOR-mask. So it’s basically the same as Shor’s period-finding problem, except that now you want to find a hidden subgroup of the group (Z2)n instead of a hidden subgroup of a cyclic group.
Comment #5 February 28th, 2007 at 1:28 pm
Michael: I said the debate was perhaps ultimately meaningless — I don’t know whether it is or not! But I have written foundations-flavored papers, gone to foundations conferences, and in general spent much of my life thinking about these issues. And one of the main reasons is that, as you point out, taking the philosophical questions seriously has led again and again to major scientific advances (the Bell inequality, quantum computing, etc). Of course, once the advance has been made, then it’s no longer called philosophy — then it’s just ordinary science.
Comment #6 February 28th, 2007 at 1:53 pm
Scott,
Didn’t mean to imply that I thought you failed to take these types of issues seriously. On the contrary, it’s one of the things I really like about the Blog. Perhaps if I had any significant understanding of the actual science, I wouldn’t be reduced solely to making philosophical pronouncements. Thanks for responding.
Comment #7 February 28th, 2007 at 2:01 pm
I think of it just as a period mod (Z2)n. That’s the insight that ultimately led me to finding the discrete log and factoring algorithms. But if you don’t want to call it periodicity, that’s fine with me, too.
Comment #8 February 28th, 2007 at 2:04 pm
And that’s supposed to be Z sub 2 sup n, and it looked that way in the preview, but got filtered out in the posting. I don’t know how Scott got his post to look that way.
Comment #9 February 28th, 2007 at 2:41 pm
If it’s not about period-finding, how Fourier transform can help? If it is about period-finding, how exactly you define a function that has a period that gives you a clue about s? I’m slightly confused.
Comment #10 February 28th, 2007 at 6:39 pm
Vasily: It helps because you’re taking a Fourier transform over (Z2)n (which reveals a hidden XOR-mask), not over ZN (which reveals hidden periodic structure). If you want more details, please read the exposition of Simon’s algorithm that I linked to.
Comment #11 February 28th, 2007 at 9:03 pm
OK, I got a clue. You are right: one has to have really sharp eye to identify this procedure as period-finding. This requires a quantum leap of imagination; I’m not yet there, but I’ll try.
Comment #12 March 1st, 2007 at 1:16 am
The many-world intepretation may look crazy, but what are the plausible alternatives?
By “plausible”, I mean an interpretation that does not require changes in the law of quantum mechanics as we know them.
Pascal Koiran.
Comment #13 March 1st, 2007 at 3:36 am
Pascal: My attitude that I agree with every interpretation to the extent it claims there’s a problem, and disagree with every interpretation to the extent it claims to have solved it.
One thing you quickly learn in this business is that just about every interpretation’s proponents claim to be taking the laws of quantum mechanics exactly as given, making the fewest extravagant assumptions, etc. Indeed, a popular move is to say that quantum mechanics doesn’t need an interpretation at all, before going on to provide one!
As I see it, most interpretations fall into three evolutionary families:
(1) The Everett Family: Many-worlds, many-minds, “relative-state,” decoherent histories…
(2) The Bohm Family: Bohmian mechanics, modal interpretations…
(3) The Bohr Family: Copenhagen, the information-theoretic “Perimeter Institute Interpretation”, the shut-up-and-calculate interpretation…
Here I’ve excluded “interpretations” like the GRW (Ghirardi-Rimini-Weber) dynamical-collapse theory, which make different predictions than quantum mechanics for the results of doable experiments. The interpretation families I listed above are all empirically indistinguishable … unless, possibly, you could put yourself in coherent superposition and then report on what it felt like!
Comment #14 March 1st, 2007 at 4:33 am
One problem that I have with the Copenhagen interpretation is that is seems to claim a rigid seperation between the macroscopic world (the observer and its measuring apparatus) and the microscopic world.
But there is no such thing in the equations.
Comment #15 March 1st, 2007 at 5:03 am
Yeah, that’s the classic problem with Copenhagen!
Comment #16 March 1st, 2007 at 5:36 am
# Pascal Koiran Says: One problem that I have with the Copenhagen interpretation is that is seems to claim a rigid separation between the macroscopic world (the observer and its measuring apparatus) and the microscopic world. But there is no such thing in the equations.
Your observation is correct, and that is why we never teach the Copenhagen interpretation to young engineers. Rather, we teach the ultra-orthodox measurement operator postulates of Chapter 2 of Nielsen and Chuang.
It is true that these postulates do not provide a rigid separation between the macroscopic and microscopic world. They do something better — they provide a flexible boundary in place of that rigid separation, and there is a well-posed and exceedingly useful mathematical invariance associated with that flexibility!
We then show our students how to exploit that invariance to derive the Copenhagen interpretation, including its mysterious “jumps”, as one possible limit of the measurement operator formalism. But there are other possible limits (physically indistinguishable ones) that do not involve jumps.
This strips away the mysterious “quanta” of quantum mechanics, which starts to look like any other state space. We teach students that makes quantum state spaces special, relative to other engineering state spaces, is solely the above-mentioned mathematical invariances.
From this point of view, the state space of quantum system engineering closely resembles the state space of other engineering disciplines, except that it has natural complex structures that are associated with powerful mathematical formalisms.
Engineering students are psychologically well-disposed to accept quantum mechanics as the natural “complexification” of traditional engineering formalisms, because they have previous experience of the benefits of complexification, in the context of the analytic extension of linear response functions to complex time and complex frequency. So students already appreciate that complexifying a formalism lends it added power, and don’t mind (too much) putting forth the additional effort to learn it.
The reason QM is not more often taught via this “Mike and Ike” pathway is IMHO mainly pragmatic — the above program requires that students have a pretty solid grasp of stochastic processes at the outset, at the level of e.g. Gardiner’s Handbook of Stochastic Processes. This requires considerable extra work and time on the part of the students.
Given the choice between several weeks spent studying stochastic processes, versus the immediate pleasure of inviting students to contemplate the mysteries of the Copenhagen interpretation, well … it’s a tough choice!
Comment #17 March 1st, 2007 at 3:07 pm
One problem that I have with the Copenhagen interpretation is that is seems to claim a rigid seperation between the macroscopic world (the observer and its measuring apparatus) and the microscopic world.
In my view, this is a problem with the deceptively simplified formalism of quantum mechanics, as it is usually introduced, more than it is a problem with the Copenhagen interpretation itself.
If you define quantum mechanics as non-commutative probability, then there is no dichtomy. Observers are treated the same way as experiments; any object can either be an experiment or an observer. The model is consistent: the quantum evolution laws (properly considered) really do imply that each object perceives the Copenhagen interpretation to be true.
Comment #18 March 2nd, 2007 at 1:07 am
Observers are treated the same way as experiments; any object can either be an experiment or an observer.
I like this point of view, but it looks to me more consistent with the many-world interpretation than with the Copenhagen interpretation. Indeed, it implies that a state of the form “observer dead + observer alive” should be considered as seriously as a state “particle with spin up + particle with spin down”. But if I’m not mistaken, in Copenhagen they refuse to consider states of the form “observer dead + observer alive” seriously.
Here’s a relevant quote from wikipedia (you can see that I love going back to the primary sources!):
the cat paradox was specifically constructed by Schrödinger to illustrate that the Copenhagen Interpretation suffered fundamental problems. It was not intended as an example that quantum mechanics actually predicted that a cat could be alive and dead simultaneously, though some have made this further assumption.
Comment #19 March 2nd, 2007 at 7:20 am
Sorry about the weather Scott – do you still plan to give your talk in Pittsburgh?
Thomas
Comment #20 March 2nd, 2007 at 7:30 am
Wasn’t it Wittgenstein who said “Philosophical problems are never solved, they are only dissolved”?
One cognitive path for dissolving at least some of the mysteries of quantum mechanics is to thoroughly analyze the notion of a “click”, as commonly invoked to describe the detection of a photon.
A photomultiplier tube is a very good (but not perfect) click generator. Solid-state diode detectors are in general less perfect. The living cells of the retina are still less perfect, yet they have surprising efficiency (and retinas come equipped with a truly wonderful user interface 🙂 ).
Continuing this progression, by the time we get to electromagnetic fields interacting with a warm brick, it is not clear that the concept of a “photon click” retains much utility at all — although we retain the mathematical freedom to employ click-type formalisms in calculating, e.g., the rate at which the brick’s temperature increases.
From a philosophical point of view, this staged analysis trains engineering students not to unnecessarily assume what their simplicity-loving hearts desire: a rigid and objective firewall between the subjective world of classical reality and the complex state space of quantum mechanics.
Instead, the staged analysis — in detail — of the performance of actual photon detectors teaches via many vivid examples that the classical-quantum boundary is flexible and movable, and further, that this boundary is subject to well-posed mathematical invariances that make it impossible to pin down even in principle. In the end, the balance between philosophical mystery and engineering-type analysis is seen to be determined largely by … pedagogic convenience!
For students who whose professional goal is to learn to design and fabricate good detectors, the practical benefits of this analytic point of view are so great as to be compelling.
This is not to say that quantum mechanics is devoid of mystery. For example, a completely mysterious question (to me at least, maybe someone can offer an answer) is this: why is the state space of quantum mechanics so large?
Here is a BibTeX quote by Howard Carmichael that expresses many of these same ideas: @book{Carmichael:99, author = {H. J. Carmichael}, title = {Statistical Methods in Quantum Optics I: Master Equations and Fokker-Planck Equations}, publisher = {Springer}, year = 1999, jasnote = {Note: there is no volume II as of 2005. Preface: “As a graduate student working in quantum optics I encountered … deep irritation caused by the work I was doing, something quite fundamental that I did not understand. … Certain elementary notions that are accepted as starting points for work in quantum optics somehow had no fundamental foundation, no verifiable root. My inclination was to mine physics vertically, and here was a subject whose tunnels were dug horizontally. … I now appreciate more clearly where my question was headed: Yes it does head downward, and it goes very deep. What is less clear is that there is a path in that direction understood by anyone very well. … Here one must face those notorious issues of interpretation that stimulate much confusion and contention but few definite answers.”}, }
—-
By the way, Howard tells me that he is almost finished with Volume II. Since Howard is the guy who invented the now-universal term “unravelling” for describing quantum trajectories, this is IMHO a book to look forward to! Hopefully, Howard’s new book will contribute greatly to the further “unravelling” of these mysteries.
Comment #21 March 2nd, 2007 at 8:18 am
I like this point of view, but it looks to me more consistent with the many-world interpretation than with the Copenhagen interpretation.
Ultimately, interpretation is just pedagogy, and there is nothing truly objectionable about either presentation. The Copenhagen interpretation is a correct description of what every actor in a quantum universe perceives. It’s also a correct description of what every actor in a classical Bayesian universe perceives. Copenhagenism isn’t really very different from Bayesianism.
Meanwhile the many-worlds stuff is a correct description of path summation, which is a valid mathematical method in both quantum mechanics and classical probability.
Where the many-worlds mantra goes wrong is in implying that the Copenhagen interpretation is somehow wrong-minded; or in claiming a distinction between classical and quantum cases. Of course, if you flip a coin, you can imagine parallel universes in which it is both heads and tails. There is nothing quantum about it.
Indeed, it implies that a state of the form “observer dead + observer alive” should be considered as seriously as a state “particle with spin up + particle with spin down”. But if I’m not mistaken, in Copenhagen they refuse to consider states of the form “observer dead + observer alive” seriously.
I am not sure who “they” is, but I make a different point. In a quantum system, you have both quantum superposition and classical superposition; the latter usually being called a “mixture”. Quantum superposition of highly mixed states does not exist, but mixture still does. You cannot write the state of being alive or happy in a pure state form, like this: |alive>. However, classical superposition of the mixed states [alive] and [dead] is fine. It does not contradict the good versions of either Copenhagen or many worlds. It only contradicts the view, which I do not consider useful, that classical and quantum superpositions are philosophically different. In my view, they are mathematically different, but philosophically equivalent.
Although as I pointed out in a lecture on this, dead states are a little bit different from alive states. There are no pure alive states of a cat in any useful sense. But if the cat has been frozen in a very good cryostat, it could be in a pure state called |dead>. You could even see quantum superpositions of different pure dead states.
Comment #22 March 2nd, 2007 at 9:08 am
Thomas: Unfortunately I had to cancel my trip to Carnegie Mellon, since the roads are so icy that I couldn’t even get a taxi to take me to the airport. It’s a shame, since I was looking forward to the visit. I’ll have to go another time!
Comment #23 March 2nd, 2007 at 10:57 am
Similar problems may arise in every other setting where we deal with linear transformations in nature. As Scott noted in lecture 9, if tranformation T makes sense, then transformation Q such that Q^2=T should make sense either. Now apply this logic to matrix T=
-1 0
0 1
in timespace (reversing x axis), then what can you say about Q? Wouldn’t it lead to superposition of something weird? (Question is inspired by reading repeatedly lecture 9 for 2 weeks; I accept no responsibility for the consequences)
Comment #24 March 2nd, 2007 at 12:04 pm
Greg says: … There are no pure alive states of a cat in any useful sense. But if the cat has been frozen in a very good cryostat, it could be in a pure state called |dead>.
That is a very thought-provoking point, not only in an abstract sense, but in a practical sense. I myself have seen freezers loaded with cattle embryos that, although frozen, were perfectly viable upon re-warming.
Perhaps the distinction between “live” and “dead” states has more to do with their time-dependent trajectory, than with the instantaneous state itself?
Schroedinger’s discussion might have been clearer, albeit less memorable, had he evoked the quantum superposition of a black cat and a white cat!
Comment #25 March 2nd, 2007 at 3:18 pm
Believe me, cats can exist quite comfortably in quantum superpositions…
Comment #26 March 2nd, 2007 at 7:54 pm
“because any time you were gonna flip a coin, you just apply a Hadamard gate instead. In textbooks, this usually takes about a page to prove. We just proved it.”
wonderful! Thanks again, Scott!
Comment #27 March 5th, 2007 at 10:38 am
I’m not sure I buy the argument that Copenhagen and many worlds are empirically indistinguishable. Wouldn’t any experimental measurement of decoherence time require the replacement of the Copenhagen measurement postulate by a mechanism? The are other distinguishing factors, I believe, but this is the most salient.
Comment #28 March 5th, 2007 at 7:12 am
Hold the presses, Scott! Everett & Bohm may be indistinguishable (though I considered Everett ill posed) but the Copenhagen interpretations are most certainly not equivalent to them. Any Copenhagen interpretation has a collapse of the wave function which is in principle distinguishable from the noncollapsed WF, as I’m sure you’re aware. Of course, if collapse occurs only at the macroscopic level distinguishing the two would require detailed info about the macroscopic wavefunctions, which makes the experiment quite difficult.
On the other hand, its quite unclear to me that putting yourself “in superposition” distinguishes anything at al. It certainly dosen’t distinguish Everett & Bohm, and well in the Copenhagen interpretation you shouldnt be in a superposition at all. The fact that everything looks more or less the same when youre “in superposition” is what led Everett to propose his theory.
Unless by “put yourself in superposition”, you meant put yourself in a situation where Copenhagen demands a collapse and then interfere the waves in the way that distinguishes collapsed from uncollapsed WFs. At which point I’m both pedantic and sorry.
Comment #29 March 5th, 2007 at 5:02 pm
Question:
Is there a simple criterion to decide whether period of a function can be effectively found by QC, based on regular DFT of this function? In other words, what properties of DFT guarantee that this can be done? Or there’s no connection?
If there’s such criterion, can we write a program which writes a program for QC?
Comment #30 March 5th, 2007 at 5:15 pm
Daniel,
I appreciate your point, but doesn’t the MWI contemplate a similar “process” (e.g., branches of the universal wavefunction split when different components of a quantum superposition “decohere” from each other as a result of environmental interference effects). I believe tests have been proposed to distinguish the interpretations (and IMO the ability to conduct such tests is “merely” an “engineering” issue), but it’s difficult to draw any conclusions absent such experimental results.
Comment #31 March 6th, 2007 at 10:39 am
Michael,
Yes, the many-worlds interpretation makes definite predictions as to how the process of quantum decoherence actually occurs. The major issue is that empirically indistinguishable and empirically undistinguished are two rather different statements.
Importantly, this is intended to be no different from what ordinary quantum mechanics would predict if measurement was removed as a preferred process. The ‘many worlds interpretation’ part comes in when we note that in the wavefunction after a ‘measurement’, each type of eigenstate in the measured system is crossed with a particular state in the measuring system. Hence the interpretation of a ‘relative collapse’.
I should state that I’m not a proponent of the many-worlds interpretation. I have a copy of Everett’s thesis here, and by binary search I think I’ve found exactly the point at which he made a mistake and our thoughts diverge. I should write a proper article on this rather than expound in the comment page of a blog. But here is the main gist of the thing:
In the typical interpretation mixed-states aren’t ‘real’ states, they’re just tools to help us when we’re talking about ensembles. If we actually did know which pure state the measuring device was in then there would be no wave-function split. The conclusion is that the split is a fallacious notion based on a mixing of quantum and classical probabilities, when there shouldn’t be.
Comment #32 March 6th, 2007 at 11:22 am
A friend and I will be attending your talk today at the University of Chicago. Given that we’re just first years, we probably won’t understand everything that you say but it should be rewarding anyway, since we like the blog a lot.
Comment #33 March 13th, 2007 at 3:00 pm
As grist for a future post (and how many people even know what “grist” is? Holy rural idiom, Batman!), MIT’s new Extreme Quantum Information Technology Center (xQIT) notes that one of its three main focus areas is “Algorithms to Solve Average-Case NP-Hard Problems: At present, very few researchers believe that NP-complete problems can be solved efficiently by a computer, be it classical or quantum. Nevertheless, algorithms exist that seem to allow the solution for average cases of such hard problems. … The adiabatic algorithm currently represents quantum computers’ best hope for solving NP-complete problems.”
I’m surely no expert—and would welcome hearing from someone who is—but isn’t it true that the phrase “average-case NP-hard” needs very careful definition?
Or do both D-Wave and MIT both know something?
Comment #34 March 13th, 2007 at 11:48 pm
I think this article warrants one of your rages against doofosity
http://www.theamericanscholar.org/sp07/newtheory-lanza.html
Comment #35 March 14th, 2007 at 5:46 pm
[…] Scott over at Shtetl is very interesting, illuminating, and persuasive in his quantum information lectures … However … His sentiment that “It’s a shame that, after proving his Completeness Theorem, Gödel never really did anything else of note. [Pause for comic effect] Well, alright, I guess a year later he proved the Incompleteness Theorem. See, the Completeness Theorem was his Master’s thesis, and the Incompleteness Theorem was his PhD thesis. Apparently, one of his PhD examiners didn’t want to give him a degree because the PhD thesis was “too similar to the Master’s thesis.” [see the source lecture here] … might be a bit premature. Scott might be correct if we strictly limit considerations to logic and metamathematics … but I would write Godel off so quickly. — details to follow […]
Comment #36 March 14th, 2007 at 5:59 pm
[…] Shtetl’s Scott says in one of his lectures “It’s a shame that, after proving his Completeness Theorem, Gödel never really did anything else of note. [Pause for comic effect] Well, alright, I guess a year later he proved the Incompleteness Theorem. See, the Completeness Theorem was his Master’s thesis, and the Incompleteness Theorem was his PhD thesis. Apparently, one of his PhD examiners didn’t want to give him a degree because the PhD thesis was “too similar to the Master’s thesis.” […]