🔬 condensed matter

Shallow quantum circuit for generating extremely low-entangled approximate state designs

This paper introduces a new ensemble of quantum states that function as $\epsilon$ -approximate state $t$ -designs with theoretically minimal entanglement, magic, and coherence, and provides an efficient ancilla-free shallow quantum circuit to generate them, thereby enabling cost-effective classical simulation and highly efficient quantum state certification.

Original authors: Wonjun Lee, Minki Hhan, Gil Young Cho, Hyukjoon Kwon

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wonjun Lee, Minki Hhan, Gil Young Cho, Hyukjoon Kwon

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Making "Random" Without the Mess

Imagine you want to create a truly random pattern, like a chaotic splash of paint or a shuffled deck of cards. In the quantum world, creating a "perfectly random" state usually requires a machine so complex and deep that it's like trying to build a skyscraper just to flip a coin. These perfect random states are incredibly "tangled" (entangled), meaning every single part of the system is connected to every other part in a messy, high-energy way.

The authors of this paper asked a simple question: Do we actually need that much mess to get a random-looking result?

They discovered a new way to create quantum states that look random enough for most important tasks, but are actually very clean, simple, and "low-tangled." It's like realizing you can create a convincing fake snowstorm using just a few snowflakes arranged cleverly, rather than needing a blizzard that fills the whole sky.

The Core Discovery: The "Shadow" Trick

The paper introduces a new type of quantum state called an $\epsilon$ -approximate state $t$ -design.

The Jargon: This sounds scary, but think of it as a "statistical shadow."
The Analogy: Imagine you want to know the average shape of a cloud. You don't need to measure every single water droplet in the sky (which is impossible). Instead, you take a few specific snapshots (a "design") that capture the average shape perfectly.
The Breakthrough: Usually, creating these "snapshots" requires a quantum computer to be in a state of maximum chaos (high entanglement). The authors found a way to make these snapshots using extremely low entanglement.

The "Magic" of Low Resources:
In quantum physics, there are three "resources" needed to make things complex:

Entanglement: How connected the parts are.
Magic: How "non-classical" or weird the state is.
Coherence: How well the state holds its quantum shape.

Usually, as you add more qubits (quantum bits), these resources grow huge. The authors proved that for their new method, these resources do not grow. Whether you have 10 qubits or 1,000 qubits, the "messiness" stays the same size (it is $O(1)$ ). It's like building a house where the amount of glue needed stays the same, no matter how many rooms you add.

How They Did It: The "Copy and Shuffle" Machine

The paper proposes a specific recipe (a shallow quantum circuit) to build these states. Here is the step-by-step analogy:

Start Small: Instead of trying to randomize the whole system at once, they start with a tiny, perfectly random group of qubits (a small subsystem).
The Random Map: They use a special "random injective map." Imagine you have a small deck of cards. You want to distribute these cards into a huge room with thousands of empty chairs.
- Instead of shuffling the whole room, you take your small deck and use a random rule to place them into specific chairs.
- Crucially, you don't mix the cards with each other; you just move them to new seats based on a random pattern.
The Result: The final arrangement looks random to anyone checking the statistics, but because you didn't actually mix the cards together, the "entanglement" (the connection between the cards) remains very low.

They built a circuit (a set of instructions) to do this using simple gates (like CNOTs and MCXs). This circuit is shallow, meaning it doesn't take long to run, and it doesn't need extra "helper" qubits (ancilla) to work.

Why This Matters: The "Shadow Tomography" Application

The paper highlights a specific, practical use for this discovery: Certifying Quantum States (checking if a quantum computer is working correctly).

The Problem: To check if a quantum computer made the right state, you usually have to measure it many times and do a lot of heavy math on a classical computer afterward. If the state is too "tangled," the math becomes impossible for classical computers to handle.
The Solution: Because the authors' states are "low-tangled," the math required to analyze them is much simpler.
The Analogy: Imagine trying to verify a complex painting.
- Old Way: You have to analyze every single brushstroke in 3D space. It takes forever.
- New Way: Because the painting was made with a simple, low-tangled technique, you can verify it by looking at just a few specific angles. You can confirm the painting is real with very few measurements and very little calculation time.

The paper claims that using their method, you can certify almost any quantum state with a constant number of measurements (you don't need more measurements just because the system gets bigger) and very fast classical processing.

Summary of Claims

New States: They found a way to make quantum states that look random but have minimal "entanglement," "magic," and "coherence."
Theoretical Limit: They proved you can't go lower than this level of resource usage; they hit the theoretical floor.
Efficient Circuit: They built a fast, shallow circuit to create these states without needing extra helper qubits.
Practical Win: This allows for much faster and cheaper "shadow tomography," meaning we can verify quantum computers and their outputs much more efficiently than before.

In short: They found a shortcut to randomness that saves energy, time, and computing power, making it easier to check if quantum computers are doing their job.

Technical Summary: Shallow Quantum Circuit for Generating Extremely Low-Entangled Approximate State Designs

Problem Statement
Random quantum states are fundamental tools in quantum information science, utilized for understanding entanglement, thermalization, and simulating chaotic dynamics. They also serve critical roles in cryptography, device benchmarking, and shadow tomography. However, generating truly Haar-random states requires quantum circuits with depth exponential in the number of qubits ( $n$ ), rendering them infeasible for near-term devices. Consequently, the field relies on approximations, primarily approximate state $t$ -designs (which mimic the first $t$ moments of the Haar distribution) and pseudorandom states.

A significant limitation of existing constructions for approximate state $t$ -designs is their resource cost. Most known methods, based on layered random circuits or chaotic dynamics, produce states with volume-law entanglement (scaling linearly with $n$ ) and high "magic" (non-Cliffordness) and coherence. While recent work on pseudorandom states demonstrated that low entanglement ( $\omega(\log n)$ ) is possible, the entanglement properties of approximate state $t$ -designs remained unexplored. The central open question addressed in this work is whether approximate state $t$ -designs can be generated with extremely low entanglement, magic, and coherence that do not scale with system size, and if so, whether they can be efficiently implemented via shallow quantum circuits without ancilla qubits.

Methodology
The authors propose a novel construction based on the intuition that a $k$ -qubit state design can be extended to an $n$ -qubit system while preserving its design properties and entanglement structure, provided a specific mapping is used.

Dimension Expansion via Random Injective Maps:
The core theoretical insight is Lemma 1, which establishes that applying a random unitary operator $U_p$ to a $k$ -qubit $\epsilon$ -approximate state $t$ -design (embedded in a subspace with $n-k$ zeros) yields an $n$ -qubit $\epsilon'$ -approximate state $t$ -design. The operator $U_p$ is defined by a $t$ -wise independent random injective map $p$ from $[2^k]$ to $[2^n]$ . Crucially, because $U_p$ preserves the number of superpositions in the computational basis, the entanglement, magic, and coherence of the resulting $n$ -qubit states remain determined by the subsystem size $k$ , not the total size $n$ .
Theoretical Lower Bounds:
The authors prove Theorem 2, establishing that any ensemble forming an $\epsilon$ -approximate state $t$ -design must possess mean entanglement, magic, and coherence of at least $\Omega(\log(t/\epsilon))$ . This proves that the resources required are fundamentally bounded by the design parameters $t$ and $\epsilon$ , not the system size $n$ .
Shallow Circuit Implementation:
To realize this construction physically, the authors develop an explicit algorithm (Algorithms 1 and 2) to implement the random injective map $U_p$ using a shallow quantum circuit.
- Mechanism: The circuit utilizes parallel CNOT gates to copy the $k$ -qubit subsystem to the rest of the system, followed by random Multi-Controlled X (MCX) gates to randomize the bits.
- Depth: The circuit depth is $O(t[\log t]^3 \log n \log(1/\epsilon))$ without ancilla qubits. With ancilla qubits, the depth improves to $\tilde{O}(t[\log t]^2 \log n \log(1/\epsilon))$ .
- Efficiency: This depth is significantly shallower than previous methods for generating state designs without ancillas (e.g., local random circuits requiring $O(n)$ depth).
Application to Shadow Tomography:
The authors apply this construction to classical shadow tomography. By using a measurement ensemble where the random unitary $U$ is composed of a $k$ -qubit unitary 3-design and the shallow random injective map $U_p$ , they construct a shadow estimator.
- Key Feature: The resulting estimator contains superpositions between only two computational basis states (for $k=1$ ).
- Benefit: This drastically reduces the classical post-processing cost. Unlike estimators based on random Clifford circuits, which can be computationally expensive to evaluate for high-stabilizer-rank observables, this method allows for efficient evaluation of observables with constant or logarithmic sample complexity, depending on the observable's properties.

Key Results

Resource Saturation: The constructed ensemble achieves the theoretical lower bound of $\Theta(\log(t/\epsilon))$ for entanglement, magic, and coherence. For fixed $t$ and $\epsilon$ , these resources are $O(1)$ with respect to the total number of qubits $n$ .
Circuit Efficiency: The proposed shallow circuit is the most efficient known method for generating approximate state $t$ -designs without ancilla qubits, with a depth scaling logarithmically with $n$ rather than linearly or polynomially.
State Certification: The authors demonstrate that almost all $n$ -qubit pure states can be certified (fidelity estimation) using $O(1/\epsilon^2)$ measurements and $O(\log(n/\epsilon))$ -depth circuits, a significant improvement over previous methods requiring $O(n^2)$ measurements.
Classical Shadow Efficiency: The new shadow estimator enables the certification of quantum states with reduced classical overhead, particularly for low-rank observables or those with anti-concentrated eigenstates.

Significance and Claims
The paper claims to open a new direction in the efficient generation of random quantum states by decoupling the resource cost (entanglement, magic, coherence) from the system size. The authors state that their work:

Resolves an Open Question: It proves that approximate state $t$ -designs can exist with non-extensive resources, challenging the assumption that high entanglement is necessary for random-like behavior in design contexts.
Enables Near-Term Applications: The shallow depth and low entanglement make these states feasible for implementation on near-term quantum devices, specifically those with all-to-all connectivity (e.g., neutral-atom quantum computers).
Improves Classical Simulation: By reducing the entanglement and the complexity of the shadow estimator, the method offers a pathway to more efficient classical simulation and post-processing of quantum experiments, facilitating tasks like quantum state certification and benchmarking with fewer samples and lower computational cost.

The authors emphasize that while pseudorandom states with low entanglement exist, they do not guarantee accurate approximation of average fidelity for all system sizes in the same way approximate state designs do, highlighting the unique utility of their construction for specific quantum information processing tasks.