Adptive quantum computation, constant depth quantum circuits and arthur-merlin games

Barbara M. Terhal; David P. DiVincenzo

Adptive quantum computation, constant depth quantum circuits and arthur-merlin games

Barbara M. Terhal^*, David P. DiVincenzo

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

106 Citations (Scopus)

Abstract

We present evidence that there exist quantum computations that can be carried out in constant depth, using 2-qubit gates, that cannot be simulated classically with high accuracy. We prove that if one can simulate these circuits classically efficiently then BQP ⊆ AM.

Original language	English
Pages (from-to)	134-145
Number of pages	12
Journal	Quantum Information and Computation
Volume	4
Issue number	2
Publication status	Published - 2004
Externally published	Yes

Keywords

Constant Depth Quantum Circuits
Quantum Computation by teleportation

Cite this

@article{7f64355cec214d21b65b7a88ce206b3f,

title = "Adptive quantum computation, constant depth quantum circuits and arthur-merlin games",

abstract = "We present evidence that there exist quantum computations that can be carried out in constant depth, using 2-qubit gates, that cannot be simulated classically with high accuracy. We prove that if one can simulate these circuits classically efficiently then BQP ⊆ AM.",

keywords = "Constant Depth Quantum Circuits, Quantum Computation by teleportation",

author = "Terhal, {Barbara M.} and DiVincenzo, {David P.}",

year = "2004",

language = "English",

volume = "4",

pages = "134--145",

journal = "Quantum Information and Computation",

issn = "1533-7146",

publisher = "Rinton Press Inc.",

number = "2",

}

TY - JOUR

T1 - Adptive quantum computation, constant depth quantum circuits and arthur-merlin games

AU - Terhal, Barbara M.

AU - DiVincenzo, David P.

PY - 2004

Y1 - 2004

N2 - We present evidence that there exist quantum computations that can be carried out in constant depth, using 2-qubit gates, that cannot be simulated classically with high accuracy. We prove that if one can simulate these circuits classically efficiently then BQP ⊆ AM.

AB - We present evidence that there exist quantum computations that can be carried out in constant depth, using 2-qubit gates, that cannot be simulated classically with high accuracy. We prove that if one can simulate these circuits classically efficiently then BQP ⊆ AM.

KW - Constant Depth Quantum Circuits

KW - Quantum Computation by teleportation

UR - http://www.scopus.com/inward/record.url?scp=2442419277&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:2442419277

SN - 1533-7146

VL - 4

SP - 134

EP - 145

JO - Quantum Information and Computation

JF - Quantum Information and Computation

IS - 2

ER -

Adptive quantum computation, constant depth quantum circuits and arthur-merlin games

Abstract

Keywords

Other files and links

Fingerprint

Cite this