Wee Kang Chua here in Singapore has pointed me to Quantum Soccer. If you want to decrease your productivity by a good ten, twenty percent, please click on the link.
Post Quantum Crytopgraphy
In the comments Who Will Program the Quantum Computers?, Hal points to PQCryto 2006, a conference on post-quantum cryptography. From their webpage:
PQCrypto 2006: International Workshop on Post-Quantum Cryptography
Will large quantum computers be built? If so, what will they do to the cryptographic landscape?
Anyone who can build a large quantum computer can break today’s most popular public-key cryptosystems: e.g., RSA, DSA, and ECDSA. But there are several other cryptosystems that are conjectured to resist quantum computers: e.g., the Diffie-Lamport-Merkle signature system, the NTRU encryption system, the McEliece encryption system, and the HFE signature system. Exactly which of these systems are secure? How efficient are they, in theory and in practice?
PQCrypto 2006, the International Workshop on Post-Quantum Cryptography, will look ahead to a possible future of quantum computers, and will begin preparing the cryptographic world for that future.
Prepare for us world, we quantum computers are coming (well, maybe not so fast 😉 )
Delta X Delta P
The science blogosphere is abuzz about Lisa Randall’s op-ed article in the New York Times. See comments at Hogg’s Universe, Not Even Wrong, Lubos Motl’s Reference Frame, and Cosmic Variance. The article just made me happy: read the following paragraph
“The uncertainty principle” is another frequently abused term. It is sometimes interpreted as a limitation on observers and their ability to make measurements. But it is not about intrinsic limitations on any one particular measurement; it is about the inability to precisely measure particular pairs of quantities simultaneously. The first interpretation is perhaps more engaging from a philosophical or political perspective. It’s just not what the science is about.
There is nothing that makes my Monday mornings brighter than a correct popular explanation of the uncertainty principle.
Optimistic Deutsch
David Deutsch thinks quantum computing is just around the corner. He has posted the following on his blog:
For a long time my standard answer to the question ‘how long will it be before the first universal quantum computer is built?’ was ‘several decades at least’. In fact, I have been saying this for almost exactly two decades … and now I am pleased to report that recent theoretical advances have caused me to conclude that we are within sight of that goal. It may well be achieved within the next decade.
The main discovery that has made the difference is cluster quantum computation, which is a marvellous new way of structuring quantum computations which makes them far easier to implement physically.
Quantum Dot Qubits
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?
My Fermion is a Boson
Recently I have been reading Quantum Field Theory Of Many-body Systems: From The Origin Of Sound To An Origin Of Light And Electrons
The place where I first learned about this sort of thing was some of the work I did in my thesis where I used the Jordan-Wigner transformation in one dimension (A good read: Michael Nielsen’s notes on the Jordan-Wigner transform.) Suppose you have a one dimensional lattice of fermions, where the fermions only interact between nearest neighbors. Let [tex]$a_i$[/tex] and [tex]$a_i^dagger$[/tex] be the annihilation and creation operators at the site [tex]$i$[/tex]. These being fermions, these operators satisfy [tex]${a_i,a_j^dagger}=delta_{i,j}$[/tex] and [tex]${a_i,a_j}=0$[/tex]. In the Jordan-Wigner transform, we replace each fermion site by a qubit, then we perform the map [tex]$a_irightarrow – prod_{j=1}^{i-1} Z_jfrac{1}{2} (X_i + i Y_i)$[/tex]. One can easily check that this mapping preserves the fermion commutation relations. Under this mapping, we can map our nearest neighbor fermion model to a nearest neighbor qubit model. It is exactly this kind of mapping, for more interesting systems, that Wen is excited about.
An interesting question to ask is how to perform the above mapping for lattices of dimension higher than one. To this end, you will notice that the mapping used above has a linear ordering and hence is not well adapted to such a task. In particular if you try to use the mapping in this manner, you will end up creating qubit Hamiltonians with very nonlocal interactions. In fact, many have tried to create higher dimensional Jordan-Wigner transforms, but in general, there were always limiations with these attempts. To this end, the recent paper cond-mat/0508353 by F. Verstraete and J.I. Cirac is very exciting. These two authors show that it is possible to convert any local fermion model into a local model with qubits (or qudits), i.e they effectively solve the problem of creating a Jordan-Wigner transform on higher dimensional lattices.
One of the points that Wen likes to raise from this work is the question of whether fermions are actually fundamental. From what I understand, while there are examples of fermions arising from these local interacting boson modes, it is not known how to do this with chiral fermions. Strangely I’ve always been more inamored with fermions than with bosons (holy cow am I a geek for writing that sentence.) But perhaps my love of bosons will have to start growing (oh, that’s even worse!)
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!