Here are some very fragmentary notes on the second day of QIP 2011. You can see arXiv references, slides, and videos of the talks here. I’ll just give links to the slides, and again I’ll only mention 3 talks.
Stephanie Werner gave a talk on the relation between the uncertainty principle and nonlocality in quantum theory. There’s a general framework for physical theories, called “generalized probabilistic theories”, which includes classical and quantum mechanics as special cases. In this framework we can see that while quantum theory is “nonlocal” in the sense made famous by John Bell, even more nonlocal theories are logically possible!
For example, while quantum theory violates the Clauser–Horn–Shimony–Holt inequality, which is obeyed by any local hidden variables theory, it doesn’t violate it to the maximum possible extent. There is a logically conceivable gadget, the Popescu–Rohrlich box, which violates the CHSH inequalities to the maximum extent allowed by a theory that prohibits faster-than-light signalling. However, such a gadget would give us implausibly godlike computational powers.
In Werner’s talk, she explained another reason not to hope for more nonlocality than quantum theory provides. Namely, given the “steering” ability we have in quantum theory — that is, our ability to prepare a state at one location by doing a measurement at another — the theory cannot be more nonlocal than it is while still obeying the uncertainty principle.
Jérémie Roland gave a talk on generalizations of Grover’s search algorithm. Grover’s algorithm is one of the implausibly godlike powers that quantum computers might give us, if only we could build the bloody things: it’s a way to search a list of N items for a given item in a time that’s only on the order of N1/2. This algorithm assumes we can freely jump from place to place on the list, so instead of a linearly ordered “list” it’s probably better to visualize this data structure as a complete graph with N vertices. Roland’s talk explained a way to generalize this idea to arbitrary graphs.
He began by considering a Markov chain on the graph — that is, a way to blunder randomly from vertex to vertex along the graph, where you can only go from one vertex to another in one step if there’s an edge connecting them. He assumed that it’s reversible and ergodic. Then, starting from this, he described how to fashion a quantum process that finds the desired vertex (or vertices) in about the square root of the time that the Markov chain would take.
Robin Kothari gave a talk on using quantum computation to efficiently detect certain properties of graphs. He considered “minor-closed properties” of graphs. Let me just tell you what those properties are, and tell you about a fascinating older result about them.
The word graph means many slightly different things, but in this blog entry I mean a finite set 
A minor of a graph is another graph that can be obtained from the first one by repeatedly:
1) removing edges,
2) removing vertices that have no edges connected to them, and
3) contracting edges, that is, shrinking them to nothing and then identifying the vertices at both ends, like this:
For example, this graph:
is a minor of this one:
A property of graphs is minor-closed if whenever one graph has it, all its minors also have it.
What are some minor-closed properties? An obvious one is lacking cycles, that is, being a forest. You can get rid of cycles by getting rid of edges and vertices, or contracting edges, but you can’t create them!
A more interesting minor-closed property is planarity. If you can draw a graph on the plane, you can clearly also draw the graph you get by removing an edge, or removing a lone vertex, or contracting an edge.
Now, Kuratowski showed that planar graphs as precisely those that don’t have this graph:
or this one:
as minors.
Similarly, graphs that lack cycles are precisely those that don’t have a triangle as a minor!
So, we could ask if this pattern generalizes. Given a minor-closed property of graphs, is it equivalent to a property saying that there’s some finite set of graphs that don’t show up as minors?
This is called Wagner’s conjecture, after Klaus Wagner. He published it in 1970.
Wagner’s conjecture is true! It was proved by Neil Robertson and Paul Seymour in 2004. But the really interesting thing, to me, is that their proof takes about 400 or 500 pages!
I find this quite surprising… but then, I wouldn’t have guessed the four-color theorem was so hard to prove, either.
To make sure you understand Wagner’s conjecture, check that if we dropped the word “finite”, it would have a one-sentence proof.
Azimuth 
Of course the scaling is the big improvement for quantum computation, Grover’s algorithm being the prime example, but what about the prefactors, the coefficients which depend upon actual implementation? Remember Landauer’s complaint that implementations were not properly modeled. You may have heard about “hug a tree”.
http://www.nasar.org/nasar/history_hug_a_tree.php
The “hug a tree” concept is maybe easier to compute in the “find your wife in the shopping mall” scenario. In that case, if she remains in one store while you search for her the prefactor is half what it would be than if she wanders from store to store. The assumption is that you search one store after another.
Anyway it is certainly possible to perform implementations that don’t scale “properly”, although these are usually “stupid” implementations. One example would be for you to have a safe point, say the mall entrance, that you return to frantically time after time, checking every store you pass by repeatedly.
The first simulated Grover’s algorithm I wrote had stupid scaling, exactly linear. After smacking my head and rewriting the obvious errors, it still didn’t scale near square root, closer with larger numbers but still. And that’s just code.
There may be issues with physical implementation that mar the pretty scaling theory.
I would not describe a square root speed-up in the Grover’s algorithm as a godlike …
I was trying to needle people in quantum information who regard Popescu-Rohrlich boxes as ‘too powerful to be plausible’, while not feeling the same about quantum computers, which while less powerful, could still accomplish rather shocking feats. Of course the big difference is that we have vast amounts of experimental evidence for quantum mechanics, but nary a shred of evidence for Popescu-Rohrlich boxes.
If someone told me they could search a phone book with a million phone numbers, and find the person with a given phone number in only a thousand steps, I might not call them ‘godlike’, but I’d still be quite impressed.
(Here, for the sake of a good story, I’m ignoring the constant factor in
, despite John F’s wise warning.)
In cross-referencing the results that David Poulin presented on the first day of QIP 2011, relating to what Poulin, Qarry, Somma and Verstraete call “the convenient illusion of Hilbert space”, there are natural links to two recent works by Johnson, Biamonte, Clark, and Jaksch, namely Dynamical simulations of classical stochastic systems using matrix product states (arXiv:1006.2639) and Categorical Tensor Network States (arXiv:1012.0531).
It is enjoyably enlightening to contemplate what amounts to the same physical ideas presented alternatively in the language of traditional quantum mechanics, computer science, linear algebra, information theory, Lindbladian dynamical flow, and now, category theory.
I discuss these emerging links further on Dave Bacon’s Quantum Pontiff weblog … it would be great fun if some category theorist would weigh in on this.
John already tried to explain to me that all people interested in quantum information consider finite Hilbert spaces only, but I am still puzzled by David Poulin’s talk: He does not mention any restriction about the dimension of the Hilbert space that his Hamiltonians act on, and he even mentions the standard model as an example of the “kind of system” he considers, so I’ll make a fool of myself again by asking: Is this talk about finite Hilbert spaces or about infinite ones?
It’s finite alright, this follows from the last slide before the summary, there is a finite volume for the sphere of the considered Hilbert space.