Random Regular Graph States Are Complex at Almost Any Depth

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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"> <a:mi>d</a:mi> </a:math> 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 <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"> <c:mi>d</c:mi> </c:math> -regular graph states and prove three distinct results: First, we show two families of IQP circuits of depth <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"> <e:mi>d</e:mi> </e:math> and show that they anticoncentrate for any <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"> <g:mn>2</g:mn> <g:mo><</g:mo> <g:mi>d</g:mi> <g:mo>=</g:mo> <g:mi>o</g:mi> <g:mo stretchy="false">(</g:mo> <g:msup> <g:mi>n</g:mi> <g:mrow> <g:mn>1</g:mn> <g:mo>/</g:mo> <g:mn>2</g:mn> </g:mrow> </g:msup> <g:mo stretchy="false">)</g:mo> </g:math> when measured in a random <k:math xmlns:k="http://www.w3.org/1998/Math/MathML" display="inline"> <k:mi>X</k:mi> </k:math> - <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline"> <m:mi>Y</m:mi> </m:math> plane product basis. This implies anticoncentration for random constant-regular graph states. Second, in the regime <o:math xmlns:o="http://www.w3.org/1998/Math/MathML" display="inline"> <o:mi>d</o:mi> <o:mo>=</o:mo> <o:mi mathvariant="normal">Θ</o:mi> <o:mo stretchy="false">(</o:mo> <o:msup> <o:mi>n</o:mi> <o:mi>c</o:mi> </o:msup> <o:mo stretchy="false">)</o:mo> </o:math> with <t:math xmlns:t="http://www.w3.org/1998/Math/MathML" display="inline"> <t:mi>c</t:mi> <t:mo>∈</t:mo> <t:mo stretchy="false">(</t:mo> <t:mn>0</t:mn> <t:mo>,</t:mo> <t:mn>1</t:mn> <t:mo stretchy="false">)</t:mo> </t:math> , we prove that random <x:math xmlns:x="http://www.w3.org/1998/Math/MathML" display="inline"> <x:mi>d</x:mi> </x:math> -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 ( <z:math xmlns:z="http://www.w3.org/1998/Math/MathML" display="inline"> <z:mi>d</z:mi> <z:mo>∼</z:mo> <z:mi>n</z:mi> <z:mo>/</z:mo> <z:mn>2</z:mn> </z:math> ), 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.