SQuInTing at Pirates

This last weekend I attended two out of three days of the SQuInT conference in Albuquerque, NM. The conference, as usual, was stellar, and was rather large this year, with nearly 150 people! The only real draw back this year was that the hotel the conference was in had variously scheduled (1) a band, and (2) a group that liked to sing and cheer in the room adjacent to where the conference talks were held. When the crowd next door broke out into a hymn I almost lost it. Almost.
Anyway there were a lot of very interesting talks at the conference (schedule can be found here.) But I must say there was also the most unusual talk I have seen in a long time. And I must say it was also one of the best talks I have seen in ages. It was given by Jonathan Walgate from the University of Calgary. Here is the title and abstract:

Quantum Buried Treasure
Jonathan Walgate (University of Calgary)
Abstract. A swashbuckling tale of greed, deception, and quantum data hiding on the high seas. When we hide or encrypt information, it’s probably because that information is valuable. I present a novel approach to quantum data hiding based on this assumption. An entangled treasure map marks the spot where a hoard of doubloons is buried, but the sailors sharing this map want all the treasure for themselves! How should they study their map using local operations and classical communication? This simple scenario yields a surprisingly rich and counterintuitive game theoretic structure. A maximally entangled map performs no better than a separable one, leaving the treasure completely exposed. But non-maximally entangled maps can hide the information almost perfectly! Quantum data hiding was developed with two motivations. It is worth investigating purely as cryptographic scheme, allowing data to be concealed from cryptanalysts sharing a perfect copy. However it also provides an operational framework for studying entanglement and nonlocality, as it hinges on the difference between local and global physical information. `Quantum buried treasure’ schemes have four key advantages. Firstly, the local perspectives of those sharing the quantum system are clearly revealed, and this allows a more detailed comparison between the local and global information. (Previous schemes have treated local observers as a single collective eavesdropper, albeit operating under local constraints.) Secondly, interesting competitive situations emerge among the local parties. These suggest a useful role for game theory in quantum mechanics that emerges naturally from its nonlocal structure, unlike artificial attempts to unify the two. Thirdly, buried treasure provides a more realistic model both of encrypted information, which tends to be actually valuable, and of the motivations of those attempting the decryption. Last but not least, Alice and Bob get to be pirates!

Argy matey. Notice especially that last point. The talk was very amusing, as you can imagine. Hopefully there will be a paper coming out soon, as the idea is fascinating and, I must say, one of the first times I’ve seen a quantum game theory paper and haven’t wanted to jump out of my seat and shout something. Well this time I only realized afterwards that I wanted to jump out of my seat, but I didn’t have a chance to ask Jonathan my question so I guess I’ll have to wait for the paper.
Another talk I found very interesting was Andrew Landahl’s work on a quantum algorithm for ordered search problems (Update: I forgot to mention this was joint work Andrew did with Andrew Childs and Pablo Parrilo.) An old result of Farhi et. al. showed that one could search an ordered list using 3 times log base 52 of the size of the database. This algorithm should, of course, be called the card players algorithm ;). If we work in base 2, this works out to an algorithm which is approximately 0.53 log base 2 of the size of the database. The best lower bound (IIRC) was 0.22 log base 2 of the size of the database. Of course, quantum computer people like square root speedups, so a natural guess is that the real answer is log base 2 of the square root of the size of the database. But Andrew was able to show, by solving some neat little semidefinite programming problems, that 4 times log base 605 the size of the database queries suffice. This is about 0.43 times the log base 2 of the size of the database, hence destroying the naive quantum computing Grover guess! Well how excited should we be about these “constant” speedups? I’m not sure. On the one hand they are not as sexy as Shor’s algorithm (what is!) but on the other hand, they are kind of cute demonstrations that if you build a quantum computer comparable to a classical computer you should pay at least a constant amount more to use the quantum computer 😉
Another talk which I need to think more about was given by Masoud Mohensi (USC/University of Toronto). Masoud talked about work he did with Daniel Lidar on what they call “Direct Characterization” of open systems quantum dynamics. The idea here is to perform process tomography without having to actually perform quantum state tomography, and in the process obtain less use of resources. In particular Masoud showed how to use entangled states as inputs into a quantum superoperator and then characterize this superoperator using 4^n Bell measurements where n is the number of qubits. Papers on this subject can be found as quant-ph/0601033 and quant-ph/0601034.
Finally, of great interest to everyone, I’m sure, I learned that the state of New Mexico is building a spaceport. That’s right, the economically depressed state of New Mexico is going to make their stamp on the world by building a spaceport! I also heard a theory about this from one of the participants at the conference. This person suggested that he now understood the UFO landing at Rosewell. Apparently the aliens simply set their time machine incorrectly and ended up a few years early! (Their maps for the spaceport were correct, but they misdialed the “YEAR” dial, most certainly due to a translation problem caused by the Babelfish.)