Do you trust your eyes? This might change you mind about the matter.
Self-Correction
Sometimes you write a paper and think it’s all ready for submission and then after you submit it to the archive you find that it is lacking for quite a few reasons. On Friday I posted the paper quant-ph/0506023 (and did the new paper dance!) But after communications from Michael Nielsen and David Poulin, I realized that I had made a mistake in one of my claims (the proof I had did not work) and that I had very much misrepresented what is new in this paper (in particular in relationship to quant-ph/0504189 and quant-ph/0412076.) Luckily the mistake in my proof was not a big deal for the paper and also luckily one can correct one’s foolishness and clarify what’s new and interesting in the paper. Here is the updated title and abstract:
Operator Quantum Error Correcting Subsystems for Self-Correcting Quantum Memories
Authors: Dave Bacon
Comments: 17 pages, 3 figures, title change, rewrite of connection to operator quantum error correction, references added
The most general method for encoding quantum information is not to encode the information into a subspace of a Hilbert space, but to encode information into a subsystem of a Hilbert space. Recently this notion has led to a more general notion of quantum error correction known as operator quantum error correction. In standard quantum error correcting codes, one requires the ability to apply a procedure which exactly reverses on the error correcting subspace any correctable error. In contrast, for operator error correcting subsystems, the correction procedure need not undo the error which has occurred, but instead one must perform correction only modulo the subsystem structure. This does not lead to codes which differ from subspace codes, but does lead to recovery routines which explicitly make use of the subsystem structure. Here we present two examples of such operator error correcting subsystems. These examples are motivated by simple spatially local Hamiltonians on square and cubic lattices. In three dimensions we provide evidence, in the form a simple mean field theory, that our Hamiltonian gives rise to a system which is self-correcting. Such a system will be a natural high-temperature quantum memory, robust to noise without external intervening quantum error correction procedures.
They Flutter Ahead of You, Your Possible Futures
I love the work I do. The fact that I get to spend large amounts of time thinking about computation and quantum theory…well I can’t believe how lucky I’ve been! And now I get to teach and yell and scream about computation and quantum theory. Yes, very lucky!
But, like most other people I know, I sometimes wonder what my life would be like if I didn’t do what I currently do. Especially at times when I don’t think I’m doing a particularly good job at the work I do, I like to muse about the different possiblities. Especially on my bus ride to work. What are my favorite daydreams? Founding a new university. Writing speculative popular science books. Touring the country delivering science lectures. None of which are really that far from what I really do. Which makes me think I am a narrow minded sheltered elitist. Which then makes me think I should do something really different, like move to a ski town and open a bookstore. Or move to a beautiful valley surrounded by mountains and become a rancher. Which makes me laugh, because these really aren’t so different for the majority of people. And then I exit the bus and get to my office and read through the list of titles in the latest Physical Review Letters, and again I can’t imagine every doing anything but my current job.
Self Promotion of Self-Correcting Paper
Everybody do the new paper dance, quant-ph/0506023
Quantum Error Correcting Subsystems and Self-Correcting Quantum Memories
Authors: D. Bacon
Comments: 16 pages
The most general method for encoding quantum information is not to encode the information into a subspace of a Hilbert space, but to encode information into a subsystem of a Hilbert space. In this paper we use this fact to define subsystems with quantum error correcting capabilities. In standard quantum error correcting codes, one requires the ability to apply a procedure which exactly reverses on the error correcting subspace any correctable error. In contrast, for quantum error correcting subsystems, the correction procedure need not undo the error which has occurred, but instead one must perform correction only modulo the subsystem structure. Here we present two examples of quantum error correcting subsystems. These examples are motivated by simple spatially local Hamiltonians on square and cubic lattices. In three dimensions we provide evidence, in the form a simple mean field theory, that our Hamiltonian gives rise to a system which is self-correcting. Such a system will be a natural high-temperature quantum memory, robust to noise without external intervening quantum error correction procedures.
APS Topical Group
The American Physical Society now has a new topical group, Quantum Information, Concepts, and Computation. Here is an article about the topical group. Some quotes
“It is meant to be a broadly inclusive home for researchers whose professional lives may have kicked off in various traditional disciplines, but who nonetheless share an over-arching interest in the foundations and ‘surprising implications’ of quantum mechanics,” said Caltech’s Hideo Mabuchi, GQI’s acting chair.
and
Greenberger also feels the field needs an effective lobbying group to represent its interests to federal funding agencies, most notably the National Science Foundation. “Many young people are becoming interested in the field, but there are few opportunities for having their research funded,” he said.
Part of the problem is that quantum theory suffers from the perception that it is a field for “old men,” since the debate dates back to 1935 and the famous Einstein-Podolsky-Rosen paradox. (That paper is still the most downloaded publication from the APS journal archives, 80 years after it was written.) But Greenberger points out that it is, in fact, a vibrant exciting field at the forefront of physics, using all the latest laboratory techniques, and spinning off the newly emerging fields of quantum cryptography and quantum computing.
A Different Duck
From a “woman seeking man” ad:
OBSESSIVE COLLECTOR OF ANTIQUE MATH-TEXTBOOKS Pure math is a lot like art. Relatively soon I will be leaving Seattle to travel around the world. Make my aquaintance now, before I die of dysentary or malaria in the dark jungles of Swaziland. minitrue, 22 #115063
And no, I didn’t find this ad myself but was led to it by a friend who was using the personals as part of an art project.
A Postmortem Chewing Out
Another interesting letter in “Perfectly Reasonable Deviations From The Beaten Track: The Letters Of Richard P. Feynman” by T. Ferris (forward), R.P. Feynman (of course!), and M. Feynman (editor) is the following:
Mr. Todd Pramberg
Stockholm, Sweden
Dear Sir:
The fact that I beat a drum has nothing to do with the fact that I do theoretical physics. Theoretical physics is a human endeavor, one of the higher developments of human beings-and this perpetual desire to prove that people who do it are human by showing that they do other things that a few other humans do (like playing bongo drums) is insulting to me.
I am human enough to tell you to go to hell.
Sincerely,
Richard P. Feynman
Why do I find this letter interesting? Well when I was senior at Caltech a movie about Feynman, “Infinity” staring Matthew Broderick, was released (I’ve never seen the movie, but I’ve heard it’s a stinker.) CNN was doing a spot about the movie and Feynman’s legacy and they needed a token undergraduate to blab about Feynman so myself and the smartest physicist in my class, Sebastian Maurer, were interviewed for the spot. Sebastian attempted to get a quote on T.V. about the Feynman lectures on physics, which, if you listened to it carefully could actually be interpretted as a statement about Mao’s little red book (Feynman’s lectures on physics used to come as a series of three red books.) Here is what I said about Feynman:
Mention his name to physics students at Cal Tech[sic] today and watch their eyes light up: “One of the reasons it was easier to become a physicist was because he was so exciting and he wasn’t the typical, you know, nerd who doesn’t say anything,” said Cal Tech[sic] senior Dave Bacon
So you see, the above letter makes me realize that what I said was exactly the sort of thing which would have driven Feynman crazy. So I kind of feel like I’ve been chewed out from beyond the grave.
A Gibberish Theory
Last night I finished reading “Perfectly Reasonable Deviations From The Beaten Track: The Letters Of Richard P. Feynman” by T. Ferris (forward), R.P. Feynman (of course!), and M. Feynman (editor). I wouldn’t recommend this collection of letters to everyone, but it is interesting for those who have read a lot of the other stuff about or by Feynman as the letters help flesh out Feynman’s character. There really aren’t that many “anecdotal” letters in the book, which is, of course, what everyone comes to expect from a Feynman collection (to be known as one gigantic anecdote generating machine…what a legacy). However, the following letter, in which information was requested about the infamous Lars Onsager, is rather amusing:
On one occasion when we were standing together, a young man came up to explain his ideas on superconductivity to us both. I didn’t understand what the fellow was saying-so I thought it must be nonsense (a bad habit I have.) I was surprised to hear Onsager say, “Yes, that seems to be the solution to the problem.” Did he mean the puzzle of superconductivity was solved-and I didn’t even know what the young man said? I guess so. I have never been sure-I think the young man could have been Cooper. Could you check?
This reminds me of a picture of Feynman’s blackboard at the time of his death. On this blackboard is a list of things “TO LEARN.” Included on the list are “the Bethe Ansatz Prob.”, “Kondo”, “2-D Hall”, “accel Temp.”, “Non-linear classical Hydro”. “Kondo” has been crossed out. This list is amazing, first in that it contains probably some of the most interesting problems in physics (“accel Temp.” refers to the Unruh effect where a uniformaly accelerating observer observes the vacuum as a thermal bath with a temperature proportional to the acceleration.) But even more amazing is that the great Richard Feynman, who legend has always portrayed as knowing everything there is to know about physics, still had “to learn” these famous problems. One wonders if Feynman’s “to learn” was a lot different than everyone elses “to learn?”
Pigeons, Discrete Log, and Entropy
The pigeon hole principle states that if you put m pigeons into n<m holes, then there are at least two pigeons in one hole. Consider, for example, the following problem
Given a list [tex]$a_1,dots,a_n$[/tex] of residues mod [tex]$p$[/tex] and suppose [tex]$n>log_2 p$[/tex], find two distinct subsets [tex]$S_1,S_2 subset {1,2,dots,n}$[/tex] so that [tex]$prod_{i in S_1} a_i =prod_{i in S_2}a_j~{rm mod}~p$[/tex].
Here we have said “find”, but how do we even know that two subsets which solve this problem exist? The pigeon hole principle! The number of possible subsets of [tex] {1,2,dots,n}$[/tex] is [tex]$2^n$[/tex] (because each element either is or is not in the subset, and “is” and “is not” is binary, and so we have a binary string of length [tex]$n$[/tex].) But [tex]2^n>p[/tex], so we are putting more objects into our “holes” which run from [tex]$0$[/tex] to [tex]$p-1$[/tex]. Thus by the pigeon hole principle there must be two distinct subsets (two pigeons) whose product is the same.
In computational complexity the above problem belongs to a class of search problems called PPP, which, according to the complexity zoo, stands for “Polynomial Pigeonhole Principle.” These are problems where we are searching for a solution to an instance of a problem, this solution can be verified to be a solution in polynomial time, and the existence of a solution is guaranteed by a pigeon hole argument. The second of these should be familiar from the class NP, and the first of these is what you’re doing when you go beyond decision problems and actually want to find a solution.
PPP is interesting for various reasons, but one of the reasons I know of it is because it is at least as hard as the discrete log problem. In the discrete log problem is given two elements [tex]$a,b in {mathbb Z}_p$[/tex] find the smallest [tex]$s$[/tex] such that [tex]$a^s=b~{rm mod}~p$[/tex]. One of the neat things about a quantum computer is that it can efficiently solve the discrete log problem, whereas there is no known efficient classical algorithm.
So what do we know about the power of quantum computers to solve problems in PPP? Well we know a little. We know that a naive approach to solving these problems will fail. Suppose that we try to solve the above PPP problem by querying the function [tex]$f_{a_1,dots,a_n}(b_1,dots,b_n)=a_1^{b_1} a_2^{b_2} dots a_n^{b_n}$[/tex], where [tex]$b_i in {mathbb Z}_2[/tex]. Then a result by Scott Aaronson says that using a quantum algorithm requires [tex]$Omega((2^n)^{1/5})$[/tex] queries of this function (later improved to [tex]$Omega((2^n)^{1/3})$[/tex] by Yaoyun Shi) to solve this problem. So this naive approach to attacking problems in PPP fails. An interesting open question remains, however, whether there is a more sophisticated approach to efficiently solving problems in PPP using a quantum computer.
Interestingly, the problem Scott and Yaoyun work on is also relavent to a physicist in the lab. The problem they consider is called the collision problem. Suppose you have a function [tex]$f$[/tex] from [tex]${mathbb Z}_N$[/tex] to [tex]${mathbb Z}_N$[/tex] which is promised to be either 1-to-1 or 2-to-1 and the problem is to distinguish between these two cases. Scott and Yaoyun’s result says that if you do this you need to query this function [tex]$Omega((2^n)^{1/3})$[/tex] times (and, it turns out that there is a quantum algorithm which uses this number of queries) to distinguish between these two cases. Now how does this have relevance to a physicist? Suppose we follow the standard query method and query the function to produce the state [tex]$N^{-1/2} sum_{x in {mathbb Z}_N} |x>|f(x)>$[/tex]. Discarding the second register produces a mixed state of rank [tex]$N$[/tex] if [tex]$f$[/tex] is 1-to-1 but of rank [tex]$N/2$[/tex] if [tex]$f$[/tex] is 2-to-1. The entropy of these states is thus either [tex]$log_2 N$[/tex] or [tex]$log_2 N-1$[/tex] respectivally. Now suppose you are a physicist in the lab and you want to measure the entropy of a quantum state which you can prepare multiple copies of. You might be interested in how many copies you will need to measure this entropy. Scott and Yaoyun’s result then imply that you will need to perform a number of experiments which is at least [tex]$Omega(d^{1/3})$[/tex] such experiments to measure the entropy, where [tex]$d$[/tex] is the dimension of your quantum states. This is bad news if you really want to measure the entropy of a many-qubit system! In a related manner one can think of the period finding function of Shor’s algorithm as a method for determining the entropy for special class of states which have a particular promise (that they are periodic).
Discrete log is a pigeon problem, naive quantum algorithms for pigeon problems fail, and pigeon problems put limits on how efficiently we can measure the entropy of a system. It’s topics like these, which spread from computer science all the way to relevance for a experimental physics, which make me happy to be working in quantum information science.
Death, Taxes, and the 2nd Law
Seth Lloyd, in Nature 430, 971 (2004):
Nothing in life is certain except death, taxes and the second law of thermodynamics. All three are processes in which useful or accessible forms of some quantity, such as energy or money, are transformed into useless, inaccessible forms of the same quantity. That is not to say that these three processes don’t have fringe benefits: taxes pay for roads and schools; the second law of thermodynamics drives cars, computers and metabolism; and death, at the very least, opens up tenured faculty positions.