{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T17:10:41Z","timestamp":1765041041094},"reference-count":17,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,4,16]],"date-time":"2020-04-16T00:00:00Z","timestamp":1586995200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>A quantum channel is said to be a<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mtext class=\"MJX-tex-mathit\" mathvariant=\"italic\">mixed-unitary<\/mml:mtext><\/mml:mrow><\/mml:math>channel if it can be expressed as a convex combination of unitary channels. We prove that, given the Choi representation of a quantum channel<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a6<\/mml:mi><\/mml:math>, it is NP-hard with respect to polynomial-time Turing reductions to determine whether or not<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a6<\/mml:mi><\/mml:math>is a mixed-unitary channel. This hardness result holds even under the assumption that<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a6<\/mml:mi><\/mml:math>is not within an inverse-polynomial distance (in the dimension of the space upon which<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">\u03a6<\/mml:mi><\/mml:math>acts) of the boundary of the mixed-unitary channels.<\/jats:p>","DOI":"10.22331\/q-2020-04-16-253","type":"journal-article","created":{"date-parts":[[2020,4,16]],"date-time":"2020-04-16T10:22:06Z","timestamp":1587032526000},"page":"253","source":"Crossref","is-referenced-by-count":13,"title":["Detecting mixed-unitary quantum channels is NP-hard"],"prefix":"10.22331","volume":"4","author":[{"given":"Colin Do-Yan","family":"Lee","sequence":"first","affiliation":[{"name":"Institute for Quantum Computing and School of Computer Science, University of Waterloo, Canada"}]},{"given":"John","family":"Watrous","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing and School of Computer Science, University of Waterloo, Canada"}]}],"member":"9598","published-online":{"date-parts":[[2020,4,16]]},"reference":[{"key":"0","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.","DOI":"10.1017\/CBO9780511804090"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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\u2013553, 2000. 10.1109\/SFCS.2000.892142.","DOI":"10.1109\/SFCS.2000.892142"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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\u2013260, 2004. 10.1007\/978-3-540-27821-4_23.","DOI":"10.1007\/978-3-540-27821-4_23"},{"key":"3","unstructured":"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."},{"key":"4","doi-asserted-by":"publisher","unstructured":"Man-Duen Choi. Completely positive linear maps on complex matrices. Linear Algebra and Its Applications, 10(3):285\u2013290, 1975. 10.1016\/0024-3795(75)90075-0.","DOI":"10.1016\/0024-3795(75)90075-0"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Shimon Even, Alan Selman, and Yacov Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159\u2013173, 1984. 10.1016\/S0019-9958(84)80056-X.","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Sevag Gharibian. Strong NP-hardness of the quantum separability problem. Quantum Information & Computation, 10(3):343\u2013360, 2010.","DOI":"10.26421\/QIC10.3-4-11"},{"key":"7","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer\u2013Verlag, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u201319. ACM, 2003. 10.1145\/780542.780545.","DOI":"10.1145\/780542.780545"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Patrick Hayden, Debbie Leung, Peter Shor, and Andreas Winter. Randomizing quantum states: constructions and applications. Communications in Mathematical Physics, 250(2):371\u2013391, 2004. 10.1007\/s00220-004-1087-6.","DOI":"10.1007\/s00220-004-1087-6"},{"key":"10","doi-asserted-by":"crossref","unstructured":"Lawrence Ioannou. Computational complexity of the quantum separability problem. Quantum Information & Computation, 7(4):335\u2013370, 2007.","DOI":"10.26421\/QIC7.4-5"},{"key":"11","unstructured":"Yi-Kai Liu. The Complexity of the Consistency and $N$-Representability Problems for Quantum States. PhD thesis, University of California, San Diego, 2007."},{"key":"12","doi-asserted-by":"publisher","unstructured":"Bill Rosgen. Additivity and distinguishability of random unitary channels. Journal of Mathematical Physics, 49(10):102107, 2008. 10.1063\/1.2992977.","DOI":"10.1063\/1.2992977"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2018-01-12-45"},{"key":"14","doi-asserted-by":"crossref","unstructured":"John Watrous. Mixing doubly stochastic quantum channels with the completely depolarizing channel. Quantum Information & Computation, 9(5):406\u2013413, 2009.","DOI":"10.26421\/QIC9.5-6-4"},{"key":"15","doi-asserted-by":"crossref","unstructured":"John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018.","DOI":"10.1017\/9781316848142"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Nengkun Yu. Separability of a mixture of Dicke states. Physical Review A, 94(6):060101, 2016. 10.1103\/PhysRevA.94.060101.","DOI":"10.1103\/PhysRevA.94.060101"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-04-16-253\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T13:11:37Z","timestamp":1666357897000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-04-16-253\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,16]]},"references-count":17,"URL":"https:\/\/doi.org\/10.22331\/q-2020-04-16-253","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,16]]},"article-number":"253"}}