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

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

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

The above citations are from SAO/NASA ADS (last updated successfully 2020-10-22 00:27:48). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2020-10-22 00:27:46).

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.