This Thanksgiving, even if we can’t all be fortunate enough to be presenting a talk at QIP, we can be thankful for being part of a vibrant research community with so many different lines of work going on. The QIP 2014 accepted talks are now posted with 36 out of 222 accepted. While many of the hot topics of yesteryear (hidden subgroup problem, capacity of the depolarizing channel) have fallen by the wayside, there is still good work happening in the old core topics (algorithms, information theory, complexity, coding, Bell inequalities) and in topics that have moved into the mainstream (untrusted devices, topological order, Hamiltonian complexity).
Here is a list of talks, loosely categorized by topic (inspired by Thomas’s list from last year). I’m pretty sad about missing my first QIP since I joined the field, because its unusually late timing overlaps the first week of the semester at MIT. But in advance of the talks, I’ll write a few words (in italics) about what I would be excited about hearing if I were there.
Quantum Shannon Theory
There are a lot of new entropies! Some of these may be useful – at first for tackling strong converses, but eventually maybe for other applications as well. Others may, well, just contribute to the entropy of the universe. The bounds on entanglement rate of Hamiltonians are exciting, and looking at them, I wonder why it took so long for us to find them.
1a. A new quantum generalization of the Rényi divergence with applications to the strong converse in quantum channel coding
Frédéric Dupuis, Serge Fehr, Martin Müller-Lennert, Oleg Szehr, Marco Tomamichel, Mark Wilde, Andreas Winter and Dong Yang. 1306.3142 1306.1586
merged with
1b. Quantum hypothesis testing and the operational interpretation of the quantum Renyi divergences
Milan Mosonyi and Tomohiro Ogawa. 1309.3228
25. Zero-error source-channel coding with entanglement
Jop Briet, Harry Buhrman, Monique Laurent, Teresa Piovesan and Giannicola Scarpa. 1308.4283
28. Bound entangled states with secret key and their classical counterpart
Maris Ozols, Graeme Smith and John A. Smolin. 1305.0848
It’s funny how bound key is a topic for quant-ph, even though it is something that is in principle purely a classical question. I think this probably is because of Charlie’s influence. (Note that this particular paper is mostly quantum.)
3a. Entanglement rates and area laws
Michaël Mariën, Karel Van Acoleyen and Frank Verstraete. 1304.5931 (This one could also be put in the condensed-matter category.)
merged with
3b. Quantum skew divergence
Koenraad Audenaert. 1304.5935
22. Quantum subdivision capacities and continuous-time quantum coding
Alexander Müller-Hermes, David Reeb and Michael Wolf. 1310.2856
Quantum Algorithms
This first paper is something I tried (unsuccessfully, needless to say) to disprove for a long time. I still think that this paper contains yet-undigested clues about the difficulties of non-FT simulations.
2a. Exponential improvement in precision for Hamiltonian-evolution simulation
Dominic Berry, Richard Cleve and Rolando Somma. 1308.5424
merged with
2b. Quantum simulation of sparse Hamiltonians and continuous queries with optimal error dependence
Andrew Childs and Robin Kothari.
update: The papers appear now to be merged. The joint (five-author) paper is 1312.1414.
35. Nested quantum walk
Andrew Childs, Stacey Jeffery, Robin Kothari and Frederic Magniez.
(not sure about arxiv # – maybe this is a generalization of 1302.7316?)
Quantum games: from Bell inequalities to Tsirelson inequalities
It is interesting how the first generation of quantum information results is about showing the power of entanglement, and now we are all trying to limit the power of entanglement. These papers are, in a sense, about toy problems. But I think the math of Tsirelson-type inequalities is going to be important in the future. For example, the monogamy bounds that I’ve recently become obsessed with can be seen as upper bounds on the entangled value of symmetrized games.
4a. Binary constraint system games and locally commutative reductions
Zhengfeng Ji. 1310.3794
merged with
4b. Characterization of binary constraint system games
Richard Cleve and Rajat Mittal. 1209.2729
20. A parallel repetition theorem for entangled projection games
Irit Dinur, David Steurer and Thomas Vidick. 1310.4113
33. Parallel repetition of entangled games with exponential decay via the superposed information cost
André Chailloux and Giannicola Scarpa. 1310.7787
Untrusted randomness generation
Somehow self-testing has exploded! There is a lot of information theory here, but the convex geometry of conditional probability distributions also is relevant, and it will be interesting to see more connections here in the future.
5a. Self-testing quantum dice certified by an uncertainty principle
Carl Miller and Yaoyun Shi.
merged with
5b. Robust device-independent randomness amplification from any min-entropy source
Kai-Min Chung, Yaoyun Shi and Xiaodi Wu.
19. Infinite randomness expansion and amplification with a constant number of devices
Matthew Coudron and Henry Yuen. 1310.6755
29. Robust device-independent randomness amplification with few devices
Fernando Brandao, Ravishankar Ramanathan, Andrzej Grudka, Karol Horodecki, Michal Horodecki and Pawel Horodecki. 1310.4544
The fuzzy area between quantum complexity theory, quantum algorithms and classical simulation of quantum systems. (But not Hamiltonian complexity.)
I had a bit of trouble categorizing these, and also in deciding how surprising I should find each of the results. I am also somewhat embarrassed about still not really knowing exactly what a quantum double is.
6. Quantum interactive proofs and the complexity of entanglement detection
Kevin Milner, Gus Gutoski, Patrick Hayden and Mark Wilde. 1308.5788
7. Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups
Hari Krovi and Alexander Russell. 1210.1550
16. Purifications of multipartite states: limitations and constructive methods
Gemma De Las Cuevas, Norbert Schuch, David Pérez-García and J. Ignacio Cirac.
Hamiltonian complexity started as a branch of quantum complexity theory but by now has mostly devoured its host
A lot of exciting results. The poly-time algorithm for 1D Hamiltonians appears not quite ready for practice yet, but I think it is close. The Cubitt-Montanaro classification theorem brings new focus to transverse-field Ising, and to the weird world of stoquastic Hamiltonians (along which lines I think the strengths of stoquastic adiabatic evolution deserve more attention). The other papers each do more or less what we expect, but introduce a lot of technical tools that will likely see more use in the coming years.
13. A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
Zeph Landau, Umesh Vazirani and Thomas Vidick. 1307.5143
15. Classification of the complexity of local Hamiltonian problems
Toby Cubitt and Ashley Montanaro. 1311.3161
30. Undecidability of the spectral gap
Toby Cubitt, David Pérez-García and Michael Wolf.
23. The Bose-Hubbard model is QMA-complete
Andrew M. Childs, David Gosset and Zak Webb. 1311.3297
24. Quantum 3-SAT is QMA1-complete
David Gosset and Daniel Nagaj. 1302.0290
26. Quantum locally testable codes
Dorit Aharonov and Lior Eldar. (also QECC) 1310.5664
Codes with spatially local generators aka topological order aka quantum Kitaev theory
If a theorist is going to make some awesome contribution to building a quantum computer, it will probably be via this category. Yoshida’s paper is very exciting, although I think the big breakthroughs here were in Haah’s still underappreciated masterpiece. Kim’s work gives operational meaning to the topological entanglement entropy, a quantity I had always viewed with perhaps undeserved skepticism. It too was partially anticipated by an earlier paper, by Osborne.
8. Classical and quantum fractal code
Beni Yoshida. I think this title is a QIP-friendly rebranding of 1302.6248
21. Long-range entanglement is necessary for a topological storage of information
Isaac Kim. 1304.3925
Bit commitment is still impossible (sorry Horace Yuen) but information-theoretic two-party crypto is alive and well
The math in this area is getting nicer, and the protocols more realistic. The most unrealistic thing about two-party crypto is probably the idea that it would ever be used, when people either don’t care about security or don’t even trust NIST not to be a tool of the NSA.
10. Entanglement sampling and applications
Frédéric Dupuis, Omar Fawzi and Stephanie Wehner. 1305.1316
36. Single-shot security for one-time memories in the isolated qubits model
Yi-Kai Liu. 1304.5007
Communication complexity
It is interesting how quantum and classical techniques are not so far apart for many of these problems, in part because classical TCS is approaching so many problem using norms, SDPs, Banach spaces, random matrices, etc.
12. Efficient quantum protocols for XOR functions
Shengyu Zhang. 1307.6738
9. Noisy Interactive quantum communication
Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette and Falk Unger. 1309.2643 (also info th / coding)
Foundations
I hate to be a Philistine, but I wonder what disaster would befall us if there WERE a psi-epistemic model that worked. Apart from being able to prove false statements. Maybe a commenter can help?
14. No psi-epistemic model can explain the indistinguishability of quantum states
Eric Cavalcanti, Jonathan Barrett, Raymond Lal and Owen Maroney. 1310.8302
??? but it’s from THE RAT
update: A source on the PC says that this is an intriguing mixture of foundations and Bell inequalities, again in the “Tsirelson regime” of exploring the boundary between quantum and non-signaling.
17. Almost quantum
Miguel Navascues, Yelena Guryanova, Matty Hoban and Antonio Acín.
FTQC/QECC/papers Kalai should read 🙂
I love the part where Daniel promises not to cheat. Even though I am not actively researching in this area, I think the race between surface codes and concatenated codes is pretty exciting.
18. What is the overhead required for fault-tolerant quantum computation?
Daniel Gottesman. 1310.2984
27. Universal fault-tolerant quantum computation with only transversal gates and error correction
Adam Paetznick and Ben Reichardt. 1304.3709
Once we equilibrate, we will still spend a fraction of our time discussing thermodynamics and quantum Markov chains
I love just how diverse and deep this category is. There are many specific questions that would be great to know about, and the fact that big general questions are still being solved is a sign of how far we still have to go. I enjoyed seeing the Brown-Fawzi paper solve problems that stumped me in my earlier work on the subject, and I was also impressed by the Cubitt et al paper being able to make a new and basic statement about classical Markov chains. The other two made me happy through their “the more entropies the better” approach to the world.
31. An improved Landauer Principle with finite-size corrections and applications to statistical physics
David Reeb and Michael M. Wolf. 1306.4352
32. The second laws of quantum thermodynamics
Fernando Brandao, Michal Horodecki, Jonathan Oppenheim, Nelly Ng and Stephanie Wehner. 1305.5278
34. Decoupling with random quantum circuits
Winton Brown and Omar Fawzi. 1307.0632
11. Stability of local quantum dissipative systems
Toby Cubitt, Angelo Lucia, Spyridon Michalakis and David Pérez-García. 1303.4744
“I hate to be a Philistine, but I wonder what disaster would befall us if there WERE a psi-epistemic model that worked. Apart from being able to prove false statements. Maybe a commenter can help?”
Nothing would be wrong if there were a psi-epsitemic model that worked, it is rather the opposite conclusion which is surprising. If we can prove the reality of the wavefunction then we get a lot of other results immediately as corollaries, e.g. Bell’s theorem, the fact that the ontic state space must be infinite, and the fact that the number of parameters required to specify the ontic state must scale exponentially with the number of qubits. These corollaries have each been used to prove things in quantum information, e.g. security proofs for cryptography from Bell’s theorem and results in communication complexity for both Bell’s theorem and size of ontic state space bounds. Since the reality of the wavefunction implies these results, morally it ought to have applications in quantum information that go beyond those of its corollaries, although I don’t know what those are yet.
The problem with existing results showing the reality of the wavefunction is that they employ auxiliary assumptions, of varying degrees of reasonableness, but it is not natural to port those assumptions over to the quantum information context. Therefore, it is important to figure out whether we can rule out psi-epsitemic models via some stronger criteria for what a psi-epistemic model means without employing such assumptions. The QIP paper of Barrett et. al. is one attempt to do this. Their result does not imply all of the same things as the reality of the wavefunction would, i.e. it does not obviously place constraints on the size of the ontic state space, but it does imply some of them like Bell’s theorem. The reason I think it is important to present such results at QIP, apart from maintaining the historical ties between quantum foundations and quantum information, is that someone needs to figure out the practical consequences of these stronger than Bell no-go theorems.
Aram, in regard to the concluding QIP-accepted paper, by Toby Cubitt, Angelo Lucia, Spyridon Michalakis and David Pérez-García, “[**Stability of local quantum dissipative systems**](http://arxiv.org/abs/1303.4744)” (arXiv:1303.4744, 2013), note that the Glauber states discussed by Cubitt *et al* are precisely the Veronese/Glauber varieties \(\mathbb{G}\) of the question that you and I have been discussing on MathOverflow (namely, “Do quantum “Sure-Shor separators” have a natural Veronese/Segre classification?”), and in particular the higher-order secant joining of these varietal state-spaces is governed (AFAICT) by more-or-less the same physical principles that Cubitt *et al* discuss … thus perhaps some of your concerns regarding the physical/thermodynamica/causal realism of dynamical models of the Kalai Postulates are addressed by the Cubitt et al theorems.
Glauber states? Glauber varieties? I only see a discussion of Glauber dynamics in that paper. I also don’t see where that paper works with any alternate theories of quantum mechanics.
The session for Hamiltonian complexity is gonna be exciting.
Thanks for going to the work of preparing this list. Quite a few merged submissions — I wonder what that says about the research directions taken by the QIP community this year… By the way, as you identified, the ordering of the names on my paper with Toby should really be reversed, corresponding to the alphabetically ordered arXiv paper.
Author ordering fixed.
It’s a good question whether we have too much of a pack mentality. The merging might also reflect the PC not wanting to say no to papers, or not wanting to decide between papers of comparable quality.
Right. In any case, I think the possibility of merging papers is a nice feature of QIP as compared with other conferences.
16 percent? Ouch that’s almos as bad as NSF funding rates 🙁
30 has a great title, would love to see the paper. In the meantime I’m having fun trying to figure out how one might get undecidability in a problem about the spectral gap. Maybe the problem with no guidance on the spectrum?
One thing they use is the the high-order bits of precision in the terms of the local Hamiltonian. You might think that they make connections with Wang tiles and other such things, but the result they get can’t really be obtained with those tools. IIRC, they use qudits with 2-local couplings on a square grid, with only two types of couplings, one for the horizontal edges and one for the vertical edges. But the qudit dimension is very high; Toby told me it is “at least 10^6” at the time (that was a year ago, and it might have changed).
Regarding the “Nested” paper, Robin Kothari’s homepage (http://www.robinkothari.com/) explains that it’s a merge of two papers.