Unconditional Pseudorandomness against Shallow Quantum Circuits

Sathyawageeswar Subramanian; Soumik Ghosh; Wei Zhan

REVIEW 2 major objections 4 minor 23 references

Unconditional Pseudorandomness against Shallow Quantum Circuits

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Every approximate state 2-design is unconditionally pseudorandom against shallow quantum circuits.

desk verdict First unconditional quantum pseudorandomness against shallow circuits, with a patchable gap in the PRU concentration lemma; deserves a serious referee. read the letter →

arxiv 2507.18796 v1 pith:DAKSDO4T submitted 2025-07-24 quant-ph cs.CC

Soumik Ghosh , Sathyawageeswar Subramanian , Wei Zhan This is my paper · ORCID

classification quant-phcs.CC MSC 81P6868Q12

keywords quantumpseudorandomnessstate2-designsunitaryQNC0AC0composedwithpseudoentanglementshallowcircuitsunconditionalsecurity

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

This paper proves that quantum pseudorandomness can be obtained with no cryptographic assumptions at all when the distinguisher is a shallow quantum circuit. The central claim is that any efficient approximate state 2-design - an ensemble matching the first two Haar moments - is already indistinguishable from Haar-random states for QNC0 circuits of constant depth and for AC0 composed with QNC0 circuits with limited ancillae, and that any unitary 2-design is a non-adaptive pseudorandom unitary against one-dimensional geometrically local QNC0 circuits. It also constructs unconditionally pseudoentangled states from random phased subspace states whose phases come from a 4-wise independent function. If correct, these results close the gap between statistical and computational pseudorandomness for shallow adversaries: matching two copies of a Haar object is enough, whereas against polynomial-time quantum distinguishers extra copies break the illusion. The bridge is a concentration phenomenon: in a 2-design, the reduced state on any small subsystem of many copies is close to maximally mixed, so the small lightcone of a shallow circuit cannot tell the ensemble from Haar.

What carries the argument

The key mechanism is a lightcone argument combined with concentration estimates. Because a depth-$d$ shallow circuit has each output depending on only $k=2^{O(d)}$ input qubits, indistinguishability reduces to comparing reduced states on $k$-qubit subsystems. The paper's Corollaries 3.2 and 3.3 state that for a Haar random state or an approximate 2-design, the reduced state on every small subsystem of $t$ copies is close to maximally mixed, with failure probability bounded by an explicit expression. For the unitary results, Lemma 4.3 bounds the expected Frobenius norm of partial traces of off-diagonal terms conjugated by a Haar random unitary, and Corollaries 4.4 and 4.5 combine this with a recursive Schmidt decomposition of the output of a one-dimensional geometrically local shallow circuit. For the AC0 post-processing step, Lemma 3.10 extends Braverman's theorem that polylogarithmic independence fools AC0 to distributions that are only almost $k$-wise indistinguishable but have high min-entropy, which is what limits the ancilla count.

What would settle it

Recompute Corollary 3.3 exactly: Lemma 2.7 gives $E[\mathrm{Tr}(\rho_A^2)-2^{-k}] \le \varepsilon + 2^{k-n}$, not $\varepsilon + 2^{-n}$, so the claimed failure probability $n^{O(k)}(\varepsilon + 2^{-n})^{1/2}\delta^{-1}$ must be corrected. Also test the summation inequality in the proof of Corollary 4.4 on a concrete recursive Schmidt decomposition; if it fails for some valid state, the claimed failure probability $O(r)2^{k-n/2}\delta^{-1}$ is not established and the parameter choices for Theorem 4.6 would need adjustment.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that every approximate state 2-design with negligible error is an unconditionally secure pseudorandom state against QNC0 circuits with arbitrarily many ancillae, and against AC0 composed with QNC0 circuits with almost linear ancillae for exact designs. It also establishes that every unitary 2-design is a non-adaptive secure pseudorandom unitary against one-dimensional geometrically local QNC0 circuits, even with limited AC0 post-processing, and that random phased subspace states with 4-wise independent phases are unconditionally pseudoentangled against these classes. The defining feature is that the only structural property required is matching two Haar moments; no one-way functions or other complexity assumptions appear. The paper's main theorems are Theorem 1.1, Corollary 3.5, Theorem 4.6, Theorem 4.7, and Corollary 3.13.

Load-bearing premise

The load-bearing premise is that every small-subsystem reduced state of many copies of a 2-design, or of Haar objects after shallow pre-processing, is close to maximally mixed with the failure probability stated in Corollaries 3.3 and 4.4; as written, those two concentration estimates contain an exponent mismatch and an invalid summation inequality, so the proofs need repair before the main theorems are fully established.

Editorial extensions

If this is right

Any efficiently implementable state 2-design becomes a drop-in unconditionally secure pseudorandom state for shallow quantum distinguishers, with no cryptographic setup required.
Against QNC0 the security holds even with arbitrarily many ancillae, so the result covers realistic near-term circuits where auxiliary qubits are freely available.
Unitary 2-designs yield parallel-query pseudorandom unitaries against one-dimensional geometrically local QNC0 circuits, giving a simple shallow-circuit construction of a quantum pseudorandom unitary.
Random phased subspace states give the first unconditional pseudoentanglement against these shallow classes, with entanglement entropy at most $d$ across every cut.
As the paper notes, the same 2-design property cannot give security against BQP adversaries, since any $t$-design is distinguishable from Haar with more than $t$ copies; the shallow-circuit result is therefore not a path to standard assumption-free pseudorandomness.

Reading between the lines

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

The same lightcone-plus-concentration recipe may apply to other circuit classes with polylogarithmic lightcones, such as shallow Clifford circuits or noisy intermediate-scale devices; this is an extension the authors did not pursue.
If the concentration estimates are repaired, the pseudoentanglement construction is efficiently preparable, so it could be implemented on near-term hardware as a direct experimental test of the theory.
The results sharpen the contrast with the BQP setting: pseudorandomness against shallow circuits is not a weaker version of the standard notion but a different phenomenon, where two-copy statistical matching already implies computational indistinguishability.
The authors conjecture that 2-designs also fool QAC0 circuits; a natural next test is whether the min-entropy extension of Braverman's theorem has a quantum analogue for unbounded fan-out gates.

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.

Desk Editor's Note

read the letter

Quick take: this is the first unconditional quantum pseudorandomness against any natural circuit class, and the core idea—two Haar moments suffice when the adversary's lightcone is small—is genuinely new and, I think, correct. The paper is worth engaging with seriously, but the proofs of the concentration lemmas need repair before I would call them complete.

What's new: the theorems that any epsilon-approximate state 2-design is a PRS against QNC0 with arbitrary ancillae, and against AC0◦QNC0 with polylog ancillae; the pseudoentanglement construction from 4-wise independent phased subspace states; and the parallel-query PRU security of unitary 2-designs against 1D geometrically local QNC0. None of these appears in prior work, and they change the picture one might have had from BQP adversaries, where two copies are far from enough. The paper also does a good job of explaining why the lightcone argument stops at QNC0/AC0, and Lemma 3.10, a min-entropy generalization of Braverman's theorem, is a nice technical contribution on its own.

Soft spots: two technical gaps, both in the concentration machinery. Corollary 3.3 states a failure probability with (epsilon+2^{-n})^{1/2}, but the proof's intermediate bound gives (epsilon+2^{k-n})^{1/2}; the claimed bound is true, but the line "E <= 2^k (epsilon+2^{-n})^{1/2}" does not follow as written. In the regimes used, the extra factors are absorbed by the n^{O(k)} term, so the state PRS results survive. Corollary 4.4 is more serious. The identity used to sum the Schmidt branches is false: the left-hand side is (sum|a_i|)^2 - sum|a_i|^2, not (sum|a_i|)^2. And the bound sum_tau 2^{k_tau/2} <= 2^{k/2} is also false; the correct upper bound has a factor of t. So the stated O(r)·2^{k-n/2} delta^{-1} failure probability is not established; the proof at this level gives O(rt)·2^{k-n/2} delta^{-1}. Since t = poly(n) and k = o(n) in Theorems 4.6 and 4.7, the extra t is absorbed and the main theorems likely survive, but only after the lemma is fixed. This is a genuine gap in the written proof of the PRU claims, not a mere typo.

The citation pattern looks fine; prior constructions do rely on cryptographic assumptions, and the paper credits the relevant QAC0 and Braverman-type results.

Who should read it: anyone working on quantum pseudorandomness, shallow-circuit complexity, or near-term quantum advantage. I would put it on a reading group list and would cite the main theorem in my own work.

Recommendation: send to peer review. A serious referee should be able to verify the patch; the conceptual contribution is strong enough that this deserves journal-level attention after the concentration lemmas are corrected.

Referee Report

2 major / 4 minor

Summary. The paper studies unconditional pseudorandomness against shallow quantum circuit classes. It claims that every approximate 2-design state ensemble is a PRS against QNC^0 circuits with arbitrarily many ancillae (Theorem 3.4, Corollary 3.5) and against AC^0∘QNC^0 circuits with polylogarithmically many ancillae (Theorem 3.11, Corollary 3.12); that random phased subspace states yield pseudoentanglement (Corollary 3.13); and that every approximate unitary 2-design is a non-adaptive secure PRU against 1-dimensional geometrically local QNC^0 circuits (Theorems 4.6 and 4.7). The proof strategy combines lightcone arguments with concentration estimates showing that reduced states on small subsystems of t copies of a 2-design are close to maximally mixed, together with a generalization of Braverman's theorem to high min-entropy distributions.

Significance. The central conceptual message—that matching two Haar moments can suffice for computational pseudorandomness against natural constant-depth circuit classes—is novel and, if the technical estimates are corrected, would be an important result. It provides the first unconditional PRS and PRU constructions against restricted quantum adversaries and sharply contrasts with the BQP setting, where two-copy indistinguishability is insufficient. The paper is also methodologically transparent: the constructions are reductions from the external 2-design property, no fitted parameters appear, and the parameter regimes are stated explicitly. No machine-checked proofs or code are provided, but the main reductions are accessible to hand verification once the concentration lemmas are repaired.

major comments (2)

[§3, Corollary 3.3] The probability bound as stated is not what the proof establishes. From Lemma 2.7 the proof obtains E[Tr(ρ_A^2)−2^{−k}]^{1/2} ≤ (ε+2^{k−n})^{1/2}; the subsequent trace-norm bound should therefore contain a factor 2^{k/2} and the term (ε+2^{k−n})^{1/2}, not (ε+2^{−n})^{1/2} with a 2^k prefactor. Because Corollary 3.3 is the bridge used in Theorems 3.4, 3.11, and Corollary 3.13, this mismatch must be fixed. In the intended regimes k=o(n) and ε=2^{−Ω(n)} the corrected bound is still negligible, so the main theorems appear repairable, but the statement and proof need to be made consistent.
[§4, Corollary 4.4] The claimed failure probability is not established. The equality used to replace Σ_{i1,...,iτ} Σ_{jτ≠iτ} |α_{i1...iτ} α_{i1...iτ−1,jτ}| by Σ_{i1...iτ−1} (Σ_{iτ} |α_{i1...iτ}|)^2 is false; the left-hand side equals (Σ|α_i|)^2 − Σ|α_i|^2. The subsequent bound Σ_{τ=1}^t r·2^{(kτ−n)/2} ≤ r·2^{(k−n)/2} is also unjustified because Σ_τ 2^{kτ/2} ≤ 2^{k/2} is false in general; the correct upper bound carries a factor t. The same missing factor t appears in the hybrid argument for the diagonal terms. As written the lemma gives only O(rt)·2^{k−n/2}δ^{−1}. Since t=poly(n) in Theorems 4.6 and 4.7, the extra factor is absorbed and those theorems appear salvageable, but Corollary 4.4 must be corrected before Theorem 4.6 is fully proved.

minor comments (4)

[§3, Lemma 3.10] The proof of Lemma 3.10 contains an apparent typo: the first bullet after invoking Braverman's lemma refers to D′_2, whereas the subsequent min-entropy argument concerns D_1 and transfers bounds from the uniform distribution via the 2^r factor; the intended statement should be clarified.
[§3, Theorem 3.4 and Corollary 3.5] The role of ancillae is left implicit: Corollaries 3.2 and 3.3 apply to the input state copies, while ancillae have fixed initial states. The proof should state explicitly that the ancilla part of the lightcone contributes the same deterministic state in both ensembles, so the trace-distance bound applies only to the input-qubit part of the lightcone.
[Throughout] There are several small typos: 'an QNC0 circuit' in the Figure 1 caption, 'techinical issue' and 'lower bound lower bound' in Section 5, and a duplicated 'every' in Definition 2.3.
[§3, Theorem 3.11] The symbol R is used both for the corrupted-qubit subsystem and for the output distribution on those bits; using a different symbol for the distribution would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorems are reductions from the external 2-design property to pseudorandomness against fixed shallow circuit classes, with no fitted constants, no load-bearing self-citations, and no definitional equivalence between inputs and outputs.

full rationale

The paper's central claims are conditional reductions of the form: if an ensemble is an (approximate) 2-design, then it is indistinguishable from Haar-random against QNC^0 or AC0∘QNC^0 adversaries. The 2-design property is an external statistical input, not defined in terms of PRS/PRU security. The proofs convert second-moment matching into t-copy indistinguishability through explicit concentration lemmas (Corollaries 3.2, 3.3, 4.4, 4.5) based on lightcone size and Schmidt-rank bounds. These lemmas are proved from first principles using Lemma 2.7/2.9, Lubkin's formula, and a Haar-random unitary off-diagonal bound (Lemma 4.3). The Haar distribution serves as an external benchmark; no parameter is fitted to the target distinguisher and then renamed a prediction. The external technical inputs, Braverman's theorem and BIV+16, are independent of the authors. Self-citations such as [ABF+24], [BFG+23], [GLG+24], and [CCG+25] appear only in related-work discussion and are not load-bearing. The skeptical concerns about Corollary 4.4's summation factor and Corollary 3.3's exponent are correctness and repair issues in the proofs as written, not cases where a claimed output is equivalent to an input by construction; they do not raise the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data; epsilon, delta, and k are analytic parameters, not empirically chosen constants. The random phased subspace state is a mathematical construction, not a new physical entity. The axioms are standard results from the literature, each explicitly cited. Correctness risk comes from proof details in the concentration lemmas, not from hidden assumptions.

assumptions (5)

standard math Second-moment formula for reduced density matrices of Haar random states (Lemma 3.1, citing Lubkin and Liu et al.).
Used in Corollaries 3.2 and 3.3 to show small subsystems are nearly maximally mixed for both Haar states and approximate 2-designs.
standard math Braverman's theorem that AC0 circuits are fooled by almost k-wise independent distributions (Lemma 3.8).
Used in Theorem 3.9 and Lemma 3.10 to handle the classical AC0 post-processing.
standard math Existence of nearby k-wise indistinguishable distributions with controlled min-entropy, attributed to Bogdanov, Ishai, Viola, and Williamson (used in Lemma 3.10).
Needed to extend the Braverman argument to the high-min-entropy, almost-k-wise-indistinguishable setting.
standard math Schmidt decomposition facts and the rank bound for 1-dimensional local QNC circuits (Lemmas 2.11 and 4.1).
Underlies the recursive Schmidt decomposition used for the PRU proofs.
domain assumption Definition of QNC0, AC0, and AC0 after QNC0 circuits, including the convention that circuits do not need to compute cleanly.
All security statements are relative to these specific circuit classes and the ancilla model defined in Section 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Unconditional Pseudorandomness against Shallow Quantum Circuits." pith.science (2026). https://pith.science/paper/DAKSDO4T

@misc{pith2026250718796,
  author       = {Pith},
  title        = {Pith review of: Unconditional Pseudorandomness against Shallow Quantum Circuits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DAKSDO4T}},
  note         = {Machine review of arXiv:2507.18796}
}

abstract

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: $\bullet$ Any quantum state 2-design yields unconditional pseudorandomness against both $\mathsf{QNC}^0$ circuits with arbitrarily many ancillae and $\mathsf{AC}^0\circ\mathsf{QNC}^0$ circuits with nearly linear ancillae. $\bullet$ Random phased subspace states, where the phases are picked using a 4-wise independent function, are unconditionally pseudoentangled against the above circuit classes. $\bullet$ Any unitary 2-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}^0$ adversaries, even with limited $\mathsf{AC}^0$ postprocessing. Our indistinguishability results for 2-designs stand in stark contrast to the standard setting of quantum pseudorandomness against $\mathsf{BQP}$ circuits, wherein they can be distinguishable from Haar random ensembles using more than two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

Figures

Figures reproduced from arXiv: 2507.18796 by the authors.

**Figure 1.** An illustration of the proof of Theorem 3.11, with partial systems and unitary lightcones in an QNC0 circuit. To prove the claim, let A be the ancilla qubits, and ρA be the initial state of the ancillae. Let the unitary operator UR consist of all gates in the QNC0 circuit that belongs to the lightcone of the ancillae. Fixing any k output qubits K, we extending K to K ∪ R so that it contains all the corrupted qubits,… view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 12 canonical work pages

[1]

Quantum Pseudoentanglement

[ABF+24] Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. “Quantum Pseudoentanglement”. Venkatesan Gu- ruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), 2:1–2:21, Dagstuhl, Germany. Schlo...

work page 2024
[4]

Polynomial-time tolerant testing stabi- lizer states

arXiv: 2410.06499 [quant-ph]. [AD25] Srinivasan Arunachalam and Arkopal Dutt. “Polynomial-time tolerant testing stabi- lizer states”. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC ’25, pages 1234–1241. ACM, June

work page arXiv
[7]

Local random quantum circuits are approximate polynomial-designs

arXiv: 2411.04353 [quant-ph]. [BHH16a] Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. “Local random quantum circuits are approximate polynomial-designs”. Communications in Mathemati- cal Physics, 346(2):397–434, August

arXiv
[8]

[CSB+25] Laura Cui, Thomas Schuster, Fernando Brandao, and Hsin-Yuan Huang

arXiv: 2507.13670 [quant-ph]. [CSB+25] Laura Cui, Thomas Schuster, Fernando Brandao, and Hsin-Yuan Huang. Unitary designs in nearly optimal depth,

arXiv
[9]

Random quantum circuits anticoncentrate in log depth

arXiv: 2507.06216 [quant-ph]. [DHB22] Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brandão. “Random quantum circuits anticoncentrate in log depth”. PRX Quantum, 3(1):010333,

arXiv
[10]

Improved pseudo- random generators for depth 2 circuits

[DET+10] Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. “Improved pseudo- random generators for depth 2 circuits”. Approximation, Randomization, and Combinato- rial Optimization. Algorithms and Techniques, APPROX/RANDOM 2010, volume 6302 of Lecture Notes in Computer Science, pages 504–517. Springer,

work page 2010
[13]

Better pseudorandom generators from milder pseudorandom restrictions

arXiv: 2312.09206 [quant-ph]. [GMR+12] Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P . Vadhan. “Better pseudorandom generators from milder pseudorandom restrictions”. 53rd An- nual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 120–129. IEEE Computer Society,

arXiv 2012
[14]

Pseudo-Entanglement is Necessary for EFI Pairs

arXiv: 2406.06881 [quant-ph]. [GNW21] David Gross, Sepehr Nezami, and Michael Walter. “Schur–weyl duality for the clifford group with applications: property testing, a robust hudson theorem, and de finetti representations”. Communications in Mathematical Physics, 385(3):1325–1393, June

work page Pith review arXiv

Show all 23 references

[16]

[JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song

arXiv: 2312.15285 [quant-ph]. [JLS18] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. Advances in Cryptology – CRYPTO

arXiv
[18]

Entanglement, quantum randomness, and complexity beyond scrambling

arXiv: 2202.00054 [quant-ph]. [LLZ+18] Zi-Wen Liu, Seth Lloyd, Elton Zhu, and Huangjun Zhu. “Entanglement, quantum randomness, and complexity beyond scrambling”. Journal of High Energy Physics , 2018(7):1–62,

2018 arXiv
[19]

On the Pauli spectrum of QAC0

arXiv: 2402.14803 [quant-ph]. [NPV+24] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. “On the Pauli spectrum of QAC0”. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1498–1506, Vancouver, BC, Canada. Association...

2024 arXiv
[20]

BPHSPACE(S)⊆ DSPACE(S3/2)

arXiv: 2401.03703 [cs.CR]. [SZ99] Michael E. Saks and Shiyu Zhou. “BPHSPACE(S)⊆ DSPACE(S3/2)”. J. Comput. Syst. Sci., 58(2):376–403,

arXiv
[21]

Parity vs. AC0 with simple quantum preprocessing

23 [Slo24] Joseph Slote. “Parity vs. AC0 with simple quantum preprocessing”. 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, volume 287 of LIPIcs, 92:1–92:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2024
[22]

Tight bounds on the fourier spectrum of AC0

[Tal17] Avishay Tal. “Tight bounds on the fourier spectrum of AC0”. 32nd Computational Complexity Conference, CCC 2017, volume 79 of LIPIcs, 15:1–15:31. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2017
[23]

How to construct quantum random functions

arXiv: 2302.11013 [hep-th]. [Zha21] Mark Zhandry. “How to construct quantum random functions”. J. ACM, 68(5), August

arXiv
[2006]

Better pseudodistributions and derandomization for space-bounded computation

[Hoz21] William M. Hoza. “Better pseudodistributions and derandomization for space-bounded computation”. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, volume 207 of LIPIcs, 28:1–28:23. Schloss Dagstuhl - Leibniz-Ze...

2021
[2012]

Eliminating intermediate measurements using pseudoran- dom generators

[GR22] Uma Girish and Ran Raz. “Eliminating intermediate measurements using pseudoran- dom generators”. 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPIcs, 76:1–76:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

2022
[2018]

[KP22] Iordanis Kerenidis and Anupam Prakash.Quantum machine learning with subspace states,

Springer International Publishing, 2018, pages 126–152. [KP22] Iordanis Kerenidis and Anupam Prakash.Quantum machine learning with subspace states,

2018
[2022]

[ADO+24] Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao.On the computational power of qac0 with barely superlinear ancillae,

arXiv: 2112.10020 [quant-ph]. [ADO+24] Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao.On the computational power of qac0 with barely superlinear ancillae,

arXiv
[2023]

[BZZ24] Adam Bouland, Chenyi Zhang, and Zixin Zhou

arXiv: 2311.12017 [quant-ph]. [BZZ24] Adam Bouland, Chenyi Zhang, and Zixin Zhou. On the hardness of learning ground state entanglement of geometrically local hamiltonians,

arXiv
[2024]

[AGQ+23] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen

arXiv: 2411.04978 [hep-th]. [AGQ+23] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. Pseudorandom (function-like) quantum state generators: new definitions and applications,

arXiv
[2025]

Bounded indistinguishability and the complexity of recovering secrets

[BIV+16] Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. “Bounded indistinguishability and the complexity of recovering secrets”. Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, volume 9816 of Lecture Notes in C...

2016
[2403]

Dynamics of pseudoentanglement

09619 [quant-ph]. [FI25] Xiaozhou Feng and Matteo Ippoliti. “Dynamics of pseudoentanglement”. Journal of High Energy Physics, 2025(2), February

2025

Pith tools

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

[1] [1]

Quantum Pseudoentanglement

[ABF+24] Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. “Quantum Pseudoentanglement”. Venkatesan Gu- ruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), 2:1–2:21, Dagstuhl, Germany. Schlo...

work page 2024

[2] [4]

Polynomial-time tolerant testing stabi- lizer states

arXiv: 2410.06499 [quant-ph]. [AD25] Srinivasan Arunachalam and Arkopal Dutt. “Polynomial-time tolerant testing stabi- lizer states”. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC ’25, pages 1234–1241. ACM, June

work page arXiv

[3] [7]

Local random quantum circuits are approximate polynomial-designs

arXiv: 2411.04353 [quant-ph]. [BHH16a] Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. “Local random quantum circuits are approximate polynomial-designs”. Communications in Mathemati- cal Physics, 346(2):397–434, August

arXiv

[4] [8]

[CSB+25] Laura Cui, Thomas Schuster, Fernando Brandao, and Hsin-Yuan Huang

arXiv: 2507.13670 [quant-ph]. [CSB+25] Laura Cui, Thomas Schuster, Fernando Brandao, and Hsin-Yuan Huang. Unitary designs in nearly optimal depth,

arXiv

[5] [9]

Random quantum circuits anticoncentrate in log depth

arXiv: 2507.06216 [quant-ph]. [DHB22] Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brandão. “Random quantum circuits anticoncentrate in log depth”. PRX Quantum, 3(1):010333,

arXiv

[6] [10]

Improved pseudo- random generators for depth 2 circuits

[DET+10] Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. “Improved pseudo- random generators for depth 2 circuits”. Approximation, Randomization, and Combinato- rial Optimization. Algorithms and Techniques, APPROX/RANDOM 2010, volume 6302 of Lecture Notes in Computer Science, pages 504–517. Springer,

work page 2010

[7] [13]

Better pseudorandom generators from milder pseudorandom restrictions

arXiv: 2312.09206 [quant-ph]. [GMR+12] Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P . Vadhan. “Better pseudorandom generators from milder pseudorandom restrictions”. 53rd An- nual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 120–129. IEEE Computer Society,

arXiv 2012

[8] [14]

Pseudo-Entanglement is Necessary for EFI Pairs

arXiv: 2406.06881 [quant-ph]. [GNW21] David Gross, Sepehr Nezami, and Michael Walter. “Schur–weyl duality for the clifford group with applications: property testing, a robust hudson theorem, and de finetti representations”. Communications in Mathematical Physics, 385(3):1325–1393, June

work page Pith review arXiv