aiqbench analysis
This research establishes a fundamental separation between pseudoentanglement and pseudorandomness within constant-depth quantum circuits, demonstrating that trivial states can possess entanglement structures intractable to estimate even for quantum polynomial time. By leveraging the hardness of the Dense-Sparse Learning Parity with Noise problem, the study proves quantum computational limits on learning the entanglement structure of ground states for both 1D and 2D local Hamiltonians. These findings advance our understanding of shallow-circuit regimes and the intrinsic complexity of simulating specific quantum many-body systems.
Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure
arXiv:2605.31448v2 Announce Type: replace Abstract: 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 $\mathbf{x} \mapsto \mathbf{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.
Abstract: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 $\mathbf{x} \mapsto \mathbf{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.
Corrected cryptographic parameters, revised the 1D Hamiltonian proof, and clarified entropy thresholds and hash assumptions; main results unchanged. 34 pages, 3 figures
Quantum Physics (quant-ph); Cryptography and Security (cs.CR)
arXiv:2605.31448 [quant-ph]
(or arXiv:2605.31448v2 [quant-ph] for this version)
Full text under the publisher's open licence · 208 words
Related coverage
New framework classifies Matrix Product Quantum Channels
Quantum Zeitgeist · Sep 17, 2026
Circuit complexity lower bounds for quantum spin glasses
arXiv · Jul 22, 2026
Running Variational Quantum Eigensolver with Qiskit Aer on AMD Instinct
AMD · May 29, 2026
Certifying bipartite entanglement on a superconducting processor from a corrected QAOA cost layer
arXiv · Sep 10, 2026