Julia Kempe - Publications by topic

Quantum Algorithms: (Quantum Walks, Adiabatic Computation, Hidden Subgroup Problem):

• 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).
• 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
• 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)
• 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)
• Comment calculer quantique ( )
  Julia Kempe, Sophie Laplante, Frederic Magniez
  La Recherche, cover story, Vol. 398 (June), p. 30-37 (2006)
• 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)
• 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
• 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)
  full version in SIAM Journal of Computing, Vol. 37, Issue 1, p. 166-194 (2007) (special issue dedicated to selected FOCS'04 papers), lanl-report quant-ph/0405098
• Discrete Quantum Walks Hit Exponentially Faster ( , ,quant-ph)
  Julia Kempe
  Proc. 7th RANDOM, p. 354-69 (2003)
  full version in Probability Theory and Related Fields, Vol. 133 (2), p. 215-235 (2005), lanl-report quant-ph/0205083
• Quantum random walks - an introductory overview ( ,quant-ph)
  Julia Kempe
  Contemporary Physics, Vol. 44 (4), p.307-327 (2003), lanl-report quant-ph/0303081
• 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
• Quantum Walks on Graphs ( ,quant-ph)
  Andris Ambainis, Dorit Aharonov, Julia Kempe, Umesh Vazirani
  Proc. 33rd ACM STOC, p. 50-59 (2001), lanl-report quant-ph/0012090

Quantum Complexity Theory (QMA and Communication Complexity):

• 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)
• 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
• 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)
• 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
• 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
• 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
• 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)
  accepted to SIAM Journal of Computing (special issue dedicated to selected STOC'06 papers), lanl-report quant-ph/0511013
• Quantum Communication Cannot Simulate a Public Coin (quant-ph)
  Dmitry Gavinsky, Julia Kempe, Ronald de Wolf
  lanl-report quant-ph/0411051
• The Complexity of the Local Hamiltonian Problem ( , ,quant-ph)
  Julia Kempe, Alexei Kitaev, Oded Regev
  Proc. 24th FSTTCS, p. 372-383 (2004)
  full version in SIAM Journal of Computing, Vol. 35(5), p. 1070-1097 (2006), lanl-report quant-ph/0406180
• 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

Noise Protection and Universal Computation (DFS, Exchange-only Computation, Fault-tolerance, Universality):

• 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)
• 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
• 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
• 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
• 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
• 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
• Encoded Universality from a Single Physical Interaction (quant-ph)
  Julia Kempe, Dave Bacon, David DiVincenzo, K. Birgitta Whaley
  Quantum Information and Computation, invited to special issue, edited by R. Clark et al. (Rinton Press, New Jersey), Vol.1 (Special Issue), p. 33-55 (2001), lanl-report quant-ph/0112013
• 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
• 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
• 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

Entanglement and Quantum Information (Multipartite Entanglement, Quantum Coding, Cloning, Separability):

• 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"
• Robustness of Multiparty Entanglement (quant-ph)
  Christoph Simon, Julia Kempe
  Phys. Rev. A, Vol. 65 (5), 052327 (2002), lanl-report quant-ph/0109102
• 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
• 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
• 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

Other:

• Quantum information processing and communication
  Peter Zoller et al. (39 authors)
  Eur. Phys. Jour. D, Vol. 36, p. 203-228 (2005), Strategic report
• 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)

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

Theses:

• 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
• Self-organised criticality in sand dunes - a study
  Julia Kempe
  Master's project, DEA-Physique Theorique, Ecole Normale Superieure, Paris, June 1997
• Vers une decomposition equidimensionelle des varietes algebriques
  Kim Gerdes, Julia Kempe
  Master's Thesis, DEA-Algebre de l' Univ. de Paris 6, Ecole Polytechnique, Palaiseau, France, October 1996