Clean Quantum and Classical Communication Protocols

Area of Science:

• Quantum Information Science
• Theoretical Computer Science
• Communication Complexity

Background:

• Standard communication protocols often leave registers in altered states.
• Clean communication protocols require all registers, except the output, to return to their initial states.
• Understanding the cost of clean computation is crucial for efficient distributed information processing.

Purpose of the Study:

• To determine the communication complexity of clean protocols for specific functions.
• To establish bounds for clean communication complexity in both classical and quantum settings.
• To explore the implications of clean protocols for distributed gate implementation.

Main Methods:

• Development of novel clean communication protocols for computing the inner product of two n-bit strings.
• Analysis of communication complexity for these protocols in the absence and presence of preshared entanglement.
• Generalization of findings to a broader class of Boolean functions.

Main Results:

• Clean inner product computation requires at most n+3 qubits (quantum) or n+O(sqrt[n]) bits (classical) without preshared entanglement.
• Optimal distributed CNOT gate implementation is inspired by the quantum inner product protocol.
• Nearly all Boolean functions exhibit maximal clean communication complexity: close to 2n bits classically and n qubits quantumly with preshared entanglement.

Conclusions:

• Clean communication protocols introduce a significant but quantifiable overhead compared to standard protocols.
• The derived bounds for inner product computation are near-optimal for both quantum and classical communication.
• The study highlights the fundamental limits of clean information processing in distributed systems.