A full day today, after a nice break yesterday (went for a run: yeah for altitude making me winded nearly instantly!)
Andrew Childs, “Universal computation by quantum walk
Andrew Childs talked about a subject whose origin can be pretty much tracked back to Feynman in the 1980s. In particular Feynman constructed a model of computing in which you have a time independent Hamiltonian. In today’s language this is equivalent to showing that there is a quantum random walk which is universal for quantum computing (though Andrew mentioned that this was a model for classical computing using a quantum device, but that it can be converted over to a quantum computing model.) If one examines the graph for which Feynman’s quantum walk would occur, it has a degree which grows with the size of the computation. Andrew has worked out a way to make quantum random walks with fixed degree simulate a quantum computation. This appears in arXiv:0806.1972.
Andrew Landahl asked an interesting question about the momentum filter in Andrew’s talk: he pointed out its similarity to the constructions in the NAND tree algorithm and wondered why this was. Anyone?
Dmitry “Michael Phelps II” Gavinsky, “Classical interaction cannot replace quantum nonlocality”
Dmitry showed an example where quantum correlations are surprisingly strong in communication complexity. Paper here: arXiv:0901.0956. In communication complexity one analyzes the situation where multiple players who each have input to a function compute this function by communicating with each other. Here one is most interested in the resources used to achieve this task as a function of the size of the inputs. Usually this resource is the amount of communication needed (measured in bits.) There are many models of communication complexity. For example you may consider a model where two parties, Alice and Bob (of course) communicate back and forth (interactive) in order to compute the function. Or you may allow Alice to communicate to Bob who will calculate the function. Or, in the simultaneous model, Alice and Bob communicate one message to a referee Reefer Joe, who then computes the function. These three models are of different power, i.e. in some models you require more communication than in the other. For example the interactive model is stronger than the simultaneous message passing model.
What Dimtry analyzed was that if you augment the simultaneous message passing model (to be clear communication is classical) with entanglement. He showed that this model is exponentially more powerful than the strongest model classically, where one allows Alice and Bob to interactively communicate to compute the function. In other words, by taking the weakest classical model, and giving the players entanglement, there are problems which can be solved exponentially better than the strongest classical model where the parties communicate interactively.
Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando Somma (speaker), and
David Yonge-Mallo, “Efficient discrete-time simulations of continuous-time quantum query algorithms”
The authors showed how to convert continuous-time quantum query algorithms into discrete-time query algorithms efficiently. Paper arXiv:0811.4428. This really frees up those want to design quantum time algorithms in the continuous-time domain by showing how to convert these into the standard model.
I’m going to have to run after this talk and may miss the 2pm talk. Anyone who would like to leave a comment on these two talks I’d love it and can paste it into this blog post. Anyone?
In other words, by taking the weakest classical model, and giving the players entanglement, there are problems which can be solved exponentially better than the strongest classical model where the parties communicate interactively.
Could entanglement in this case mean that there is shared information at the start of the computation? [E.g. could I get away with calling it an affine calculation, where the affinity is known to both Alice and Bob, or have I missed the point?]
Does the communication necessarily entail communicating the function to be computed as well as its solution?
As Andrew Landahl has mentioned in his paper arXiv:0802.1207 the Feynman’s construction is the proof of the universality of continuous-time quantum walk *not* quantum RANDOM walk, which is a different model. Please correct me if I am wrong.
I decided now would be a good time to finish up the posts on additivity I had in my drafts folder. The results are here and here. I hope someone finds them useful!