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 the complexity class BQP is contained in
AM.
Related papers
Ranked by semantic similarity — how closely each paper's abstract matches this one (100% = near-identical topic).