## Computer Science

# Bounds on the power of constant-depth quantum circuits

## Document Type

Conference Paper

## Abstract

We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, for 0 < ∈ ≤ δ ≤ 1, we define BQNC∈,δ0 to be the class of languages recognized by constant depth, polynomial-size quantum circuits with acceptance probability either < ∈ (for rejection) or ≥ δ (for acceptance). We show that BQNC∈,δ0, ⊆ P, provided that 1 - δ ≤ 2-2d(1 - ∈), where d is the circuit depth. On the other hand, we adapt and extend ideas of Terhal & DiVincenzo [1] to show that, for any family ℱ of quantum gates including Hadamard and CNOT gates, computing the acceptance probabilities of depth-five circuits over ℱ is just as hard as computing these probabilities for arbitrary quantum circuits over ℱ. In particular, this implies that NQNC0 = NQACC = NQP = coC=P, where NQNC0 is the constant-depth analog of the class NQP. This essentially refutes a conjecture of Green et al. that NQACC ∈ TC0 [2]. © Springer-Verlag Berlin Heidelberg 2005.

## Publication Title

Lecture Notes in Computer Science

## Publication Date

2005

## Volume

3623

## First Page

44

## Last Page

55

## ISSN

0302-9743

## DOI

10.1007/11537311_5

## Keywords

dependency graph, quantum circuit, quantum gate, constant depth, acceptance probability

## Repository Citation

Fenner, Stephen; Green, Frederic; Homer, Steven; and Zhang, Yong, "Bounds on the power of constant-depth quantum circuits" (2005). *Computer Science*. 59.

https://commons.clarku.edu/faculty_computer_sciences/59

## APA Citation

Fenner, S., Green, F., Homer, S., & Zhang, Y. (2005, August). Bounds on the power of constant-depth quantum circuits. In *International Symposium on Fundamentals of Computation Theory* (pp. 44-55). Berlin, Heidelberg: Springer Berlin Heidelberg.