Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure

Pseudoentanglement in constant depth explores how states prepared by shallow quantum circuits can possess entanglement structures that are computationally hard to estimate, separating this phenomenon from standard pseudorandomness. The core finding is the construction of publicly samplable families of 2D-local constant-depth circuits whose output states exhibit an additive entanglement entropy gap across a fixed cut, while the circuit descriptions remain computationally indistinguishable. This establishes a separation between pseudoentanglement and pseudorandomness in the shallow-circuit regime, yielding quantum hardness results for learning the entanglement structure of local Hamiltonians.

Key Findings and Theoretical Separation

The paper formally defines pseudoentangled states as those whose entanglement entropy across a specified cut cannot be estimated in quantum polynomial time (QPT). The central result is Theorem 1.1, which constructs efficiently samplable distributions over tuples of circuits and cuts such that the entropy gap between the low- and high-branch states, measured across the cut, satisfies an additive condition: "There exists a function ∆: N → R≥1 such that, with overwhelming probability over the sampled tuple, letting ψ low n⟩ = C low n0 n⟩, ψ high n⟩ = C high n0 n⟩, and ρb n = TrW n ψb n⟩ ⟨ψb n, b ∈ [low, high], one has S ρhigh n ≥ S ρlow n + ∆(n). Moreover, the gap can be chosen so that ∆(n) = ω(log n)." This demonstrates that pseudoentanglement is possible even when preparation circuits are public and of polynomial size, distinguishing it from pseudorandom states where the preparation circuit must be hidden.

Construction via Randomized Encoding

The construction relies on leveraging the quantum intractability of the Dense-Sparse Learning Parity with Noise (Dense-Sparse LPN) problem, introduced in [DJ25]. The main technical ingredient is a perfect randomized encoding of a dense linear map with bounded fan-in and bounded fan-out, formalized in Theorem 1.2. This encoding, denoted REM(x; r, s) = (w, z), preserves the entropy of the underlying linear map exactly: H(REM(X; R, S)) = mq + q(m − 1) + H(MX). The randomized encoding circuit itself is designed to be computable in constant depth with bounded fan-in and bounded fan-out gates.

Application to Hamiltonian Hardness

The existence of these pseudoentangled states is used to prove quantum hardness for learning the entanglement structure of local Hamiltonians.

1. For 2D local Hamiltonians, Theorem 1.3 shows that there exists an efficiently samplable distribution over tuples (Hlow n, Hhigh n, Wn) such that the ground states inherit the entanglement gap: S TrW n ϕhigh n⟩ ⟨ϕhigh n ≥ S TrW n ϕlow n⟩ ⟨ϕlow n + ∆(n).

2. For 1D local Hamiltonians, Theorem 1.4 similarly establishes hardness, showing that the task of learning the entanglement entropy to within constant additive error across a fixed cut is quantumly hard for 1D local Hamiltonians.

Cryptographic Corollary

A direct cryptographic consequence of the randomized encoding theorem is Theorem B.3, which yields a collision-resistant hash family. By assuming the hardness of random-code bSVPβ, the family HM defined by HM(x, r, s) = REM(Exp(x); r, s) is shown to be a collision-resistant hash family with bounded fan-in and bounded fan-out. This construction utilizes local low-weight embeddings (Definition B.2) as a black box.

Geometric Realization and Limitations

The 2D construction is realized by overlaying two one-dimensional dependency patterns in a row-and-column layout, using a constant-size plaquette for each matrix position (i, j). The circuit structure ensures that the resulting states are 2D-local and constant-depth. However, the paper notes limitations: the hidden cut is fixed and non-geometric. This restricts direct application to physically motivated settings like geometric cuts arising in quantum gravity research. Furthermore, while the entropy gap is additive, it does not preserve the multiplicative entropy ratio of ideal lossy-function calculations; instead, it preserves the additive gap exactly. The construction also relies on a specific source distribution (Bernoulli with bias t/m) for the analysis of Shannon entropy.

Alternative Construction

An alternative approach involves using biased Poor man’s GHZ states (PMGHZs) prepared in constant depth.

As a fastidious researcher, I have analyzed this paper, Pseudoentanglement in constant depth, by Alexandru Gheorghiu, and identified several high-impact avenues for improving AI systems. The core contribution is establishing a rigorous separation between computational pseudorandomness (PRSs/PRUs) and pseudoentanglement in the shallow-circuit regime, providing new hardness results based on post-quantum assumptions (Dense-Sparse LPN).

Here are the specific improvements to AI systems that can be derived from this research:

)1. Hardness of Learning Entanglement Structure for Quantum Models

The paper proves that learning the entanglement entropy across a fixed cut in 2D local constant-depth quantum circuits is quantumly hard, even when the preparation circuits are public (public-key pseudoentangled states).

• A new class of quantum models can be constructed where determining the entanglement structure of their ground states is computationally intractable for quantum computers.

• A specific focus on 2D local Hamiltonians suggests that AI/ML models describing physical systems (e.g., condensed matter physics, lattice models) could be modeled as Hamiltonians. This paper provides a theoretical tool to prove that learning the entanglement properties (which encode the phase or structure of the state) is hard, even if one knows the general class of local interactions and circuit depth.

)2. Robustness Against Circuit Learning Attacks

The construction allows for states whose entanglement entropy across a fixed cut cannot be estimated in quantum polynomial time (QPT). Furthermore, these states are implicitly public-key and not pseudorandom.

• AI/ML models that rely on the randomness of their internal state structure (e.g., certain types of quantum neural networks or complex generative models) can be designed to produce states that are computationally indistinguishable from random but possess a hidden, hard-to-estimate entanglement property.

• This provides a new theoretical guarantee for the security of such models: an attacker cannot efficiently determine the entanglement structure defining the state's complexity, even with access to polynomial resources.

)3. Enhanced Cryptographic Primitives via Randomized Encoding

The paper introduces a perfect randomized encoding scheme that computes complex linear maps (like those used in post-quantum cryptography based on LPN assumptions) using only constant-depth, bounded-fan-in/fan-out circuits.

• This allows for the construction of novel cryptographic primitives—such as collision-resistant hash functions (Theorem B.3)—that possess strong locality properties (bounded fan-in/out).

• AI systems can leverage this to build local cryptographic modules that are highly efficient in terms of gate complexity while maintaining a security level based on hard problems like random-code bSVP. This could lead to more compact, verifiable AI accelerators or secure hardware implementations where the randomness generation is inherently local and structured.

)4. Improved Phase Recognition in Physical Systems

The paper connects pseudoentanglement hardness to learning the entanglement structure of ground states of local Hamiltonians, particularly those with constant gaps (2D) or inverse-polynomial gaps (1D).

• AI/ML systems used for materials discovery or phase transition prediction can be framed as trying to learn the ground state properties of such Hamiltonians. The paper proves that learning the entanglement structure across a fixed cut is hard.

• This suggests that recognizing the phase or structural equivalence of two physical states (e.g., two different material configurations) might be computationally hard, even if one knows they are both governed by local, constant-gap dynamics.

)5. Theoretical Framework for Separating Complexity Classes

The research explicitly separates pseudoentanglement from pseudorandomness in the shallow-circuit regime.

• This provides a formal benchmark for complexity theory applied to quantum computation and circuit depth limitations. AI researchers can use this framework to classify different types of hardness inherent in quantum processes based on circuit structure (constant vs. polylogarithmic depth) rather than just state distribution properties.

We construct a family of 2D-local constant-depth quantum circuits that output states whose entanglement entropy across a specified cut cannot be estimated in quantum polynomial time. As constant-depth quantum circuits can be learned from polynomially many quantum samples, our resulting pseudoentangled states are implicitly public-key and not pseudorandom. This separates pseudoentanglement from pseudorandomness in the shallow-circuit regime: the former is possible, while the latter is not. The construction is based on the quantum intractability of the Dense-Sparse Learning Parity with Noise problem introduced in [DJ25] and uses a bounded-fan-in, bounded-fan-out classical randomized encoding for linear maps x Mx, which could be of independent interest. As applications, we obtain quantum hardness for the problem of learning the entanglement structure (across a fixed cut) of the ground-state of 1D and 2D local Hamiltonians. The 1D Hamiltonian has an inverse polynomial gap, whereas the 2D one has a constant gap. This complements the result of [BZZ24] that showed only factoring-based hardness for the 1D case, though achieving a volume versus area entanglement difference.