Posters For Some, Minature American Flags for Others

“Ideal conversation must be an exchange of thought, and not, as many of those who worry most about their shortcomings believe, an eloquent exhibition of wit or oratory”
– Emily Post(er)

As a literature major physicist, one of the biggest culture shocks I’ve encountered when attending theory computer science conferences (STOC and FOCS) is the lack of a poster session at these conferences (or at least the ones I attended, which, truth be told, is not many.) Admittedly, I’m a sucker for free wine, beer, and cheese (or at least a cash bar peoples) and some of my warmest thoughts are of the science projects I did growing up (though I still think my eighth grade project was wrongly not awarded grand prize because the judges didn’t think I could have done the project.) But truthfully, I think I get more out of posters at conferences than most of the talks. And, in some deep sense, I find the lack of a poster session at these conferences nearly…anti-scientific. There. I’ve said it. Anti-scientific, Pontiff? Really? Well yeah I am prone to hyperbole.
Yes, I know that getting a paper into a top CS theory conference is the mark of acceptance and praise and “yes you are one of us” for the theoretical computer science community. And while I think that this system is inherently troubling for a few reasons, it doesn’t disturb me nearly as much as the suppression of ideas which are just “not good enough” or “too far on the fringe.” As far as I can tell, the inclusion of a poster session is strictly a positive: it gives students chance to discuss their work, it encourages breadth for a conference by allowing in submissions that might not fit with what is “in” at the moment, it is perhaps the best place I know to start a collaboration, and it encourages civil discussion of results that are…wrong.
Which brings me to my final point. I’ve been on the QIP program committee for two years now, and blessedly QIP does have a poster session (perhaps due to its hybrid nature combining physics and computer science.) This is great…for example in Santa Fe last year I learned about some very cool work the Dorit Aharonov and collaborators were doing from her poster (and a yelling match we had driving from ABQ to Santa Fe :)) as well as about some new results on the hidden subgroup problem over the Heisenberg group (okay I’ll admit that one is only really exciting to me!) In the course of these years we have, on the program committee, rejected posters from the conference. Now there are certain reason why I can imagine doing this, but it doesn’t really make me happy. For me, the only reason why one should reject a poster is that the poster should be off topic. For posters, because they’re just posters, damnit, I don’t even use the requirement that the paper is correct (sorry.) If QIP gets a paper on nonlinear fluid dynamics, then certainly reject the poster, but if you get a poster on P=NP? I say accept it as a poster (and I mean, it could be useful for the author to hear repeatedly why he or she is incorrect.)
So, if the QIP business meeting gets boring, and you want to stir up some debate, I suggest that someone raise the following question: what are our standards for poster session and are they ones that the conference should have? This might be especially relevant for QIP, which is increasingly computer science oriented (I said increasingly, not solely), and where there are certainly, say, implementation papers, that might get rejected (and I would argue they should be accepted: the beauty of quantum information science it’s crossing disciplines, and to cut of completely one discipline is like chopping your arm off.)
(One interesting issue for QIP is that for posters one submits the same 3 page brief note about the research that speakers submit. In most physics conferences when you submit a poster all you submit is an abstract, from which it is nearly impossible to judge whether the work is relevant/correct and so more posters are included.)
So, posters for all, says this scientific popularist.

QIP Talks That Have arXiv Papers

QIP 2010 talks and associated papers if I could find them (amazing how almost all papers for this conference are available, for free, online at one location….also interesting how papers seem to cluster in the 10-12 months of the listings 🙂 ) If anyone has corrections please leave a comment.


  • Daniel Gottesman and Sandy Irani
    The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems
  • Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang
    On the power of a unique quantum witness
  • Scott Aaronson and Andrew Drucker
    A full characterization of quantum advice
    No paper found
  • Rahul Jain (invited talk)
  • Antonio Acin, Antoine Boyer de la Giroday, Serge Massar, and Stefano Pironio
    Random numbers certified by Bell’s theorem
  • Dave Bacon and Steve Flammia
    Adiabatic gate teleportation
    arXiv:0905.0901 (see also arXiv:0912.2098)


  • Ben Reichardt (invited talk)
    Span programs and quantum algorithms
    A series of papers, including the 70 pager arXiv:0904.2759
  • David Gross, Yi-Kai Liu, Steven Flammia, Stephen Becker, and Jens Eisert
    Non-commutative compressed sensing: theory and applications for quantum tomography
    arXiv:0909.3304 (see also the followup arXiv:0910.1879 update: and the paper referred to in David’s talk as arXiv:1001.2738)
  • Norbert Schuch, J. Ignacio Cirac, Dorit Aharonov, Itai Arad, and Sandy Irani
    An efficient algorithm for finding Matrix Product ground states
    arXiv:0910.5055 and arXiv:0910.4264
  • Dominic W. Berry and Andrew M. Childs
    The query complexity of Hamiltonian simulation and unitary implementation
  • Maarten Van den Nest
    Simulating quantum computers with probabilistic methods
  • Philippe Corboz (invited talk)
    Simulation of fermionic lattice models in two dimensions with tensor network algorithms
  • Boris Altshuler, Hari Krovi, and J√©r√©mie Roland
    Adiabatic quantum optimization fails for random instances of NP-complete problems
  • Kristan Temme, Tobias Osborne, Karl Gerd Vollbrecht, David Poulin, and Frank Verstraete
    Quantum metropolis sampling
  • Sergey Bravyi, David Poulin, and Barbara Terhal
    Tradeoffs for reliable quantum information storage in 2D systems


  • Andr√© Chailloux (invited talk)
    Quantum coin flipping
  • Matthias Christandl, Norbert Schuch, and Andreas Winter
    Highly entangled states with almost no secrecy
  • Anindya De and Thomas Vidick
    Improved extractors against bounded quantum storage
  • Ivan Damg√•rd, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner
    Improving the security of quantum protocols via commit-and-open
  • Robert Koenig, Stephanie Wehner, and Juerg Wullschleger
    Unconditional security from noisy quantum storage
    arXiv:0906.1030 and arXiv:0911.2302
  • Pablo Arrighi, Vincent Nesme, and Reinhard Werner
    Unitarity plus causality implies localizability


  • Aram Harrow (invited talk)
    Quantum algorithms for linear systems of equations
  • Stefano Chesi, Beat R√∂thlisberger, Daniel Loss, Sergey Bravyi, and Barbara M. Terhal
    Stability of topological quantum memories in contact with a thermal bath
  • Robert Koenig, Greg Kuperberg, and Ben Reichardt
    Quantum computation with Turaev-Viro codes
    No paper found
  • Mark Howard and Wim van Dam
    Tight noise thresholds for quantum computation with perfect stabilizer operations
  • Prabha Mandayam and Hui Khoon Ng
    A simple approach to approximate quantum error correction
  • Sergey Bravyi, Cristopher Moore, Alexander Russell, Christopher Laumann, Andreas L√§uchli, Roderich Moessner, Antonello Scardicchio, and Shivaji Sondhi
    Random quantum satisfiability: statistical mechanics of disordered quantum optimization
    arXiv:0903.1904 and arXiv:0907.1297
  • Julia Kempe (invited talk)
    A quantum Lov√°sz Local Lemma


  • Marcin Pawlowski
    Information causality
  • Salman Beigi, Sergio Boixo, Matthew Elliot, and Stephanie Wehner
    Local quantum measurement and relativity imply quantum correlations
  • David Gross, Markus Mueller, Roger Colbeck, and Oscar Dahlsten
    All reversible dynamics in maximally non-local theories are trivial
  • Michael Wolf, David Perez-Garcia, and Carlos Fernandez
    Measurements incompatible in quantum theory cannot be measured jointly in any other no-signaling theory
  • Toby Cubitt, Jens Eisert, and Michael Wolf
    Laying the quantum and classical embedding problems to rest
  • Salman Beigi, Peter Shor, and John Watrous
    Quantum interactive proofs with short messages
    No paper found.
  • Scott Aaronson (invited talk)
    New evidence that quantum mechanics is hard to simulate on classical computers
    No paper found.
  • Julia Kempe and Oded Regev
    No strong parallel repetition with entangled and non-signaling provers
  • Toby Cubitt, Debbie Leung, William Matthews, and Andreas Winter
    Zero-error channel capacity and simulation assisted by non-local correlations
  • Jianxin Chen, Toby Cubitt, Aram Harrow, and Graeme Smith
    Super-duper-activation of the zero-error quantum capacity
    arXiv:0906.2547 and arXiv:0912.2737

On the Turing Away

“The miracle of the appropriateness of the language of mathematics for the formulation of the laws of physics is a wonderful gift which we neither understand nor deserve.”
E. P. Wigner

Our universe, or at least our understanding of the universe, appears to allow us to see its naked underbelly only through the use of mathematical reasoning. As Wigner says about this state of affairs, we neither understand nor deserve this. On the other hand, I’ve come to believe, this observation can also be a huge aid in describing the world of theoretical computer science. There is no doubt in most people’s opinion that theoretical computer science is mathematics of a highly sophisticated nature (or, well, sophisticated to this lowly physicist.) But theoretical computer science, unlike pure mathematics unfettered in its abstract glory, at its core must be concerned with the practical applicability of its reasoning. Here by practical I do not mean contributing to the better good of software development (though this may be important for the well being, read salary, of the practioners) but that at its core theoretical computer science must be about computers that exist in the real world. On the one hand, this observation leads direction to quantum computing. To paraphrase Feynman: the universe is quantum, damnit, so we better make our models of computing quantum. But it also should influence even our most basic classical computational models. In this vein, then, I would like to attack one of the most sacred holy cows of computer science, the holy mother cow of them all, the Turing machine.
Continue reading “On the Turing Away”

Rowers, Funding, Metropolis, and Equilibria

Stuff to read while you wait around for finals and the Christmas holidays:

Machine Learning Ruins Blackjack

Blackjack, or 21, is a game that many enjoy wasting their money playing at casinos. For those who don’t like to waste their money, or at least want to waste it more slowly than others, card counting is a time honored tradition for moving the odds away from the casino and in the players direction (blessed be Ed Thorp.) In other words it makes the game at least slightly enjoyable for those who like to win. But now a graduate of the University of Dundee, Kris Zutis, is going to ruin this small smidgen of fun:

A University of Dundee graduate has created a computer system with the potential to make the game of Blackjack fairer by detecting card counters and dealer errors.

Okay so catching dealer errors certainly makes the game “more fair.” But detecting card counters? People who are eking out a minor advantage (and have to be aware of methods to avoid detection because casinos can kick them out not because of card counting per se, but because the casinos run the game) by using their damn brains are not acting fair? To be fair, of course casinos are already doing this so we should be nice to the grad student 🙂
And further, of course all is fair in love, war, and casino games. But this makes me wonder about arbitrage in the era of machine learning, each machine vying to outdo the other in keeping their profits locked up tight. My high margin classifier just gave me 21, yipee! Oh wait, this is already happening on Wall Street. Remind me again about the market making and liquidy arguments for blackjack.

QIP 2010 and CSQ 2010

Two conferences. Renato Renner sends along a note about QIP 2010. The paper submission deadline is one month away:

QIP 2010 will be held in Zurich, Switzerland, January 18-22.
The submission deadline for contributed talks is 22 October 2009.
For more information, please see
We look forward to welcoming you to Zurich,
the organizers

Also a conference on superconducting qubits in San Diego:

Please note our conference coming next spring; Coherence in Superconducting Qubits, to be held April 25-28, 2010, in San Diego, CA.
The agenda and registration are described at

Zurich in winter, San Diego in spring…life must be good for the traveling postdoc.

Netflix Prize Awarded

The Netflix prize for movie rankings has been awarded with the winner being BellKor’s Pragmatic Chaos. This is very cool, but since it’s Monday I think we need a good dose of reality. So here is the first comment on the New York Times Bit blog:

This sounds like an interesting project, but they ought to emphasize acquiring more movies for their online streaming than telling people what to watch. – kt

Good work, BellKor’s Pragmatic Chaos, but could you work on that tube that delivers my potato chips without me having to get up to go to the kitchen?

Puzzle for the Day

How do you build a computer out of fire?
(Motivated by the observation that if you take three pieces of string and tie them together at a single point, you can make an OR gate. If we denote the presence of fire on a string as a 1 and the absence of fire as a 0, then this contraption clearly computes the OR function. But OR by itself is not universal.)

Help Rod With His Summer Reading

Rod Van Meter is in search of some summer reading:

I’m feeling the need to recharge my store of ideas, and I have the
nagging feeling that my lack of currency in a bunch of fields is
causing me to miss some connections I could use in my own research.
So, I’m looking for a reading list of, say, the one hundred most
important papers of the decade. It doesn’t have to be an even
hundred, but I’m looking for a good summer’s reading. (Given that
it’s mid-2009, now would be a good time to start composing such a list
anyway, depending on where you want to place the “decade” boundary.)
I want these papers to cover *ALL* fields of computer science and
engineering; I am by nature catholic in my reading.

Head over to his site and help out with your favorite gem of CS/engineering!


Today on the arXiv an new paper appeared of great significance to quantum computational complexity: arXiv:0907.4737 (vote for it on scirate here)

Authors: Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semidefinite programs that captures the computational power of quantum interactive proofs. As the containment of PSPACE in QIP follows immediately from the well-known equality IP = PSPACE, the equality QIP = PSPACE follows.

This solves a long standing open problem (we can say long standing in quantum computing when we mean less than nine years because our field is so young.) It has always been known that PSPACE is in QIP, but prior to this result (assuming its correct: I just downloaded the paper and am starting to read it now) the best known inclusion in the other direction was that QIP is in EXP (this result is due to Kitaev and Watrous.) But wait a second, what the hell are all these letters representing?
Continue reading “OMG QIP=PSPACE!”