Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1902.03164 · Quantum

Detecting mixed-unitary quantum channels is NP-hard

Colin Do-Yan Lee, John Watrous

Published Apr 16, 2020• 15 citations
arXivHTMLPDF

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 Φ is a mixed-unitary channel. This hardness result holds even under the assumption that Φ is not within an inverse-polynomial distance (in the dimension of the space upon which Φ acts) of the boundary of the mixed-unitary channels.

DOI
10.22331/q-2020-04-16-253

Related papers

Computational Distinguishability of Quantum Channels

Bill Rosgen

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.

arXiv:0909.3930•Sep 22, 2009•9 citations

Additivity and distinguishability of random unitary channels

Bill Rosgen

A random unitary channel is one that is given by a convex combination of unitary channels. It is shown that the conjectures on the additivity of the minimum output entropy and the multiplicativity of the maximum output p-norm can be equivalently restated in terms of random unitary channels. This is done by constructing a random unitary approximation to a general quantum channel. This approximation can be constructed efficiently, and so it is also applied to the computational problem of distinguishing quantum circuits. It is shown that the problem of distinguishing random unitary circuits is as hard as the problem of distinguishing general mixed-state circuits, which is complete for the class of problems having quantum interactive proof systems.

arXiv:0804.1936•Journal of Mathematical Physics•Oct 1, 2008•19 citations

Additivity and distinguishability of random unitary channels

Bill Rosgen

A random unitary channel is one that is given by a convex combination of unitary channels. It is shown that the conjectures on the additivity of the minimum output entropy and the multiplicativity of the maximum output p-norm can be equivalently restated in terms of random unitary channels. This is done by constructing a random unitary approximation to a general quantum channel. This approximation can be constructed efficiently, and so it is also applied to the computational problem of distinguishing quantum circuits. It is shown that the problem of distinguishing random unitary circuits is as hard as the QIP-complete problem of distinguishing general mixed state circuits. 1

•Jan 1, 2008•15 citations

On the Hardnesses of Several Quantum Decoding Problems

Kao-Yueh Kuo, Chung-Chin Lu

We classify the time complexities of three important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then over the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may be impossible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.

arXiv:1306.5173•Jun 21, 2013•6 citations

On the hardness of decoding quantum stabilizer codes under the depolarizing channel

Kao-Yueh Kuo, Chung-Chin Lu

We classify the complexity classes of several important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then under the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may not be possible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.

International Symposium on Information Theory and its Applications•Oct 1, 2012•7 citations

Quantum memory precludes mixed-unitary dynamics

Charlotte Bäcker, Konstantin Beyer, Walter T. Strunz

Unital quantum channels, defined by their property of leaving the maximally mixed state invariant, form an important class of quantum operations. A distinguished subset of these channels can be represented as a probabilistic mixture of unitary evolutions. Characterizing channels that do not admit such a decomposition is in general a hard problem with significant implications for noise mitigation in quantum technologies and for fundamental problems in quantum information theory. Here we establish a link between mixed-unitarity of unital channels and the (quantum) nature of the memory effects in non-Markovian dynamics. Translating the problem into the language of process tensors, this connection yields a hierarchy of semidefinite programs that provides numerically efficient witnesses for non-mixed-unitary behavior, outperforming existing criteria. We demonstrate the power of this approach through illustrative examples of unital channels in dimensions three and four, and show how the method can detect non-mixed-unitary behavior based on incomplete channel tomography.

quant-pharXiv:2603.17010•Physical Review Research•Mar 19, 2026•0 citations
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 Φ is a mixed-unitary channel. This hardness result holds even under the assumption that Φ is not within an inverse-polynomial distance (in the dimension of the space upon which Φ acts) of the boundary of the mixed-unitary channels.
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.
A random unitary channel is one that is given by a convex combination of unitary channels. It is shown that the conjectures on the additivity of the minimum output entropy and the multiplicativity of the maximum output p-norm can be equivalently restated in terms of random unitary channels. This is done by constructing a random unitary approximation to a general quantum channel. This approximation can be constructed efficiently, and so it is also applied to the computational problem of distinguishing quantum circuits. It is shown that the problem of distinguishing random unitary circuits is as hard as the problem of distinguishing general mixed-state circuits, which is complete for the class of problems having quantum interactive proof systems.
A random unitary channel is one that is given by a convex combination of unitary channels. It is shown that the conjectures on the additivity of the minimum output entropy and the multiplicativity of the maximum output p-norm can be equivalently restated in terms of random unitary channels. This is done by constructing a random unitary approximation to a general quantum channel. This approximation can be constructed efficiently, and so it is also applied to the computational problem of distinguishing quantum circuits. It is shown that the problem of distinguishing random unitary circuits is as hard as the QIP-complete problem of distinguishing general mixed state circuits. 1
We classify the time complexities of three important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then over the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may be impossible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.
We classify the complexity classes of several important decoding problems for quantum stabilizer codes. First, regardless of the channel model, quantum bounded distance decoding is shown to be NP-hard, like what Berlekamp, McEliece and Tilborg did for classical binary linear codes in 1978. Then under the depolarizing channel, the decoding problems for finding a most likely error and for minimizing the decoding error probability are also shown to be NP-hard. Our results indicate that finding a polynomial-time decoding algorithm for general stabilizer codes may not be possible, but this, on the other hand, strengthens the foundation of quantum code-based cryptography.
Unital quantum channels, defined by their property of leaving the maximally mixed state invariant, form an important class of quantum operations. A distinguished subset of these channels can be represented as a probabilistic mixture of unitary evolutions. Characterizing channels that do not admit such a decomposition is in general a hard problem with significant implications for noise mitigation in quantum technologies and for fundamental problems in quantum information theory. Here we establish a link between mixed-unitarity of unital channels and the (quantum) nature of the memory effects in non-Markovian dynamics. Translating the problem into the language of process tensors, this connection yields a hierarchy of semidefinite programs that provides numerically efficient witnesses for non-mixed-unitary behavior, outperforming existing criteria. We demonstrate the power of this approach through illustrative examples of unital channels in dimensions three and four, and show how the method can detect non-mixed-unitary behavior based on incomplete channel tomography.