1.4k citations · 12.2k across the 98 of their papers we have counts for
4 papers · 1 filter
Merlin-Arthur Games and Stoquastic Complexity
Sergey Bravyi, Arvid J. Bessen, Barbara M. Terhal
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 comple…
The Bounded Storage Model in The Presence of a Quantum Adversary
Robert Koenig, Barbara M. Terhal
An extractor is a function E that is used to extract randomness. Given an imperfect random source X and a uniform seed Y, the output E(X,Y) is close to uniform. We study properties…
The Complexity of Stoquastic Local Hamiltonian Problems
Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira +1
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-diagon…
Noise Threshold for a Fault-Tolerant Two-Dimensional Lattice Architecture
Krysta M. Svore, David P. DiVincenzo, Barbara M. Terhal
We consider a model of quantum computation in which the set of operations is limited to nearest-neighbor interactions on a 2D lattice. We model movement of qubits with noisy SWAP o…