Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.12472

Stabilizer complexity and the Python's lunch

Abhirup Bhattacharya, Jatin Narde, Onkar Parrikar, Suprakash Paul

hep-thquant-phSubmitted Aug 12, 2026• Announced Aug 14, 2026• 2 citations
arXivHTMLPDF

Abstract

In this note, we study the stabilizer complexity of the reduced density matrix corresponding to one side of a partially entangled thermal (PET) state with fixed energy boundary conditions in a holographic CFT. In particular, we study Wigner negativity, an operationally meaningful magic monotone which can be interpreted as the complexity of classically simulating any quantum circuit preparation of the reduced state on the subregion. Using assumptions on the pseudorandomness of the CFT spectrum and the heavy operator insertion, we observe that the Wigner negativity of the PET state relative to the microcanonical density matrix at the given energy is given by $\exp\left[\frac{1}{8G_N}(A_{\text{out}} - A_{\text{min}})\right]$, where $A_{\text{out}}$ is the area of the outer extremal surface, while $A_{\text{min}}$ is the area of the minimal extremal surface. Thus, the stabilizer complexity of the reduced density matrix on the boundary subregion is $O(1)$ in the absence of a python's lunch, but gets exponentially enhanced in the presence of a python's lunch in the bulk geometry.

Comments
12 pages, 2 Figures

Related papers

Stabilizer complexity of Hawking radiation

Anonymous, Onkar Parrikar, Suprakash Paul +1 more

We study the complexity of Hawking radiation for an evaporating black hole from the perspective of the stabilizer theory of quantum computation. Specifically, we calculate Wigner negativity—a magic monotone that can be interpreted as a measure of the stabilizer complexity, or equivalently, the complexity of classical simulation—in various toy models for evaporating black holes. We first calculate the Wigner negativity of Hawking radiation in the Penington-Shenker-Stanford-Yang (PSSY) model directly using the gravitational path integral, and show that the negativity is O ( 1 ) before the Page transition, but becomes exponentially large past the Page transition. We also derive a universal, information theoretic formula for the negativity that interpolates between the two extremes. We then study the Wigner negativity of radiation in a dynamical model of black hole evaporation. In this case, the negativity shows a sharp spike at early times resulting from the coupling between the black hole and the radiation system, but at late times when the system settles down, we find that the negativity satisfies the same universal formula as in the PSSY model. Finally, we also propose a geometric formula for Wigner negativity in general holographic states using intuition from fixed area states and random tensor networks, and argue that a python’s lunch in the entanglement wedge implies a stabilizer complexity that is exponentially large in 1 8 G N times the difference between the areas corresponding to the outermost and minimal extremal surfaces.

arXiv:2510.18967•Physical review. D/Physical review. D.•Jul 13, 2026•6 citations

A world without pythons would be so simple

Netta Engelhardt, Geoff Penington, Arvin Shahbazi-Moghaddam

Abstract We show that bulk operators lying between the outermost extremal surface and the asymptotic boundary admit a simple boundary reconstruction in the classical limit. This is the converse of the Python’s lunch conjecture, which proposes that operators with support between the minimal and outermost (quantum) extremal surfaces—e.g. the interior Hawking partners—are highly complex. Our procedure for reconstructing this ‘simple wedge’ is based on the HKLL construction, but uses causal bulk propagation of perturbed boundary conditions on Lorentzian timefolds to expand the causal wedge as far as the outermost extremal surface. As a corollary, we establish the Simple Entropy proposal for the holographic dual of the area of a marginally trapped surface as well as a similar holographic dual for the outermost extremal surface. We find that the simple wedge is dual to a particular coarse-grained CFT state, obtained via averaging over all possible Python’s lunches. An efficient quantum circuit converts this coarse-grained state into a ‘simple state’ that is indistinguishable in finite time from a state with a local modular Hamiltonian. Under certain circumstances, the simple state modular Hamiltonian generates an exactly local flow; we interpret this result as a holographic dual of black hole uniqueness.

arXiv:2102.07774•Classical and Quantum Gravity•Oct 7, 2021•76 citations

Holographic dual of Bures metric and subregion complexity

Marius Gerbershagen, Juan Hernandez, Mikhail Alexandrovich Khramtsov +1 more

A bstract Within the AdS/CFT correspondence, computational complexity for reduced density matrices of holographic conformal field theories has been conjectured to be related to certain geometric observables in the dual gravity theory. We study this conjecture from both the gravity and field theory point of view. Specifically, we consider a measure of complexity associated to the Bures metric on the space of density matrices. We compute this complexity measure for mixed states associated to single intervals in descendant states of the vacuum in 2d CFTs. Moreover, we derive from first principles a geometric observable dual to the Bures metric which is localized in the entanglement wedge of the AdS spacetime associated to the quantum circuit on the boundary. Finally, we compare the Bures metric complexity measure with holographic subregion complexity within the “complexity=volume” paradigm for perturbatively small transformations of the vacuum. While there is no exact agreement between these two quantities, we find striking similarities as we vary the target state and interval size, suggesting that these quantities are closely related.

arXiv:2412.08707•Journal of High Energy Physics•Apr 9, 2025•6 citations

Holographic pseudoentanglement and the complexity of the AdS/CFT dictionary

Chris Akers, Adam Bouland, Lijie Chen +3 more

The `quantum gravity in the lab' paradigm suggests that quantum computers might shed light on quantum gravity by simulating the CFT side of the AdS/CFT correspondence and mapping the results to the AdS side. This relies on the assumption that the duality map (the `dictionary') is efficient to compute. In this work, we show that the complexity of the AdS/CFT dictionary is surprisingly subtle: there might be cases in which one can efficiently apply operators to the CFT state (a task we call 'operator reconstruction') without being able to extract basic properties of the dual bulk state such as its geometry (which we call 'geometry reconstruction'). Geometry reconstruction corresponds to the setting where we want to extract properties of a completely unknown bulk dual from a simulated CFT boundary state. We demonstrate that geometry reconstruction may be generically hard due to the connection between geometry and entanglement in holography. In particular we construct ensembles of states whose entanglement approximately obey the Ryu-Takayanagi formula for arbitrary geometries, but which are nevertheless computationally indistinguishable. This suggests that even for states with the special entanglement structure of holographic CFT states, geometry reconstruction might be hard. This result should be compared with existing evidence that operator reconstruction is generically easy in AdS/CFT. A useful analogy for the difference between these two tasks is quantum fully homomorphic encryption (FHE): this encrypts quantum states in such a way that no efficient adversary can learn properties of the state, but operators can be applied efficiently to the encrypted state. We show that quantum FHE can separate the complexity of geometry reconstruction vs operator reconstruction, which raises the question whether FHE could be a useful lens through which to view AdS/CFT.

arXiv:2411.04978•Nov 7, 2024•21 citations

Entanglement Wedge Reconstruction without Holographic Quantum Error Correction

Seiji Terashima

Bulk reconstruction is a central problem in AdS/CFT, and entanglement wedge reconstruction is its subregion version. We argue that this subregion statement should be separated from the stronger holographic quantum error correction interpretation, in which one region-independent logical bulk operator has code-preserving representatives in several boundary regions. A simple locality argument shows that such a common reconstruction must commute with the code-preserving local algebras in the complementary regions. This is the mechanism realized in HaPPY-type codes: the erased regions are blind to a protected logical algebra. An ordinary finite $N$ holographic CFT does not have such a protected invisible sector for supergravity fields. Its low-energy local observables, in particular, suitably smeared stress tensors, detect the physical support and gravitational dressing of ordinary bulk operators, up to possible center or superselection data. Thus, there is no such holographic quantum error correction and the $N=\infty$ agreement of global and subregion HKLL formulae is a free-theory statement. What remains is entanglement wedge reconstruction without holographic quantum error correction, or subregion complementarity: each boundary region has its own code-preserving low-energy algebra and its own region-adapted bulk interpretation, rather than a shared logical operator.

hep-thCross-listedarXiv:2607.08684•Jul 10, 2026

Complexity and entanglement in non-local computation and holography

Alex May

Does gravity constrain computation? We study this question using the AdS/CFT correspondence, where computation in the presence of gravity can be related to non-gravitational physics in the boundary theory. In AdS/CFT, computations which happen locally in the bulk are implemented in a particular non-local form in the boundary, which in general requires distributed entanglement. In more detail, we recall that for a large class of bulk subregions the area of a surface called the ridge is equal to the mutual information available in the boundary to perform the computation non-locally. We then argue the complexity of the local operation controls the amount of entanglement needed to implement it non-locally, and in particular complexity and entanglement cost are related by a polynomial. If this relationship holds, gravity constrains the complexity of operations within these regions to be polynomial in the area of the ridge.

arXiv:2204.00908•Quantum•Nov 28, 2022•34 citations
In this note, we study the stabilizer complexity of the reduced density matrix corresponding to one side of a partially entangled thermal (PET) state with fixed energy boundary conditions in a holographic CFT. In particular, we study Wigner negativity, an operationally meaningful magic monotone which can be interpreted as the complexity of classically simulating any quantum circuit preparation of the reduced state on the subregion. Using assumptions on the pseudorandomness of the CFT spectrum and the heavy operator insertion, we observe that the Wigner negativity of the PET state relative to the microcanonical density matrix at the given energy is given by exp⁡[18GN(Aout−Amin)]\exp\left[\frac{1}{8G_N}(A_{\text{out}} - A_{\text{min}})\right]exp[8GN​1​(Aout​−Amin​)], where AoutA_{\text{out}}Aout​ is the area of the outer extremal surface, while AminA_{\text{min}}Amin​ is the area of the minimal extremal surface. Thus, the stabilizer complexity of the reduced density matrix on the boundary subregion is O(1)O(1)O(1) in the absence of a python's lunch, but gets exponentially enhanced in the presence of a python's lunch in the bulk geometry.
We study the complexity of Hawking radiation for an evaporating black hole from the perspective of the stabilizer theory of quantum computation. Specifically, we calculate Wigner negativity—a magic monotone that can be interpreted as a measure of the stabilizer complexity, or equivalently, the complexity of classical simulation—in various toy models for evaporating black holes. We first calculate the Wigner negativity of Hawking radiation in the Penington-Shenker-Stanford-Yang (PSSY) model directly using the gravitational path integral, and show that the negativity is O ( 1 ) before the Page transition, but becomes exponentially large past the Page transition. We also derive a universal, information theoretic formula for the negativity that interpolates between the two extremes. We then study the Wigner negativity of radiation in a dynamical model of black hole evaporation. In this case, the negativity shows a sharp spike at early times resulting from the coupling between the black hole and the radiation system, but at late times when the system settles down, we find that the negativity satisfies the same universal formula as in the PSSY model. Finally, we also propose a geometric formula for Wigner negativity in general holographic states using intuition from fixed area states and random tensor networks, and argue that a python’s lunch in the entanglement wedge implies a stabilizer complexity that is exponentially large in 1 8 G N times the difference between the areas corresponding to the outermost and minimal extremal surfaces.
Abstract We show that bulk operators lying between the outermost extremal surface and the asymptotic boundary admit a simple boundary reconstruction in the classical limit. This is the converse of the Python’s lunch conjecture, which proposes that operators with support between the minimal and outermost (quantum) extremal surfaces—e.g. the interior Hawking partners—are highly complex. Our procedure for reconstructing this ‘simple wedge’ is based on the HKLL construction, but uses causal bulk propagation of perturbed boundary conditions on Lorentzian timefolds to expand the causal wedge as far as the outermost extremal surface. As a corollary, we establish the Simple Entropy proposal for the holographic dual of the area of a marginally trapped surface as well as a similar holographic dual for the outermost extremal surface. We find that the simple wedge is dual to a particular coarse-grained CFT state, obtained via averaging over all possible Python’s lunches. An efficient quantum circuit converts this coarse-grained state into a ‘simple state’ that is indistinguishable in finite time from a state with a local modular Hamiltonian. Under certain circumstances, the simple state modular Hamiltonian generates an exactly local flow; we interpret this result as a holographic dual of black hole uniqueness.
A bstract Within the AdS/CFT correspondence, computational complexity for reduced density matrices of holographic conformal field theories has been conjectured to be related to certain geometric observables in the dual gravity theory. We study this conjecture from both the gravity and field theory point of view. Specifically, we consider a measure of complexity associated to the Bures metric on the space of density matrices. We compute this complexity measure for mixed states associated to single intervals in descendant states of the vacuum in 2d CFTs. Moreover, we derive from first principles a geometric observable dual to the Bures metric which is localized in the entanglement wedge of the AdS spacetime associated to the quantum circuit on the boundary. Finally, we compare the Bures metric complexity measure with holographic subregion complexity within the “complexity=volume” paradigm for perturbatively small transformations of the vacuum. While there is no exact agreement between these two quantities, we find striking similarities as we vary the target state and interval size, suggesting that these quantities are closely related.
The `quantum gravity in the lab' paradigm suggests that quantum computers might shed light on quantum gravity by simulating the CFT side of the AdS/CFT correspondence and mapping the results to the AdS side. This relies on the assumption that the duality map (the `dictionary') is efficient to compute. In this work, we show that the complexity of the AdS/CFT dictionary is surprisingly subtle: there might be cases in which one can efficiently apply operators to the CFT state (a task we call 'operator reconstruction') without being able to extract basic properties of the dual bulk state such as its geometry (which we call 'geometry reconstruction'). Geometry reconstruction corresponds to the setting where we want to extract properties of a completely unknown bulk dual from a simulated CFT boundary state. We demonstrate that geometry reconstruction may be generically hard due to the connection between geometry and entanglement in holography. In particular we construct ensembles of states whose entanglement approximately obey the Ryu-Takayanagi formula for arbitrary geometries, but which are nevertheless computationally indistinguishable. This suggests that even for states with the special entanglement structure of holographic CFT states, geometry reconstruction might be hard. This result should be compared with existing evidence that operator reconstruction is generically easy in AdS/CFT. A useful analogy for the difference between these two tasks is quantum fully homomorphic encryption (FHE): this encrypts quantum states in such a way that no efficient adversary can learn properties of the state, but operators can be applied efficiently to the encrypted state. We show that quantum FHE can separate the complexity of geometry reconstruction vs operator reconstruction, which raises the question whether FHE could be a useful lens through which to view AdS/CFT.
Bulk reconstruction is a central problem in AdS/CFT, and entanglement wedge reconstruction is its subregion version. We argue that this subregion statement should be separated from the stronger holographic quantum error correction interpretation, in which one region-independent logical bulk operator has code-preserving representatives in several boundary regions. A simple locality argument shows that such a common reconstruction must commute with the code-preserving local algebras in the complementary regions. This is the mechanism realized in HaPPY-type codes: the erased regions are blind to a protected logical algebra. An ordinary finite NNN holographic CFT does not have such a protected invisible sector for supergravity fields. Its low-energy local observables, in particular, suitably smeared stress tensors, detect the physical support and gravitational dressing of ordinary bulk operators, up to possible center or superselection data. Thus, there is no such holographic quantum error correction and the N=∞N=\inftyN=∞ agreement of global and subregion HKLL formulae is a free-theory statement. What remains is entanglement wedge reconstruction without holographic quantum error correction, or subregion complementarity: each boundary region has its own code-preserving low-energy algebra and its own region-adapted bulk interpretation, rather than a shared logical operator.
Does gravity constrain computation? We study this question using the AdS/CFT correspondence, where computation in the presence of gravity can be related to non-gravitational physics in the boundary theory. In AdS/CFT, computations which happen locally in the bulk are implemented in a particular non-local form in the boundary, which in general requires distributed entanglement. In more detail, we recall that for a large class of bulk subregions the area of a surface called the ridge is equal to the mutual information available in the boundary to perform the computation non-locally. We then argue the complexity of the local operation controls the amount of entanglement needed to implement it non-locally, and in particular complexity and entanglement cost are related by a polynomial. If this relationship holds, gravity constrains the complexity of operations within these regions to be polynomial in the area of the ridge.