Julia Kempe - Publications in reverse chronological order

Preprints:

• Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing ( ,quant-ph)
  Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf
  submitted, quant-ph/0802.1464 (2008)
• The Unique Games Conjecture with Entangled Provers is False ( ,quant-ph)
  Julia Kempe, Oded Regev, Ben Toner
  accepted as long contributed talk at QIP'08, submitted, quant-ph/0710.0655 (2007)
• Entangled games are hard to approximate ( ,quant-ph)
  Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick
  accepted as short contributed talk at QIP'08, submitted, quant-ph/0704.2903 (2007), among other things strengthens results from quant-ph/0612063
• Using Entanglement in Quantum Multi-Prover Interactive Proofs ( ,quant-ph)
  Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick
  to appear in Proc. 23rd CCC'08 (Complexity), accepted as long contributed talk at QIP'08, quant-ph/0711.3715 (2007)
• Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity ( )
  Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
  accepted to SIAM Journal of Computing (special issue dedicated to selected STOC'06 papers)
• Quantum Algorithms - Lecture Notes ( )
  Julia Kempe
  Summer School and Workshop on Theory and Technology in Quantum Information, Communication, Computation and Cryptography, ITP, Trieste, June (2006)

Published:

• Permutation groups, minimal degrees and quantum computing ( ,quant-ph)
  Julia Kempe, Laszlo Pyber, Aner Shalev
  Groups, Geometry, and Dynamics, Vol. 1 (4), p. 553-584 (2007), quant-ph/0607204 (2006)
• The power of quantum systems on the line ( , ,quant-ph)
  Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe
  Proc. 48th FOCS, p.373-383 (2007). Earlier 3-author version accepted as long contributed talk at QIP'07, full version submitted, quant-ph/0705.4077 (2007).
• Exponential separations for one-way quantum communication complexity, with applications to cryptography ( , ,quant-ph)
  Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf
  Proc. 39th STOC, p. 516-525 (2007), accepted as long contributed talk at QIP'07, full version submitted, quant-ph/0611209 (2006), supersedes Technical Report quant-ph/0607174
• Approaches to Quantum Error Correction ( ,quant-ph)
  Julia Kempe
  book chapter in Quantum Decoherence, Poincaré Seminar 2005, B. Duplantier, J.-M. Raimond and V. Rivasseau Editors, Progress in Mathematical Physics series, Birhäuser, p. 85--123, 2006, quant-ph/0612185
• Quantum Algorithms ( )
  Julia Kempe
  book chapter in Lecture Notes on Quantum Information, D. Bruss and G. Leuchs, Editors, Physics Textbook, Whiley-VCH, p. 87--102 (2006)
• Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation ( )
  Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev
  SIAM Journal of Computing, Vol. 37, Issue 1, p. 166-194 (2007) (special issue dedicated to selected FOCS'04 papers)
• Strengths and Weaknesses of Quantum Fingerprinting ( ,quant-ph)
  Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
  Proc. 21st CCC (Complexity), p. 288-295 (2006), lanl-report quant-ph/0603173
• Comment calculer quantique ( )
  Julia Kempe, Sophie Laplante, Frederic Magniez
  La Recherche, cover story, Vol. 398 (June), p. 30-37 (2006)
• Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity ( ,quant-ph)
  Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf
  Proc. 38th STOC, p. 594-603 (2006), invited to special issue dedicated to selected STOC'06 papers, accepted as long contributed talk at QIP'06, lanl-report quant-ph/0511013
• The Complexity of the Local Hamiltonian Problem ( )
  Julia Kempe, Alexei Kitaev, Oded Regev
  SIAM Journal of Computing, Vol. 35(5), p. 1070-1097 (2006)
• Fault-tolerant quantum computation - a dynamical systems approach ( ,quant-ph)
  Jesse Fern, Julia Kempe, Shankar Sastry
  IEEE Transactions on Automated Control, Vol. 51 (3), p. 448-459 (2006), lanl-report quant-ph/0409084
• Quantum information processing and communication
  Peter Zoller et al. (39 authors)
  Eur. Phys. Jour. D, Vol. 36, p. 203-228 (2005), Strategic report
• Discrete Quantum Walks Hit Exponentially Faster ( )
  Julia Kempe
  Probability Theory and Related Fields, Vol. 133 (2), p. 215-235 (2005)
• Full protection of superconducting qubit systems from coupling errors (quant-ph)
  Markus Storcz, Jiri Vala, Kenneth Brown, Julia Kempe, Simon Myrgren, K. Birgitta Whaley
  Phys. Rev. B, Vol. 72, 064511 (2005), lanl-report cond-mat/0407780
• Coins Make Quantum Walks Faster ( ,quant-ph)
  Andris Ambainis, Julia Kempe, Alexander Rivosh
  Proc. 16th ACM-SIAM SODA, p. 1099-1108 (2005), lanl-report quant-ph/0402107
• The hidden subgroup problem and permutation group theory ( ,quant-ph)
  Julia Kempe, Aner Shalev
  Proc. 16th ACM-SIAM SODA, p. 1118-1125 (2005), lanl-report quant-ph/0406046
• The Complexity of the Local Hamiltonian Problem ( ,quant-ph)
  Julia Kempe, Alexei Kitaev, Oded Regev
  Proc. 24th FSTTCS, p. 372-383 (2004), lanl-report quant-ph/0406180
• Quantum Advantage in Transmitting a Permutation ( ,quant-ph)
  Joshua von Korff, Julia Kempe
  Phys. Rev. Lett., Vol. 93 (46), 260502 (2004), lanl-report quant-ph/0405086, previous title: "Quantum Color Coding is Better"
• Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation ( ,quant-ph)
  Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev
  Proc. 45th FOCS, p. 42-51 (2004), invited to special issue dedicated to selected FOCS'04 papers, lanl-report quant-ph/0405098
• An explicit universal gate-set for exchange-only quantum computation (quant-ph)
  Michael Hsieh, Julia Kempe, Simon Myrgren, K. Birgitta Whaley
  Quantum Information Processing, Vol. 2 (4),p. 289-307, (2003), lanl-report quant-ph/0309002
• Quantum random walks - an introductory overview ( ,quant-ph)
  Julia Kempe
  Contemporary Physics, Vol. 44 (4), p.307-327 (2003), lanl-report quant-ph/0303081
• 3-Local Hamiltonian is QMA-complete ( ,quant-ph)
  Julia Kempe, Oded Regev
  Quantum Information and Computation, Vol. 3(3), p.258-64 (2003), lanl report quant-ph/0302079
• Discrete Quantum Walks Hit Exponentially Faster ( ,quant-ph)
  Julia Kempe
  Proc. 7th RANDOM, p. 354-69 (2003), lanl-report quant-ph/0205083
• Quantum Random-Walk Search Algorithm (quant-ph)
  Neil Shenvi, Julia Kempe, K. Birgitta Whaley
  Phys. Rev. A, Vol. 67 (5), 052307 (2003), lanl-report quant-ph/0210064
• Exact gate-sequences for universal quantum computation using the XY-interaction alone (quant-ph)
  Julia Kempe, K. Birgitta Whaley
  Phys. Rev. A, Vol. 65 (5), 052330 (2002), lanl-report quant-ph/0112014
• Robustness of Multiparty Entanglement (quant-ph)
  Christoph Simon, Julia Kempe
  Phys. Rev. A, Vol. 65 (5), 052327 (2002), lanl-report quant-ph/0109102
• Encoded Universality from a Single Physical Interaction (quant-ph)
  Julia Kempe, Dave Bacon, David DiVincenzo, K. Birgitta Whaley
  invited paper for special issue of Quantum Information and Computation, edited by R. Clark et al. (Rinton Press, New Jersey), Vol.1 (Special Issue), p. 33-55 (2001), lanl-report quant-ph/0112013
• Universal Noiseless Quantum Computation: Theory and Applications (psgz)
  Julia Kempe
  PhD-thesis, Mathematics, UC Berkeley, December 2001
• Calcul Quantique: Marches Aleatoires et Etude d'Enchevetrement (psgz)
  Julia Kempe
  PhD-thesis, Computer Science, Ecole Nationale Superieure des Telecommunications, Paris, April 2001
  the version above is in English, here is the original: English with French Intro
• Encoded Universality in Physical Implementations of a Quantum Computer (quant-ph)
  Dave Bacon, Julia Kempe, Daniel Lidar, K. Birgitta Whaley, David DiVincenzo
  Proc. IQC (Intern. Conference on Experimental Implementation of Quantum Computation), p. 257-262 (2001), Sydney, Australia, lanl-report quant-ph/0102140
• Separable States are more disordered globally than locally ( ,quant-ph)
  Michael Nielsen, Julia Kempe
  Phys. Rev. Lett., Vol. 86, 5184-7 (2001), lanl-report quant-ph/0011117
• Quantum Walks on Graphs ( ,quant-ph)
  Andris Ambainis, Dorit Aharonov, Julia Kempe, Umesh Vazirani
  Proc. 33rd STOC, p. 50-59 (2001), lanl-report quant-ph/0012090
• Universal Simulation of Markovian Quantum Dynamics (quant-ph)
  Dave Bacon, Andrew Childs, Isaac Chuang, Julia Kempe, Debbie Leung, Xinlan Zhou
  Phys. Rev. A, Vol. 64, 062302 (2001), lanl-report quant-ph/0008070
• Decoherence-Free Subspaces for Multiple-Qubit Errors: (II) Universal, Fault-Tolerant Quantum Computation (quant-ph)
  Daniel Lidar, Dave Bacon, Julia Kempe, K. Birgitta Whaley
  Phys. Rev. A, Vol 63 (2), 022307 (2001), lanl-report quant-ph/0007013
• Decoherence-Free Subspaces for Multiple-Qubit Errors: (I) Characterization (quant-ph)
  Daniel Lidar, Dave Bacon, Julia Kempe, K. Birgitta Whaley
  Phys. Rev. A, Vol 63 (2), 022306 (2001), lanl-report quant-ph/9908064
• Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation ( ,quant-ph)
  Julia Kempe, Dave Bacon, Daniel Lidar, K. Birgitta Whaley
  Phys. Rev. A, Vol. 63 (4), 042307 (2001), lanl-report quant-ph/0004064
• Universal Quantum Computation with the Exchange Interaction ( ,quant-ph)
  David DiVincenzo, Dave Bacon, Julia Kempe, Guido Burkard, K. Birgitta Whaley
  NATURE, Vol. 408, p. 339-342 (2000), lanl-report quant-ph/0005116
• Lambda's, V's and optimal cloning with stimulated emission (quant-ph)
  Julia Kempe, Christoph Simon, Gregor Weihs
  Phys. Rev. A, Vol. 62 (3), 032302 (2000), lanl-report quant-ph/0003025
• Universal Fault Tolerant Quantum Computation on Decoherence-Free Subspaces ( ,quant-ph)
  Dave Bacon, Julia Kempe, Daniel Lidar, K. Birgitta Whaley
  Phys. Rev. Lett. , Vol. 85 (8), p. 1758-61 (2000), lanl-report quant-ph/9909058
• Protecting Quantum Information Encoded in Decoherence Free States Against Exchange Errors (quant-ph)
  Daniel Lidar, Dave Bacon, Julia Kempe, K. Birgitta Whaley
  Phys. Rev. A Vol. 61 (5), p.52307 (2000), lanl-report quant-ph/9907096
• Multipartite entanglement and its applications to cryptography (quant-ph)
  Julia Kempe
  Phys. Rev. A, Vol. 60 (2), p. 910-916 (1999), lanl-report quant-ph/9902036
• New Transform Techniques Applied to Anomalous Absorption in the Dense Chain of Metal Cylinders
  Julia Kempe, Alex Radchik, Geoff Smith
  Proc. Roy. Soc. A, Vol. 452, p. 1845-1856 (1996)

Technical Reports:

• On the power of entangled quantum provers ( ,quant-ph)
  Julia Kempe, Thomas Vidick
  contains a subset of the results in quant-ph/0704.2903 but proved in a very different way, contains "nearly-commuting versus almost-commuting" conjecture, quant-ph/0612063 (2006)
• The power of quantum systems on the line ( ,quant-ph)
  Dorit Aharonov, Daniel Gottesman, Julia Kempe
  accepted as long contributed talk at QIP'07, quant-ph/0705.4077 v1 (2007), subsumed by merged version with same title and one more co-author
• Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function ( ,quant-ph)
  Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
  quant-ph/0607174, ECCC TR06-086 (2006), Technical Report, superseded by "Exponential separations for one-way quantum communication complexity, with applications to cryptography" with two more co-authors
• Quantum Communication Cannot Simulate a Public Coin (quant-ph)
  Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
  lanl-report quant-ph/0411051, most results absorbed in later papers "Strengths and Weaknesses of Quantum Fingerprinting" and "Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity"

Press Releases:

• Haven for Quantum Computation
  Science Vol.289 issue 5484 (click here if you do not have subsciption)
• Alternative quantum bits go natural
  Technology Research News, April 2001

Patent:

• Universal Quantum Computation with the Exchange Interaction
  Dave Bacon, Julia Kempe, Daniel Lidar, K. Birgitta Whaley
  US Patent Number 7,184,555; 27 February 2007