# Quantum complexity The complexity of an operator measures the difficulty of constructing it using simple gates. More precisely, for a $K$-qubit system (having a $2^K$ dimensional Hilbert space), one can define the complexity of generating a unitary operator $V$ to be the smallest number of 2-qubit gates that can approximate this $V$. The quantum complexity can be very big, but it is upper bounded by $\exp K$. This is actually saturated for almost all unitary operators. For a two-sided black hole in holography, the complexity of the time evolution operators for each side, $U_L(t)$ and $U_R(t)$, typically increase linearly in time as $\mathcal{C}(t)=K t$before reaching the upper bound. Therefore, the complexity of the operator $U\left(t_L\right) U\left(t_R\right)$ will be$\mathcal{C}\left(t_L, t_R\right)=K\left|t_L+t_R\right|.$This led [[2014#Susskind (Feb)|Susskind]] to propose complexity = volume and subsequently other similar proposals. ## Reviews - [[2025#Baiguera, Balasubramanian, Caputa, Chapman, Haferkamp, Heller, Halpern (Review)]] ## Conjectures - CV (volume) - [[2014#Susskind (Feb)]] - [[2014#Stanford, Susskind]] - CA (action) - [[2015#Brown, Roberts, Susskind, Swingle, Zhao (Sep)]] - [[2015#Brown, Roberts, Susskind, Swingle, Zhao (Dec)]] - CV2.0 (spacetime volume) - [[2016#Couch, Fischler, Nguyen]] - complexity equals (anything)^2? - [[2021#Belin, Myers, Ruan, Sarosi, Speranza]] - [[2022#Belin, Myers, Ruan, Sarosi, Speranza]] ## Examples/models - [[0050 JT gravity|JT gravity]] - [[2018#Brown, Gharibyan, Lin, Susskind, Thorlacius, Zhao]] - [[2023#Bhattacharya, Bhattacharyya, Patra]] - [[2025#Miyaji, Ruan, Shibuya, Yano]]: non-perturbative ## Understanding it - [[2021#Pedraza, Russo, Svesko, Weller-Davies]] - using Lorentzian threads similar to [[0211 Bit thread|bit threads]] - [[AlishahihaBanerjeeKames-King2022]][](https://arxiv.org/pdf/2205.01150.pdf) - via replica trick - [[ChandraDeBoerFloryHellerHortnerRolph2021]] - on finite cut-off spacetimes as quantum circuit, with action given by the action - [[2025#Miyaji, Ruan, Shibuya, Yano]]: non-perturbative - see also: [[0196 Python's lunch]] ## Properties - positive complexity conjecture - [[EngelhardtFolkestad202109]][](https://arxiv.org/abs/2109.06883) - negative complexity when compact dimensions are included - [[EngelhardtFolkestad202111]][](https://arxiv.org/abs/2111.14897) - what exactly is the CFT complexity that is dual to bulk complexity? - [[YangAnNiuZhangKim2020]][](https://arxiv.org/pdf/2011.14636.pdf) - subregion complexity and measurements - [[2023#Jian, Zhang]] - geometric features - [[2024#Arora, Headrick, Lawrence, Sasieta, Wolfe]] ## Applications - probing singularity - [[2023#Jorstad, Myers, Ruan]] ## Extensions - non-perturbative - [[2021#Iliesiu, Mezei, Sarosi]]: including all-genus contributions JT gravity in the Euclidean section gives a plateau for the complexity growth, which is expected from the boundary - quantum corrections - [[EmparanFrassinoSasietaTomasevic2021]][](https://arxiv.org/pdf/2112.04860.pdf) - dS - [[JorstadMyersRuan2022]][](https://arxiv.org/abs/2202.10684) - Fubini-Study distance (a more quantitative proposal) - [[ErdmengerGerbershagenHellerWeigel2022]][](https://arxiv.org/abs/2212.00043) - geometric approach - [[Wu2021]][](https://arxiv.org/abs/2108.11621) - group cohomology - [[Czech2022]][](https://arxiv.org/pdf/2201.01303.pdf) - "cost" - [[ChandraDeBoerFloryHellerHortnerRolph2022]][](https://arxiv.org/pdf/2203.08842.pdf) ## Related - [[0196 Python's lunch]] <!--- ## Learning resources (Patrick Hayden) Scott Aaronson's Quantum Computing Since Democritus is a great read. It's a semipopular book rather than a monograph, but can teach you a lot. John Watrous has a survey/review from 2008 but it is perhaps more of a compendium than a pedagogical development: [https://arxiv.org/abs/0804.3401](https://arxiv.org/abs/0804.3401). There is a nice tradition in computer science of having students take "scribe notes" in classes, which are then shared. I find that they often provide a more efficient way into a subject than reading a whole book. The scribe notes for Scott Aaronson's 2010 quantum complexity course at MIT are available at [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-845-quantum-complexity-theory-fall-2010/lecture-notes/](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-845-quantum-complexity-theory-fall-2010/lecture-notes/). --->