The Quantum Pontiff

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


  1. #1 David
    January 15, 2010

    Don’t be too hard on Aaronson. It’s going to be a challenge to find anything on the arXiv from him until they start accepting powerpoint as a native upload.

  2. #2 Ian Durham
    January 15, 2010

    > also interesting how papers seem to cluster in the 10-12
    > months of the listings

    I think there’s a policy about that. Oh, wait, maybe that’s what the emoticon was for. I’m dense.

  3. #3 John Sidles
    January 18, 2010

    Dave, thank you for this fantastic list!

    I have looked at a fair proportion of those preprints, of which my favorite (so far) is the Corboz/Orus/Bauer/Vidal preprint Simulation of strongly correlated fermions in two spatial dimensions with fermionic Projected Entangled-Pair States.

    The Corboz preprint had a very different “look-and-feel” to the other preprints … and it made me laugh when I realized why … it is that the Corboz et al. preprint does *not* contain the word “theorem” anywhere … whereas the other QIP2010 preprints (that I looked at) all were theorem-centric. :)

    Should we regard this as evidence that QIP perhaps will *not* evolve into a theorem-proving monoculture, along the lines of FOCS/STOC? After all, nowadays rather few practicing software engineers care to attend FOCS/STOC … perhaps this is because “a very great deal more truth can become known than can be proven”?

    On the other hand, a rigorous emphasis on theorem-proving might be the *best* course for QIP. After all, FOCS/STOC is an outstandingly successful academic culture.

    Dave, you’re on the QIP Program Committee … what is the thinking on this? Balancing rigor-versus-vigor must have been pretty challenging.

  4. #4 Frédéric Grosshans
    January 19, 2010

    You can also probably add for David Gross’s Today’s talk : I think it’s the one he called on his slides

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.