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

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


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

► 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

Cited by

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

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

[3] 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", arXiv:2003.14405.

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-23 05:12:23) and SAO/NASA ADS (last updated successfully 2021-04-23 05:12:25). The list may be incomplete as not all publishers provide suitable and complete citation data.