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

New comments have been temporarily disabled. Please check back soon.