A Quantum Lovasz Local Lemma (2009)
Ambainis, Andris, Kempe, Julia, Sattath, Or
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the...
No Strong Parallel Repetition with Entangled and Non-signaling Provers (2009)
We consider one-round games between a classical verifier and two provers. One of the main questions in this area is the \emph{parallel repetition question}: If the game is played $\ell$ times in...
Dmitry Gavinsky, Iordanis Kerenidis, Julia Kempe, Ran Raz, Ronald De Wolf
separations for one-way quantum communication
Jesse Fern, Julia Kempe, Slobodan N. Simić, Shankar Sastry
quantum computation a dynamical systems approach
Generalized Performance of Concatenated Quantum Codes—A Dynamical Systems Approach (2008)
Jesse Fern, Julia Kempe, Slobodan N. Simić, Shankar Sastry
Abstract—We apply a dynamical systems approach to concatenation of quantum error correcting codes, extending and generalizing the results of Rahn et al. to both diagonal and nondiagonal channels....
Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing (2008)
Kempe, Julia, Regev, Oded, Unger, Falk, De Wolf, Ronald
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of...
Dmitry Gavinsky, Iordanis Kerenidis, Julia Kempe, Ran Raz, Ronald De Wolf
separation for one-way quantum communication
Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing (2008)
Julia Kempe, Oded Regev, Falk Unger, Ronald Wolf
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of...
The Unique Games Conjecture with Entangled Provers is False (2008)
Kempe, Julia, Regev, Oded, Toner, Ben
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e.,...
Using Entanglement in Quantum Multi-Prover Interactive Proofs (2007)
Kempe, Julia, Kobayashi, Hirotada, Matsumoto, Keiji, Vidick, Thomas
The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared between provers affects the verification power of the proof system. We study for the first...
The Unique Games Conjecture with Entangled Provers is False (2007)
Kempe, Julia, Regev, Oded, Toner, Ben
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e.,...
The power of quantum systems on a line (2007)
Aharonov, Dorit, Gottesman, Daniel, Irani, Sandy, Kempe, Julia
We study the computational strength of quantum particles (each of finite dimensionality) arranged on a line. First, we prove that it is possible to perform universal adiabatic quantum computation...
Entangled games are hard to approximate (2007)
Kempe, Julia, Kobayashi, Hirotada, Matsumoto, Keiji, Toner, Ben, Vidick, Thomas
We establish the first hardness results for the problem of computing the value of one-round games played by a verifier and a team of provers who can share quantum entanglement. In particular, we show...
The unique game conjecture with entangled provers is false (2007)
Julia Kempe, Oded Regev, Ben Toner
We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are ‘unique ’ constraints (i.e.,...
Julia Kempe, Keiji Matsumoto, Hirotada Kobayashi, Thomas Vidick
The central question in quantum multi-prover interactive proof systems is whether or not entanglement shared between provers affects the verification power of the proof system. We study for the first...
Approaches to Quantum Error Correction (2006)
The purpose of this little survey is to give a simple description of the main approaches to quantum error correction and quantum fault-tolerance. Our goal is to convey the necessary intuitions both...
On the Power of Entangled Quantum Provers (2006)
We show that the value of a general two-prover quantum game cannot be computed by a semi-definite program ofvpolynomial size (unless P=NP), a method that has been successful in more restricted...
Gavinsky, Dmitry, Kempe, Julia, Kerenidis, Iordanis, Raz, Ran, De Wolf, Ronald
We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean Hidden Matching Problem of Bar-Yossef et al.)...
Permutation groups, minimal degrees and quantum computing (2006)
Kempe, Julia, Pyber, Laszlo, Shalev, Aner
We study permutation groups of given minimal degree without the classical primitivity assumption. We provide sharp upper bounds on the order of a permutation group of minimal degree m and on the...
Gavinsky, Dmitry, Kempe, Julia, De Wolf, Ronald
We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result...
Strengths and Weaknesses of Quantum Fingerprinting (2006)
Gavinsky, Dmitry, Kempe, Julia, De Wolf, Ronald
We study the power of quantum fingerprints in the simultaneous message passing (SMP) setting of communication complexity. Yao recently showed how to simulate, with exponential overhead, classical...
The Complexity of the Local Hamiltonian Problem (2006)
Kempe, Julia, Kitaev, Alexei, Regev, Oded
The k-LOCAL Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analogue of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k >= 2. It was...
∗ These lecture notes are based on a book chapter written by the author for ”Lectures in Quantum Information”, edited by D. Bruss and G. Leuchs and to be published by
We consider the problem of bounded-error quantum state identification: given either state α0 or state α1, we are required to output ‘0’, ‘1 ’ or ‘? ’ (“don’t know”), such that...
Dmitry Gavinsky, Julia Kempe, Oded Regev, De Wolf
Abstract. We consider the problem of bounded-error quantum state identification: given either state α0 or state α1, we are required to output ‘0’, ‘1 ’ or ‘? ’ (“don’t know”),...
Gavinsky, Dmitry, Kempe, Julia, Regev, Oded, De Wolf, Ronald
We consider the problem of bounded-error quantum state identification: given either state \alpha_0 or state \alpha_1, we are required to output `0', `1' or `?' ("don't know"), such that conditioned...
Quantum Communication Cannot Simulate a Public Coin (2004)
Gavinsky, Dmitry, Kempe, Julia, De Wolf, Ronald
We study the simultaneous message passing model of communication complexity. Building on the quantum fingerprinting protocol of Buhrman et al., Yao recently showed that a large class of efficient...
Generalized Performance of Concatenated Quantum Codes -- A Dynamical Systems Approach (2004)
Fern, Jesse, Kempe, Julia, Simic, Slobodan, Sastry, Shankar
We apply a dynamical systems approach to concatenation of quantum error correcting codes, extending and generalizing the results of Rahn et al. [1] to both diagonal and nondiagonal channels. Our...
The Complexity of the Local Hamiltonian Problem (2004)
Kempe, Julia, Kitaev, Alexei, Regev, Oded
The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k
The hidden subgroup problem and permutation group theory (2004)
We employ concepts and tools from the theory of finite permutation groups in order to analyse the Hidden Subgroup Problem via Quantum Fourier Sampling (QFS) for the symmetric group. We show that...
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation (2004)
Aharonov, Dorit, Van Dam, Wim, Kempe, Julia, Landau, Zeph, Lloyd, Seth, Regev, Oded
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation...
Quantum Color-Coding Is Better (2004)
Von Korff, Joshua, Kempe, Julia
We describe a quantum scheme to ``color-code'' a set of objects in order to record which one is which. In the classical case, N distinct colors are required to color-code N objects. We show that in...
Coins Make Quantum Walks Faster (2004)
Ambainis, Andris, Kempe, Julia, Rivosh, Alexander
We show how to search N items arranged on a $\sqrt{N}\times\sqrt{N}$ grid in time $O(\sqrt N \log N)$, using a discrete time quantum walk. This result for the first time exhibits a significant...
The complexity of the local Hamiltonian problem (2004)
Julia Kempe, Alexei Kitaev, Oded Regev
Abstract. The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analogue of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k ≥...
Quantum random walks - an introductory overview (2003)
This article aims to provide an introductory survey on quantum random walks. Starting from a physical effect to illustrate the main ideas we will introduce quantum random walks, review some of their...
3-Local Hamiltonian is QMA-complete (2003)
It has been shown by Kitaev that the 5-local Hamiltonian problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-local Hamiltonian is already QMA-complete.
A Quantum Random Walk Search Algorithm (2002)
Shenvi, Neil, Kempe, Julia, Whaley, K. Birgitta
Quantum random walks on graphs have been shown to display many interesting properties, including exponentially fast hitting times when compared with their classical counterparts. However, it is still...
Quantum Random Walks Hit Exponentially Faster (2002)
We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical...
ABSTRACT Quantum Walks on Graphs (2002)
Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani
We set the ground for a theory of quantum walks on graphsthe generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution,...
Robustness of Multi-Party Entanglement (2001)
Simon, Christoph, Kempe, Julia
How common is large-scale entanglement in nature? As a first step towards addressing this question, we study the robustness of multi-party entanglement under local decoherence, modeled by partially...
Quantum walks on graphs (2001)
Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani
We initiate the study of the generalization of random walks on nite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible....
Quantum walks on graphs (2001)
Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani
We initiate the study of the generalization of random walks on nite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible....
Universal noiseless quantum computation : mathematical theory and applications / (2001)
Thesis (Ph. D. in Mathematics)--University of California, Berkeley, Fall 2001.
Quantum Walks On Graphs (2000)
Aharonov, Dorit, Ambainis, Andris, Kempe, Julia, Vazirani, Umesh
We set the ground for a theory of quantum walks on graphs- the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution,...
Universal simulation of Markovian quantum dynamics (2000)
Bacon, Dave, Childs, Andrew M., Chuang, Isaac L., Kempe, Julia, Leung, Debbie W., Zhou, Xinlan
Although the conditions for performing arbitrary unitary operations to simulate the dynamics of a closed quantum system are well understood, the same is not true of the more general class of quantum...
Lidar, Daniel A., Bacon, Dave, Kempe, Julia, Whaley, K. B.
Decoherence-free subspaces (DFSs) shield quantum information from errors induced by the interaction with an uncontrollable environment. Here we study a model of correlated errors forming an Abelian...
Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation (2000)
Kempe, Julia, Bacon, Dave, Lidar, Daniel A., Whaley, K. Birgitta
Universal quantum computation on decoherence-free subspaces and subsystems (DFSs) is examined with particular emphasis on using only physically relevant interactions. A necessary and sufficient...
Lambda's, V's and optimal cloning with stimulated emission (2000)
Kempe, Julia, Simon, Christoph, Weihs, Gregor
We show that optimal universal cloning of the polarization state of photons can be achieved via stimulated emission in three-level systems, both of the Lambda and the V type. We establish the...
Universal Fault-Tolerant Computation on Decoherence-Free Subspaces (1999)
Bacon, Dave, Kempe, Julia, Lidar, Daniel A., Whaley, K. B.
A general scheme to perform universal quantum computation within decoherence-free subspaces (DFSs) of a system's Hilbert space is presented. This scheme leads to the first fault-tolerant realization...
Decoherence-Free Subspaces for Multiple-Qubit Errors: (I) Characterization (1999)
Lidar, Daniel A., Bacon, Dave, Kempe, Julia, Whaley, K. B.
Coherence in an open quantum system is degraded through its interaction with a bath. This decoherence can be avoided by restricting the dynamics of the system to special decoherence-free subspaces....
Protecting Quantum Information Encoded in Decoherence Free States Against Exchange Errors (1999)
Lidar, Daniel A., Bacon, David, Kempe, Julia, Whaley, K. Birgitta
The exchange interaction between identical qubits in a quantum information processor gives rise to unitary two-qubit errors. It is shown here that decoherence free subspaces (DFSs) for collective...
Multi-particle entanglement and its applications to cryptography (1999)
Entanglement between three or more parties exhibits a realm of properties unknown to two-party states. Bipartite states are easily classified using the Schmidt decomposition. The Schmidt coefficients...