Detecting mixed-unitary quantum channels is NP-hard

Abstract

A quantum channel is said to be a mixed-unitary channel if it can be expressed as a convex combination of unitary channels. We prove that, given the Choi representation of a quantum channel, it is NP-hard with respect to polynomial-time Turing reductions to determine whether or not that channel is a mixed-unitary channel. This hardness result holds even under the assumption that the channel is not within an inverse-polynomial distance (in the dimension of the space upon which it acts) of the boundary of the mixed-unitary channels.

arXiv comment24 pages

References in corpus (5)

• Randomizing quantum states: Constructions and applications
• Separability of diagonal symmetric states: a quadratic conic optimization problem
• Separability of Bosonic Systems
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Additivity and Distinguishability of Random Unitary Channels

Cited by in corpus (12)

• Symmetry protected topological phases under decoherence
• Geometry of faithful entanglement
• On the mixed-unitary rank of quantum channels
• Quantum-Inspired Hierarchy for Rank-Constrained Optimization
• A-unital Operations and Quantum Conditional Entropy
• Frequency estimation under non-Markovian spatially correlated quantum noise: Restoring superclassical precision scaling
• Quantum Channel Learning
• Simulation of open quantum systems on universal quantum computers
• Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
• Operator Algebra Generalization of a Theorem of Watrous and Mixed Unitary Quantum Channels
• Probabilistic Unitary Formulation of Open Quantum System Dynamics
• Nullspaces of Entanglement Breaking Channels and Applications