Category: Computer Science

Posted on

More Hot Water Fodder

Since, my remarks in the last post about classical computational complexity got me into such hot water with those who are much smarter than I am, I thought I’d post another of the less often expressed reasons for studying quantum computation from my notes:

It is often remarked upon by mathematicians and physicists that there is a mysterious harmony between these two disciplines. Indeed both fields have benefitted immensely from each other. The same can not be said, I think, for computer science. A good question to ask is why this is true? One idea floating around in research land is that the reason for the lack of such deep connections has been that this is because the wrong model of computation has been studied. It makes sense that if the universe obeys the laws of quantum theory, then we shouldn’t be surprised if a theory of computation based on classical theory doesn’t make connection to the physics of these devices. And going one further step it also seems likely that if we use the theory of computation which is more relevant to the way our world works, then we just might be able to prove and reason about these computers in a simpler manner. A rough analog might be that between real analysis and complex analysis: certainly those of you who have had a class on real analysis and complex analysis remember how “easier” everything is in complex analysis than in real analysis. Might quantum computers lead to a similar shift? Right now there are only a few results that I can point to along these directions, for example Scott Aaronson’s has a very eloquent proof that the complexity class PP is closed under intersection which begins by first showing that PP is equal to a model of quantum computing in which one can post-selection the outcome of the quantum computation and then is extremely simple due to the properties of the quantum model of computation to show closure under intersction. Might not more of the theory of computational complexity be as easy if we focus on the model of quantum computation?

Posted on

CSE 599d Lecture Notes 1

Well class begins for me this afternoon. As I’ve mentioned before I’m teaching a graduate course in quantum computing. Here are the first set of lecture notes for the class: Introduction and Basics of Quantum Theory. As part of these notes, I’ve put a little section with some of the less often expressed reasons I think doing research in quantum computing is important. Here is one excerpt which I’m sure many of you will enjoy:

If today someone was to prove that P does not equal NP for a classical computer, would we be satisfied? Well certainly we would be very excited and this would be the breakthrough of the century in computation, but because the universe is fundamentally quantum mechanical, would we really be satisfied that the intractability of NP-complete problems had been shown? Quantum computers open up an entire bag of worrying about the foundations of computational complexity. It is dangerous to say this, of course: if this view is correct, then the hard work of classical computational theory might have been in vain. But if this is the correct view, then we need to begin weaning ourselves off of the classical model of computation.

Posted on

Schurly Your Joking Drs. Bacon, Chuang, and Harrow?

What better way to start the new year than with the new paper dance. You can dance, you can dance, everyone publish their rants.
Thanks to the hard work and good timing of coauthor Aram Harrow, we were able to get the first paper of the new year on quant-ph: quant-ph/0601001. Happy new year!
The Quantum Schur Transform: I. Efficient Qudit Circuits
Authors: Dave Bacon, Isaac L. Chuang, Aram W. Harrow
Comments: 24 pages

We present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the Schur transform. The Schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. If we desire to implement the Schur transform to an accuracy of epsilon, then our circuit construction uses a number of gates which is polynomial in n, d and log(1/epsilon). The important insights we use to perform this construction are the selection of the appropriate subgroup adapted basis and the Wigner-Eckart theorem. Our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and is an important new efficient quantum circuit family which goes significantly beyond the standard paradigm of the quantum Fourier transform.

Posted on

Ion Trap Scaling Work

One of the big pushes occuring in ion trap quantum computing these days is the construction of different ion traps which will be useful in scaling up these quantum computer architectures. Chris Monroe’s group at Michigan (in collaboration with Keith Schwab at the PRL in Maryland) has a nice paper out a few days ago in Nature Physics describing a new ion trap they have built (for a news release, see here. ) This microtrap is built, basically, on a semiconductor chip, and is of the micrometer size as compared to the millimeter sized traps normally used for trapping ions. Because these traps are fabricated using semiconductor MEMS technology, it is not unreasonable to think of building traps which can stored hundreds to thousands of ions at a time.
One interesting property of the traps described in the paper is the shallow depth of the trapping potential as compared to the depth of the potential for larger, milimeter scale traps (about 0.08 eV in the former compared to order 1 eV in the latter.) What this means is that the ions they trap stay in the trap for minutes as opposed to days, and that it has not been possible to simultaneously trap two ions in the trap. Which is what I love about experiments: while this is an important step, we’re certain to see more steps in the future and it is not unreasonable to expect some good scaling up in of ion trap quantum computers in the next few years.
Another set of experiments involving traps designed to be scalable comes from Isaac Chuang’s group at MIT. A preprint of their work is available as quant-ph/0511018. Me, I just like to flip to the end of their paper and stare at their neat hexagonal trap and dream of the cool things I could do with such a trap.

Posted on

Physicists and Computer Scientists

Scott Aaronson and Lance Fortnow discuss What should physicists know about computational complexity?
I’m thinking that this deserves a rejoiner, “What should a computer scientist know about computational complexity?” I mean, how silly have these computer scientists been…they’ve been studying classical computers for all these years, when it is totally obvious (at least to a physicist like me) that they should have been studying quantum computers. 😉
This reminds me of my favorite way to distinguish between a computer scientist and a physicist at quantum computing conference. Physicists are the ones who think that NP stands for “not polynomial” and computer scientists are the ones who think that a Hamiltonian is some sort of sandwich.

Posted on

QIP 2006 Talks

QIP 2006, to be held in Paris, now has the list of talks for this workshop here. There were 160 submissions! There are eight invited talks, sixteen long talks, and sixteen short talks. Lots of interesting talks, which makes me wish I could have figured a way to attend (that and I’ve never spent any time in Paris.)
By the way, for those of you thinking of applying to graduate school in quantum information science theory, this list of speakers, and the institutions they represent, would probably be a good place to start.

Posted on

Jobs in Quantum Information Science

This is the first year in a few that I haven’t been applying for jobs (You might suspect that this makes me less grumpy. Well, judge for yourself!) Now I could be wrong, but is this the first explicit advertisement by a U.S. university physics department for a theory position in quantum information science?

Quantum Information Theory
The Department of Physics and Astronomy at the University of Southern California invites applications for tenure or tenure track positions at all faculty levels in the area of Quantum Information Theory.

Well even if it isn’t the first, can we take this as a good sign?

Posted on

Ion Trap Quantum Computer Papers

Interesting papers in experimental ion trap quantum computation:
Creation of a six-atom ‘Schrödinger cat’ state from Wineland’s group at NIST Boulder, Nature 438, 639-642 (1 December 2005.) Schrodinger’s cat is now six qubits big! And growing! What a cute little kitten.
Scalable multiparticle entanglement of trapped ions from Blatt’s group in Innsbruck. Nature 438, 643-646 (1 December 2005.) In this paper the group discusses experiment they performed which created the so-called “W” entangled state for up to eight qubits. That’s a quantum byte, peoples! Amazingly the group performs full state tomography on these states. Wow that sounds like an awful lot of graduate student hours.

Posted on

More Dice

The full t’ ‘t Hooft (look I put the apostrophy in the correct location!) article is now posted at Physics World (not Physics Today, as I listed incorrectly in my first post) commentary by Edward Witten, Fay Dowker, and Paul Davies. Quick summary: Witten thinks that quantum cosmology is perplexing, Dowker worries about the emergence of classical physics, and Davies postulates that complexity is the key to understanding the emergence of classicality. Davies suggests that quantum mechanics will break down when the Hilbert space is of size 10^120 and suggests that quantum comptuers will fail at this size. His argument could equally be applied to probablistic classical computers, and so I suggest that if he is right, then classical computers using randomness cannot be any larger than 400 bits.

Posted on

SQuInT 2006

My favoritest ( 😉 ) meeting SQuInT will be having it’s nineth conference in Albuquerque February 17-19. Whoop, another chance to visit the rattlesnake museum!