Polynomial Equivalence of Complexity Geometries

Adam R. Brown

doi:10.22331/q-2024-07-02-1391

Polynomial Equivalence of Complexity Geometries

Adam R. Brown

\vbox\center#1
Google Research (Blueshift), Mountain View, CA 94043, USA
Stanford Institute for Theoretical Physics and Department of Physics, \ Stanford University, Stanford, CA 94305, USA

Published:	2024-07-02, volume 8, page 1391
Eprint:	arXiv:2205.04485v3
Doi:	https://doi.org/10.22331/q-2024-07-02-1391
Citation:	Quantum 8, 1391 (2024).

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

Abstract

This paper proves the polynomial equivalence of a broad class of definitions of quantum computational complexity. We study right-invariant metrics on the unitary group—often called `complexity geometries' following the definition of quantum complexity proposed by Nielsen—and delineate the equivalence class of metrics that have the same computational power as quantum circuits. Within this universality class, any unitary that can be reached in one metric can be approximated in any other metric in the class with a slowdown that is at-worst polynomial in the length and number of qubits and inverse-polynomial in the permitted error. We describe the equivalence classes for two different kinds of error we might tolerate: Killing-distance error, and operator-norm error. All metrics in both equivalence classes are shown to have exponential diameter; all metrics in the operator-norm equivalence class are also shown to give an alternative definition of the quantum complexity class BQP.

My results extend those of Nielsen et al., who in 2006 proved that one particular metric is polynomially equivalent to quantum circuits. The Nielsen et al. metric is incredibly highly curved. I show that the greatly enlarged equivalence class established in this paper also includes metrics that have modest curvature. I argue that the modest curvature makes these metrics more amenable to the tools of differential geometry, and therefore makes them more promising starting points for Nielsen's program of using differential geometry to prove complexity lowerbounds.

In a previous paper my collaborators and I—inspired by the UV/IR decoupling that happens in the phenomenon of renormalization—conjectured that high- dimensional metrics that look very different at short scales will often nevertheless give rise at long scales to the same emergent effective geometry. The results of this paper provide evidence for those conjectures, since many complexity metrics that have radically different penalty factors and therefore radically different short- distance properties are shown to belong to the same long-distance equivalence class.

► BibTeX data

@article{Brown2024polynomial,
  doi = {10.22331/q-2024-07-02-1391},
  url = {https://doi.org/10.22331/q-2024-07-02-1391},
  title = {Polynomial {E}quivalence of {C}omplexity {G}eometries},
  author = {Brown, Adam R.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1391},
  month = jul,
  year = {2024}
}

► References

[1] Michael A. Nielsen, ``A geometric approach to quantum circuit lower bounds,'' arXiv:quant-ph/0502070.
https://doi.org/10.48550/arXiv.quant-ph/0502070
arXiv:quant-ph/0502070

[2] M. A. Nielsen, M. Dowling, M. Gu, and A. C. Doherty, ``Quantum Computation as Geometry'', Science 311, 1133 (2006), arXiv:quant-ph/0603161.
https://doi.org/10.1126/science.1121541
arXiv:quant-ph/0603161

[3] M. A. Nielsen, M. R. Dowling, M. Gu, and A. C. Doherty, ``Optimal control, geometry, and quantum computing'', Phys. Rev. A 73, 062323 (2006), arXiv:quant-ph/0603160.
https://doi.org/10.1103/PhysRevA.73.062323
arXiv:quant-ph/0603160

[4] Mark R. Dowling and Michael A. Nielsen, ``The geometry of quantum computation'' arXiv:quant-ph/0701004.
https://doi.org/10.48550/arXiv.quant-ph/0701004
arXiv:quant-ph/0701004

[5] Mile Gu, Andrew Doherty & Michael Nielsen ``Quantum control via geometry: An explicit example'', Physical Review A, 78 032327 (2008), arXiv:0808.3212 [quant-ph].
https://doi.org/10.1103/PhysRevA.78.032327
arXiv:0808.3212

[6] A. R. Brown, M. H. Freedman, H. W. Lin and L. Susskind, ``Effective Geometry, Complexity, and Universality,'' Nature, 622, 58-62 (2023) [arXiv:2111.12700].
https://doi.org/10.1038/s41586-023-06460-3
arXiv:2111.12700

[7] A. R. Brown, ``A quantum complexity lower bound from differential geometry,'' Nature Physics 19, no.3, 401-406 (2023) [arXiv:2112.05724 [hep-th]].
https://doi.org/10.1038/s41567-022-01884-6
arXiv:2112.05724

[8] A. R. Brown and L. Susskind, ``Complexity geometry of a single qubit,'' Phys. Rev. D 100, no. 4, 046020 (2019) [arXiv:1903.12621 [hep-th]].
https://doi.org/10.1103/PhysRevD.100.046020
arXiv:1903.12621

[9] Bin Li, Zu-Huan Yu, Shao-Ming Fei, ``Geometry of Quantum Computation with Qutrits'', Scientific Reports 3 2594 (2013), [arXiv:1309.3357].
https://doi.org/10.1038/srep02594
arXiv:1309.3357

[10] A. R. Brown, L. Susskind and Y. Zhao, ``Quantum Complexity and Negative Curvature,'' Phys. Rev. D 95, no. 4, 045010 (2017) [arXiv:1608.02612 [hep-th]].
https://doi.org/10.1103/PhysRevD.95.045010
arXiv:1608.02612

[11] A. R. Brown and L. Susskind, ``Second law of quantum complexity,'' Phys. Rev. D 97, no. 8, 086015 (2018) [arXiv:1701.01107 [hep-th]].
https://doi.org/10.1103/PhysRevD.97.086015
arXiv:1701.01107

[12] H. W. Lin, ``Cayley graphs and complexity geometry,'' [arXiv:1808.06620 [hep-th]].
https://doi.org/10.1007/JHEP02(2019)063
arXiv:1808.06620

[13] V. Balasubramanian, M. Decross, A. Kar and O. Parrikar, ``Quantum Complexity of Time Evolution with Chaotic Hamiltonians,'' [arXiv:1905.05765 [hep-th]].
https://doi.org/10.1007/JHEP01(2020)134
arXiv:1905.05765

[14] A. Bhattacharyya, P. Nandy and A. Sinha, ``Renormalized Circuit Complexity,'' Phys. Rev. Lett. 124, no.10, 101602 (2020) [arXiv:1907.08223 [hep-th]].
https://doi.org/10.1103/PhysRevLett.124.101602
arXiv:1907.08223

[15] H. W. Lin and L. Susskind, ``Complexity Geometry and Schwarzian Dynamics,'' [arXiv:1911.02603 [hep-th]].
https://doi.org/10.1007/JHEP01(2020)087
arXiv:1911.02603

[16] B. Yan and W. Chemissany, ``Quantum Chaos on Complexity Geometry,'' [arXiv:2004.03501 [quant-ph]].
https://doi.org/10.48550/arXiv.2004.03501
arXiv:2004.03501

[17] R. J. Caginalp and S. Leutheusser, ``Complexity in One- and Two-Qubit Systems,'' [arXiv:2010.15099 [hep-th]].
https://doi.org/10.48550/arXiv.2010.15099
arXiv:2010.15099

[18] R. Auzzi, S. Baiguera, G. B. De Luca, A. Legramandi, G. Nardelli and N. Zenoni, ``Geometry of quantum complexity,'' Phys. Rev. D 103, no.10, 106021 (2021) [arXiv:2011.07601 [hep-th]].
https://doi.org/10.1103/PhysRevD.103.106021
arXiv:2011.07601

[19] V. Balasubramanian, M. DeCross, A. Kar, Y. Li and O. Parrikar, ``Complexity growth in integrable and chaotic models,'' [arXiv:2101.02209 [hep-th]].
https://doi.org/10.1007/JHEP07(2021)011
arXiv:2101.02209

[20] V. B. Bulchandani and S. L. Sondhi, ``How smooth is quantum complexity?,'' [arXiv:2106.08324 [quant-ph]].
https://doi.org/10.1007/JHEP10(2021)230
arXiv:2106.08324

[21] Q. F. Wu, ``Sectional curvatures distribution of complexity geometry,'' [arXiv:2108.11621 [hep-th]].
https://doi.org/10.1007/JHEP08(2022)197
arXiv:2108.11621

[22] P. Basteiro, J. Erdmenger, P. Fries, F. Goth, I. Matthaiakakis and R. Meyer, ``Quantum complexity as hydrodynamics,'' Phys. Rev. D 106, no.6, 065016 (2022) [arXiv:2109.01152 [hep-th]].
https://doi.org/10.1103/PhysRevD.106.065016
arXiv:2109.01152

[23] S. Chapman, M. P. Heller, H. Marrochio and F. Pastawski, ``Toward a Definition of Complexity for Quantum Field Theory States,'' Phys. Rev. Lett. 120, no. 12, 121602 (2018) [arXiv:1707.08582 [hep-th]].
https://doi.org/10.1103/PhysRevLett.120.121602
arXiv:1707.08582

[24] R. Jefferson and R. C. Myers, ``Circuit complexity in quantum field theory,'' [arXiv:1707.08570 [hep-th]].
https://doi.org/10.1007/JHEP10(2017)107
arXiv:1707.08570

[25] R. Khan, C. Krishnan and S. Sharma, ``Circuit Complexity in Fermionic Field Theory,'' Phys. Rev. D 98, no.12, 126001 (2018) [arXiv:1801.07620 [hep-th]].
https://doi.org/10.1103/PhysRevD.98.126001
arXiv:1801.07620

[26] L. Hackl and R. C. Myers, ``Circuit complexity for free fermions,'' [arXiv:1803.10638 [hep-th]].
https://doi.org/10.1007/JHEP07(2018)139
arXiv:1803.10638

[27] A. Bhattacharyya, A. Shekar and A. Sinha, ``Circuit complexity in interacting QFTs and RG flows,'' [arXiv:1808.03105 [hep-th]].
https://doi.org/10.1007/JHEP10(2018)140
arXiv:1808.03105

[28] ``Quantum Computation and Quantum Information'', Michael A. Nielsen and Isaac L. Chuang, Cambridge University Press, Chapter 4.
https://doi.org/10.1017/CBO9780511976667

[29] E. Knill, ``Approximation by quantum circuits,'' [arXiv:quant-ph/9508006 [quant-ph]].
https://doi.org/10.48550/arXiv.quant-ph/9508006
arXiv:quant-ph/9508006

[30] A. Y. Kitaev, ``Quantum computations: algorithms and error correction'', Russ. Math. Surv., 52 (6) 1191-1249 (1997).
https://doi.org/10.1070/rm1997v052n06abeh002155

[31] C. M. Dawson & M. A. Nielsen, ``The Solovay-Kitaev algorithm'', arXiv:quantph/0505030 (2005).
https://doi.org/10.48550/arXiv.quant-ph/0505030
arXiv:quantph/0505030

[32] S. Lloyd, ``Universal Quantum Simulators'', Science 273 5278 (1996).
https://doi.org/10.1126/science.273.5278.1073

[33] https://en.wikipedia.org/wiki/Aircraft_principal_axes.
https://en.wikipedia.org/wiki/Aircraft_principal_axes

[34] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, ``Exponential improvement in precision for simulating sparse hamiltonians'', Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC 14 (2014).
https://doi.org/10.1145/2591796.2591854

[35] D. W. Berry, A. M. Childs, and R. Kothari, ``Hamiltonian simulation with nearly optimal dependence on all parameters'', IEEE 56th Annual Symposium on Foundations of Computer Science (2015).
https://doi.org/10.1109/FOCS.2015.54

[36] G. H. Low and I. L. Chuang, ``Optimal hamiltonian simulation by quantum signal processing'', Phys. Rev. Lett. 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501

[37] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, ``Simulating hamiltonian dynamics with a truncated taylor series'', Phys. Rev. Lett. 114, 090502 (2015).
https://doi.org/10.1103/PhysRevLett.114.090502

[38] G. H. Low and I. L. Chuang, ``Hamiltonian Simulation by Qubitization'', Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163

[39] L. Susskind, ``Computational Complexity and Black Hole Horizons,'' Fortsch. Phys. 64, 24 (2016) arXiv:1402.5674 [hep-th]], [arXiv:1403.5695 [hep-th].
https://doi.org/10.48550/arXiv.1403.5695
arXiv:1402.5674

[40] D. Stanford and L. Susskind, ``Complexity and Shock Wave Geometries,'' Phys. Rev. D 90, no. 12, 126007 (2014) [arXiv:1406.2678 [hep-th]].
https://doi.org/10.1103/PhysRevD.90.126007
arXiv:1406.2678

[41] A. R. Brown, D. A. Roberts, L. Susskind, B. Swingle and Y. Zhao, ``Holographic Complexity Equals Bulk Action?,'' Phys. Rev. Lett. 116, no. 19, 191301 (2016) [arXiv:1509.07876 [hep-th]].
https://doi.org/10.1103/PhysRevLett.116.191301
arXiv:1509.07876

[42] A. R. Brown, D. A. Roberts, L. Susskind, B. Swingle and Y. Zhao, ``Complexity, action, and black holes,'' Phys. Rev. D 93, no. 8, 086006 (2016) [arXiv:1512.04993 [hep-th]].
https://doi.org/10.1103/PhysRevD.93.086006
arXiv:1512.04993

[43] M. Gromov, ``Carnot-carathéodory spaces seen from within'', Sub-Riemannian geometry, pages 79–323, Springer (1996).
https://www.ihes.fr/~gromov/wp-content/uploads/2018/08/carnot_caratheodory.pdf

[44] J. Milnor, ``Curvatures of Left Invariant Metrics on Lie Groups'', Advances in Mathematics 21, 293-329 (1976).
https://doi.org/10.1016/S0001-8708(76)80002-3

[45] D. Berry, G. Ahokas, R. Cleve, & B. Sanders, ``Efficient quantum algorithms for simulating sparse Hamiltonians'', Communications in Mathematical Physics 270, 359 (2007) [arXiv:0508139 [quant-ph]].
https://doi.org/10.1007/s00220-006-0150-x
arXiv:0508139

[46] D. Wecker, B. Bauer, B. Clark, M. Hastings, M. Troyer, ``Gate-count estimates for performing quantum chemistry on small quantum computers'', Physical Review A. 90(2), 022305 (2014) [arXiv:1312.1695].
https://doi.org/10.1103/PhysRevA.90.022305
arXiv:1312.1695

[47] A. Childs, Y. Su, ``Nearly optimal lattice simulation by product formulas'', Phys. Rev. Lett. 123, 050503 (2019) [arXiv:1901.00564].
https://doi.org/10.1103/PhysRevLett.123.050503
arXiv:1901.00564

[48] I. Kivlichan, et al., ``Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization'', Quantum 4, 296 (2020) [arXiv:1902.10673].
https://doi.org/10.22331/q-2020-07-16-296
arXiv:1902.10673

[49] D. Layden, ``First-Order Trotter Error from a Second-Order Perspective,'' Phys. Rev. Lett. 128, no.21, 210501 (2022) [arXiv:2107.08032 [quant-ph]].
https://doi.org/10.1103/PhysRevLett.128.210501
arXiv:2107.08032

[50] Q. Zhao, Y. Zhou, A. F. Shaw, T. Li and A. M. Childs, ``Hamiltonian Simulation with Random Inputs,'' Phys. Rev. Lett. 129, no.27, 270502 (2022) [arXiv:2111.04773 [quant-ph]].
https://doi.org/10.1103/PhysRevLett.129.270502
arXiv:2111.04773

[51] C. Chen & F. Brandão, ``Average-case Speedup for Product Formulas'', [arXiv:2111.05324].
https://doi.org/10.48550/arXiv.2111.05324
arXiv:2111.05324

Cited by

[1] Michał Oszmaniec, Marcin Kotowski, Michał Horodecki, and Nicholas Hunter-Jones, "Saturation and Recurrence of Quantum Complexity in Random Local Quantum Dynamics", Physical Review X 14 4, 041068 (2024).

[2] Vijay Balasubramanian, Javier M. Magan, Poulami Nandi, and Qingyue Wu, "Spread complexity and the saturation of wormhole size", Physical Review D 113 4, 046004 (2026).

[3] Stefano Baiguera, Shira Chapman, Giuseppe Policastro, and Tal Schwartzman, "The Complexity of Being Entangled", Quantum 8, 1472 (2024).

[4] Sergio E. Aguilar-Gutierrez, "Towards complexity in de Sitter space from the doubled-scaled Sachdev-Ye-Kitaev model", Journal of High Energy Physics 2024 10, 107 (2024).

[5] Stefano Baiguera, Vijay Balasubramanian, Pawel Caputa, Shira Chapman, Jonas Haferkamp, Michal P. Heller, and Nicole Yunger Halpern, "Quantum complexity in gravity, quantum field theory, and quantum information science", Physics Reports 1159, 1 (2026).

[6] Stefano Baiguera, Nicolas Chagnet, Shira Chapman, and Osher Shoval, "CFT complexity and penalty factors", Journal of High Energy Physics 2026 2, 247 (2026).

[7] C. Jess Riedel, "Wavefunction branches demand a definition!", Quantum Views 9, 85 (2025).

[8] Stefano Baiguera, Vijay Balasubramanian, Pawel Caputa, Shira Chapman, Jonas Haferkamp, Michal P. Heller, and Nicole Yunger Halpern, "Quantum complexity in gravity, quantum field theory, and quantum information science", arXiv:2503.10753, (2025).

[9] Adam R. Brown, Michael H. Freedman, Henry W. Lin, and Leonard Susskind, "Universality in long-distance geometry and quantum complexity", Nature 622 7981, 58 (2023).

[10] Johanna Erdmenger, Anna-Lena Weigel, Marius Gerbershagen, and Michal P. Heller, "From complexity geometry to holographic spacetime", Physical Review D 108 10, 106020 (2023).

[11] S. E. Aguilar-Gutierrez, "De Sitter space, complexity, and the double-scaled SYK model", arXiv:2406.19089, (2024).

[12] Farzad Omidi, "Generalized volume-complexity for two-sided hyperscaling violating black branes", Journal of High Energy Physics 2023 1, 105 (2023).

[13] C. Jess Riedel, "Wavefunction branches demand a definition!", arXiv:2506.15663, (2025).

[14] Qi-Feng Wu, "Sectional curvatures distribution of complexity geometry", Journal of High Energy Physics 2022 8, 197 (2022).

[15] S. Aravinda and Ranjan Modak, "Complexity growth for one-dimensional free-fermionic lattice models", Physical Review B 108 6, 064309 (2023).

[16] Adam R. Brown and Michael H. Freedman, "Enhanced Bishop-Gromov Theorem", arXiv:2209.09288, (2022).

[17] Jonathan J. Heckman, Rebecca J. Hicks, and Chitraang Murdia, "Generalized Complexity Distances and Non-Invertible Symmetries", arXiv:2604.14275, (2026).

[18] Mike Freedman, "Critical Metrics and Covering Number", arXiv:2205.13638, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 04:10:24) and SAO/NASA ADS (last updated successfully 2026-08-09 13:37:31). 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-08-10 04:10:24: 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.