Tradeoffs for reliable quantum information storage in 2D systems (2009)
Bravyi, Sergey, Poulin, David, Terhal, Barbara
We ask whether there are fundamental limits on storing quantum information reliably in a bounded volume of space. To investigate this question, we study quantum error correcting codes specified by...
Quantum algorithms for testing properties of distributions (2009)
Bravyi, Sergey, Harrow, Aram W., Hassidim, Avinatan
Suppose one has access to oracles generating samples from two unknown probability distributions P and Q on some N-element set. How many samples does one need to test whether the two distributions are...
Thermodynamic stability criteria for a quantum memory based on stabilizer and subsystem codes (2009)
Chesi, Stefano, Loss, Daniel, Bravyi, Sergey, Terhal, Barbara M.
We discuss and review several thermodynamic criteria that have been introduced to characterize the thermal stability of a self-correcting quantum memory. We first examine the use of symmetry-breaking...
Bounds on the quantum satisfibility threshold (2009)
Bravyi, Sergey, Moore, Cristopher, Russell, Alexander
Quantum k-SAT is the problem of deciding whether there is a n-qubit state which is perpendicular to a set of vectors, each of which lies in the Hilbert space of k qubits. Equivalently, the problem is...
Bravyi, Sergey, Terhal, Barbara
We study properties of stabilizer codes that permit a local description on a regular D-dimensional lattice. Specifically, we assume that the stabilizer group of a code (the gauge group for subsystem...
Complexity of stoquastic frustration-free Hamiltonians (2008)
Bravyi, Sergey, Terhal, Barbara
We study several problems related to properties of non-negative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we...
Bravyi, Sergey, DiVincenzo, David P., Loss, Daniel, Terhal, Barbara M.
We show how to map a given n-qubit target Hamiltonian with bounded-strength k-body interactions onto a simulator Hamiltonian with two-body interactions, such that the ground-state energy of the...
Contraction of matchgate tensor networks on non-planar graphs (2008)
A tensor network is a product of tensors associated with vertices of some graph $G$ such that every edge of $G$ represents a summation (contraction) over a matching pair of indexes. It was shown...
Polynomial-time algorithm for simulation of weakly interacting quantum spin systems (2007)
Bravyi, Sergey, DiVincenzo, David, Loss, Daniel
We describe an algorithm that computes the ground state energy and correlation functions for 2-local Hamiltonians in which interactions between qubits are weak compared to single-qubit terms. The...
Bansal, Nikhil, Bravyi, Sergey, Terhal, Barbara M.
We describe an efficient approximation algorithm for evaluating the ground-state energy of the classical Ising Hamiltonian with linear terms on an arbitrary planar graph. The running time of the...
Upper bounds on entangling rates of bipartite Hamiltonians (2007)
We discuss upper bounds on the rate at which unitary evolution governed by a non-local Hamiltonian can generate entanglement in a bipartite system. Given a bipartite Hamiltonian H coupling two finite...
Merlin-Arthur Games and Stoquastic Complexity (2006)
Bravyi, Sergey, Bessen, Arvid J., Terhal, Barbara M.
MA is a class of decision problems for which `yes'-instances have a proof that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete problem which we...
On measurement-based quantum computation with the toric code states (2006)
Bravyi, Sergey, Raussendorf, Robert
We study measurement-based quantum computation (MQC) using as quantum resource the planar code state on a two-dimensional square lattice (planar analogue of the toric code). It is shown that MQC with...
The Complexity of Stoquastic Local Hamiltonian Problems (2006)
Bravyi, Sergey, DiVincenzo, David P., Oliveira, Roberto I., Terhal, Barbara M.
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: all off-diagonal matrix elements...
GHZ extraction yield for multipartite stabilizer states (2006)
Bravyi, Sergey, Fattal, David, Gottesman, Daniel
Let |Psi> be an arbitrary stabilizer state distributed between three remote parties, such that each party holds several qubits. Let S be a stabilizer group of |Psi>. We show that |Psi> can be...
Universal quantum computation with the v=5/2 fractional quantum Hall state (2006)
We consider topological quantum computation (TQC) with a particular class of anyons that are believed to exist in the fractional quantum Hall effect state at Landau-level filling fraction v =5/2....
Efficient algorithm for a quantum analogue of 2-SAT (2006)
Complexity of a quantum analogue of the satisfiability problem is studied. Quantum k-SAT is a problem of verifying whether there exists n-qubit pure state such that its k-qubit reduced density...
Universal Quantum Computation with the nu=5/2 Fractional Quantum Hall State (2005)
We consider topological quantum computation (TQC) with a particular class of anyons that are believed to exist in the Fractional Quantum Hall Effect state at Landau level filling fraction nu=5/2....
Classical capacity of fermionic product channels (2005)
We study multi-qubit quantum channels that can be represented as a product of one-mode fermionic attenuation channels. An explicit formula for the classical capacity $C_1$ and for the minimum output...
GHZ extraction yield for multipartite stabilizer states (2005)
Bravyi, Sergey, Fattal, David, Gottesman, Daniel
Let $|\Psi>$ be an arbitrary stabilizer state distributed between three remote parties, such that each party holds several qubits. Let $S$ be a stabilizer group of $|\Psi>$. We show that $|\Psi>$ can...
Universal quantum computation with ideal Clifford gates and noisy ancillas (2005)
Bravyi, Sergey, Kitaev, Alexei
We consider a model of quantum computation in which the set of elementary operations is limited to Clifford unitaries, the creation of the state |0>, and qubit measurement in the computational basis....
Long-range quantum entanglement in noisy cluster states (2004)
Raussendorf, Robert, Bravyi, Sergey, Harrington, Jim
We describe a phase transition for long-range entanglement in a three-dimensional cluster state affected by noise. The partially decohered state is modeled by the thermal state of a suitable...
Entanglement in the stabilizer formalism (2004)
Fattal, David, Cubitt, Toby S., Yamamoto, Yoshihisa, Bravyi, Sergey, Chuang, Isaac L.
We define a multi-partite entanglement measure for stabilizer states, which can be computed efficiently from a set of generators of the stabilizer group. Our measure applies to qubits, qudits and...
Lagrangian representation for fermionic linear optics (2004)
Notions of a Gaussian state and a Gaussian linear map are generalized to the case of anticommuting (Grassmann) variables. Conditions under which a Gaussian map is trace preserving and (or) completely...
Unextendible product bases and locally unconvertible bound entangled states (2003)
Mutual convertibility of bound entangled states under local quantum operations and classical communication (LOCC) is studied. We focus on states associated with unextendible product bases (UPB) in a...
Requirements for compatibility between local and multipartite quantum states (2003)
We consider a partial trace transformation which maps a multipartite quantum state to collection of local density matrices. We call this collection a mean field state. The necessary and sufficient...
Fermionic quantum computation (2000)
Bravyi, Sergey, Kitaev, Alexei
We define a model of quantum computation with local fermionic modes (LFMs) -- sites which can be either empty or occupied by a fermion. With the standard correspondence between the Foch space of $m$...