title: Communication capacity of quantum computation.
abstract: By considering quantum computation as a communication process, we relate its efficiency to its classical communication capacity. This formalism allows us to derive lower bounds on the complexity of search algorithms in the most general context. It enables us to link the mixedness of a quantum computer to its efficiency and also allows us to derive the critical level of mixedness beyond which there is no quantum advantage in computation.
authors.affiliation: Centre for Quantum Computation, Clarendon Laboratory, University of Oxford, Parks Road, Oxford OX1 3PU, England.
authors.forename: S
authors.initials: S
authors.lastname: Bose
authors.forename: L
authors.initials: L
authors.lastname: Rallan
authors.forename: V
authors.initials: V
authors.lastname: Vedral