Halfday at the Santa Fe Basin with other SFI cohorts. Mostly this trip was notable for a beautiful crash in which I had to hike 50 meters up the mountain to retrieve my ski. It wasn’t so much that I was going fast, as that I did many acrobatic twists as I slid down the hill.
Two Questions
Quantum theory is famous, if for nothing else, than for the various raging debates about the interpretation of quantum theory. One of the issues which has been bugging me in this debate for a while is that I think that sometimes the combatents are actually debating different questions. In particular I would like to make the distinction between (1) the reconcilliation of the classical world with the quantum world and (2) the consistency of post-quantum theories with the quantum world.
In the first question, we ask how it is that the classical world of probabilities arises from the quantum world of amplitudes. Once we say that quantum theory is describing what is going on, then this question I think is important. And I also think we have lots of good reasons to believe we understand at least a little about the transition from quantum to classical. It’s totaly consistent to hold the point of view that there is nothing mysterious about the quantum world, that’s just the way it works, and if we are unconfortable with it, it is because we never directly experience it. In this case, what needs to be explained is how our classical world emerges from quantum theory.
The second question is a different and more challenging question. It asks what kind of theories exist which can reproduce quantum theory (exactly, or perhaps in some appropriate limit.) Often this question gets bungled up with the first question. In other words, we think of finding a deeper theory as finding a classical theory. But the deeper theory need not have anything to do with the quantum/classical transition. In fact, perhaps one of the greatest biases in thinking about deeper theories is that we implicity try to give them classical properties. But this doesn’t have to be the way it works.
Now, when I hear the many debators in the great quantum interpretation wars, the conversation sounds kind of funny. Like, Alice: “Pizza is better than hamburgers!” Bob: “Vegans eat lettuce.” So if you see me laughing when a consistent historian meets a Bohmian realist, you’ll now know why.
Decohered Myself
From an email today:
Greetings Dear Quantum Professor,
A compliment: I can only be a quantum professor if I am coherent. Mostly, however, I am neither coherent nor a professor.
Slow Steady Climb
The slow steady rise of quantum information science.
A Large Influence
At QIP, I was struck by something odd about the invited speakers. First, of course, was their age. The group of speakers was much younger than in previous years. Many of the speakers are from the second generation of the quantum information science revolution (we must compete with string theory, no?) But then it struck me: most of the speakers have spent a considerable length of time at the Institute for Quantum Information at Caltech. In fact 12 of the 22 invited speakers are IQI alumni in some manner. Now that’s a pretty amazing track record for a single institute.
CEPI Seminar 1/19/05: H. Jeff Kimble
Complexity, Entropy, and the Physics of Information Lecture Series
Wednesday, January 19, 2005, 5:00 PM. Refreshments 4:15 PM.
Robert N. Noyce Conference Room, Santa Fe Insitute
H. Jeff Kimble
Department of Physics, California Institute of Technology
Title: Quantum Information Enabled by Quantum Optics
Abstract: Across a broad front in physics, an exciting advance in recent years has been the increasing ability to observe and manipulate the dynamical processes of individual quantum systems. In this endeavor, an important physical system has been a single atom strongly coupled to the electromagnetic field of a high-Q cavity within the setting of cavity quantum electrodynamics (cavity QED). Diverse new phenomena in cavity QED include the realization of nonlinear interactions between single photons and the development of a laser in a regime of strong coupling that operates with “one-and-the-same-atom”. Because of several unique advantages, cavity QED is playing an important role in the new science of quantum information, such as for the realization of complex quantum networks and for the investigation of quantum dynamics of single quantum systems. This presentation will give an overview of recent developments in cavity QED and several other areas in Quantum Optics that are providing enabling capabilities for Quantum Information Science.
QIP 2005 Trip Report
First, Boston was cold. Actually it wasn’t too much colder than Santa Fe, but the extra wetness and windiness made it feel much colder. Except one strange night, where, after embibing some refreshments at the “Miracle of Science” bar (this is M.I.T. you know), the walk home at midnight was filled with a strong, probably 55 degree breeze. Very strange.
There were a lot of good talks at QIP, but, like any conference, the talks do not fully make up the content of the conference. I had a good time talking to various people about the hidden subgroup problem and I am more optimistic about the problem than I have been in a long time. Expect a lot of good work to be reported in the next six months.
My favorite talk of the conference was probably Oded Regev’s talk on a new public-key cryptosystem. While previous lattice based public-key cryptosystems (like the one by Ajtai and Dwork and an improvement of this system by Oded himself) were based on a problem called the unique shortest vector in a lattice problem, breaking the new cryptosystem is based on the hardness of the shortest vector problem. The funny thing is that it is based not on the classical hardness of the shortest vector problem, but is based on the quantum hardness of the shortest vector problem. One intersting offshoot of this is that there is a learning problem whose solution will lead to a quantum algorithm for certain shortest vector in a lattice problems.
Another very interesting and entertaining talk was given by Scott Aaronson (quantum computing’s younger clown.) Scott talked about a model of quantum computation in which you get to postselect on the measurement outcome. In other words, you get to perform a quantum measurement and, instead of getting one of say two outcomes, you get to always assume that you got only one of the two possible outcomes. Postselection is, as far as we know, not possible, but you know computer scientists: always talking about crazy complexity classes whose practical value is dubious. But just because there is no practical value doesn’t mean that this craziness cannot lead to some astoundingly nice results. And this is exactly what Scott was able to show. In particular he showed that the model of quantum computation with postselection, postBQP, is exactly equal to the complexity class PP. The class PP (called, unfortunately, “probabilistic polynomial time”) is the class of problems solvable by a non-deterministic Turing machine such that if the answer is yes then at least 1/2 of the paths accept and if the answer is no then less than 1/2 of the computational paths accept. A comparison with NP is that in NP, the answer is yes if at least one of the paths accept and if the answer is no then none of the paths accept. One of the trickier properties to establish about PP is that it is closed under intersection. This was done by Beigel, Reingold, and Spielman in 1991. What is really cute about Scott’s result is that he is able to obtain this proof in a very very simple way from the fact that postBQP=PP. The technique also produces a lot of other previous results in a nice clean manner. Amazing how a quantum model of computation, with a crazy extra assumption (postselection) can make things so much clearer!
QIP 2006 will be held in Paris and QIP 2007 will be held in Brisbane, Australia.
From Outer Space
Back!
No sooner had I gotten back to my office after spending last week in Boston, and lo and behold a bobcat walked in front of my office window. Since my gut reaction was, “Look at the big kitty,” and the encounter was really brief I have no picture of this bobcat, but my camera is now ready if he decides to come visit me again.
Two Quantum Tapas
Here is the talk i gave this morning at QIP 2005: Two Quantum Tapas.
In the talk I discuss Bell inequalities with communication for multipartite quantum correlations and also quantum error correcting subsystems.
Dihedral Hidden Subgroup Problem
Nothing like a little shameless self-promotion: quant-ph 0501044
Optimal measurements for the dihedral hidden subgroup problem
Dave Bacon, Andrew Childs, and Wim van Dam
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.