PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Pseudoentanglement

Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, Zixin Zhou

arXiv:2211.00747v2quant-phcs.CCcs.CR

TL;DR

The paper asks whether quantum states can be efficiently constructed with low entanglement while remaining indistinguishable from maximally entangled states. It constructs pseudorandom states with entropy arbitrarily close to log n across all cuts, matching the computational lower bound and enabling applications to testing, distillation, and quantum gravity.

  • Problem

    The paper studies whether efficiently constructible quantum states with low entanglement can be indistinguishable from maximally entangled states.

    Source: §1 · p. 2

  • Method

    It constructs pseudoentangled states from a new family of quantum pseudorandom states and proves their efficient preparation, pseudorandomness, and low entropy across cuts.

    Source: §2 · p. 4, §2.4.2 · p. 12

  • Results

    The construction achieves entanglement entropy arbitrarily close to log n across all cuts, producing a Θ(n) versus ω(log n) pseudoentanglement gap simultaneously across cuts.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The result separates computational from information-theoretic quantum pseudorandomness and supports lower bounds for MPS testing, Schmidt-rank testing, entanglement distillation, and AdS/CFT complexity.

    Source: §1 · p. 2

    The pseudo-area-law variants provide only an upper bound on entanglement entropy, whose tightness remains open.

    Source: §4 · p. 25

Abstract

from arXiv · show

Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. Inspired by recent work of Gheorghiu and Hoban, we define the notion of "pseudoentanglement'', a property exhibited by ensembles of efficiently constructible quantum states which are indistinguishable from quantum states with maximal entanglement. Our construction relies on the notion of quantum pseudorandom states -- first defined by Ji, Liu and Song -- which are efficiently constructible states indistinguishable from (maximally entangled) Haar-random states. Specifically, we give a construction of pseudoentangled states with entanglement entropy arbitrarily close to $\log n$ across every cut, a tight bound providing an exponential separation between computational vs information theoretic quantum pseudorandomness. We discuss applications of this result to Matrix Product State testing, entanglement distillation, and the complexity of the AdS/CFT correspondence. As compared with a previous version of this manuscript (arXiv:2211.00747v1) this version introduces a new pseudorandom state construction, has a simpler proof of correctness, and achieves a technically stronger result of low entanglement across all cuts simultaneously.

1 Introduction

The paper defines pseudoentanglement as efficiently constructible quantum states with low entanglement that remain indistinguishable from maximally entangled states, and constructs states achieving near-optimal low entropy across all relevant cuts. It also formalizes the notion and derives applications to property testing, entanglement distillation, and quantum gravity.

1 Introduction

  • Pseudoentanglement consists of efficiently constructible low-entanglement states that are computationally indistinguishable from states with maximal entanglement.The construction relies on quantum pseudorandom states, which are efficiently preparable yet indistinguishable from Haar-random states.Source: §1 · p. 2
  • Pseudorandom states can have entanglement entropy arbitrarily close to log n across all cuts, achieving the lower bound up to the stated asymptotic form.This yields an exponential separation from information-theoretic pseudorandomness, which requires Ω(n) entropy across each cut.Source: §1 · p. 2
  • The new construction improves the prior fixed-cut result by achieving low entanglement across all cuts simultaneously, with a simpler proof and a new pseudorandom-state construction.The earlier technique could produce pseudo-area-law scaling for selected cuts but could not reduce entanglement across all cuts.Source: §1 · p. 3

1.1 Applications

  • MPS testing receives new lower bounds in both information-theoretic and computational settings, with stronger bounds in the regime of high bond dimension k.The result complements prior MPS-testing lower bounds and implies that testing becomes more difficult as k grows.Source: §1.1 · p. 3
  • The construction makes Schmidt-rank testing and related tomography problems hard even for efficiently constructible states, and also yields lower bounds for entanglement distillation.These applications include estimating the largest Schmidt coefficients and extracting entanglement from Haar-entangled random states via the Schur transform.Source: §1.1 · p. 3
  • Pseudoentanglement may provide evidence that holographic dictionary maps in the AdS/CFT correspondence are exponentially difficult to compute.The proposed connection builds on the relationship between entanglement and geometry and extends the motivation of [GH20].Source: §1.1 · p. 3, §1.2 · p. 4

1.2 A formal definition of pseudo-entanglement

  • The paper defines a pseudoentangled state ensemble using efficient preparation, an entanglement-entropy gap across cuts, and computational indistinguishability between the ensembles.Its main corollary gives a Θ(n) versus ω(log n) gap across all cuts simultaneously while retaining pseudorandomness, assuming a quantum-secure OWF.Source: §1.2 · p. 4

2 Main result

This section constructs efficiently preparable pseudorandom subset phase states with optimally low, tunable entanglement across every cut, while remaining indistinguishable from Haar-random states. It presents constructions based on pseudorandom functions, permutations, and 4-wise independent functions, including QNC1 implementations using quantum fan-out gates.

2 Main result

  • The construction achieves the strongest possible pseudoentanglement: optimally low entropy across every cut, matching the lower bound of Ji, Liu, and Song.The entanglement entropy can be tuned to Θ(f(n)) across each cut for any function f = ω(log(n)).Source: §2 · p. 4

2.1 The subset phase state construction

  • Subset phase states are efficiently preparable using quantum-secure pseudorandom functions and permutations.Varying the subset size provides tight control over the construction’s entanglement.Source: §2.1 · p. 5

2.4 Proof of statistical closeness to Haar random states

  • For K = 2^ω(log n), polynomially many copies of a random subset phase state are statistically close to polynomially many copies of a Haar-random state.This establishes statistical closeness even when the distinguisher receives polynomially many copies.Source: §2.1 · p. 5, §2.4 · p. 7

2.4.1 Useful results

  • A uniformly random fixed-size subset yields a truncated symmetric-subspace projector close in trace distance to the full Haar symmetric projector.The closeness depends on the subset size and assumes K ≥ t.Source: §2.4.1 · p. 7

2.4.2 Proof of Theorem 2.1

  • With a fixed subset and random phases, the proof uses hybrids to show closeness to the normalized symmetric projector on the truncated subspace.The hybrid differences are O(t^2/|S|), and sufficiently large quasi-polynomial K gives inverse quasi-polynomial trace-distance closeness to Haar states.Source: §2.4.2 · pp. 11–12

2.5 Proof of computational indistinguishability

  • The keyed ensemble defined by pseudorandom functions, permutations, and inverse permutations is an efficiently preparable pseudorandom quantum-state ensemble.The secret key consists of the descriptions of f, p, and p−1.Source: §2.5 · pp. 12–13

2.5.1 Security analysis

  • When |S| = 2^ω(log n), the subset phase-state ensemble is computationally indistinguishable from Haar-random states.The security proof replaces the cryptographic oracles with truly random ones, then invokes the statistical-closeness theorem.Source: §2.5.1 · p. 13

2.6 Entanglement entropy of pseudorandom subset phase states

  • For |S| = 2^poly log n, the construction achieves optimally low pseudoentanglement across every cut, independent of spatial geometry.The subset size can then be varied to tune the entanglement entropy.Source: §2.6 · p. 14

2.7.1 Pseudorandom matrices for subset phase states

  • The reduced density matrix across a cut is represented using a pseudorandom matrix B_X:Y,f whose entries equal f(i,j) when ij ∈ S.Here |S| = 2^k, with i and j indexing the two sides of the partition.Source: §2.7.1 · pp. 14–15

2.7.2 Tuning the entanglement entropy

  • The tunable ensemble chooses f using a 4-wise independent function h and a quantum-secure pseudorandom permutation q, and f is computationally indistinguishable from a truly random function.This supplies both pseudorandomness and 4-wise independence for the entropy analysis.Source: §2.7.2 · p. 15
  • For ω(log n) ≤ k ≤ n and |S| = 2^k, Theorem 2.7 gives a high-probability entanglement-entropy characterization for cuts with both sides of size at least k.The proof uses the pseudorandom matrix associated with the cut, with the upper bound from Corollary 2.6.1 and a lower-bound argument based on 4-wise independence.Source: §2.7.2 · pp. 15–16

2.8 Instantiating our constructions using low depth circuits

  • The constructions can be instantiated from quantum-secure one-way functions and implemented with low-depth primitives, including NC1 pseudorandom functions and Luby–Rackoff pseudorandom permutations.Because bounded-fan-out compilation may increase depth, QNC1 implementation uses special quantum fan-out gates; ordinary NC1 implementability alone does not establish QNC1 compilation.Source: §2.8 · pp. 17–18

3 Applications

The construction yields applications showing that efficiently constructible low-entanglement states can make distillation and property testing difficult, while also informing questions about AdS/CFT complexity.

3.1 Low entropy pseudorandom states imply inefficient entropy distillation protocols

  • Under quantum-secure one-way functions, efficient distillation of more than polylogarithmically many EPR pairs from polynomially many copies is ruled out for the constructed low-entropy states.Proposition 3.2 states that p = ω(poly log S(ρ)) cannot be achieved with non-negligible probability for the specified bipartitions.Source: §3.1 · pp. 18–19

3.2 Applications to property testing: An overview

  • The construction strengthens property-testing lower bounds to efficiently describable states, including eigenvalue estimation and Schmidt-rank estimation.For eigenvalue estimation, Task 3 has a lower-bound lemma under quantum-secure one-way functions; for Schmidt-rank estimation, m = ω(poly(n)).Source: §3.2 · p. 19, §3.2.1 · p. 20, §3.2.2 · p. 20

3.3 Improved lower bound for testing matrix product states

  • Ω(√r) copies are required to test whether an n-qubit state has MPS bond dimension r, in information-theoretic and computational settings.This improves on the prior Ω(√n) lower bound when r is large.Source: §3.3 · p. 20, §3.3.3 · pp. 21, 23

3.3.3 Our results

  • The MPS lower bound is obtained by constructing one ensemble of low-rank subset-phase states and another ensemble far from MPS(r), then distinguishing them.Any distinguisher with constant success probability requires t = Ω(√r) copies.Source: §3.3.3 · pp. 22–23

3.4 Applications to quantum gravity

  • The AdS/CFT application connects hidden entanglement entropies to the possible exponential complexity of computing the dictionary.This argument is presented as complementary to prior work and does not yet establish holographic pseudoentanglement.Source: §3.4 · pp. 24–25
  • The result provides subvolume-law pseudoentanglement, a necessary but insufficient condition for realizing pseudoentanglement within the holographic regime of AdS/CFT.The authors leave construction of holographic entanglement structures and further implications for future work.Source: §3.4 · pp. 24–25

4 Future directions

The paper leaves open questions about simplifying the phase construction, tightening entanglement bounds, and extending pseudoentanglement applications.

4 Future directions

  • It remains open whether random phases are necessary when the subset is pseudorandomly chosen.The question concerns states using a pseudorandom subset without the paper’s pseudorandom phases.Source: §4 · p. 25, A Low entanglement across a fixed cut… · p. 30
  • For other state families, the paper proves only upper bounds for pseudo-area-law entanglement, so tightness remains unresolved.The authors specifically ask whether other families achieve tightly tuned pseudoentanglement across arbitrary cuts.Source: §4 · p. 25
  • Further applications of pseudoentanglement to cryptography, complexity theory, and quantum computing remain open.Source: §4 · p. 25

A.1 Sketch of result

The construction turns pseudorandom matrices into quantum states whose entanglement is controlled by matrix rank while preserving computational indistinguishability from Haar-random states. It combines pseudorandomness, low-rank row repetition, and high-entropy matrix constructions to obtain pseudoentangled families.

A.1 Sketch of result

  • Repeating selected rows lowers matrix rank and therefore reduces the entanglement entropy of the corresponding reduced density matrix.The reduced density matrix is proportional to A A^T, so rank reduction directly constrains its entropy.Source: §A.1 · p. 30
  • A pseudorandom 2^(n/2−k)-to-1 row-selection function produces rank at most 2^k and entanglement entropy at most k.The function is constructed as g = f1(f2(x) mod 2^k), using pseudorandom permutations and hybrid arguments to preserve pseudorandomness.Source: §A.1 · p. 30
  • The low-entropy construction remains computationally secure down to k = ω(log n), because smaller ranges would create efficiently detectable collisions.The security argument relies on collision bounds for distinguishing random functions with small range from pseudorandom permutations.Source: §A.1 · pp. 30–31

B.1.2 Constructing pseudoentangled states

  • Pseudorandom matrix indistinguishability transfers to phase-state indistinguishability, yielding pseudorandom quantum states through polynomially many preparable copies.A black-box distinguisher for phase states would distinguish the underlying matrix from a random matrix; random-matrix phase states are statistically close to Haar-random states.Source: §B.1.2 · p. 33

B.2.1 High level overview of the construction

  • The high-entropy construction seeks matrices that are both quantum-indistinguishable from random matrices and 4-wise independent.4-wise independence supports the Frobenius-norm analysis needed to establish high entanglement entropy.Source: §B.2.1 · p. 34

B.2.3 Analysis of oracle indistinguishability

The high-entropy construction establishes oracle indistinguishability from random matrices while using 4-wise independence to control the Frobenius norm and hence the state’s entanglement. The resulting phase states are efficiently preparable pseudorandom states.

B.2.3 Analysis of oracle indistinguishability

  • A random sample from a 4-wise independent function family is 2^-n/4-biased with high probability.This bias estimate supports replacing the resulting matrix distribution by an unbiased random matrix in the oracle analysis.Source: §B.2.3 · p. 35
  • An efficiently sampleable 2^-n/4-biased random matrix is oracle-indistinguishable from a 0-biased random matrix.The argument uses statistical indistinguishability of the entry distributions together with the cited quantum oracle result.Source: §B.2.3 · p. 35

B.2.6 Putting the two properties together

  • The combined construction is oracle-indistinguishable from a truly random matrix and satisfies the required Frobenius-norm bound with high probability.The two properties are combined using 4-wise independence and the preceding indistinguishability lemmas.Source: §B.2.6 · p. 37

B.2.7 Constructing a pseudorandom state with high entropy

  • The high-entropy state is efficiently preparable because its key specifies efficient descriptions of the permutation and 4-wise independent function used by the phase oracle.Preparing a superposition and querying the phase oracle yields the state in polynomial time.Source: §B.2.7 · p. 38

B.3.1 High level overview of the construction

  • The low-entropy construction starts from a high-entropy pseudorandom matrix and repeats rows through a pseudorandom small-range function to reduce rank without exposing the change to polynomial-time adversaries.The row-selection function is built by composing pseudorandom functions.Source: §B.3.1 · p. 38, §B.3.2 · p. 39

B.3.3 Security analysis of small range distributions

Small-range distributions provide the security bridge for low-rank row composition, while rank bounds give the corresponding entropy upper bounds. The same framework extends to tunable-entropy constructions using permutation-based row selection.

B.3.3 Security analysis of small range distributions

  • A 2^k-range row-selection function makes the reduced density matrix have entropy O(k), because the resulting matrix has rank at most 2^k.This is the central entropy bound for the low-entanglement construction.Source: §B.3.3 · p. 39
  • The composed function f(g(·) mod 2^k) is oracle-indistinguishable from a small-range random function when f and g are pseudorandom functions.The proof proceeds through hybrids replacing the inner and outer pseudorandom functions by random functions.Source: §B.3.3 · p. 39

B.3.4 Putting everything together

  • Row-composing any oracle-indistinguishable pseudorandom matrix with the small-range function preserves indistinguishability from a uniformly random matrix.This theorem transfers the small-range security argument to the matrix construction.Source: §B.3.4 · p. 40

B.4.1 Overview of the construction

  • The tunable construction combines high-entropy pseudorandom matrices with row composition by a function whose range size is controlled by k.This generalizes the earlier low-entropy construction.Source: §B.4 · p. 41, §B.4.1 · p. 41

B.4.2 Upper and lower bound on the entropy

  • f(h(·) mod 2^k) is a 2^(n/2−k)-to-1 function; the entropy upper bound comes from matrix-rank analysis, while the lower bound comes from lower bounding.Source: §B.4.1 · p. 41, §B.4.2 · p. 42

B.4.3 Security analysis of 2n/2−k-to-1 functions

The paper proves that permutation-based 2^(n/2−k)-to-1 functions are indistinguishable from the pseudorandom small-range functions needed for entropy control. The resulting states are efficiently preparable, tunable in entropy, and applicable beyond equal half-half cuts.

B.4.3 Security analysis of 2^(n/2−k)-to-1 functions

  • For k = ω(log n), f(g(·) mod 2^k) is oracle-indistinguishable from p(h(·) mod 2^k), where f,g are PRFs and p,h are PRPs.The proof uses hybrids replacing PRPs with random permutations and PRFs, then invokes random-function versus random-permutation indistinguishability.Source: §B.4.3 · pp. 43–44
  • This indistinguishability lets the construction use permutation-based row selection while retaining pseudorandomness of the resulting matrix.The row-composed matrix remains pseudorandom when the underlying matrix is pseudorandom.Source: §B.4.3 · p. 44

B.4.4 Constructing a pseudorandom state with tunable entropy

  • The tunable-entropy state is efficiently preparable from a key describing the matrix and the two permutations used in its phase oracle.The phase oracle can be constructed in polynomial time from the key.Source: §B.4.4 · pp. 44–45
  • The same arguments yield tunable entanglement entropy Θ(k) for bipartitions whose two regions each contain Ω(n) qubits.The equal n/2 versus n/2 partition is not essential to the construction.Source: §B.4.4 · p. 45

C.1 Definitions

  • Area-law pseudorandom states are impossible because an appropriate boundary can distinguish them from Haar-random states, which obey volume-law entropy.Consequently, pseudoentangled states cannot have area-law scaling under this construction.Source: §C.1 · p. 45, C Entanglement scaling and geometry · p. 45

C.2 Area–law pseudorandom states are impossible

The paper rules out area-law pseudorandom states, then introduces quasi-area-law constructions whose entanglement remains polylogarithmic even for large boundaries. Its matrix procedure preserves pseudorandomness while reducing rank across successive cuts.

C.2 Area–law pseudorandom states are impossible

  • Area-law pseudorandom states are impossible because a SWAP-test distinguisher achieves inverse-polynomial bias between Haar-random and area-law states.The distinguisher uses two copies, traces out one region, and compares the resulting states after choosing partitions with O(log n) boundary and ω(log n) interiors.Source: §C.2 · p. 46

C.3 Introducing quasi–area law states

  • Quasi-area-law pseudoentangled states achieve entanglement entropy Θ(poly log n) across every cut, without dependence on boundary size.This remains true even when the boundary has size Ω(n), giving the strongest stated quasi-area-law behavior.Source: §C.3 · p. 46

C.4 Quasi–area law pseudoentanglement across every cut

  • The construction generalizes pseudoentanglement from a fixed bipartition to every cut and supports one- and two-dimensional spatial geometries.The detailed construction is deferred to the appendix, while the subsequent procedure implements the one-dimensional phase-state construction.Source: §C.4 · p. 47

D Pseudo-area law entangled PRS within the JLS phase state construction

  • The area-law construction proceeds by defining a matrix property, building a low-entropy pseudorandom state in 1-D, proving entropy bounds, and extending the construction to 2-D.Efficient preparation and a hybrid-based security proof complete the construction.Source: D Pseudo-area law entangled PRS within… · p. 47

D.1 A property of matrices

  • The matrix transformation cannot increase rank: Proposition D.1 states that rank(A′) ≤ rank(A).The proof observes that every row of A′ is a row of A, so the number of linearly independent rows cannot increase.Source: §D.1 · p. 47

D.2 Constructing the pseudorandom matrix

  • Iteratively hashing down the matrix rank preserves low rank across successive one-dimensional bipartitions.The procedure starts from one partition, moves right through the line, and applies the rank-reducing transformation at each step.Source: §D.2 · p. 48, §D.2.1 · p. 48

D.2.2 The procedure

The procedure starts with a pseudorandom matrix and repeatedly hashes down its bond dimension, while hybrid arguments preserve pseudorandomness. The resulting matrix is converted into an efficiently preparable phase-state ensemble.

D.2.2 The procedure

  • The procedure initializes a 2^m1 × 2^m2 pseudorandom matrix and iteratively hashes down its bond dimension using a public 4-wise independent function family and public pseudorandom permutations.Iterations run for t ≤ n − 2 log_2 n, starting with A′ = A, t = 0, and k = log_2 n.Source: §D.2.2 · p. 48
  • The final matrix A′ remains pseudorandom by a polynomial-length hybrid argument over the pseudorandom-function transformations.Each adjacent pair of iterates is computationally indistinguishable, so the initial pseudorandom matrix and final A′ are indistinguishable.Source: §D.2.2 · p. 49
  • The construction bounds the final matrix rank by 2^log_2 n, yielding the low-rank property used for entanglement control.This follows from the rank inequality and the construction’s final dimension parameters.Source: §D.2.2 · p. 49

D.3 Constructing the pseudorandom quantum state

  • The matrix A′ defines an n-qubit phase-state ensemble through the amplitudes indexed by m1 = n − log_2 n and m2 = log_2 n.The key includes a matrix description and quantum-secure many-to-one functions, and the resulting state is specified from A′.Source: §D.3 · p. 49, §D.3.1 · p. 49

D.3.2 Proof of pseudorandomness

The constructed phase states are efficiently preparable and pseudorandom, while their matrix rank bounds their entanglement across contiguous cuts. The construction therefore realizes quasi-area-law pseudorandom states.

D.3.2 Proof of pseudorandomness

  • With high probability, the constructed state is a pseudorandom quantum state satisfying the stated low-entanglement bound for every contiguous partition.The entanglement bound follows from the rank bound established for the transformed matrix.Source: §D.3.2 · pp. 49–50
  • Efficient preparation uses the key to construct A′, implements its phase oracle, and queries that oracle on an equal superposition.Security follows because A′ is pseudorandom and the corresponding phase state inherits pseudorandomness.Source: §D.3.2 · p. 50
  • The same proof extends to any function f(n) = ω(log n) by appropriately tuning the construction parameters.The resulting quasi-area-law pseudorandom states satisfy the corresponding entropy scaling for any contiguous partition.Source: §D.3.2 · p. 50

D.4 Proving 1–D quasi–area law

The one-dimensional construction obeys a boundary-dependent quasi-area law, and the snake embedding transfers the bound to a two-dimensional grid. However, these bounds need not saturate the universal ω(log n) lower bound for every cut.

D.4 Proving 1–D quasi–area law

  • For a one-dimensional arrangement, every partition has entanglement entropy bounded by the boundary size times O(poly log n).Subadditivity decomposes an arbitrary partition into B contiguous cuts, each bounded by Theorem D.4.Source: §D.4 · p. 50

D.5 Generalizing the construction for 2–D

  • For a two-dimensional grid filled as a one-dimensional snake, a boundary of size B cuts the snake in O(B) places, giving the analogous quasi-area-law bound.Each crossing defines a contiguous one-dimensional partition, so subadditivity and the one-dimensional theorem apply.Source: §D.5 · p. 51

D.6 A discussion on entanglement scaling

  • When B = O(log n), the upper bounds can remain separated from the ω(log n) SWAP-test lower bound, so the lower bound is not generally saturated for every cut.The paper identifies a later construction that saturates the lower bound for every cut and spatial dimension.Source: §D.6 · p. 51

E Proof that the [GH20] pseudoentanglement construction is not a PRS

This section shows that the [GH20] construction is not pseudorandom: its states and underlying functions admit efficient distinguishers, while enlarging the field size can hide the distinguishing branch but leaves a related function-level obstruction.

E.1 The [GH20] construction based on Extended Trapdoor Claw-Free Functions (ETCFs)

  • The ETCF-based states hide approximately log q bits of entropy across the displayed bipartition, with entropies approximately (n + 1) log q and n log q.The construction uses the functions Cf and Cg with fixed, nonpublic s, u, and e′ parameters.Source: §E.1 · p. 52

E.2 Sketch that neither state is a pseudorandom quantum state

  • The [GH20] states encode Gaussian samples that can be exposed by measuring registers and checking the resulting histogram against Haar-random behavior.For the state construction, conditioning on b = 0 lets the distinguisher subtract Ax and test whether the remaining vector follows a Gaussian distribution.Source: §E.2 · p. 53

E.3 Larger field sizes

  • For polynomially large k, the enlarged-field states have entropies approximately t and ct, creating an entropy gap of approximately (1 − c)t, while the earlier distinguisher fails.The failure occurs because the measured vector b is zero only with inverse exponentially small probability.Source: §E.3 · p. 53

E.4 Sketch that neither function is a pseudorandom function

  • Despite that measurement-based failure, the enlarged-field functions are not pseudorandom functions, because Gaussian outputs remain distinguishable from random-function outputs by their histograms.Querying the function at a fixed input yields a Gaussian histogram for Sg but a uniform histogram for a random function.Source: §E.3 · p. 53, §E.4 · p. 54

F Lower bound on entanglement entropy of pseudorandom states from the SWAP test

This section proves a lower bound on the entanglement entropy of pseudorandom states by showing that a sufficiently low-entropy state could be distinguished from a Haar-random state with a SWAP test.

F Lower bound on entanglement entropy of pseudorandom states from the SWAP test

  • Pseudorandom n-qubit states must have high entanglement entropy across an equipartition, as formalized by Proposition F.1.The proposition relates the reduced density matrix ρk to its entanglement entropy S(ρk) with high probability.Source: F Lower bound on entanglement entropy… · p. 54
  • The proof assumes low entropy and distinguishes the state from Haar randomness by tracing out half the registers and applying a SWAP test to the reduced states.The test outputs 0 for the candidate state and otherwise identifies a Haar-random state.Source: F Lower bound on entanglement entropy… · p. 54
  • The Haar-random comparison supplies the needed high-probability bound on the reduced-state spectrum and completes the contradiction.The argument uses spectral quantities of the reduced density matrix and Jensen’s inequality.Source: F Lower bound on entanglement entropy… · pp. 54–55

G Pseudorandom states and matrix product states

This section connects pseudorandom states to matrix product state descriptions and learning: efficient classical descriptions can be nearly optimal in size, yet efficient learning is ruled out under one-way functions.

G Pseudorandom states and matrix product states

  • Assuming one-way functions, no efficient quantum learner can output a polynomial-sized description of an efficiently describable state from polynomially many copies.The result applies even when the learner is promised that the state itself has an efficient description.Source: G Pseudorandom states and matrix… · p. 55
  • A hypothetical efficient learner for pseudorandom states would enable SWAP-test checking and thereby break the security of the pseudorandom-state construction.The contradiction follows by obtaining an efficient description of any efficiently preparable pseudorandom state.Source: G Pseudorandom states and matrix… · p. 55
  • For bond dimension χ = 2^poly log n, the MPS description size O(2^poly log n) is nearly optimal, although the lemma does not bound learning runtime or copy complexity.The absence of an efficient polynomial-copy learner establishes the lower boundary, while the lemma itself may require superpolynomial resources.Source: G Pseudorandom states and matrix… · p. 56
Loading 2211.00747v2…