QIP 2013 accepts

****Edit 11/23****

Plenary talks have now been posted. Talks that were not already among the list of accepted papers (see below) are:

• Ronald de Wolf (based on joint work with S. Fironi, S. Massar, S. Pokutta, H. Tiwary), “Lower bounds for combinatorial polytopes, inspired by quantum communication complexity”
• David DiVincenzo, “Prospects for Superconducting Qubits”.
• Ben Reichardt (based on joint work with F. Unger, U. Vazirani), “A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games”.
• Thomas Vidick (based on joint work with T. Ito), “A multi-prover interactive proof for NEXP sound against entangled provers”
• Liang Jiang, “Majorana Fermions and Topological Quantum Information Processing.”

These are quite a nice boost to the program! The first paper has been around for some time now, and it is a beautiful result. The connection with quantum information is somewhat tenuous but it has the merit of illustrating how techniques from our field can lead to advances in unexpected areas, a growing phenomenon in TCS (see the survey, this recent work on SDP hierarchies, advances in efficient SDP solvers, or my own shameless self-promotion, which came out of work on quantum XOR games). I won’t repeat how beautiful I think the second paper, by Reichardt et al., is. And I can’t say I know much about the last, but that’s one of the main points of QIP: a broad spectrum of talks and lectures, in single-track, that (somewhat ) forces one to pay attention to exciting advances from all areas of quantum information.

****End edit****

Next QIP‘s list of accepted papers is out (though we are still left waiting for the list of invited talks ). I counted 36 accepts, including 2 merged talks, so 38 papers total. That’s about the same, maybe even a bit fewer, as last year: excluding plenary lectures, there were 37 talks; presumably some of this year’s 36 accepts will also be plenaries.

(In related news, Yaoyun Shi reminds us that the deadline to apply for student and postdoc travel grants is very soon: November 15th. No need to have an accepted paper to apply!)

Below is a very roughly categorized list of accepts (sorry for the miscategorizations — some of the papers clearly should be in more than one category, or have a category of their own), with links when I could find them.

Anyone exited? My personal favorites would include the Brandao/Harrow result on a new de Finetti theorem, the beautiful paper by Kerenidis and co-authors on zero-error communication complexity, Carlos Palazuelos’ paper on super-activation of nonlocality, the Childs et al. paper on universal computation by quantum walks, the Li/Winter paper on  squashed entanglement, the excellent paper by Kastoryano and my colleague Kristan Temme on quantum log-Sobolev inequalitites…and, last but not least, the papers from our new  “thermodynamics” category! That’s more than enough to justify a trip to Beijing (not that such a trip would need any justification), and I hope many of us will be there.

Ground states of local Hamiltonians

• Fernando Brandao and Michal Horodecki, “Exponential Decay of Correlations Implies Area Law.”
• Zeph Landau, Umesh Vazirani, Itai Arad, and Alexei Kitaev, “An area law and sub-exponential algorithm for 1D systems.”
• Fernando Brandao and Aram Harrow, “Approximation Guarantees for the Quantum Local Hamiltonian Problem and Limitations for Quantum PCPs.”
• Norbert Schuch, Didier Poilblanc, Ignacio Cirac, and David Perez-Garcia, “Resonating valence bond states in the PEPS formalism.”

Cryptography

• Umesh Vazirani and Thomas Vidick, “Fully device independent quantum key distribution.”
• Harry Buhrman, Matthias Christandl, and Christian Schaffner, “Complete Insecurity of Quantum Protocols for Classical Two-Party Computation.”
• Jonathan Barrett, Roger Colbeck, and Adrian Kent, “Unconditionally secure device-independent quantum key distribution with only two devices.”

Nonlocality

• Rodrigo Gallego, Lluis Masanes, Gonzalo de La Torre, Chirag Dhara, Leandro Aolita, and Antonio Acin, “Full randomness from arbitrarily deterministic events.”
• Tom Cooney, Marius Junge, Carlos Palazuelos, David Perez-Garcia, Oded Regev, and Thomas Vidick, “Rank-one and Quantum XOR games.”
• Carlos Palazuelos, “Super-activation of quantum nonlocality.”
• Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jeremie Roland, and David Xiao, “Bell tests and applications to communication and information complexity.” (maybe also this paper?)
• Michael Walter, Brent Doran, David Gross, and Matthias Christandl, “Entanglement Polytopes.”
• Eric Chitambar, Debbie Leung, Laura Mancinska, Maris Ozols, and Andreas Winter, “Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask).”

Topological computing and error-correcting codes

• Sergey Bravyi and Robert Koenig, “Classification of topologically protected gates for local stabilizer codes.”
• Kamil Michnicki, “Topological stabilizer codes with a power law energy barrier via welding.”
• Dominic Else, Stephen Bartlett, and Andrew Doherty, “Symmetry protection of measurement-based quantum computation in ground states.”
• Olivier Landon-Cardinal and David Poulin, “Local topological order inhibits thermal stability in 2D.”

Algorithms and query complexity

• Stephen Jordan, Keith Lee, and John Preskill, “Quantum Algorithms for Quantum Field Theories.”
• Aleksandrs Belovs and Robert Spalek, “Adversary Lower Bound for the k-sum Problem.”
• Andrew Childs, David Gosset, and Zachary Webb, “Universal computation by multi-particle quantum walk.”
• Troy Lee, Frederic Magniez, and Miklos Santha, “Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing.”
• Aleksandrs Belovs, “Learning-Graph-Based Quantum Algorithm for k-distinctness.”
• Victor Veitch, Chris Ferrie, David Gross, and Joseph Emerson, “Negative Quasi-Probability as a Resource for Quantum Computation.”

Information theory

• Ashley Montanaro, “Weak multiplicativity for random quantum channels.”
• Robert Koenig and Graeme Smith, “Limits on classical communication from quantum entropy power inequalities.”
• Michael Kastoryano and Kristan Temme, “Quantum logorithmic Sobolev inequalities and rapid mixing.”
• Ke Li and Andreas Winter, “Relative entropy and squashed entanglement.”
• Matthias Christandl, Mehmet Burak Sahinoglu, and Michael Walter, “Recoupling Coefficients and Quantum Entropies.”
• Oleg Szehr, David Reeb, and Michael Wolf, “Spectral Bounds on the Convergence of Classical and Quantum Markov Chains.” (an extension of this paper?)
• William Matthews and Stephanie Wehner, “Finite blocklength converse bounds for quantum channels.”
• Marco Tomamichel and Masahito Hayashi, “A Hierarchy of Information Quantities for the Finite Block Length Analysis of Quantum Tasks”; and Ke Li, “Second Order Asymptotics for Quantum Hypothesis Testing.” (Merged talk)
• Patrick Hayden and Alex May, “Summoning Information in Spacetime, or Where and When Can a Qubit Be?”

Complexity

• Hirotada Kobayashi, Francois Le Gall, and Harumichi Nishimura, “Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete”; and Stephen Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura, “Achieving Perfect Completeness in Classical-Witness Quantum Merlin-Arthur Proof Systems.” (Merged talk)
• Fernando Brandao and Aram Harrow, “Quantum de Finetti Theorems under Local Measurements with Applications.”

Thermodynamics

• Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim, “Quantum Refrigerator.”
• Michal Horodecki and Jonathan Oppenheim, “Fundamental limitations for quantum and nano thermodynamics.”