Detecting mixed-unitary quantum channels is NP-hard

Colin Do-Yan Lee; John Watrous

doi:10.22331/q-2020-04-16-253

Detecting mixed-unitary quantum channels is NP-hard

Colin Do-Yan Lee and John Watrous

Institute for Quantum Computing and School of Computer Science, University of Waterloo, Canada

Published:	2020-04-16, volume 4, page 253
Eprint:	arXiv:1902.03164v3
Doi:	https://doi.org/10.22331/q-2020-04-16-253
Citation:	Quantum 4, 253 (2020).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

A quantum channel is said to be a $\textit{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 $\Phi$, it is NP-hard with respect to polynomial-time Turing reductions to determine whether or not $\Phi$ is a mixed-unitary channel. This hardness result holds even under the assumption that $\Phi$ is not within an inverse-polynomial distance (in the dimension of the space upon which $\Phi$ acts) of the boundary of the mixed-unitary channels.

► BibTeX data

@article{Lee2020detectingmixed,
  doi = {10.22331/q-2020-04-16-253},
  url = {https://doi.org/10.22331/q-2020-04-16-253},
  title = {Detecting mixed-unitary quantum channels is {NP}-hard},
  author = {Lee, Colin Do-Yan and Watrous, John},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {253},
  month = apr,
  year = {2020}
}

► References

[1] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

[2] Andris Ambainis, Michele Mosca, Alain Tapp, and Ronald de Wolf. Private quantum channels. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pages 547–553, 2000. 10.1109/SFCS.2000.892142.
https://doi.org/10.1109/SFCS.2000.892142

[3] Andris Ambainis and Adam Smith. Small pseudo-random families of matrices: Derandomizing approximate quantum encryption. In Proceedings of the 8th International Workshop on Randomization and Computation, volume 3122 of Lecture Notes in Computer Science, pages 249–260, 2004. 10.1007/978-3-540-27821-4_23.
https://doi.org/10.1007/978-3-540-27821-4_23

[4] Peter Alberti and Armin Uhlmann. Stochasticity and Partial Order: Doubly Stochastic Maps and Unitary Mixing, volume 9 of Mathematics and Its Applications. D. Reidel Publishing Company, 1982.

[5] Man-Duen Choi. Completely positive linear maps on complex matrices. Linear Algebra and Its Applications, 10(3):285–290, 1975. 10.1016/0024-3795(75)90075-0.
https://doi.org/10.1016/0024-3795(75)90075-0

[6] Shimon Even, Alan Selman, and Yacov Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159–173, 1984. 10.1016/S0019-9958(84)80056-X.
https://doi.org/10.1016/S0019-9958(84)80056-X

[7] Sevag Gharibian. Strong NP-hardness of the quantum separability problem. Quantum Information & Computation, 10(3):343–360, 2010.

[8] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer–Verlag, 1988.

[9] Leonid Gurvits. Classical deterministic complexity of Edmonds' problem and quantum entanglement. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pages 10–19. ACM, 2003. 10.1145/780542.780545.
https://doi.org/10.1145/780542.780545

[10] Patrick Hayden, Debbie Leung, Peter Shor, and Andreas Winter. Randomizing quantum states: constructions and applications. Communications in Mathematical Physics, 250(2):371–391, 2004. 10.1007/s00220-004-1087-6.
https://doi.org/10.1007/s00220-004-1087-6

[11] Lawrence Ioannou. Computational complexity of the quantum separability problem. Quantum Information & Computation, 7(4):335–370, 2007.

[12] Yi-Kai Liu. The Complexity of the Consistency and $N$-Representability Problems for Quantum States. PhD thesis, University of California, San Diego, 2007.

[13] Bill Rosgen. Additivity and distinguishability of random unitary channels. Journal of Mathematical Physics, 49(10):102107, 2008. 10.1063/1.2992977.
https://doi.org/10.1063/1.2992977

[14] Jordi Tura, Albert Aloy, Ruben Quesada, Maciej Lewenstein, and Anna Sanpera. Separability of diagonal symmetric states: a quadratic conic optimization problem. Quantum, 2:45, January 2018. 10.22331/q-2018-01-12-45.
https://doi.org/10.22331/q-2018-01-12-45

[15] John Watrous. Mixing doubly stochastic quantum channels with the completely depolarizing channel. Quantum Information & Computation, 9(5):406–413, 2009.

[16] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018.

[17] Nengkun Yu. Separability of a mixture of Dicke states. Physical Review A, 94(6):060101, 2016. 10.1103/PhysRevA.94.060101.
https://doi.org/10.1103/PhysRevA.94.060101

Cited by

[1] Mark Girard, Debbie Leung, Jeremy Levick, Chi-Kwong Li, Vern Paulsen, Yiu Tung Poon, and John Watrous, "On the Mixed-Unitary Rank of Quantum Channels", Communications in Mathematical Physics 394 2, 919 (2022).

[2] Mikhail Gennadievich Belov, Victor Victorovich Dubov, Alexey Vladimirovich Filimonov, and Vladislav Gennadievich Malyshkin, "Quantum channel learning", Physical Review E 111 1, 015302 (2025).

[3] Xiao-Dong Yu, Timo Simnacher, H. Chau Nguyen, and Otfried Gühne, "Quantum-Inspired Hierarchy for Rank-Constrained Optimization", PRX Quantum 3 1, 010340 (2022).

[4] Jong Yeon Lee, Yi-Zhuang You, and Cenke Xu, "Symmetry protected topological phases under decoherence", Quantum 9, 1607 (2025).

[5] S. Attal, J. Deschamps, and C. Pellegrini, Lecture Notes in Mathematics 2301, 341 (2022) ISBN:978-3-030-96408-5.

[6] Huan-Yu Liu, Xiaoshui Lin, Zhao-Yun Chen, Cheng Xue, Tai-Ping Sun, Qing-Song Li, Xi-Ning Zhuang, Yun-Jie Wang, Yu-Chun Wu, Ming Gong, and Guo-Ping Guo, "Simulation of open quantum systems on universal quantum computers", Quantum 9, 1765 (2025).

[7] Otfried Gühne, Yuanyuan Mao, and Xiao-Dong Yu, "Geometry of Faithful Entanglement", Physical Review Letters 126 14, 140503 (2021).

[8] David W Kribs, Jeremy Levick, Rajesh Pereira, and Mizanur Rahaman, "Operator algebra generalization of a theorem of Watrous and mixed unitary quantum channels", Journal of Physics A: Mathematical and Theoretical 57 11, 115303 (2024).

[9] Mahathi Vempati, Saumya Shah, Nirman Ganguly, and Indranil Chakrabarty, "A-unital Operations and Quantum Conditional Entropy", Quantum 6, 641 (2022).

[10] Qi Han, Shuai Wang, Lijie Gou, and Rong Zhang, "Quantum conditional entropy based on local quantum Bernoulli noises", Reviews in Mathematical Physics 36 02, 2350037 (2024).

[11] Le Hu and Andrew N. Jordan, "Probabilistic unitary formulation of open quantum system dynamics", Physical Review A 110 6, 062205 (2024).

[12] David W Kribs, Jeremy Levick, Katrina Olfert, Rajesh Pereira, and Mizanur Rahaman, "Nullspaces of entanglement breaking channels and applications", Journal of Physics A: Mathematical and Theoretical 54 10, 105303 (2021).

[13] Francisco Riberi, Leigh M Norris, Félix Beaudoin, and Lorenza Viola, "Frequency estimation under non-Markovian spatially correlated quantum noise", New Journal of Physics 24 10, 103011 (2022).

[14] Michał Kotowski and Michał Oszmaniec, "Pretty-good simulation of all quantum measurements by projective measurements", arXiv:2501.09339, (2025).

[15] Uma Girish, Ran Raz, and Wei Zhan, "Quantum Logspace Algorithm for Powering Matrices with Bounded Norm", arXiv:2006.04880, (2020).

[16] Cristhiano Duarte, Barbara Amaral, Marcelo Terra Cunha, and Matthew Leifer, "Investigating Coarse-Grainings and Emergent Quantum Dynamics with Four Mathematical Perspectives", arXiv:2011.10349, (2020).

[17] Timothy Heightman and Grzegorz Rajchel-Mieldzioć, "Spoofing of Quantum Channels Enables Low-Rank Projective Simulation", arXiv:2410.14608, (2024).

[18] D. W. Kribs, J. Levick, K. Olfert, R. Pereira, and M. Rahaman, "Nullspaces of Entanglement Breaking Channels and Applications", arXiv:2007.15893, (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 04:59:43) and SAO/NASA ADS (last updated successfully 2026-07-14 14:47:07). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-15 04:59:43: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.