I had seen these results in a previous talk, but now the paper is out in Nature Science. Charles Marcus’s group at Harvard has been working on building a qubit from a semiconductor quantum dot. One of the difficulties for this type of qubit is that the qubit couples via a hyperfine interaction to surrounding nuclei. If you don’t do anything about this hyperfine interaction, this causes a typical Rabi flopping experiment to exhibit decoherence rates of 10 nanoseconds. Way to short to make a useful quantum computer! But what is nice about the hyperfine decoherence mechanism, is that it is a constant coupling which can be overcome by doing a spin echo experiment. In the above paper, Marcus and colleagues show that with appropriate spin echo techniques, they get lifetimes of 1 microseconds. Nothing like that many orders of magnitude improvement, no?
Snarky Snark Snark
Update: Patrick says I’m very senstive. Which I certainly am. And as Patrick says, what Clifford is doing with the course sounds very very cool. So take this post with a grain of salt, or as an indication of what happens when I wake up on the wrong side of the bed (or the world?)
Update, update: Well it turns out that the answer to my question was neither (a),(b), or (c)! See the comments for the answer!
Clifford over at Cosmic Variance, tells a story
The semester started, and I showed up to teach what I thought was supposed to be the second part of a graduate string theory class, as long promised.
…
The first warning sign was that I looked on the online schedule to see where my class was to be held (small classes often end up in surprise mystery buildings all over campus…I like this because I get to learn of new teaching spaces over in the Humanities territories, for example), and saw that the title of the course was something like “Introduction to Relativistic Field Theory”.
…
So I showed up for the first class (this is three weeks ago now), and sure enough, there are the six or seven graduate students from Nick’s class…. but there are four or five students from the condensed matter group, and from the quantum information groups, part of CSI (I kid you not) over in Electrical Engineering! They saw a course with that title and, understandably, thought it was a good chance to learn some Relativistic Field Theory.
Which perplexs me. Is Clifford (a) confused that quantum information is part of the Communication Science Institute, (b) shocked that quantum information science is “relegated” to Electrical Engineering, or (c) dismayed that there are smart people in quantum information science who are interested in learning relativistic field theory, because, you know, quantum information science is just linear algebra and all?
Prehistoric Quantum Algorithms
In 1993, Bernstein and Vazirani had demonstrated a superpolynomial query complexity speedup for quantum computers over classical computers. Charlie Bennett wrote a article in Nature in April 1993 about these new recent developements in quantum computing. In this article, Charlie wrote:
An early but probably vain hope was that quantum parallelism might provide a fast way of solving problems such as factoring or the travelling-salesman problem, which appear to be hard in the same way as finding a needle in a haystack is hard, that is because they involve a search for a successful solution among exponentially many candidates. A computer able to test all the candidates in parallel, and signal unambiguously if it found one that worked, would solve these problems exponentially faster than known methods.
It is easy to program a quantum computer to branch out into exponentially many computational paths; the difficult part is getting the paths to intefere in a useful way at the end, so that the answer comes out with a non-negligible probability. This difficulty is illustrated by the factoring problem above. Suppose the quantum computer is programmed to factor a 100-digit number by trying in parallel to divite it by all numbers of fifty digits or fewer. If any of the approximately 10^50 computation yeilds a zero remainder, it will in a sense have solved the problem. But if there is only one successful path, the interference pattern among all the paths, which determines the behaviour of the computer as a whole, will scarecely be affected. Quantum computers cannot amplify an answer found on a single computation to a detectable level because interference is an additive process, to which each path contributes only as much weight as it started out with.
How strange: to use brute force factoring as the example of a hard problem for quantum computing! Amazingly, Charlie wasn’t even the first to perform this strange analogy. Here is Greg Egan in the book Quarantine in 1992:
Let a computer smear-with the right kind of quantum randomness-and you create, in effect, a ‘parallel’ machine with an astronomical number of processors…All you have to do is to be sure that when you collapse the system, you choose the version that happened to find a needle in the mathematical haystack.
Which makes one wonder, why the heck were all these people thinking about factoring and quantum computers right before Shor’s discovery? Strange, no?
Pop, Coke, …
SODA papers are out. One quantum paper: “Quantum Verification of Matrix Products” by Harry Buhrman and Robert Spalek. Also known as quant-ph/0409035.
Going to MIT and Negative Information
Patrick Hayden (awesome ski picture) sends me an email that negative quantum information was discussed…..on the public radio show “Car Talk!” (The August 27th edition, available for purchase from audible.com.) You know your work has hit it big time when it makes it onto a show which discusses how to repair your car. The next step after “Car Talk” is if your work appears on “The Daily Show.”
Of course, we shouldn’t be too surprised. The hosts of “Car Talk”, Tom Magliozzi and Ray Magliozzi (click and clack), both graduated from MIT. In the show where they discuss negative quantum information, one of the two hosts says something like “Of course you know who Claude Shannon is.” Of course!
FTQC 2005 Talks
A workshop I very much regret missing because I was in Italy, “IBM Workshop on Fault-Tolerant Quantum Computation” now has all of their presentations online.
Quantum Letterman
According to the ISI Web of Science, here are the top cited papers under a “subject” search of “quantum computation”:
1. Loss D, DiVincenzo DP
Quantum computation with quantum dots
PHYSICAL REVIEW A 57 (1): 120-126 JAN 1998
Times Cited: 1003
2. Bouwmeester D, Pan JW, Mattle K, et al.
Experimental quantum teleportation
NATURE 390 (6660): 575-579 DEC 11 1997
Times Cited: 837
3. Ohno Y, Young DK, Beschoten B, et al.
Electrical spin injection in a ferromagnetic semiconductor heterostructure
NATURE 402 (6763): 790-792 DEC 16 1999
Times Cited: 758
4. Gershenfeld NA, Chuang IL
Bulk spin-resonance quantum computation
SCIENCE 275 (5298): 350-356 JAN 17 1997
Times Cited: 617
5. MONROE C, MEEKHOF DM, KING BE, et al.
DEMONSTRATION OF A FUNDAMENTAL QUANTUM LOGIC GATE
PHYSICAL REVIEW LETTERS 75 (25): 4714-4717 DEC 18 1995
Times Cited: 595
6. DIVINCENZO DP
QUANTUM COMPUTATION
SCIENCE 270 (5234): 255-261 OCT 13 1995
Times Cited: 594
7. SHOR PW
SCHEME FOR REDUCING DECOHERENCE IN QUANTUM COMPUTER MEMORY
PHYSICAL REVIEW A 52 (4): R2493-R2496 OCT 1995
Times Cited: 565
8. BARENCO A, BENNETT CH, CLEVE R, et al.
ELEMENTARY GATES FOR QUANTUM COMPUTATION
PHYSICAL REVIEW A 52 (5): 3457-3467 NOV 1995
Times Cited: 557
9. Ekert A, Jozsa R
Quantum computation and Shor’s factoring algorithm
REVIEWS OF MODERN PHYSICS 68 (3): 733-753 JUL 1996
Times Cited: 525
10. Knill E, Laflamme R, Milburn GJ
A scheme for efficient quantum computation with linear optics
NATURE 409 (6816): 46-52 JAN 4 2001
Times Cited: 435
What this means is beyond me, but what the heck, who said I was going to provide useful information on this blog!
Who Will Program the Quantum Computers?
Quantum computers can break many of today’s modern public key cryptosystems. Hence there are lots of three and four letter agencies in governments around the world who are very interested in getting a quantum computer built. (If we put our paranoid hats on, we can ask: are there any countries that are pursuing a secret project for quantum computing? Is it beyond possibility that China, for example, has a secret quantum computing project, and that they will beat the rest of the world to building a quantum computer? Could this be the next Sputnik? OK, enough paranoid mode!) What will the sensitive nature of quantum computers current killer application, breaking public key cryptosystems, mean for researchers in quantum computation? Will it mean that the first large scale quantum computers, when they are built, will have restricted access? Will all hell break loose once quantum computers which can break today’s public key cryptosystems? I’m not just thinking about spy versus spy schemes, but instead, I’m thinking about financial transactions, online use of credit cards, and the whole of the electronic economy. Sometimes it feels like it is a shame that the main attention grabbing algorithm for quantum computers is factoring. Other times, I think about the above line of reasoning, as it scares the bejesus out of me.
How will we make the transition from a world where public key cryptosystems are no longer secure? Will we use the unbroken cryptosystems (lattice based, and linear decoding based?) which have drawbacks which are fairly severe? Will we install quantum key distribution into our networks? And will this transition be gradual, or will it hit like a shockwave, as serious size quantum computers get built over a short span of time?
Interestingly, I don’t think the quantum computing community has had a serious dialogue about these issues. At least not that I know of. Sure we talk about these things over lunches in quantum groups around the world, but is there any consensus over how the public quantum computing community should deal with these issues?
Patterns? You Want Patterns?
I highly recommend this post over at Three-Toed Sloth about identifying coherent structures in spatiotemporal systems. What a pretty post! Oh, and the science is fascinating as well. It reminds me of a question I’ve always wondered about in cellular automata theory. It’s a bit long winded, so if I get the time I’ll write a post on it.
Bohring Fault-Tolerance
(Update: Sean Barret points out that his comment when I first posted this was exactly the point I talk about in this post. Somehow my brain didn’t register this when I read his comment. Doh.)
Back from a workshop in Arlington, VA.
One of the most interesting events in this workshop was that Daniel Lidar talked (all to briefly) about his (along with Alicki and Zanardi’s) objections to the theory of fault-tolerant quantum computation. I’ve talked about this before here, where the resulting discussion in the comments was very interesting. At the workshop, Hideo Mabuchi brought up something about the paper which I had totally missed. In particular, the paper says that (almost all) constructions of fault-tolerant quantum computation are based upon three assumptions. The first of these is that the time to execute a gate times the Bohr frequency of the system should be on the order of unity. The second assumption is a constant supply of fresh ancillas. The third is that the error correlations decay exponentially in time and in space.
What Hideo pointed out was that this first assumption is actually too strong and is not assumed in the demonstrations/proofs of the theory of fault-tolerant quantum computation. The Bohr frequency of a system is the frequency which comes from the energy spacings of the system doing the quantum computing. The Bohr frequency is (usually) related to the upper limit on the speed of computation (see my post here), but is not the speed which is relevant for the theory of fault-tolerance. In fault-tolerance, one needs gates which are fast in comparison to the decoherence/error rate of your quantum system. Typically one works with gate speeds in implementations of quantum computers which are much slower than the Bohr frequency. For example, in the this implementation of a controlled-NOT gate in ion traps at NIST, the relevant Bohr frequency is in the gigahertz range, while the gate speeds are in the hundreds of kilohertz range. What is important for fault-tolerance is not that this first number, the Bohr frequency, is faster than your decoherence rates/error rates (which it is), but instead that the gate speed (roughly the Rabi frequency) is faster than your decoherence rates/error rates (which is also true.) In short, the first assumption used to question the theory of fault-tolerance doesn’t appear to me to be the right assumption.
So does this mean that we don’t need to worry about non-Markovian noise? I don’t think so. I think in many solid state implementations of quantum computers, there is a strong possibility of non-Markovian noise. But I don’t now see how the objection raised by Alicki, Lidar, and Zanardi applies to many of the quantum computing proposed systems. Quantifying the non-Markovian noise, if it exists, in different physical implementations is certainly an interesting problem, and an important task for the experimentalists (and something they are making great progess on, I might add.) Along these lines it is also important to note that there are now fault-tolerant constructions for non-Markovain noise models (Terhal and Burkard, quant-ph/0402104 and Aliferis, Gottesman, and Preskill, quant-ph/0504218.) Interestingly, these models postulate non-Markovian models which are extremely strong in the sense that the memory correlations are possibly infinitely long. However, it is likely that any non-Markovian noise in solid state systems isn’t of this severly adversarial form. So understanding how the “amount” of non-Markovian dynamics effects the threshold for fault-tolerance is an interesting question.