Computational Distinguishability of Quantum Channels

Understand

The computational problem of distinguishing two quantum channels is central to quantum computing.

• It is a generalization of the well-known satisfiability problem from classical to quantum computation.
• This problem is shown to be surprisingly hard: it is complete for the class QIP of problems that have quantum interactive proof systems, which implies that it is hard for the class PSPACE of problems solvable by a classical computation in polynomial space.
• Several restrictions of distinguishability are also shown to be hard.