An Efficient Algorithm for approximating 1D Ground States (2009)
Aharonov, Dorit, Arad, Itai, Irani, Sandy
The most commonly used algorithm for approximating ground states of 1D quantum systems is the Density Matrix Renormalization Group approach (DMRG). DMRG works very well in practice, but there is no...
The Detectability Lemma and Quantum Gap Amplification (2008)
Aharonov, Dorit, Arad, Itai, Landau, Zeph, Vazirani, Umesh
The quantum analogue of a constraint satisfaction problem is a sum of local Hamiltonians - each local Hamiltonian specifies a local constraint whose violation contributes to the energy of the given...
Interactive Proofs For Quantum Computations (2008)
Aharonov, Dorit, Ben-Or, Michael, Eban, Elad
The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantum computers might already be too large to be simulated classically. Is it possible to...
Aharonov, Dorit, Ben-Or, Michael, Sattath, Or
Valiant-Vazirani showed in 1985 that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are...
ABSTRACT Adiabatic Quantum State Generation and Statistical Zero Knowledge (2008)
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of ’quantum state generation’....
amnon @ cs.berkeley.edu (2008)
doria @ cs.berkeley.edu Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commit-ment is known to be impossible also in the quantum world....
Adiabatic quantum state generation (2008)
Abstract. The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to this task by studying the problem of quantum state...
Dorit Aharonov, Michael Ben-or, Russell Impagliazzo, Noam Nisan
In this paper we study noisy reversible circuits. Noisy computation and reversible computation have been studied separately, and it is known that they are equivalent in power to unrestricted...
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...
Aharonov, Dorit, Arad, Itai, Eban, Elad, Landau, Zeph
In the first 36 pages of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes...
Detrimental Decoherence (2007)
Gil Kalai, Dorit Aharonov, Michael Ben-or, Greg Kuperberg
We propose and discuss two conjectures on the nature of informa-tion leaks (decoherence) for quantum computers. These conjectures, if (or when) they hold, are damaging for quantum error-correction as...
The quantum FFT can be classically simulated (2006)
Aharonov, Dorit, Landau, Zeph, Makowsky, Johann
In this note we describe a simple and intriguing observation: the quantum Fourier transform (QFT) over $Z_q$, which is considered the most ``quantum'' part of Shor's algorithm, can in fact be...
This review is about to tell the story of theoretical quantum computation. It begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models,...
The BQP-hardness of approximating the Jones Polynomial (2006)
Following the work by Kitaev, Freedman and Wang, Aharonov, Jones and Landau recently gave an explicit and efficient quantum algorithm for approximating the Jones polynomial of the plat closure of a...
Fault-Tolerant Quantum Computation with Long-Range Correlated Noise (2006)
Aharonov, Dorit, Kitaev, Alexei, Preskill, John
We prove a new version of the quantum accuracy threshold theorem that applies to non-Markovian noise with algebraically decaying spatial correlations. We consider noise in a quantum computer arising...
Quantum computation - alternative models and algorithms (2006)
Quantum Information, Computation and Complexity * Programme at the Institut Henri Poincaré, January 4th April 7th, 2006 * Organizers: Ph.Grangier, M.Santha and D.L.Shepelyansky * Lectures have...
Quantum computation - alternative models and algorithms (2006)
Quantum Information, Computation and Complexity * Programme at the Institut Henri Poincaré, January 4th April 7th, 2006 * Organizers: Ph.Grangier, M.Santha and D.L.Shepelyansky * Lectures have...
A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2005)
Aharonov, Dorit, Jones, Vaughan, Landau, Zeph
The Jones polynomial, discovered in 1984, is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten) to be...
Fault-tolerant quantum computation with long-range correlated noise (2005)
Aharonov, Dorit, Kitaev, Alexei, Preskill, John
We prove a new version of the quantum accuracy threshold theorem that applies to non-Markovian noise with algebraically decaying spatial correlations. We consider noise in a quantum computer arising...
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...
Lattice Problems in NP ∩ coNP (2004)
We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of √n lie in NP intersect coNP. The result (almost) subsumes the three...
A Lattice Problem in Quantum NP (2003)
We consider coGapSVP_\sqrt{n}, a gap version of the shortest vector in a lattice problem. This problem is known to be in AM\cap coNP but is not known to be in NP or in MA. We prove that it lies...
A Simple Proof that Toffoli and Hadamard are Quantum Universal (2003)
Recently Shi proved that Toffoli and Hadamard are universal for quantum computation. This is perhaps the simplest universal set of gates that one can hope for, conceptually; It shows that one only...
Adiabatic Quantum State Generation and Statistical Zero Knowledge (2003)
Aharonov, Dorit, Ta-Shma, Amnon
The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum state generation'....
Adiabatic quantum state generation and statistical zero knowledge (2003)
The design of new quantum algorithms has proven to be an extremely di#cult task. This paper considers a di#erent approach to the problem by studying the problem of 'quantum state...
Adiabatic Quantum State Generation and Statistical Zero Knowledge (2003)
The design of new quantum algorithms has proven to be an extremely di#cult task. This paper considers a di#erent approach to the problem.
We describe Kitaev's result from 1999, in which he defines the complexity class QMA, the quantum analog of the class NP, and shows that a natural extension of 3-SAT, namely local Hamiltonians, is QMA...
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,...
We describe Kitaev’s result from 1999, in which he defines the complexity class QMA, the quantum analog of the class NP, and shows that a natural extension of 3−SAT, namely local Hamiltonians, is...
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....
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,...
Aharonov, Dorit, Ta-Shma, Amnon, Vazirani, Umesh, Yao, Andrew
Unconditionally secure bit commitment and coin flipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We introduce a related...
Dorit Aharonov, Amnon Ta-shma, Umesh V. Vazirani, Andrew C. Yao
Unconditionally secure bit commitment and coin ipping are known to be impossible in the classical world. Bit commitment is known to be impossible also in the quantum world. We introduce a related new...
A Quantum to Classical Phase Transition in Noisy Quantum Computers (1999)
The fundamental problem of the transition from quantum to classical physics is usually explained by decoherence, and viewed as a gradual process. The study of entanglement, or quantum correlations,...
Fault-Tolerant Quantum Computation With Constant Error Rate (1999)
Aharonov, Dorit, Ben-Or, Michael
This paper proves the threshold result, which asserts that quantum computation can be made robust against errors and inaccuracies, when the error rate, $\eta$, is smaller than a constant threshold,...
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if...
Quantum Circuits with Mixed States (1998)
Aharonov, Dorit, Kitaev, Alexei, Nisan, Noam
We define the model of quantum circuits with density matrices, where non-unitary gates are allowed. Measurements in the middle of the computation, noise and decoherence are implemented in a natural...
Quantum circuits with mixed states (1998)
Dorit Aharonov, Alexei Kitaev, Noam Nisan
Current formal models for quantum computation deal only with unitary gates operating on "pure quantum states". In these models it is difficult or impossible to deal formally with...
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if...
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if...
Polynomial Simulations of Decohered Quantum Computers (1996)
Aharonov, Dorit, Ben-Or, Michael
We define formally decohered quantum computers (using density matrices), and present a simulation of them by a probabalistic classical Turing Machine. We study the slowdown of the simulation for two...
Fault Tolerant Quantum Computation with Constant Error (1996)
Aharonov, Dorit, Ben-Or, Michael
Recently Shor showed how to perform fault tolerant quantum computation when the error probability is logarithmically small. We improve this bound and describe fault tolerant quantum computation when...
Polynomial simulations of decohered quantum computers (1996)
Dorit Aharonov, Michael Ben-or
Recently it has become clear, that a key issue in quantum computation is understanding how interaction with the environment, or "decoherence", effects the computational power of...