Computational Distinguishability of Quantum Channels
arXiv:0909.3930
Abstract
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. It is no easier when restricted to quantum computations of logarithmic depth, to mixed-unitary channels, to degradable channels, or to antidegradable channels. These hardness results are demonstrated by finding reductions between these classes of quantum channels. These techniques have applications outside the distinguishability problem, as the construction for mixed-unitary channels is used to prove that the additivity problem for the classical capacity of quantum channels can be equivalently restricted to the mixed unitary channels.
Ph.D. Thesis, 178 pages, 35 figures
References in corpus (46)
- Quantum Teleportation is a Universal Computational Primitive
- Improved Simulation of Stabilizer Circuits
- Quantum fingerprinting
- On the Power of One Bit of Quantum Information
- Complete Characterization of a Quantum Process: the Two-Bit Quantum Gate
- Distance measures to compare real and ideal quantum processes
- General Entanglement Breaking Channels
- Superadditivity of communication capacity using entangled inputs
- Universal Quantum Estimator
- Direct estimations of linear and non-linear functionals of a quantum state
- Capacities of Quantum Erasure Channels
- Randomizing quantum states: Constructions and applications
- Optimal Encryption of Quantum Bits
- Largest separable balls around the maximally mixed bipartite quantum state
- Simulation of topological field theories by quantum computers
- Additivity for a class of unital qubit channels
- Optimal discrimination of quantum operations
- Quantum information and precision measurement
- Information-capacity description of spin-chain correlations
- Entanglement can enhance the distinguishability of entanglement-breaking channels
- An introduction to measurement based quantum computation
- Parallelizing Quantum Circuits
- On some additivity problems in quantum information theory
- Quantum Capacities of Channels with small Environment
- On Random Unitary Channels
- Quantum Circuits with Unbounded Fan-out
- On Universal and Fault-Tolerant Quantum Computing
- Fast parallel circuits for the quantum Fourier transform
- Entanglement assisted capacity of the broadband lossy channel
- Quantum Randomness and Nondeterminism
- Semidefinite programs for completely bounded norms
- On complementary channels and the additivity problem
- Fault Tolerant Quantum Computation with Constant Error
- Sending quantum entanglement through noisy channels
- Cryptographic Distinguishability Measures for Quantum Mechanical States
- Identity check is QMA-complete
- Private Quantum Channels and the Cost of Randomizing Quantum Information
- On the minimum number of unitaries needed to describe a random-unitary channel
- Simplification of additivity conjecture in quantum information theory
- Stabilisation of Quantum Computations by Symmetrisation
- The Efficiency of Quantum Identity Testing of Multiple States
- Quantum statistical zero-knowledge
- PSPACE has 2-round quantum interactive proof systems
- On the complexity of approximating the diamond norm
- The Persistent Quantum Bit
- On the hardness of distinguishing mixed-state quantum computations