Julia Kempe - Selected Publications#

1. D.P. DiVincenzo, D. Bacon, J. Kempe, G. Burkard, K.B. Whaley: “Universal Quantum Computation with the Exchange Interaction”, NATURE Vol. 408, p. 339-342 (2000), based on J. Kempe, D. Bacon, D. Lidar, K.B. Whaley: “Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation”, Phys. Rev. A, Vol. 63(4), 042307-1–29 (2001) and expanded in J. Kempe, D. Ba- con, D. P. DiVincenzo, K.B. Whaley: ”Encoded Universality from a Single Physical Interaction”, in Special Issue of Quantum Information and Computation, edited by R. Clark et al. (Rinton Press, New Jersey), p. 33-55 (2001)

2. N. Shenvi, J.Kempe, K.B. Whaley: “A Quantum Random Walk Search Algorithm”, Phys. Rev. A, Vol. 67 (5), 052307-1–11 (2003)

3. J. Kempe: ”Discrete Quantum Walks Hit Exponentially Faster”, Proceedings of RANDOM’03, p. 354-69 (2003), also elaborated in J. Kempe: “Quantum random walks - an introductory overview”, Contemporary Physics, Vol. 44(4), p. 307-27 (2003)

4. D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani: “Quantum Walks on Graphs”, Proceedings of 33rd ACM Symposium on Theory of Computation (STOC), p. 50-59 (2001)

5. J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner and T. Vidick:“Entangled games are hard to approximate”, SIAM J. Comp., Vol. 40(3), p. 848-877 (2011), preliminary version in Proc. 49th FOCS’08, p. 447-456 (2008), invited to special issue of SICOMP dedicated to selected FOCS’08 papers, also accepted as contributed short talk to QIP’08

6. D. Aharonov, D. Gottesman, S. Irani and J. Kempe:“The power of quantum systems on the line”, Comm. Math. Phys., Vol. 287(1), p. 41-65 (2009), journal version of Proc. 48th FOCS, p. 373-383 (2007), accepted as long talk to QIP’07

7. D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, O. Regev, ”Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation”, SIAM Review, issue 50-4, p. 755–787, December 2008, SIAM Journal of Computing, Vol. 37, Issue 1, p. 164-196 (2007), preliminary version in Proc. 45th FOCS, p. 42-51 (2004), invited to special issue of SICOMP dedicated to selected FOCS’04 papers

8. D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf: ”Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity”, SIAM Journal of Computing, Vol. 39 (1), p.1-24 (2009), journal version of Proc. 38th STOC, p. 594-603 (2006), invited to special issue of SICOMP dedicated to selected STOC’06 papers, also accepted as long contributed talk at QIP’06

9. J. Kempe, A. Kitaev and O. Regev: ”The Complexity of the Local Hamiltonian Problem”, SIAM Journal of Computing, Vol. 35(5), p. 1070-1097 (2006), journal version of Proc. 24th Found. Software Tech. and Theoretical Computer Science (FSTTCS), p. 372-383 (2004), invited to QIP’04

10. J.Kempe: ”Multiparticle entanglement and its applications to cryptography”, Phys. Rev. A Vol. 60 (2), p. 910-916 (1999)