Computer Science

Quantum lower bounds for fanout

Document Type

Article

Abstract

We consider the resource bounded quantum circuit model with circuits restricted by the number of qubits they act upon and by their depth. Focusing on natural universal sets of gates which are familiar from classical circuit theory, several new lower bounds for constant depth quantum circuits are proved. The main result is that parity (and hence fanout) requires log depth quantum circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancillae. Under this constraint, this bound is close to optimal. In the case of a non-constant number a of ancillae and n input qubits, we give a tradeoff between a and the required depth, that results in a non-constant lower bound for fanout when a = n1-o(1). We also show that, regardless of the number of ancillæ arbitrary arity Toffoli gates cannot be simulated exactly by a constant depth circuit family with gates of bounded arity. © Rinton Press.

Publication Title

Quantum Information and Computation

Publication Date

2006

Volume

6

Issue

1

First Page

046

Last Page

057

ISSN

1533-7146

Keywords

circuit complexity, fanout, quantum complexity, quantum computation

APA Citation

Fang, M., Fenner, S., Green, F., Homer, S., & Zhang, Y. (2003). Quantum lower bounds for fanout. arXiv preprint quant-ph/0312208.

Link to Full Text

Share

COinS