analiza aiqbench
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)
Text integral sub licența deschisă a publicației · 208 cuvinte
Subiecte conexe
New framework classifies Matrix Product Quantum Channels
Quantum Zeitgeist · 17 sept. 2026
Circuit complexity lower bounds for quantum spin glasses
arXiv · 22 iul. 2026
Running Variational Quantum Eigensolver with Qiskit Aer on AMD Instinct
AMD · 29 mai 2026
Certifying bipartite entanglement on a superconducting processor from a corrected QAOA cost layer
arXiv · 10 sept. 2026