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

• URL: http://arxiv.org/abs/2605.31448v1
• Date: Fri, 29 May 2026 15:43:00 GMT
• Title: Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure
• Abstract summary: We construct a family of 2D-local constant-depth quantum circuits whose entanglement entropy across a cut cannot be estimated in quantum time.<n>As constant-depth quantum circuits can be learned from specifiedly many quantum samples, our resulting pseudoentangled states are implicitly public-key and not pseudorandom.
• Score: 52.51019642214249
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Limitations of Noisy Geometrically Local Quantum Circuits [0.2039123720459736]
  We show that noisy quantum circuits with interspersed noise converge to the uniform distribution at $omega(log n)$ depth, where $n$ is the number of qubits.<n>We conjecture that our bound is still loose and that a $Theta(1)$-depth threshold suffices for simulability due to a percolation effect.
  arXiv  Detail & Related papers  (2025-10-07T18:08:23Z)
• Zipping many-body quantum states: a scalable approach to diagonal entropy [0.0]
  We explore using the Lempel-Ziv lossless image compression algorithm as an efficient, scalable alternative to a brute-force tomographic approach.<n>We test this approach on several examples: one-dimensional quantum Ising model, and two-dimensional states that display conventional symmetry breaking.<n>We also analyze the singular part of the diagonal entropy density using renormalization group on a replicated action.
  arXiv  Detail & Related papers  (2025-02-26T07:24:47Z)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem.<n>We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions.<n>We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
  Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
  arXiv  Detail & Related papers  (2024-09-23T17:45:33Z)
• Realizing fracton order from long-range quantum entanglement in programmable Rydberg atom arrays [45.19832622389592]
  Storing quantum information requires battling quantum decoherence, which results in a loss of information over time. To achieve error-resistant quantum memory, one would like to store the information in a quantum superposition of degenerate states engineered in such a way that local sources of noise cannot change one state into another. We show that this platform also allows to detect and correct certain types of errors en route to the goal of true error-resistant quantum memory.
  arXiv  Detail & Related papers  (2024-07-08T12:46:08Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Fault-tolerant quantum speedup from constant depth quantum circuits [0.0]
  We show that there is no classical algorithm which can sample according to its output distribution in $poly(n)$ time. We present two constructions, each taking $poly(n)$ physical qubits, some of which are prepared in noisy magic states.
  arXiv  Detail & Related papers  (2020-05-23T13:53:27Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates [0.0]
  We prove that $poly(t)cdot n1/D$-depth local random quantum circuits with two qudit nearest-neighbor gates are approximate $t$-designs in various measures. We also prove that anti-concentration is possible in depth O(log(n) loglog(n) using a different model.
  arXiv  Detail & Related papers  (2018-09-18T22:28:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.