Communication Capacity of Quantum Computation

2000/03/17 by S. Bose, Sougato Bose, L. Rallan +3
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #quant-ph

paper · pdf · doi:10.1103/physrevlett.85.5448

published as Phys. Rev. Lett., 85, 5448 (2000) · 4 pages, revtex

arxiv created 2000/03/17 · openalex publication_date 2000/12/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Strengths and Weaknesses of Quantum Computing
• A continuity property of the entropy density for spin lattice systems
• A fast quantum mechanical algorithm for database search
• A formal theory of inductive inference. Part II
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A formal theory of inductive inference. Part I