PaperlayerView exact revision on arXiv

Source-linked AI summary

On estimating the entropy of shallow circuit outputs

Alexandru Gheorghiu, Matty J. Hoban

arXiv:2002.12814v2quant-phcs.CC

TL;DR

The paper asks how hard entropy estimation is for outputs of shallow classical and quantum circuits. It defines shallow-circuit entropy-difference problems and proves LWE-based hardness, while giving evidence that log-depth versions occupy an intermediate regime and motivating AdS/CFT applications.

  • Problem

    Entropy estimation is important in information theory and physics, but the paper asks how computationally hard it remains when distributions or quantum states come from shallow circuits.

    Source: §1 · pp. 3–4

  • Method

    The paper studies entropy-difference problems for bounded-fan-in, unbounded-fan-out circuits of logarithmic or constant depth, and extends the quantum setting to Hamiltonian ground states.

    Source: §1.1 · p. 5, §4 · p. 24

  • Results

    Both classical and quantum shallow-circuit entropy distinguishability are at least as hard as LWE, while log-depth versions have complexity-theoretic evidence of being easier than their general polynomial-depth counterparts.

    Source: §1 · p. 5, §1.1 · p. 8, §3.1 · p. 16

  • Takeaways & Limitations

    Entropy can remain intractable for efficient quantum computation even when the underlying circuits are shallow, and the results motivate connections to bulk-to-boundary complexity in AdS/CFT.

    Source: §1 · p. 5

    The results do not extend to constant-depth circuits with bounded-fan-out gates, and the holographic application still contains potentially intractable steps and unresolved modeling questions.

    Source: §4.1 · pp. 29–30

Abstract

from arXiv · show

Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. Here, we examine the hardness of this task for the case of probability distributions or quantum states produced by shallow circuits. Specifically, 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 (LWE) problem, and thus believed to be intractable even for efficient quantum computation. This illustrates that quantum circuits do not need to be complex to render the computation of entropy a difficult task. We also give complexity-theoretic evidence that this problem for log-depth circuits is not as hard as its counterpart with general polynomial-size circuits, seemingly occupying an intermediate hardness regime. Finally, we discuss potential future applications of our work for quantum gravity research by relating our results to the complexity of the bulk-to-boundary dictionary of AdS/CFT.

1 Introduction

This section establishes hardness results for entropy estimation and separation in shallow classical and quantum circuits, including extensions to larger gaps, entropy ratios, and Hamiltonians. It also examines the complexity regime of these problems and discusses connections to AdS/CFT, while identifying open questions involving bounded-fan-out circuits and CFT Hamiltonians.

1 Introduction

  • Entropy estimation is motivated by applications in compression, cryptography, entanglement theory, condensed matter, and quantum gravity, but estimating entropy from unknown states can require resources scaling with support or Hilbert-space dimension.The introduction also gives an advice-based argument that efficient additive-error entropy estimation for arbitrary mixed states would imply an implausibly powerful quantum-advice complexity consequence.Source: §1 · p. 3
  • The work targets shallow circuits because near-term devices produce low-depth states, while MERA and the Ryu–Takayanagi formula connect shallow-state entropy to bulk geometry in AdS/CFT.The paper argues that difficult boundary entropy estimation could challenge efficient quantum simulation or imply an exponentially complex bulk-to-boundary map.Source: §1 · p. 4, §1.1 · p. 8

1.1 Main results

  • Oracle separations show that shallow entropy-difference classes are unlikely to equal SZK and QSZK, placing them in an intermediate complexity regime.The paper also shows that transcript-preserving compression of log-depth QSZK protocols would imply BQP = BPP^QNC1.Source: §1 · p. 5, §1.1 · pp. 5–6
  • Entropy difference for logarithmic- and constant-depth circuits is intractable for classical and quantum algorithms assuming quantum hardness of LWE.The constant-depth reduction uses log-depth ETCF evaluations followed by randomized encodings, and QED reduces immediately from ED.Source: §1.1 · pp. 6–7
  • The Hamiltonian quantum entropy-difference problem is at least as hard as the circuit version, with QED ≤P HQED and shallow-depth reductions inherited by HQED.The construction uses Feynman–Kitaev history states and padding so the Hamiltonian ground states retain the original entropy difference up to inverse-polynomial factors.Source: §1.1 · pp. 7–8

1.2 Discussion and open questions

  • Constant-depth hardness with bounded-fan-out gates remains unresolved, and open questions include characterizing shallow entropy-difference classes, optimal and average-case algorithms, and entropy estimation for random circuits.Follow-up work distinguishes public-key from private-key pseudoentanglement and shows that the present results concern one specified bipartition under the LWE assumption.Source: §1.2 · pp. 8–9
  • The construction makes the entropy separation exactly one bit and can be generalized to produce larger entropy differences, unlike generic one-way functions whose separation value is unclear.It also provides an example of a lossy-function construction.Source: §1.2 · p. 10
  • The approach extends to estimating the entropy of constant-depth quantum circuits with bounded fan-in and bounded fan-out, while depth-efficient ETCF constructions support classical-verifier quantum protocols [Mah18] [BCM+18] [GV19] and depth-efficient proofs of quantumness [LG21].The latter application uses depth-efficient ETCF constructions in protocols based on these functions.Source: §1.2 · p. 10
  • The work leaves open whether a CFT Hamiltonian can encode the hard problem and whether boundary evolution produces bulk geometry changes detectable by observers.A constant entropy difference may be geometrically unnoticeable if bulk observers detect only large-scale changes.Source: §1.2 · p. 10
  • The entropy-ratio problem is equivalent to entropy-difference estimation under Turing-Cook reductions, and LWE reduces to estimating entropy ratios of shallow-circuit states.This establishes hardness even when geometric effects are related to entropy ratios rather than constant entropy differences.Source: §1.2 · p. 10

2 Preliminaries

The preliminaries establish notation, complexity classes, entropy-difference problems, and the cryptographic tools used to study shallow-circuit entropy estimation.

2.1 Notation

  • The paper defines states as density matrices, distributions over n-bit strings, Shannon and von Neumann entropy, support, distances, uniform sampling, and negligible functions.Source: §2.1 · p. 11

2.2 Complexity theory

  • NC and QNC classify polynomial-size circuits by depth, while constant-depth quantum classes distinguish bounded from unbounded fan-out gates.Source: §2.2 · p. 11
  • Entropy-difference variants use a constant entropy gap because parallel repetition amplifies an inverse-polynomial gap without increasing circuit depth.Source: §2.2 · p. 12, §2.3.1 · p. 12
  • ED compares entropies of classical circuit outputs and is SZK-complete, whereas QED compares reduced output-state entropies and is QSZK-complete.Source: §2.2 · p. 12

2.3.1 Learning with Errors (LWE)

  • LWE asks whether noisy linear samples reveal a secret or can be distinguished from uniform, under an assumption believed hard for quantum polynomial-time algorithms.Source: §2.3.1 · pp. 12–13

2.3.2 Claw-free functions

  • ETCFs combine injective and claw-free functions whose descriptions are computationally indistinguishable, while randomized encodings provide perfect privacy and correctness with NC0 output locality.Source: §2.3.2 · pp. 13–14

2.3.3 Randomized encodings

  • Randomized encodings preserve function information through efficient evaluation, decoding, and simulation, and every NC1 function has a perfect NC0 encoding using unbounded fan-out gates.Source: §2.3.3 · pp. 14–15

3 Entropy difference for shallow circuits with unbounded fan-out gates

This section defines entropy-difference problems for shallow classical and quantum circuits and characterizes their statistical zero-knowledge classes. It establishes complexity-theoretic evidence for their relative weakness while proving LWE-hardness through reductions based on 1-to-1 versus approximately 2-to-1 output maps, including quantum circuits with unbounded fan-out gates.

3 Entropy difference for shallow circuits with unbounded fan-out gates

  • For polylogarithmic-depth circuits, SZKpolylog and QSZKpolylog exactly characterize promise problems with statistical zero-knowledge protocols whose verifier and simulator have polylogarithmic depth.The definitions cover classical and quantum entropy difference, with constant-depth variants distinguished by bounded versus unbounded fan-out; the entropy gap is taken to be at least 1 unless otherwise specified.Source: §3 · pp. 15–16

3.1 Entropy difference is easier for shallow circuits

  • Relative to a d-shuffling oracle with d = Ω(n), EDpolylog and QEDpolylog are strictly weaker than ED and QED because polylogarithmic-depth circuits cannot obtain a noticeable correlation with the oracle type.The corresponding protocol distinguishes equiprobable injective and 2-to-1 cases with probability at most 1/2 + poly(n)/2^n, and the result extends to circuits of depth strictly less than d.Source: §3.1 · pp. 18–19
  • If a transcript-preserving polynomial-time reduction maps QSZK protocols with log-depth verifiers to QSZKlog, then BQP = BPPQNC1.The construction uses log-depth SWAP-test verification of history-like states generated by simulators for a language and its complement.Source: §3.1 · pp. 19–20

3.2 Hardness based on Learning with Errors

  • LWE ≤P EDlog, by reducing LWE to distinguishing injective and 2-to-1 ETCF functions evaluated with logarithmic-depth circuits.The constructed circuits incorporate uniformly sampled inputs transformed by a log-depth Gaussify procedure into truncated-Gaussian errors.Source: §3.2 · pp. 20–22
  • The entropy gap arises because Cf behaves injectively while Cg is 2-to-1 except on a negligible fraction of inputs, yielding a positive constant gap.Their entropies are S(Cf) = n · log(q) + 1 + SGaussian and S(Cg) = n · log(q) + SGaussian + µ(n), with µ(n) negligible.Source: §3.2 · p. 22
  • The gap can be amplified or generalized: a 1-to-1 function versus a 2^k-to-1 function produces an entropy difference of k − negl(n).The explicit 4-to-1 construction gives an entropy difference of 2 − negl(n).Source: §3.2 · p. 22
  • EDlog is hard-on-average under LWE for randomly chosen circuits of the specified logarithmic-depth structure.The constructed circuits have differing output entropies, allowing entropy distinction to identify the underlying 1-to-1 versus 2-to-1 case.Source: §3.2 · pp. 21–23
  • Compiling the logarithmic-depth constructions with randomized encodings gives LWE ≤P EDO(1), while preserving injective invariance and the entropy difference.The encodings remain 1-to-1 and 2-to-1 respectively, so their entropy gap matches that of the original circuits.Source: §3.2 · p. 23
  • The quantum extension establishes LWE ≤P QEDO(1), because classical reversible circuits are included in the quantum setting after tracing out required ancillas.The resulting quantum circuits lie in QNC0_f and use unbounded fan-out gates.Source: §3.2 · p. 24
  • The quantum result does not cover bounded-fan-out constant-depth circuits, leaving that extension as an open problem.Unbounded fan-out enables powerful operations such as GHZ-state preparation and approximate Quantum Fourier Transform implementations [HˇS05].Source: §3.2 · p. 24

4 Hamiltonian quantum entropy difference

This section reduces quantum entropy difference to entropy differences between reduced ground states of local Hamiltonians, preserving the gap and circuit-depth regime. It then proposes an AdS/CFT thought experiment linking hard entropy estimation to potentially intractable bulk-to-boundary translation.

4 Hamiltonian quantum entropy difference

  • HQED compares the entanglement entropy of reduced ground states of two local Hamiltonians, with degenerate-groundspace cases choosing the minimum-entropy ground state.The reduced states are obtained by tracing out specified subsystems of the Hamiltonian ground states.Source: §4 · p. 24
  • A deterministic polynomial-time reduction maps QED instances to HQED instances while preserving the entropy difference up to 1/poly(n + k).The construction uses local Hamiltonians whose ground states are padded Feynman-Kitaev history states.Source: §4 · pp. 25, 27
  • Identity padding gives the final circuit output enough weight in each history state for reduced ground-state entropies to approximate the original circuit-output entropies.The padded circuit leaves the final state unchanged while increasing its contribution to the history-state superposition.Source: §4 · pp. 25–26
  • The Fannes-Audenaert inequality converts the trace-distance approximation between constructed reduced states and circuit outputs into a corresponding entropy approximation.This transfers the original QED promise to the Hamiltonian setting with only inverse-polynomial error.Source: §4 · pp. 26–27
  • The reduction preserves shallow-depth structure: log-depth and constant-depth QED circuits yield HQED instances with logarithmic- and constant-depth approximating purifications.A separate constant-depth construction can make the Hamiltonian ground state exactly equal to the circuit output.Source: §4 · pp. 24, 27

4.1 Applications to holography

  • Under the Ryu-Takayanagi relation, a bulk observer could infer the entropy case by measuring a minimal-surface area, while Alice simulates the corresponding evolution through the AdS dictionary.The proposed procedure uses boundary-state preparation, dual Hamiltonian evolution, and SWAP tests to distinguish the function types.Source: §4.1 · pp. 27, 29
  • If the holographic procedure were efficient, it would distinguish the function types and make LWE tractable; the authors therefore suggest that the AdS dictionary may be computationally intractable.The argument remains a thought experiment because efficient CFT-state preparation and formal encoding of LWE instances are unresolved.Source: §4.1 · pp. 27–30
  • The holographic proposal assumes efficiently preparable CFT states whose entanglement entropy differs according to whether an underlying function is 1-to-1 or 2-to-1.Such states are motivated by local-Hamiltonian constructions and quantum error-correcting-code toy models of AdS/CFT.Source: §4.1 · p. 28

A An unconditional lower bound on entropy estimation

This section proves an unconditional lower bound for quantum entropy estimation by showing that an overly efficient estimator would collapse BQP/qpoly to ALL. The contradiction uses advice states encoding yes- and no-instances of an arbitrary language.

A An unconditional lower bound on entropy estimation

  • No quantum algorithm can estimate an n-qubit state's entropy within additive error ϵ in time poly(n, log(1/ϵ)).The theorem rules out this runtime regardless of the number of copies used within the stated scaling.Source: A An unconditional lower bound on… · p. 34
  • Assuming such an estimator exists would allow a BQP/qpoly algorithm to decide every language, implying BQP/qpoly = ALL.The advice consists of polynomially many copies of equal superpositions over yes- and no-instances at each input length.Source: A An unconditional lower bound on… · p. 35
  • For an input x, the EQ_x operation produces reduced states whose entropy distinguishes whether x belongs to the language, with the yes-state entropy at least 2^-n.Setting ϵ = 2^-n-1 lets the hypothetical estimator determine which reduced state has nonzero entropy.Source: A An unconditional lower bound on… · p. 35
  • The resulting collapse contradicts the known separation BQP/qpoly ≠ ALL, establishing the unconditional lower bound.The contradiction uses the containment EESPACE ⊄ BQP/qpoly cited in the proof.Source: A An unconditional lower bound on… · p. 35

B The entropy ratio problem

The entropy ratio problem asks whether the entropies of two circuit-generated states differ by a promised multiplicative gap, with the denominator bounded away from zero. The paper shows that this problem is equivalent to entropy difference under polynomial-time Cook reductions and remains LWE-hard for logarithmic- and constant-depth circuits.

Motivation

  • The ratio problem is motivated by AdS/CFT settings where geometric quantities correspond to entropies and observable comparisons concern ratios rather than differences.The paper connects entropy ratios to first-order geometric lengths, areas, or volumes in the bulk-to-boundary correspondence.Source: B The entropy ratio problem · p. 36

Problem definition and promise

  • The QER promise requires S(ρ2) > 1/poly(n + k), preventing arbitrarily small denominators.Without this condition, a reduction from SAT would make the problem NP-hard through ratios that distinguish zero from nonzero entropy.Source: B The entropy ratio problem · p. 36

Hardness relationship

  • QER is equivalent to QED under polynomial-time Cook reductions.One direction estimates both entropies using a QER oracle and subtracts them; the reverse direction uses QED instances with the identity circuit or a Bell-pair circuit to estimate ratios.Source: B The entropy ratio problem · pp. 37–38

Open reduction question

  • The paper leaves finding Karp or log-space reductions between the entropy problems as an open question, despite constant-depth validity of the results.The available reductions are polynomial-time Cook reductions.Source: B The entropy ratio problem · pp. 37–38

Constant-depth hardness

  • LWE reduces to QER for constant-depth circuits, while the construction uses functions with approximately 1-to-1 and 2^r-to-1 behavior.The constant-depth result is stated as LWE ≤P QER_O(1), and the reduction replaces a 2-to-1 function with a 2^r-to-1 function.Source: B The entropy ratio problem · p. 38

Logarithmic-depth hardness

  • For logarithmic-depth circuits, the construction makes one entropy ratio smaller than 1/p(n), while distinguishing the cases remains as hard as LWE.The circuits can be implemented in NC1, and randomized encodings extend the result to constant depth and quantum circuits.Source: B The entropy ratio problem · pp. 38–39

C HQED with constant depth ground state

For constant-depth circuits, the paper gives an exact reduction from quantum entropy difference to a local Hamiltonian problem. The constructed Hamiltonians have the circuit outputs themselves as unique ground states, so their entanglement entropy difference is preserved exactly.

Exact constant-depth reduction

  • QED_O(1) reduces to HQED_O(1) while exactly preserving the entropy difference.This improves on history-state constructions that preserve the difference only up to an additive 1/poly(n + k) term.Source: C HQED with constant depth ground state · p. 39

Hamiltonian construction

  • For a depth-d circuit, each Hamiltonian term has locality 2d, making the Hamiltonian local when d is constant.The unique ground state of each Hamiltonian is Cj|00...0⟩, matching the corresponding circuit output exactly.Source: C HQED with constant depth ground state · p. 39
Loading 2002.12814v2…