Quantum Lower Bounds for Fanout

Simple item page
dc.creatorFang, Maosen
dc.creatorFenner, Stephen
dc.creatorGreen, Frederic
dc.creatorHomer, Steven
dc.creatorZhang, Yong
dc.date2003-12-28
dc.date.accessioned2026-07-07T06:08:42Z
dc.date.available2026-07-07T06:08:42Z
dc.descriptionWe prove several new lower bounds for constant depth quantum circuits. The main result is that parity (and hence fanout) requires log depth circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancillæ. Under this constraint, this bound is close to optimal. In the case of a non-constant number $a$ of ancillae, we give a tradeoff between $a$ and the required depth, that results in a non-trivial lower bound for fanout when $a = n^{1-o(1)}$.
dc.identifierhttps://arxiv.org/abs/quant-ph/0312208
dc.identifierhttp://arxiv.org/abs/quant-ph/0312208
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/91720
dc.subjectQuantum Physics
dc.titleQuantum Lower Bounds for Fanout
dc.typetext

Files

Collections

arXiv