Random Regular Graph States Are Complex at Almost Any Depth
PRX Quantum · 24.11.2025 · 6 (4)
DOI: 10.1103/52xz-3hpc ↗Kurz gefasst
Fachartikel in der Zeitschrift PRX Quantum, online erschienen am 24.11.2025. Verfasst von Soumik Ghosh und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 92 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Simons Institute for the Theory of Computing, Dutch Research Council, Quantum Software Consortium.
Abstract (Originalsprache)
Graph states are fundamental objects in the theory of quantum information due to their simple classical description and rich entanglement structure. They are also intimately related to instantaneous quantum polynomial-time (IQP) circuits, which have applications in quantum pseudorandomness and quantum advantage. For us, they are a toy model to understand the relation between circuit connectivity, entanglement structure, and computational complexity. In the worst case, a strict dichotomy in the computational universality of such graph states appears as a function of the degree d of a regular graph state [Ghosh , Phys. Rev. Lett. 131, 030601 (2023)]. In this paper, we study the average-case complexity of simulating random graph states of varying degree when measured in random product bases and give distinct evidence that a similar complexity-theoretic dichotomy exists in the average case. Specifically, we consider random d -regular graph states and prove three distinct results: First, we show two families of IQP circuits of depth d and show that they anticoncentrate for any 2 < d = o ( n 1 / 2 ) when measured in a random X - Y plane product basis. This implies anticoncentration for random constant-regular graph states. Second, in the regime d = Θ ( n c ) with c ∈ ( 0 , 1 ) , we prove that random d -regular graph states contain polynomially large grid graphs as induced subgraphs with high probability. This implies that they are universal resource states for measurement-based computation. Third, in the regime of high degree ( d ∼ n / 2 ), we show that random graph states are not sufficiently entangled to be trivially classically simulable, unlike Haar-random states. Proving the three results requires different techniques—the analysis of a classical statistical-mechanics model using Krawtchouck polynomials, graph-theoretic analysis using the switching method, and analysis of the ranks of submatrices of random adjacency matrices, respectively.
Förderung
- Simons Institute for the Theory of Computing
- Dutch Research Council
- Quantum Software Consortium
Zitieren
APA
Ghosh, S., Hangleiter, D., & Helsen, J. (2025). Random Regular Graph States Are Complex at Almost Any Depth. PRX Quantum, 6(4). https://doi.org/10.1103/52xz-3hpc
Vancouver
Ghosh S, Hangleiter D, Helsen J. Random Regular Graph States Are Complex at Almost Any Depth. PRX Quantum. 2025;6(4). doi:10.1103/52xz-3hpc
BibTeX
@article{Ghosh2025,
author = {Ghosh, Soumik and Hangleiter, Dominik and Helsen, Jonas},
title = {Random Regular Graph States Are Complex at Almost Any Depth},
journal = {PRX Quantum},
year = {2025},
volume = {6},
number = {4},
doi = {10.1103/52xz-3hpc}
}
EUVIMED