Pith. sign in

REVIEW 4 major objections 6 minor 73 references

Near-Term Pseudorandom and Pseudoresource Quantum States

T0 review · 4 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper defines pseudorandom quantum states for sub-polynomial-time observers and shows they require fewer quantum resources as the observer's power shrinks.

desk verdict A useful new framework for weakening PRS, but the construction proofs cover fewer copies than the definition demands, and the unspecified runtime model undermines the sublinear claims. read the letter →

arxiv 2504.17650 v1 pith:Z3CAMZTR submitted 2025-04-24 quant-ph cs.CR

Andrew Tanggara , Mile Gu , Kishor Bharti This is my paper · ORCID
classification quant-phcs.CR MSC 81P68
keywords pseudorandomquantumstatesnear-termcomputersT-negligiblefunctionssubsetphasepseudoresourcecoherenceentanglement
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Pseudorandom quantum states (PRS) are ensembles that look Haar-random to efficient quantum algorithms, but "efficient" has always meant polynomial-time. This paper relaxes that to observers whose runtime grows slower than any polynomial, defining T-PRS for a runtime bound T(n). It gives two explicit constructions, based on subset phase states and subset states, and shows that if the subset is super-polylarge relative to f(n), the states are f(n)-PRS with constant copies, and poly(f(n))-PRS when the subset is super-polylarge relative to poly(f(n)) and the observer gets poly(f(n)) copies. The paper then proves that the minimum coherence, entanglement, and magic needed to impersonate Haar-random states decreases as the observer's computational power decreases, so computationally weaker observers can be fooled by cheaper quantum states.

What carries the argument

The load-bearing machinery is a parameterized notion of computational indistinguishability. A function is T-negligible if it is eventually smaller than 1/g(n) for every g in Theta(T), and the closure properties under addition and repetition, with repetition consistency, ensure that repeating a distinguishing test does not amplify success beyond negligibility. Indistinguishability is defined for algorithms whose runtime on t copies stays within O(T(n)). The explicit states are f,S-subset phase states, uniform superpositions over a subset S with phases (-1)^{f(x)}, and subset states, which drop the phase. Their security follows from a hybrid argument using T-quantum-secure pseudorandom phase functions and T-quantum-secure pseudorandom permutations, together with trace-distance bounds inherited from prior subset-phase and subset-state constructions. For resources, the proofs use constant-size circuits as distinguishers: a projective measurement for Hilbert-Schmidt coherence, the SWAP test for entanglement, and the Hadamard test for magic.

What would settle it

Exhibit a quantum algorithm with runtime O(T(n)) that, given O(1) copies of an f,S-subset phase state with |S| in omega(f(n)), guesses whether the input is from that ensemble or from the Haar-random ensemble with advantage larger than any T-negligible function. Since the proof reduces this to the trace-distance closeness of random subset phase states to Haar-random states, a direct computation showing a non-negligible trace distance for some f would also falsify the construction.

Watch

Extended reading notes

Core claim

The paper's central claim is that pseudorandomness does not require the full polynomial-time security framework. Theorems 17 and 21 state that subset phase states and subset states whose subset size is |S| in omega(f(n)) form f(n)-PRS with O(1) copies, and with |S| in omega(poly f(n)) form poly(f(n))-PRS with O(poly f(n)) copies, where f is any non-decreasing polynomially bounded function. Indistinguishability holds with respect to the paper's T-negligible functions and repeat-consistency conditions. For T equal to linearithmic, linear, polylogarithmic, and logarithmic, the paper derives lower bounds on the expected relative entropy of coherence, entanglement entropy, and stabilizer Renyi entropy of any ensemble that is T-indistinguishable from Haar-random; these bounds fall as T falls, yielding larger pseudoresource gaps for weaker observers.

Load-bearing premise

The constructions inherit their security from T-quantum-secure pseudorandom phase functions and permutations for the same runtime bound T; if no such primitives exist for subpolynomial T, the explicit T-PRS constructions collapse.

Editorial extensions

If this is right

  • Subset phase states with |S| in omega(f(n)) are f(n)-PRS with constant copies, and subset states with omega(f(n)) < |S| < o(2^n) are f(n)-PRS with constant copies.
  • With |S| in omega(poly f(n)) and O(poly f(n)) copies, both families are poly(f(n))-PRS.
  • Any ensemble that is T-indistinguishable from Haar-random must carry at least the stated expected coherence, entanglement, and magic; for weaker observers these required amounts shrink, implying that near-term devices can use lower-resource states to mimic randomness.
  • The pseudoresource gap between a T-PRS and the Haar-random ensemble sits strictly between the gap for polynomial-time PRS and the zero-resource gap of pseudorandom density matrices.
  • The T-framework can be applied to other pseudorandom objects, including pseudorandom density matrices, function-like states, unitaries, and isometries.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If T-quantum-secure pseudorandom phase functions and permutations exist for subpolynomial T, then near-term hardware would only need to prepare subset states with modestly large subsets to pass subpolynomial-time scrutiny; this is a directly testable prediction on small devices.
  • The resource lower bounds are necessary conditions, not sufficiency: a state with the required coherence, entanglement, or magic need not be pseudorandom, and the paper's constructions are one explicit way to meet the bounds.
  • The same T-indistinguishability formulation could convert any resource-versus-observer tradeoff into a quantitative relation whenever a small distinguishing circuit is known, potentially covering resources beyond coherence, entanglement, and magic.
  • The paper leaves open the case where the generator is also T-bounded rather than polynomial-time; if that were achieved, T-PRS would be useful for low-power preparation, not only low-power verification.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper generalizes pseudorandom quantum states (PRS) to a notion of T-PRS, where the distinguisher's runtime is bounded by a subpolynomial function T(n). It introduces T-negligible functions, defines T-indistinguishability, and proposes two constructions: subset phase states and subset states, built from T-quantum-secure pseudorandom phase functions and permutations. It then derives lower bounds on the coherence, entanglement, and magic of any low-resource ensemble that is T-indistinguishable from a high-resource ensemble, and tabulates how these required resources decrease as T goes from polynomial to logarithmic time. The central claims are Theorems 17 and 21 (the constructions) and Propositions 22–24 with Tables I–III (the resource characterization).

Significance. If the main theorems were valid, the paper would provide a useful framework for near-term pseudorandomness and an interesting quantitative connection between an observer's computational power and the amount of quantum resource that can be faked. The closure-property treatment of T-negligible functions is clean, and the resource lower-bound propositions are internally coherent derivations from the imposed indistinguishability assumption. The paper is also explicit that its constructions are conditional on T-secure pseudorandom primitives. However, the positive constructions and the resource bounds are not simultaneously supportable: the runtime model is never fixed, and the security definition demands indistinguishability for all allowed copy counts while the proofs only cover very restricted copy counts. These issues affect the paper's central claims, not merely its presentation.

major comments (4)
  1. [Section I.B, Definition 10; Section II.A, Theorem 17 and Remark 16] Definition 10 defines T-indistinguishability by quantifying over every function t(n) such that s(nt(n)) ∈ O(T(n)) for the distinguisher's runtime s. However, Proposition 15 and Theorem 17 only establish indistinguishability for t(n) ∈ O(1) in the f(n) case, and Remark 16 explicitly restricts to this copy count. This is not a harmless simplification: for T(n) = log n and s(N) = O(log N), any polynomial t(n) = n^c satisfies s(nt(n)) = O(log n), so polynomial copy numbers are allowed by Definition 10. The proofs therefore do not establish that the constructed ensembles are T-PRS as defined.
  2. [Section II.A, Theorem 17(1); Section II.B, Theorem 21(1)] Under a circuit-depth cost model, the constructions are falsified by a simple collision test. Take f(n) = log n and choose subset size |S| = n, which is allowed because n = ω(log n) and, for subset states, n < o(2^n). Let t(n) = n + 1. Since log(n(n+1)) = O(log n), this t(n) is permitted by Definition 10. A depth-O(log n) circuit can measure all t copies in the computational basis and check whether two of the t n-bit outcomes coincide, using an AND-tree comparison of O(log n) depth. For a subset phase state or subset state with |S| = n, the t outcomes are i.i.d. uniform over a fixed set of size n, so a collision is certain; for a Haar-random state, the collision probability is O(t^2/2^n), which is negligible. This gives a distinguisher with advantage 1, contradicting Theorems 17(1) and 21(1) if 'runtime' means circuit depth. The same construction with |S| = n^k and t = n^k + 1 works for polylogarithmic T.
  3. [Section III.A–C, Propositions 22–24] The resource lower-bound proofs use distinguishers that act on entire n-qubit registers: the projector Π_c2 in Proposition 22, the SWAP test in Proposition 23, and the Hadamard test in Proposition 24. If 'runtime' means circuit size (gate count), these distinguishers require Ω(n) gates or more, so they are not available to an O(log n)-time or O(polylog n)-time observer; the statement in the proof of Proposition 23 that the SWAP test is a 'constant-size' circuit is false in this model. If 'runtime' means circuit depth, these tests are cheap, but then the collision attack in the previous comment invalidates the T-PRS constructions. The manuscript never fixes the cost model, so the central claim that the positive constructions and the resource lower bounds coexist is not well-defined.
  4. [Definition 12 and Theorems 17 and 21] The constructions are conditional on the existence of T-QPRPF and T-QPRP with evaluation time O(T(n)) and security against O(T(n))-time adversaries. No construction or supporting evidence for these primitives is provided for subpolynomial T, and the abstract's reference to standard quantum-secure pseudorandom functions and permutations is not the same as the T-secure primitives used in the proofs. The paper should state clearly that Theorems 17 and 21 are conditional on the existence of these stronger primitives and should discuss their plausibility, since the claimed 'constructions' otherwise rest on an unproven assumption.
minor comments (6)
  1. [Section I.A, Definition 3] The notation Θ(T) is used for a family of functions T, but this is not standard and should be defined carefully, since T is a set of functions rather than a single function.
  2. [Figure 1 caption] The caption contains a duplicated expression 'A(E_k[|ψ_k>])∈{0,1}' where the second occurrence should refer to the φ ensemble.
  3. [Abstract and Section II] The abstract says the constructions use 'quantum-secure pseudorandom functions and pseudorandom functions', while the body uses T-QPRPF and T-QPRP; the terminology should be aligned, and the word 'demonstate' should be corrected.
  4. [Remark 16] Remark 16 says t(n) = O(1) is required to satisfy f(n)-indistinguishability, but this conflicts with the universal quantification over t(n) in Definition 10; the remark should be reconciled with the definition rather than simply stating the restriction.
  5. [Section II.A, Lemma 14 and Theorem 17 proof] Lemma 14 states that the subset phase state can be generated by a circuit of depth O(polyn), while the proof of Theorem 17 says the states can be generated 'in O(n)'; the manuscript should specify whether this is circuit size or depth, since the two notions behave very differently for sublinear T.
  6. [Table III caption] The caption contains an incomplete sentence ('We assume that Right column...') and should be rewritten.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the T-PRS constructions are conditional on explicitly stated external primitives, and the resource lower bounds follow directly from the definition of T-negligibility rather than from fitted inputs or self-referential derivations.

full rationale

The paper's central T-PRS constructions (Theorems 17 and 21) are conditional on the assumed existence of T-QPRPF and T-QPRP primitives (Definition 12) and on external trace-distance bounds cited from prior work (Lemma 14 from [4] and Lemma 19 from [6]). These are genuine external hypotheses, not inputs secretly defined by the target conclusions. Proposition 15 and Proposition 20 choose subset sizes omega(f(n)) or omega(polyf(n)) so that the cited trace-distance bounds become T-negligible; this is parameter selection in an explicit construction, not fitting a prediction to data. The resource lower bounds in Propositions 22-24 and Tables I-III follow by taking the T-negligible function eta from the T-indistinguishability definition and inverting the relevant test probabilities; this is a direct mathematical consequence of the definition of T-negligible, not a circular equivalence. While the paper cites prior works with overlapping authors ([9] and [22]), those citations are used for comparison or corroboration and are not load-bearing for the derivation. No equation is shown to equal its input by construction, and no fitted parameter is renamed as a prediction. The sublinear-T claims raise legitimate questions about the meaning of 'runtime' in the cost model, but that is a correctness and rigor concern, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 3 invented entities

The paper introduces no fitted constants. The central results rest on the assumed existence of subpolynomial-time pseudorandom functions and permutations and on cited trace distance bounds for random subset states. The resource lower bounds are derived from the T-indistinguishability definition rather than from data.

assumptions (4)
  • domain assumption Existence of T-quantum-secure pseudorandom phase functions (T-QPRPF) and T-quantum-secure pseudorandom permutations (T-QPRP) for the target runtimes f(n) and polyf(n).
    Theorems 17 and 21 reduce T-PRS security to these primitives; no constructions or reductions for these primitives are given in the paper.
  • domain assumption Trace distance bounds for random subset phase states (Aaronson et al., ref [4], Theorem 2) and random subset states (Giurgica-Tiron and Bouland, ref [6], Theorem 1) are accepted as given.
    These bounds are used directly in Propositions 15 and 20 to set the subset size and prove T-negligibility.
  • standard math Standard cryptographic closure properties of negligible functions under addition and repetition (Katz and Lindell, ref [24], Proposition 3.6).
    Used in Definitions 1 and 7 and Propositions 8 and 9 to justify the choice of repeat functions.
  • domain assumption Resource measure relations: C(rho) >= -log(1-C2(rho)), H(rho) >= H2(rho), and the stabilizer Renyi entropy formulas in eqns (37), (59), and (78).
    These are taken from the cited resource theory literature and used to convert distinguishing tests into resource lower bounds.
invented entities (3)
  • T-pseudorandom quantum state (T-PRS)
    purpose: Generalize PRS to observers with subpolynomial runtime; used as efficient stand-in for Haar-random states in near-term settings.
    Definitional concept introduced in Definition 11; no falsifiable prediction outside the framework.
  • T-quantum-secure pseudorandom phase function and permutation (T-QPRPF and T-QPRP)
    purpose: Cryptographic primitives assumed to exist; used to build T-PRS constructions in Section II.
    Assumed primitives; the paper does not construct them or provide independent evidence of their existence.
  • T-pseudoresource pair
    purpose: Pair of T-indistinguishable ensembles with different amounts of a quantum resource; used to quantify resource gaps.
    Conceptual framework introduced in Section III; no independent empirical handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Term Pseudorandom and Pseudoresource Quantum States." pith.science (2026). https://pith.science/paper/Z3CAMZTR

@misc{pith2026250417650,
  author       = {Pith},
  title        = {Pith review of: Near-Term Pseudorandom and Pseudoresource Quantum States},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z3CAMZTR}},
  note         = {Machine review of arXiv:2504.17650}
}
abstract

A pseudorandom quantum state (PRS) is an ensemble of quantum states indistinguishable from Haar-random states to observers with efficient quantum computers. It allows one to substitute the costly Haar-random state with efficiently preparable PRS as a resource for cryptographic protocols, while also finding applications in quantum learning theory, black hole physics, many-body thermalization, quantum foundations, and quantum chaos. All existing constructions of PRS equate the notion of efficiency to quantum computers which runtime is bounded by a polynomial in its input size. In this work, we relax the notion of efficiency for PRS with respect to observers with near-term quantum computers implementing algorithms with runtime that scales slower than polynomial-time. We introduce the $\mathbf{T}$-PRS which is indistinguishable to quantum algorithms with runtime $\mathbf{T}(n)$ that grows slower than polynomials in the input size $n$. We give a set of reasonable conditions that a $\mathbf{T}$-PRS must satisfy and give two constructions by using quantum-secure pseudorandom functions and pseudorandom functions. For $\mathbf{T}(n)$ being linearithmic, linear, polylogarithmic, and logarithmic function, we characterize the amount of quantum resources a $\mathbf{T}$-PRS must possess, particularly on its coherence, entanglement, and magic. Our quantum resource characterization applies generally to any two state ensembles that are indistinguishable to observers with computational power $\mathbf{T}(n)$, giving a general necessary condition of whether a low-resource ensemble can mimic a high-resource ensemble, forming a $\mathbf{T}$-pseudoresource pair. We demonstate how the necessary amount of resource decreases as the observer's computational power is more restricted, giving a $\mathbf{T}$-pseudoresource pair with larger resource gap for more computationally limited observers.

Figures

Figures reproduced from arXiv: 2504.17650 by the authors.

Figure 1
Figure 1. FIG. 1. In this illustration, we consider [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

73 extracted references · 60 canonical work pages

  1. [1]

    Given any number of copiest(n) of any n-qubit state ∣τ⟩ as an input to any algorithmA chosen by the observer, the runtime of computing its output A(∣τ⟩⊗t(n)) is bounded bys(n)∈O(T(n))

    work page

  2. [2]

    For the observer with computational resource bounded by T, the negligible probabilityη(n) of its chosen algorithm A distinguishing ∣ψ⟩ and ∣φ⟩ given t(n) copies of them is preserved even when composing A with other algorithmA′ it has access to or by runningA repeatedly with total runtime still bounded asO(T(n)). After we have these requirements characteri...

    work page

  3. [3]

    Remark 2

    r(n)η1(n)∈ N for anyr ∈ R. Remark 2. The first closure property concerns two al- gorithms A and A′ with probabilities of distinguishing PRS and Haar-random states bounded byη1 and η2, re- spectively (in the sense of eqn (1)). This property guar- antees that the two algorithms combined together still give a negligible probability. Particularly if we denote...

    work page

  4. [4]

    There exists a uniform quantum circuit{Gn}n with sizeg(n)∈O(polyn)thatoutputsan n-qubitquan- tum stateGn(k)= ∣ψk⟩ given inputk

    work page

  5. [5]

    Ensemble {∣ψ⟩}ψ and n-qubit Haar-random state ensemble {∣φ⟩}φ are T-indistinguishable as defined in Definition 10

    work page

  6. [6]

    The set of negligible functionsneglT must satisfy the closure properties with respect to some repeat function R consistent with T as defined in Defini- tion 1 and Definition 7. Note that here the bound for theT-PRS generator is the same as the polynomial-time PRS, namely that we 6 demand the generator must be a polynomial-size circuit regardless of T boun...

    work page

  7. [7]

    For number of copiest ∶= t(n) ∈ O(1) and size of subset ∣S∣ = 2m ∶= 2m(n) ∈ ω(f(n)), the trace dis- tance in eqn.(17) is f(n)-negligible. 7

    work page

  8. [8]

    For number of copiest ∶=t(n) ∈O(polyf(n)) and size of subset∣S∣ = 2m ∶= 2m(n) ∈ω(polyf(n)), the trace distance in eqn.(17) is polyf(n)-negligible. Proof. ForO(T)=O(f(n)), set the number of copies as t(n)∈O(1) and size of subset as2m(n) ∈ω(f(n)). Hence there existsc> 0 and N such thatn≥N⇒t(n)≤c and for allc′ > 0 there existsN such thatn ≥N ⇒ 2m(n) > c′f(n)...

    work page

Show all 73 references
  1. [9]

    A subset phase state ensemble{∣ψf,σ⟩}f,σ with sub- set size ∣S∣∈ω(f(n)) is af(n)-PRS given number of copiest∶=t(n)∈O(1)

  2. [10]

    A subset phase state ensemble{∣ψf,σ⟩}f,σ with sub- set size∣S∣∈ω(polyf(n)) is apolyf(n)-PRS given number of copiest∶=t(n)∈O(polyf(n)). Proof. These subset phase states can be generated in O(n) by Lemma 14, so we only need to show that it is T-indistinguishable to Haar-random s...

  3. [11]

    Hybrid 0:tcopies of size∣S∣∈ω(f(n))subset phase state ensemble {∣ψf,σ⟩}f,σ with f(n)-QPRPF f and f(n)-QPRP σ as an input toA

  4. [12]

    Hybrid 1: t copies of size ∣S∣ ∈ ω(f(n)) subset phase state ensemble{∣ψrσ,rf⟩}rσ,rf for uniformly random permutation and phase functionrσ, rf, re- spectively, as an input toA

  5. [13]

    Clearly, for t ∈ O(1) algorithm A outputs A(∣τ⟩⊗t) in s(nt) ∈ O(f(n)) since the input size is a just constant multiple ofn

    Hybrid 2:t copies of Haar random ensemble{∣φ⟩} as an input toA. Clearly, for t ∈ O(1) algorithm A outputs A(∣τ⟩⊗t) in s(nt) ∈ O(f(n)) since the input size is a just constant multiple ofn. Now we show that ∣ Pr f,σ [A(∣ψf,σ⟩⊗t(n))= 1]− Pr φ [A(∣φ⟩⊗t(n))= 1]∣<η(n) (22) forη(n)∈ ...

  6. [14]

    For number of copiest ∶= t(n) ∈ O(1) and subset size ∣S∣=m(n) satisfying ω(f(n))<m(n)<o(2n), the trace distance in eqn.(27) is f(n)-negligible

  7. [15]

    (27) is polyf(n)-negligible

    For number of copiest ∶=t(n) ∈O(polyf(n)) and subset size ∣S∣ = m(n) satisfying ω(polyf(n)) < m(n) < o(2n), the trace distance in eqn. (27) is polyf(n)-negligible. Proof. First, sett∶=t(n)=O(1)andm∶=m(n)suchthat ω(f(n))<m(n)<o(2n). We will evaluate the first term O(tm/2n) of t...

  8. [16]

    A subset state ensemble {∣ψσ⟩}σ with subset size ∣S∣ =m(n) such thatω(f(n)) <m(n) <o(2n) is a f(n)-PRS given number of copiest∶=t(n)∈O(1)

  9. [17]

    A subset state ensemble {∣ψσ⟩}σ with subset size ∣S∣ =m(n) such thatω(polyf(n)) <m(n) <o(2n) is a polyf(n)-PRS given number of copies t ∶= t(n)∈O(polyf(n)). Proof. Since {∣ψσ⟩}σ can be generated by anO(n) cir- cuit similar to the subset phase state construction, we only need t...

  10. [18]

    Hybrid 0: t copies of size ∣S∣ = m(n) such that ω(f(n)) < m(n) < o(2n) subset state ensemble {∣ψσ⟩}σ with f(n)-QPRP σ as an input toA

  11. [19]

    Hybrid 1: t copies of size ∣S∣ = m(n) such that ω(f(n))<m(n)<o(2n) subset phase state ensem- ble {∣ψrσ⟩}rσ for uniformly random permutationrσ as an input toA

  12. [20]

    free states

    Hybrid 2:t copies of Haar random ensemble{∣φ⟩} as an input toA. Clearly, for t ∈ O(1) algorithm A outputs A(∣τ⟩⊗t) in s(nt) ∈ O(f(n)) since the input size is a just constant multiple ofn. We use negligible function neglf(n) with respect to repeat function R = O(1), which is co...

  13. [21]

    T(n) = polyn = nO(1)), it holds that O(2−n)+ 1 polyn = 2−O(logn), (45) since polyn = nO(1) = 2O(1) logn = 2O(logn) and since O(2−n) grows slower than 2−ω(logn)

    For a poly-time observer (i.e. T(n) = polyn = nO(1)), it holds that O(2−n)+ 1 polyn = 2−O(logn), (45) since polyn = nO(1) = 2O(1) logn = 2O(logn) and since O(2−n) grows slower than 2−ω(logn). Thus, by Proposition 22, we obtain Eψ[C(ψ)]≥− log(2−O(logn))=ω(logn), (46) which agre...

  14. [22]

    T(n) = O(n logn), first note that for g(n) ∈ O(n logn), it holds that there exists c > 0 and N ∈ N such thatg(n)<cn logn ifn>N, which is equivalent to g(n)∈O(1)n logn

    For a linearithmic time observer (i.e. T(n) = O(n logn), first note that for g(n) ∈ O(n logn), it holds that there exists c > 0 and N ∈ N such thatg(n)<cn logn ifn>N, which is equivalent to g(n)∈O(1)n logn. Thus we can obtain the equiv- alence O(n logn)= 2O(1)+log(n logn), whi...

  15. [23]

    (49) Thus the expected relative entropy of coherence of {∣ψ⟩} is lower bounded as Eψ[C(ψ)]≥− log(2−O(1)−logn) =ω(1)+ logn

    For a linear-time observer (i.e.T(n) = O(n)), by using the equivalenceO(n)= 2O(1)+logn we have O(2−n)+ 1 O(n) = 2−O(1)−logn. (49) Thus the expected relative entropy of coherence of {∣ψ⟩} is lower bounded as Eψ[C(ψ)]≥− log(2−O(1)−logn) =ω(1)+ logn. (50)

  16. [24]

    T(n) = O(poly log(n))), first note that poly logn = logO(1)n = 2log(logO(1)n) = 2O(log logn)

    For polylogarithmic time observer (i.e. T(n) = O(poly log(n))), first note that poly logn = logO(1)n = 2log(logO(1)n) = 2O(log logn). Hence we obtain 2−γ(n)+ T(n)−1 =O(2−n)+ 2−O(log logn) = 2−O(log logn). (51) Then by using Proposition 22 this gives Eψ[C(∣ψ⟩)]≥− log(2−O(log lo...

  17. [25]

    T(n) = O(logn)), we have the equivalence O(logn) = 2O(1)+log logn which gives O(2−n)+ 2−O(1)−log logn = 2−O(1)−log logn, (53) since O(2−n) grows slower than 2−O(1)−log logn

    For logarithmic time observer (i.e. T(n) = O(logn)), we have the equivalence O(logn) = 2O(1)+log logn which gives O(2−n)+ 2−O(1)−log logn = 2−O(1)−log logn, (53) since O(2−n) grows slower than 2−O(1)−log logn. Thus the expected relative entropy of coherence of {∣ψ⟩} is lower b...

  18. [26]

    O(T) = O(poly(n))), it holds that forη ∈ neglpolyn 1 2ξ(n) +η(n)<O(2−n)+ 1 polyn = 2−O(logn)

    For a poly-time observer (i.e. O(T) = O(poly(n))), it holds that forη ∈ neglpolyn 1 2ξ(n) +η(n)<O(2−n)+ 1 polyn = 2−O(logn). (65) Hence by Proposition 23, Eψ[E(ψ)]≥− log(2−O(logn) =ω(logn), (66) which matches the bound in [4]

  19. [27]

    For linearithmic-time ( O(n logn)) observer, it holds that forη ∈ negln logn 1 2ξ(n) +η(n)<O(2−n)+ 1 O(n logn) =O(2−n)+ 2−O(1)−log(n logn) (67) Hence by Proposition 23, Eψ[E(ψ)]≥− log(O(2−n)+ 2−O(1)−log(n logn)) =ω(1)+ log(n logn). (68)

  20. [28]

    For linear-time observer (O(n)), it holds that for η ∈ negln 1 2ξ(n) +η(n)<O(2−n)+ 1 O(n) = 2−O(1)−logn (69) Hence by Proposition 23, Eψ[E(ψ)]≥− log(O(2−n)+ 2−O(1)−logn) =ω(1)+ logn. (70)

  21. [29]

    For polylogarithmic-time observer (O(poly logn)), it holds that forη ∈ neglpoly logn 1 2ξ(n) +η(n)<O(2−n)+ 2−O(log logn) (71) Hence by Proposition 23, Eψ[E(ψ)]≥− log(O(2−n)+ 2−O(log logn)) =ω(log logn). (72)

  22. [30]

    For logarithmic-time observer (O(logn)), it holds that forη ∈ negllogn 1 2ξ(n) +η(n)<O(2−n)+ 2−O(1)−log logn (73) Hence by Proposition 23, Eψ[E(ψ)]≥− log(O(2−n)+ 2−O(1)−log logn) =ω(1)+ log logn. (74) C. Magic resource gap Stabilizer Rényi-α entropy [31, 32] ofn-qubit stateρ i...

  23. [31]

    For poly-time observers (T(n) = polyn), we have η ∈ neglpoly, i.e. η(n) < 2−ω(logn) and α = t(n) ∈ O(polyn), hence − log(neglT(n))+ 2−(α−1)τ (n) neglT(n) α− 1 > ω(logn) α− 1 (89) 15 T(n) Eψ[Mα(ψ)] ∆Mα({φ},{ψ})≤ O(polyn) ω(logn) α−1 O(n) − ω(logn) α−1 O(n logn) ω(1)+log(nlogn) ...

  24. [32]

    Thus for such function f, it holds that for all c > 0 there existsN ∈ N such thatn ≥ N ⇒ logf(n) > logcn logn = logc+ log(n logn)

    For linearithmic-time observers, note that f ∈ O(n logn) means that for all c > 0 there exists N ∈ N such that n ≥ N → f(n) > cn logn. Thus for such function f, it holds that for all c > 0 there existsN ∈ N such thatn ≥ N ⇒ logf(n) > logcn logn = logc+ log(n logn). In other wo...

  25. [33]

    For linear-time observers we have − log(neglT(n))+ 2−(α−1)τ (n) neglT(n) α− 1 = − logη(n)−O(2−n) α− 1 > logω(n) α− 1 = ω(1)+ logn α− 1 . (91)

  26. [34]

    For polylogarithmic-time observers we have − log(neglT(n))+ 2−(α−1)τ (n) neglT(n) α− 1 = − logη(n)−O(2−n) α− 1 > log 2−ω(log logn) α− 1 = ω(1)+ log logn α− 1 . (92)

  27. [35]

    For logarithmic-time observers we have − log(neglT(n))+ 2−(α−1)τ (n) neglT(n) α− 1 = − logη(n)−O(2−n) α− 1 > logω(logn) α− 1 = ω(1)+ log logn α− 1 . (93) IV. DISCUSSION In this work, we extend the notion of pseudorandom- ness for quantum states from the regime of polynomial- t...

  28. [36]

    Pseudorandom quantum states

    Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceed- ings, Part III 38, pages 126–152. Springer, 2018

    2018

  29. [37]

    (pseudo) random quantum states with binary phase

    Zvika Brakerski and Omri Shmueli. (pseudo) random quantum states with binary phase. InTheory of Cryp- tography Conference, pages 229–250. Springer, 2019

    2019

  30. [38]

    Scalable pseudoran- dom quantum states

    Zvika Brakerski and Omri Shmueli. Scalable pseudoran- dom quantum states. InAnnual International Cryptology Conference, pages 417–440. Springer, 2020

    2020

  31. [39]

    Quantum pseudoentanglement

    Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Quantum pseudoentanglement. arXiv preprint arXiv:2211.00747, 2022

    2022 arXiv

  32. [40]

    Quantum pseudorandom scram- blers

    Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Quantum pseudorandom scram- blers. InTheory of Cryptography Conference, pages 3–35. Springer, 2024

    2024

  33. [41]

    Pseu- dorandomness from subset states

    Tudor Giurgica-Tiron and Adam Bouland. Pseu- dorandomness from subset states. arXiv preprint arXiv:2312.09206, 2023

    2023 arXiv

  34. [42]

    Cryptography from pseudorandom quantum states

    Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Annual International Cryptology Conference, pages 208–

  35. [43]

    Pseudorandom (function-like) quantum state generators: New definitions and applications

    Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. Pseudorandom (function-like) quantum state generators: New definitions and applications. In Theory of Cryptography Conference , pages 237–265. Springer, 2022

    2022

  36. [44]

    Pseudorandom density ma- trices

    Nikhil Bansal, Wai-Keong Mok, Kishor Bharti, Dax En- shan Koh, and Tobias Haug. Pseudorandom density ma- trices. arXiv preprint arXiv:2407.11607, 2024

    2024 arXiv

  37. [45]

    Quantum unpredictability

    Tomoyuki Morimae, Shogo Yamada, and Takashi Ya- makawa. Quantum unpredictability. In International Conference on the Theory and Application of Cryptology and Information Security, pages 3–32. Springer, 2025

    2025

  38. [46]

    Grilo and Álvaro Yángüez

    Alex B. Grilo and Álvaro Yángüez. Quantum pseudore- sources imply cryptography, 2025

    2025

  39. [47]

    Quantum commitments and signatures without one-way functions

    Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Annual International Cryptology Conference, pages 269–295. Springer, 2022

    2022

  40. [48]

    Quantum advantage in learning from experiments.Sci- ence, 376(6598):1182–1186, 2022

    Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. Quantum advantage in learning from experiments.Sci- ence, 376(6598):1182–1186, 2022

    2022

  41. [49]

    Computational pseudorandomness, the wormhole growth paradox, and constraints on the ads/cft duality.arXiv preprint arXiv:1910.14646, 2019

    Adam Bouland, Bill Fefferman, and Umesh Vazirani. Computational pseudorandomness, the wormhole growth paradox, and constraints on the ads/cft duality.arXiv preprint arXiv:1910.14646, 2019

    1910 arXiv

  42. [50]

    Cryptographic cen- sorship

    Netta Engelhardt, Åsmund Folkestad, Adam Levine, Evita Verheijden, and Lisa Yang. Cryptographic cen- sorship. Journal of High Energy Physics, 2025(1):1–58, 2025

    2025

  43. [51]

    The complexity of learning (pseudo) random dynamics of black holes and other chaotic systems

    Lisa Yang and Netta Engelhardt. The complexity of learning (pseudo) random dynamics of black holes and other chaotic systems. Journal of High Energy Physics, 2025(3):1–65, 2025

    2025

  44. [52]

    Dynamics of pseudoentanglement

    Xiaozhou Feng and Matteo Ippoliti. Dynamics of pseudoentanglement. Journal of High Energy Physics, 2025(2):1–53, 2025

    2025

  45. [53]

    Simulating quantum chaos without chaos

    Andi Gu, Yihui Quek, Susanne Yelin, Jens Eisert, and Lorenzo Leone. Simulating quantum chaos without chaos. arXiv preprint arXiv:2410.18196, 2024. 17

    2024 arXiv

  46. [54]

    Pseudo- entanglement is necessary for efi pairs

    Manuel Goulão and David Elkouss. Pseudo- entanglement is necessary for efi pairs. arXiv preprint arXiv:2406.06881, 2024

    2024 arXiv

  47. [55]

    Pseudoentanglement ain’t cheap

    Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Pseudoentanglement ain’t cheap. arXiv preprint arXiv:2404.00126, 2024

    2024

  48. [56]

    Pseu- doentanglement from tensor networks

    Zihan Cheng, Xiaozhou Feng, and Matteo Ippoliti. Pseu- doentanglement from tensor networks. arXiv preprint arXiv:2410.02758, 2024

    2024 arXiv

  49. [57]

    Pseu- dorandom unitaries are neither real nor sparse nor noise- robust

    Tobias Haug, Kishor Bharti, and Dax Enshan Koh. Pseu- dorandom unitaries are neither real nor sparse nor noise- robust. arXiv preprint arXiv:2306.11677, 2023

    2023 arXiv

  50. [58]

    Yelin, and Yihui Quek

    Andi Gu, Lorenzo Leone, Soumik Ghosh, Jens Eisert, Su- sanne F. Yelin, and Yihui Quek. Pseudomagic quantum states. Physical Review Letters, 132(21), May 2024

    2024

  51. [59]

    Chapmanand hall/CRC, 2007

    Jonathan Katz and Yehuda Lindell.Introduction to mod- ern cryptography: principles and protocols. Chapmanand hall/CRC, 2007

    2007

  52. [60]

    Quantum resource the- ories

    Eric Chitambar and Gilad Gour. Quantum resource the- ories. Reviews of modern physics, 91(2):025001, 2019

    2019

  53. [61]

    Resources of the quantum world

    Gilad Gour. Resources of the quantum world. arXiv preprint arXiv:2402.05474, 2024

    2024

  54. [62]

    Quantifying coherence

    Tillmann Baumgratz, Marcus Cramer, and Martin B Plenio. Quantifying coherence. Physical review letters, 113(14):140401, 2014

    2014

  55. [63]

    Colloquium: Quantum coherence as a resource.Re- views of Modern Physics, 89(4):041003, 2017

    Alexander Streltsov, Gerardo Adesso, and Martin B Ple- nio. Colloquium: Quantum coherence as a resource.Re- views of Modern Physics, 89(4):041003, 2017

    2017

  56. [64]

    Concentrating partial en- tanglement by local operations

    Charles H Bennett, Herbert J Bernstein, Sandu Popescu, and Benjamin Schumacher. Concentrating partial en- tanglement by local operations. Physical Review A, 53(4):2046, 1996

    1996

  57. [65]

    The tangled state of quantum hy- pothesis testing

    Mario Berta, Fernando GSL Brandão, Gilad Gour, Lu- dovico Lami, Martin B Plenio, Bartosz Regula, and Marco Tomamichel. The tangled state of quantum hy- pothesis testing. nature physics, 20(2):172–175, 2024

    2024

  58. [66]

    Stabilizer rényi entropy

    Lorenzo Leone, Salvatore FE Oliviero, and Alioscia Hamma. Stabilizer rényi entropy. Physical Review Let- ters, 128(5):050402, 2022

    2022

  59. [67]

    Stabilizer entropies and nonstabilizerness monotones

    Tobias Haug and Lorenzo Piroli. Stabilizer entropies and nonstabilizerness monotones. Quantum, 7:1092, 2023

    2023

  60. [68]

    Efficient quantum algorithms for stabilizer entropies.Physical Re- view Letters, 132(24):240602, 2024

    Tobias Haug, Soovin Lee, and Myung-Shik Kim. Efficient quantum algorithms for stabilizer entropies.Physical Re- view Letters, 132(24):240602, 2024

    2024

  61. [69]

    PhD thesis, Uni- versity of Massachusetts Boston, 2023

    Lorenzo Leone.Clifford Group and Beyond: Theory and Applications in Quantum Information. PhD thesis, Uni- versity of Massachusetts Boston, 2023

    2023

  62. [70]

    Random unitaries in extremely low depth.arXiv preprint arXiv:2407.07754, 2024

    Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth.arXiv preprint arXiv:2407.07754, 2024

    2024 arXiv

  63. [71]

    How to construct ran- dom unitaries

    Fermi Ma and Hsin-Yuan Huang. How to construct ran- dom unitaries. arXiv preprint arXiv:2410.10116, 2024

    2024 arXiv

  64. [72]

    Pseudorandom isometries

    Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin. Pseudorandom isometries. InAnnual In- ternational Conference on the Theory and Applications of Cryptographic Techniques, pages 226–254. Springer, 2024

    2024

  65. [73]

    Computational entanglement theory

    Rotem Arnon-Friedman, Zvika Brakerski, and Thomas Vidick. Computational entanglement theory. arXiv preprint arXiv:2310.02783, 2023

    2023 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.