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

This paper demonstrates that constant-depth quantum circuits can generate pseudoentangled states with unestimable entanglement entropy based on the Dense-Sparse LPN assumption, thereby separating pseudoentanglement from pseudorandomness in the shallow-circuit regime and establishing quantum hardness for learning the entanglement structure of local Hamiltonian ground states.

The Gist

The Big Idea: The "Magic" of Simple Circuits

Imagine you have a machine that takes a bunch of coins (qubits) and flips them around to create a specific pattern. In the quantum world, this machine is called a quantum circuit.

Usually, if a machine is very simple and fast (what scientists call "constant depth" and "local"), it can only create simple patterns. It's like a child playing with Legos: if they can only reach a few blocks at a time and can't build very high, they can't make a complex castle. They can only make a flat, simple shape.

In quantum physics, "simple" shapes are called trivial states. They are boring because the parts of the system aren't deeply connected to each other. "Complex" shapes are entangled states, where the parts are so linked that changing one instantly affects the others, no matter how far apart they are.

The paper's main discovery is a surprise: The author found a way to build a machine that is very simple and fast (like the child with limited reach), yet it produces a state that looks incredibly complex and deeply connected.

However, there's a catch. While the machine is simple and its instructions are public (anyone can see how it works), the amount of connection (entanglement) it creates is a secret that is computationally impossible to figure out quickly.

The Core Concept: Pseudoentanglement

To understand this, let's look at two types of "hidden" things in cryptography:

1. Pseudorandomness: Imagine a deck of cards that looks perfectly shuffled (random) to anyone looking at it, but it was actually created by a specific, simple rule. If you don't know the rule, you can't tell the difference between this deck and a truly random one.
2. Pseudoentanglement (The new discovery): Imagine a deck of cards that looks like it has a very specific, complex pattern of connections between the cards. To an observer, it's impossible to tell if the deck has a "high connection" pattern or a "low connection" pattern, even though the deck was made by a very simple machine.

The Breakthrough:
For a long time, scientists thought that if a machine was simple enough to be "learned" quickly (which simple quantum machines are), it couldn't hide anything. You could look at the machine, understand it, and know exactly what it does.

This paper proves that you can be wrong. You can look at the machine, see it's simple, and still be completely unable to calculate how "connected" the output is. The machine is public, but the entanglement is hidden.

How They Did It: The "Secret Code" Analogy

The author used a clever trick called a Randomized Encoding.

Imagine you want to send a message (a calculation) to a friend, but you want to hide the message itself while still letting them get the result.

• The Old Way: You might need a huge, complex machine to scramble the message so no one can read it.
• The New Way (This Paper): You use a simple, local machine that adds a bunch of "noise" (randomness) to the message in a very specific way.

Think of it like this:

1. You have a simple math problem: $y = M \times x$.
2. Normally, calculating this requires a deep, complex circuit if the numbers are huge.
3. The author created a "wrapper" (the randomized encoding). This wrapper takes the simple inputs and the random noise, and passes them through a grid of tiny, simple switches (CNOT gates).
4. The output looks like a mess of random bits.
5. The Magic: If you know the secret "decoder," you can clean up the mess and get the answer. But if you just look at the mess, you can't tell if the original math problem was "easy" (low connection) or "hard" (high connection).

The author built this wrapper so that every switch only touches its immediate neighbors (like a 2D grid of people passing notes). This makes the whole machine constant depth (it finishes in the same amount of time regardless of size) and local (no long-distance wires).

The Two Results: 2D and 1D

The paper shows this works in two different physical setups:

1. The 2D Grid (The Flat Floor):
   Imagine a floor tiled with squares. The machine is built right on the tiles. The connections only happen between neighbors on the floor. The author proves that even on this simple 2D floor, you can create a state where the "entanglement gap" (the difference between a simple state and a complex one) is huge, but no one can measure it.

2. The 1D Line (The Train Track):
   Imagine the tiles are arranged in a single line, like a train track. Usually, 1D lines are even more restricted than 2D grids. The author takes the 2D machine, flattens it into a long line, and adds a "history" (a record of every step the machine took).

   • The Result: Even on this simple 1D line, the ground state (the lowest energy state) of the system has a hidden entanglement gap.
   • Why it matters: This proves that even in the most restricted 1D world, you can't easily predict how "quantum" a system is just by looking at the rules that built it.

The "Why Should We Care?" (Without the Hype)

The paper doesn't claim this will build a new battery or cure a disease. Instead, it solves a theoretical puzzle in computer science and physics:

• Separating "Randomness" from "Entanglement": It proves that you don't need a "black box" (a secret machine) to hide entanglement. You can have a public, simple machine that still hides the amount of entanglement. This separates the concept of "pseudo-randomness" (hiding the whole state) from "pseudoentanglement" (hiding just the connection strength).
• Hardness of Learning: It shows that for certain types of quantum systems (specifically those described by "local Hamiltonians"), it is computationally impossible to learn how entangled they are. Even if you have the blueprints of the system, a computer cannot figure out the answer in a reasonable time.

Summary in One Sentence

The author built a simple, public, and fast quantum machine that creates a state where the "connectedness" of the particles is so hard to calculate that it's effectively a secret, proving that even the simplest quantum machines can hide complex quantum secrets.

Technical Summary

Technical Summary: Pseudoentanglement in Constant Depth

Problem Statement
The study of entanglement is central to quantum information, yet estimating the entanglement entropy of a quantum state is generally computationally hard, even for quantum computers. This motivates the concept of pseudoentanglement: families of quantum states where the entanglement structure is computationally indistinguishable from states with different entanglement entropy, despite the states themselves being efficiently preparable.

A critical open question concerns the relationship between pseudoentanglement and pseudorandomness. While pseudorandom states (PRSs) and unitaries (PRUs) require the preparation circuit to be hidden (or the circuit depth to be sufficient to prevent efficient learning), recent results indicate that constant-depth, bounded-fan-in quantum circuits ($QNC^0$) are efficiently learnable from polynomially many samples. This learnability rules out the existence of pseudorandom states in $QNC^0$. However, it remains unclear whether pseudoentangled states can be prepared by such shallow, geometrically local circuits. Specifically, can "trivial" states (those preparable by constant-depth circuits) exhibit entanglement structures that are computationally hard to estimate?

Methodology
The paper constructs a family of 2D-local, constant-depth quantum circuits that output pseudoentangled states. The construction relies on three main technical components:

1. Cryptographic Assumption: The hardness of the Dense-Sparse Learning Parity with Noise (Dense-Sparse LPN) problem, introduced by Dao and Jain [DJ25]. This assumption provides a pair of linear maps, $F_{low}$ and $F_{high}$, which are computationally indistinguishable but possess different entropy properties on sparse inputs. Specifically, $F_{high}$ is injective on sparse inputs (yielding high entropy), while $F_{low}$ is many-to-one (yielding low entropy).
2. Bounded-Fan-in Randomized Encoding: The core technical contribution is a new perfect randomized encoding for dense linear maps $x \mapsto Mx$. Unlike previous encodings that required unbounded fan-out gates, this construction uses only bounded fan-in and bounded fan-out (specifically, fan-in/fan-out $\le 3$).
   • The encoding introduces uniform random masks $r$ and $s$.
   • It outputs bits $w$ and $z$ such that a deterministic decoder can recover $Mx$.
   • Crucially, the entropy of the encoded output is exactly $H(Mx)$ plus a fixed, mask-dependent term independent of the matrix $M$. This preserves the entropy gap between the "low" and "high" branches of the underlying linear map.
   • The encoding is implemented via a 2D grid of constant-size plaquettes using only nearest-neighbor CNOT gates, ensuring the circuit is 2D-local and constant-depth.
3. State Preparation: The authors prepare a coherent superposition of the input bits (sampled from a sparse Bernoulli distribution) and the random masks. They apply the randomized encoding circuit coherently. Tracing out the input and mask registers leaves a diagonal density matrix on the output registers whose Shannon entropy equals the entropy of the randomized encoding. Due to the entropy preservation property, the entanglement entropy across the input-output cut reflects the entropy gap of the underlying linear maps.

Key Contributions and Results

• Theorem 1.1 (Constant-depth Pseudoentanglement): Assuming the intractability of Dense-Sparse LPN for quantum polynomial-time (QPT) adversaries, there exists an efficiently samplable distribution over tuples $(C_{low}, C_{high}, W)$, where $C_{low}$ and $C_{high}$ are 2D-local constant-depth circuits. The output states $|\psi_{low}\rangle$ and $|\psi_{high}\rangle$ have an additive entanglement entropy gap of $\omega(\log n)$ across a fixed cut $W$, yet the circuit descriptions are computationally indistinguishable.

  • Significance: This demonstrates that pseudoentanglement is possible in the $QNC^0$ regime, whereas pseudorandomness is not. The states are "public-key" pseudoentangled: their preparation circuits are public and shallow, yet their entanglement structure is hidden.

• Theorem 1.2 (Randomized Encoding): The paper provides a formal proof of the bounded-fan-in, bounded-fan-out randomized encoding for dense linear maps. This encoding preserves the exact entropy of the linear map up to an additive constant and is of independent interest for low-depth cryptography (e.g., constructing collision-resistant hashes from random-code assumptions).

• Theorem 1.3 (2D Hamiltonian Hardness): By conjugating local projectors with the pseudoentangled circuits, the authors construct a family of 2D local Hamiltonians with a constant spectral gap (gap = 1). The unique ground states of these Hamiltonians inherit the entanglement gap, making the task of learning the entanglement entropy across a fixed cut quantumly hard.

• Theorem 1.4 (1D Hamiltonian Hardness): Using a padded 1D Feynman–Kitaev history-state construction, the authors extend the result to 1D local Hamiltonians. These Hamiltonians have an inverse-polynomial spectral gap. The unique ground states retain the entanglement gap (up to a small additive loss), establishing hardness for 1D systems based on a post-quantum code-based assumption.

Significance and Claims
The paper claims to establish a sharp separation between pseudorandomness and pseudoentanglement in the shallow-circuit regime. While constant-depth circuits cannot generate pseudorandom states (due to efficient learnability), they can generate pseudoentangled states.

• Public-Key Nature: Unlike pseudorandom states, which require the preparation circuit to be secret, these pseudoentangled states are generated by public circuits. This allows hardness results to be framed in the computational complexity model (input is a classical description of a circuit/Hamiltonian) rather than the sample complexity model.
• Post-Quantum Security: The hardness relies on Dense-Sparse LPN, a code-based assumption believed to be secure against quantum adversaries, contrasting with previous results (e.g., [BZZ24]) that relied on factoring (which is quantumly tractable).
• Limitations: The authors explicitly note limitations. The "hidden" cut is fixed and non-geometric (determined by the circuit structure rather than a connected spatial region), meaning the result does not directly address geometric cuts relevant to area-law vs. volume-law distinctions in quantum gravity. Additionally, the construction is specific to von Neumann (Shannon) entropy; extending the result to other Rényi entropies is not guaranteed by the current lossy-function analysis.

In summary, the work demonstrates that "trivial" states (constant-depth, local) can possess non-trivial, computationally hidden entanglement structures, provided one accepts plausible post-quantum cryptographic assumptions.