{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T11:31:24Z","timestamp":1767871884199,"version":"3.49.0"},"reference-count":63,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF Grant","award":["DMS-2247114"],"award-info":[{"award-number":["DMS-2247114"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"We introduce a new framework for quantifying the complexity of quantum channels, grounded in a suitably chosen resource set. This class of convex functions is designed to analyze the complexity of both open and closed quantum systems. By leveraging Lipschitz norms inspired by quantum optimal transport theory, we rigorously establish the fundamental properties of this complexity measure. The flexibility in selecting the resource set allows us to derive effective lower bounds for gate complexities and simulation costs of both Hamiltonian simulations and dynamics of open quantum systems. Additionally, we demonstrate that this complexity measure exhibits linear growth for random quantum circuits and finite-dimensional quantum simulations, up to the Brown-Susskind threshold.<\/jats:p>","DOI":"10.22331\/q-2026-01-08-1960","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:15:28Z","timestamp":1767860128000},"page":"1960","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Resource-Dependent Complexity of Quantum Channels"],"prefix":"10.22331","volume":"10","author":[{"given":"Roy","family":"Araiza","sequence":"first","affiliation":[{"name":"Department of Mathematics and Illinois Quantum Information Science and Technology Center (IQUIST), University of Illinois at UrbanaChampaign"}]},{"given":"Yidong","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Physics, University of Illinois at Urbana-Champaign"}]},{"given":"Marius","family":"Junge","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Illinois Quantum Information Science and Technology Center (IQUIST), University of Illinois at UrbanaChampaign"}]},{"given":"Peixue","family":"Wu","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing and Department of Applied Mathematics, University of Waterloo"}]}],"member":"9598","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"M. Alishahiha. ``Holographic complexity''. Phys. Rev. D 92: 126009 (2015).","DOI":"10.1103\/PhysRevD.92.126009"},{"key":"1","unstructured":"R. Araiza, M. Junge, and P. Wu. ``Transportation cost and contraction coefficient for channels on von Neumann algebras'', (2025). Available online: https:\/\/arxiv.org\/abs\/2506.04197."},{"key":"2","doi-asserted-by":"publisher","unstructured":"A. Avdoshkin, A. Dymarsky, and M. Smolkin. ``Krylov complexity in quantum field theory, and beyond''. Journal of High Energy Physics 2024(6) (2024).","DOI":"10.1007\/jhep06(2024)066"},{"key":"3","unstructured":"S. Beigi and P. W. Shor. ``On the Complexity of Computing Zero-Error and Holevo Capacity of Quantum Channels'', (2008). Available online: https:\/\/arxiv.org\/abs\/0709.2090."},{"key":"4","doi-asserted-by":"publisher","unstructured":"M. Bellare, O. Goldreich, and M. Sudan. ``Free bits, PCPs and non-approximability-towards tight results''. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 422\u2013431, (1995), DOI: 10.1109\/SFCS.1995.492573.","DOI":"10.1109\/SFCS.1995.492573"},{"key":"5","doi-asserted-by":"publisher","unstructured":"A. Ben-Aroya, O. Schwartz, and A. Ta-Shma. ``Quantum Expanders: Motivation and Constructions''. In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 292\u2013303, (2008), DOI: 10.1109\/CCC.2008.23.","DOI":"10.1109\/CCC.2008.23"},{"key":"6","doi-asserted-by":"publisher","unstructured":"E. Bernstein and U. Vazirani. ``Quantum Complexity Theory''. SIAM Journal on Computing 26(5): 1411\u20131473 (1997).","DOI":"10.1137\/S0097539796300921"},{"key":"7","doi-asserted-by":"publisher","unstructured":"D. W. Berry, A. M. Childs, and R. Kothari. ``Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters''. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, page 792\u2013809, (2015), DOI: 10.1109\/focs.2015.54.","DOI":"10.1109\/focs.2015.54"},{"key":"8","doi-asserted-by":"publisher","unstructured":"H. Blier and A. Tapp. ``All Languages in NP Have Very Short Quantum Proofs''. In 2009 Third International Conference on Quantum, Nano and Micro Technologies, pages 34\u201337, (2009), DOI: 10.1109\/ICQNM.2009.21.","DOI":"10.1109\/ICQNM.2009.21"},{"key":"9","doi-asserted-by":"publisher","unstructured":"A. R. Brown and L. Susskind. ``Second law of quantum complexity''. Phys. Rev. D 97: 086015 (2018).","DOI":"10.1103\/PhysRevD.97.086015"},{"key":"10","doi-asserted-by":"publisher","unstructured":"A. R. Brown and L. Susskind. ``Complexity geometry of a single qubit''. Phys. Rev. D 100: 046020 (2019).","DOI":"10.1103\/PhysRevD.100.046020"},{"key":"11","doi-asserted-by":"publisher","unstructured":"K. Bu, R. J. Garcia, A. Jaffe, D. E. Koh, and L. Li. ``Complexity of Quantum Circuits via Sensitivity, Magic, and Coherence''. Communications in Mathematical Physics 405(7) (2024).","DOI":"10.1007\/s00220-024-05030-6"},{"key":"12","unstructured":"E. Caglioti, F. Golse, and T. Paul. ``Towards Optimal Transport for Quantum Densities'', (2021). Available online: https:\/\/arxiv.org\/abs\/2101.03256."},{"key":"13","doi-asserted-by":"publisher","unstructured":"E. Campbell. ``Random Compiler for Fast Hamiltonian Simulation''. Physical Review Letters 123(7) (2019).","DOI":"10.1103\/physrevlett.123.070503"},{"key":"14","doi-asserted-by":"publisher","unstructured":"E. A. Carlen and J. Maas. ``Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance''. Journal of Functional Analysis 273(5): 1810\u20131869 (2017).","DOI":"10.1016\/j.jfa.2017.05.003"},{"key":"15","doi-asserted-by":"publisher","unstructured":"E. A. Carlen and J. Maas. ``Non-commutative Calculus, Optimal Transport and Functional Inequalities in Dissipative Quantum Systems''. Journal of Statistical Physics 178(2): 319\u2013378 (2019).","DOI":"10.1007\/s10955-019-02434-w"},{"key":"16","unstructured":"C.-F. Chen, J. Haah, J. Haferkamp, Y. Liu, T. Metger, and X. Tan. ``Incompressibility and spectral gaps of random circuits'', (2024). Available online: https:\/\/arxiv.org\/abs\/2406.07478."},{"key":"17","doi-asserted-by":"publisher","unstructured":"A. M. Childs, A. Ostrander, and Y. Su. ``Faster quantum simulation by randomization''. Quantum 3: 182 (2019).","DOI":"10.22331\/q-2019-09-02-182"},{"key":"18","doi-asserted-by":"publisher","unstructured":"A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. ``Theory of Trotter Error with Commutator Scaling''. Phys. Rev. X 11: 011020 (2021).","DOI":"10.1103\/PhysRevX.11.011020"},{"key":"19","doi-asserted-by":"crossref","unstructured":"A. Connes, J. Cuntz, and M. A. Rieffel. ``Noncommutative geometry''. Oberwolfach Reports 6(3): 2271\u20132334 (2010).","DOI":"10.4171\/owr\/2009\/41"},{"key":"20","doi-asserted-by":"publisher","unstructured":"A. Connes and J. Lott. ``The metric aspect of noncommutative geometry''. In New symmetry principles in quantum field theory, pages 53\u201393. Springer (1992).","DOI":"10.1007\/978-1-4615-3472-3_3"},{"key":"21","doi-asserted-by":"publisher","unstructured":"G. De Palma, M. Marvian, D. Trevisan, and S. Lloyd. ``The Quantum Wasserstein Distance of Order 1''. IEEE Transactions on Information Theory 67(10): 6627\u20136643 (2021).","DOI":"10.1109\/tit.2021.3076442"},{"key":"22","doi-asserted-by":"publisher","unstructured":"D. Deutsch and R. Penrose. ``Quantum theory, the Church\u2013Turing principle and the universal quantum computer''. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400(1818): 97\u2013117 (1985).","DOI":"10.1098\/rspa.1985.0070"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Z. Ding, M. Junge, P. Schleich, and P. Wu. ``Lower Bound for Simulation Cost of Open Quantum Systems: Lipschitz Continuity Approach''. Communications in Mathematical Physics 406(3) (2025).","DOI":"10.1007\/s00220-025-05240-6"},{"key":"24","doi-asserted-by":"publisher","unstructured":"A. Dymarsky and M. Smolkin. ``Krylov complexity in conformal field theory''. Physical Review D 104(8) (2021).","DOI":"10.1103\/physrevd.104.l081702"},{"key":"25","doi-asserted-by":"publisher","unstructured":"L. Fortnow and J. Rogers. ``Complexity Limitations on Quantum Computation''. Journal of Computer and System Sciences 59(2): 240\u2013252 (1999).","DOI":"10.1006\/jcss.1999.1651"},{"key":"26","doi-asserted-by":"publisher","unstructured":"L. Gao, M. Junge, and N. LaRacuente. ``Fisher information and logarithmic Sobolev inequality for matrix-valued functions''. Annales Henri Poincar\u00e9 21(11): 3409\u20133478 (2020).","DOI":"10.1007\/s00023-020-00947-9"},{"key":"27","doi-asserted-by":"publisher","unstructured":"L. Gao, M. Junge, and N. LaRacuente. ``Relative entropy for von Neumann subalgebras''. Internat. J. Math. 31(6): 2050046, 35 (2020).","DOI":"10.1142\/S0129167X20500469"},{"key":"28","unstructured":"L. Gao, M. Junge, N. LaRacuente, and H. Li. ``Relative entropy decay and complete positivity mixing time'', (2023). Available online: https:\/\/arxiv.org\/abs\/2209.11684."},{"key":"29","doi-asserted-by":"publisher","unstructured":"L. Gao and C. Rouz\u00e9. ``Coarse Ricci curvature of quantum channels''. Journal of Functional Analysis 286(8): 110336 (2024).","DOI":"10.1016\/j.jfa.2024.110336"},{"key":"30","unstructured":"J. Haferkamp. ``On the moments of random quantum circuits and robust quantum complexity'', (2023). Available online: https:\/\/arxiv.org\/abs\/2303.16944."},{"key":"31","doi-asserted-by":"publisher","unstructured":"J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, and N. Yunger Halpern. ``Linear growth of quantum circuit complexity''. Nature Physics 18(5): 528\u2013532 (2022).","DOI":"10.1038\/s41567-022-01539-6"},{"key":"32","doi-asserted-by":"publisher","unstructured":"A. Hahn, P. Hartung, D. Burgarth, P. Facchi, and K. Yuasa. ``Lower Bounds for the Trotter Error'', (2024). Available online: https:\/\/arxiv.org\/abs\/2410.03059.","DOI":"10.1103\/PhysRevA.111.022417"},{"key":"33","doi-asserted-by":"publisher","unstructured":"N. Y. Halpern, N. B. Kothakonda, J. Haferkamp, A. Munson, J. Eisert, and P. Faist. ``Resource theory of quantum uncomplexity''. Physical Review A 106(6): 062417 (2022).","DOI":"10.1103\/PhysRevA.106.062417"},{"key":"34","doi-asserted-by":"publisher","unstructured":"A. W. Harrow and A. Montanaro. ``Extremal eigenvalues of local Hamiltonians''. Quantum 1: 6 (2017).","DOI":"10.22331\/q-2017-04-25-6"},{"key":"35","doi-asserted-by":"publisher","unstructured":"S. Hollands and A. Ranallo. ``Channel Divergences and Complexity in Algebraic QFT''. Communications in Mathematical Physics 404: 927\u2013962 (2023).","DOI":"10.1007\/s00220-023-04855-x"},{"key":"36","doi-asserted-by":"publisher","unstructured":"R. A. Jefferson and R. C. Myers. ``Circuit complexity in quantum field theory''. Journal of High Energy Physics 2017(10) (2017).","DOI":"10.1007\/jhep10(2017)107"},{"key":"37","doi-asserted-by":"publisher","unstructured":"M. Junge and J. Parcet. Mixed-norm inequalities and operator space $L_p$ embedding theory. volume 203, American Mathematical Society (2010).","DOI":"10.1090\/S0065-9266-09-00570-5"},{"key":"38","unstructured":"M. Junge and P. Wu. ``Stability property for the quantum jump operators of an open system'', (2022). Available online: https:\/\/arxiv.org\/abs\/2211.07527."},{"key":"39","unstructured":"H. Klauck. ``Quantum Communication Complexity'', (2000). Available online: https:\/\/arxiv.org\/abs\/quant-ph\/0005032."},{"key":"40","doi-asserted-by":"publisher","unstructured":"L. Li, K. Bu, D. E. Koh, A. Jaffe, and S. Lloyd. ``Wasserstein Complexity of Quantum Circuits'', (2022). Available online: https:\/\/arxiv.org\/abs\/2208.06306 DownloadArticle PDF.","DOI":"10.1088\/1751-8121\/ade381"},{"key":"41","doi-asserted-by":"publisher","unstructured":"G. Lindblad. ``On the generators of quantum dynamical semigroups''. Communications in mathematical physics 48: 119\u2013130 (1976).","DOI":"10.1007\/BF01608499"},{"key":"42","doi-asserted-by":"publisher","unstructured":"M. A. Nielsen. ``A Geometric Approach to Quantum Circuit Lower Bounds''. Quantum Information and Computation 6(3): 213\u2013262 (2006).","DOI":"10.26421\/QIC6.3-2"},{"key":"43","doi-asserted-by":"publisher","unstructured":"M. A. Nielsen, M. R. Dowling, M. Gu, and A. C. Doherty. ``Optimal control, geometry, and quantum computing''. Phys. Rev. A 73: 062323 (2006).","DOI":"10.1103\/PhysRevA.73.062323"},{"key":"44","doi-asserted-by":"publisher","unstructured":"M. A. Nielsen, M. R. Dowling, M. Gu, and A. C. Doherty. ``Quantum Computation as Geometry''. Science 311(5764): 1133\u20131135 (2006).","DOI":"10.1126\/science.1121541"},{"key":"45","doi-asserted-by":"publisher","unstructured":"A. Nietner, M. Ioannou, R. Sweke, R. Kueng, J. Eisert, M. Hinsche, and J. Haferkamp. ``On the average-case complexity of learning output distributions of quantum circuits''. Quantum 9: 1883 (2025).","DOI":"10.22331\/q-2025-10-13-1883"},{"key":"46","doi-asserted-by":"publisher","unstructured":"R. Oliveira and B. M. Terhal. ``The Complexity of Quantum Spin Systems on a Two-Dimensional Square Lattice''. Quantum Info. Comput. 8(10): 900\u2013924 (2008).","DOI":"10.26421\/QIC8.10-2"},{"key":"47","doi-asserted-by":"publisher","unstructured":"G. D. Palma and D. Trevisan. ``Quantum Optimal Transport: Quantum Channels and Qubits'', (2023). Available online: https:\/\/arxiv.org\/abs\/2307.16268.","DOI":"10.1007\/978-3-031-50466-2_4"},{"key":"48","doi-asserted-by":"publisher","unstructured":"D. E. Parker, X. Cao, A. Avdoshkin, T. Scaffidi, and E. Altman. ``A Universal Operator Growth Hypothesis''. Physical Review X 9(4) (2019).","DOI":"10.1103\/physrevx.9.041017"},{"key":"49","doi-asserted-by":"publisher","unstructured":"V. Paulsen. Completely Bounded Maps and Operator Algebras. Cambridge University Press (2003).","DOI":"10.1017\/CBO9780511546631"},{"key":"50","doi-asserted-by":"publisher","unstructured":"M. Pimsner and S. Popa. ``Entropy and index for subfactors''. In Annales scientifiques de l'Ecole normale sup\u00e9rieure, volume 19, pages 57\u2013106, (1986), DOI: 10.24033\/asens.1504.","DOI":"10.24033\/asens.1504"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Qiskit contributors. ``Qiskit: An Open-source Framework for Quantum Computing'', (2023). DOI: 10.5281\/zenodo.2573505.","DOI":"10.5281\/zenodo.2573505"},{"key":"52","doi-asserted-by":"publisher","unstructured":"E. Rabinovici, A. Sanchez-Garrido, R. Shir, and J. Sonner. ``Operator complexity: a journey to the edge of Krylov space''. Journal of High Energy Physics (62) (2021).","DOI":"10.1007\/JHEP06(2021)062"},{"key":"53","doi-asserted-by":"publisher","unstructured":"E. Rabinovici, A. Sanchez-Garrido, R. Shir, and J. Sonner. ``Krylov complexity from integrability to chaos''. Journal of High Energy Physics (151) (2022).","DOI":"10.1007\/JHEP07(2022)151"},{"key":"54","doi-asserted-by":"publisher","unstructured":"M. A. Rieffel. ``Metrics on state spaces''. Documenta Mathematica 4: 559\u2013600 (1999).","DOI":"10.4171\/dm\/68"},{"key":"55","doi-asserted-by":"publisher","unstructured":"M. A. Rieffel. ``Compact quantum metric spaces''. Contemporary Mathematics 365: 315\u2013330 (2004).","DOI":"10.1090\/conm\/365\/06709"},{"key":"56","unstructured":"G. Rosenthal, H. Aaronson, S. Subramanian, A. Datta, and T. Gur. ``Quantum Channel Testing in Average-Case Distance'', (2024). Available online: https:\/\/arxiv.org\/abs\/2409.12566."},{"key":"57","doi-asserted-by":"publisher","unstructured":"B. Rosgen and J. Watrous. ``On the hardness of distinguishing mixed-state quantum computations''. In 20th Annual IEEE Conference on Computational Complexity (CCC'05), pages 344\u2013354, (2005), DOI: 10.1109\/CCC.2005.21.","DOI":"10.1109\/CCC.2005.21"},{"key":"58","doi-asserted-by":"publisher","unstructured":"E. St\u00f8rmer. ``Conditional expectations and projection maps of von Neumann algebras''. Operator Algebras and Applications pages 449\u2013461 (1997).","DOI":"10.1007\/978-94-011-5500-7_15"},{"key":"59","doi-asserted-by":"publisher","unstructured":"J. Watrous. ``PSPACE has constant-round quantum interactive proof systems''. Theoretical Computer Science 292(3): 575\u2013588 (2003).","DOI":"10.1016\/S0304-3975(01)00375-9"},{"key":"60","unstructured":"M. Wirth. ``A Noncommutative Transport Metric and Symmetric Quantum Markov Semigroups as Gradient Flows of the Entropy'', (2021). Available online: https:\/\/arxiv.org\/abs\/1808.05419."},{"key":"61","doi-asserted-by":"publisher","unstructured":"X.-M. Zhang and X. Yuan. ``Circuit complexity of quantum access models for encoding classical data''. npj Quantum Information 10(1) (2024).","DOI":"10.1038\/s41534-024-00835-8"},{"key":"62","doi-asserted-by":"publisher","unstructured":"K. Zyczkowski and W. Slomczynski. ``The Monge distance between quantum states''. Journal of Physics A: Mathematical and General 31(45): 9095\u20139104 (1998).","DOI":"10.1088\/0305-4470\/31\/45\/009"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-01-08-1960\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:16:06Z","timestamp":1767860166000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-01-08-1960\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":63,"URL":"https:\/\/doi.org\/10.22331\/q-2026-01-08-1960","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"article-number":"1960"}}