Parallel Kac's Walk Generates PRU

Chuhan Lu; Fang Song; Minglong Qin; Mingnan Zhao; Penghui Yao

REVIEW 3 major objections 4 minor 23 references

Parallel Kac's Walk Generates PRU

T0 review · 3 major / 4 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 A linear number of repeated parallel Kac's walk steps is computationally indistinguishable from Haar-random unitaries, even against adversaries with inverse-query access.

desk verdict The paper proves the Kac-walk PRU conjecture with a substantial path-recording proof and adds inverse-query security; the main thing to check is the imported O(1/N^2) RSS bound from LQS+24. read the letter →

arxiv 2504.14957 v2 pith:4BYKIMRH submitted 2025-04-21 quant-ph cs.CCcs.CR

Chuhan Lu , Minglong Qin , Fang Song , Penghui Yao , Mingnan Zhao This is my paper · ORCID

classification quant-phcs.CCcs.CR

keywords pseudorandomunitariesparallelKac'swalkpath-recordingtechniqueHaar-randomrandomstatescramblerinverse-querysecurityquantumcryptography

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 claims that a linear number of sequential repetitions of the parallel Kac's walk forms a pseudorandom unitary family (PRU): after $T+1$ steps with $T=30n$ and $n$ qubits, the sampled unitary is computationally indistinguishable from the Haar measure on $U(N)$, where $N=2^n$. It further claims that $2T+1$ steps are statistically indistinguishable from Haar even to adversaries who may query both the unitary and its inverse. The construction is simply the repeated basic module of the walk—each step randomizes a permutation of the basis and applies independent $2\times2$ Haar rotations on paired states—so if the result is correct, PRUs can be built by iterating a single primitive. This confirms a conjecture from the paper that introduced the parallel Kac's walk and gives another demonstration that the path-recording proof technique yields adaptive security.

What carries the argument

The load-bearing objects are the distinct block subspace, the purified function-permutation oracle HPO, and the Compress isometry. The distinct block subspace consists of tuples of basis states lying in different two-element blocks, where a block is a pair of strings sharing the length-$(n-1)$ suffix; Lemma 3.1 shows that an $O(1/N^2)$-random state scrambler (a distribution whose $t$-copy output on any pure state is $\epsilon$-close to Haar) followed by a random permutation places any adversary state in this subspace up to error $O(t^2/N)$. HPO is the coherent version of one walk step: it records the sampled function $f$ and permutation $\sigma$ in environment registers and applies $H_f P_\sigma$ to the query register. The Compress isometry maps HPO's relation states $|\phi_R\rangle$ to the path-recording oracle's relation states $|R\rangle$, and Lemma 4.13 shows that after projecting onto the distinct block subspace the two oracle views agree up to the same $O(t^2/N)$ error. Once the compressed view matches the path-recording oracle, the oracle's right-invariance property lets the proof move all adaptive queries into the environment, which is what renders the walk's output Haar-indistinguishable.

What would settle it

Take small qubit counts (n=6 through 12), run 30n rounds of the parallel Kac's walk on several random input states, and compare the two-copy output distribution with the Haar two-copy distribution in trace distance; the proof's projection lemma requires this distance to be O(1/$N^{2}$), so a measured rate slower than that at the stated step count would falsify the central theorem.

Watch

Extended reading notes

Core claim

The central theorem is that the distribution $\mathrm{HP}_{n,T+1}$ with $T=30n$ and $d=5n$ is computationally indistinguishable from Haar random unitaries (Theorem 4.4), and that $\mathrm{HP}_{n,2T+1}$ is statistically indistinguishable even against inverse-query adversaries: any $t$-query adversary distinguishing $\mathrm{HP}_{n,2T+1}$ from Haar has advantage at most $2t(11t+20)/N^{1/8}$ (Theorem 5.1). The proof splits into two phases: the first $T$ rounds scramble the adversary's query history into the distinct block subspace, and the final round is analyzed through a purified function-permutation oracle and a path-recording oracle whose right invariance moves adaptive queries into an environment register. Replacing the random functions and permutations with quantum-secure pseudorandom counterparts makes the construction an efficient PRU under post-quantum one-way functions (Theorem 4.16).

Load-bearing premise

The whole proof depends on the previously established claim that 30n steps of the parallel Kac's walk bring every input pure state to within O(1/$N^{2}$) of the Haar-random state, with N=2^n; if that scrambling claim is false or needs more steps, the projection into the distinct block subspace and the PRU conclusion do not follow.

Editorial extensions

If this is right

The distribution $\mathrm{HP}_{n,30n+1}$ with $d=5n$ is computationally indistinguishable from Haar, so a linear number of parallel Kac's walk steps gives an adaptive-secure PRU.
The distribution $\mathrm{HP}_{n,60n+1}$ is a statistical strong PRU: any $t$-query adversary with forward and inverse queries has distinguishing advantage at most $2t(11t+20)/N^{1/8}$.
When random functions and permutations are replaced by quantum-secure PRFs and PRPs, the resulting family is efficiently sampleable and is a PRU under the existence of post-quantum one-way functions.
The finite-precision approximation $\widehat{\mathrm{HP}}_{n,T+1}$ is computationally indistinguishable from $\mathrm{HP}_{n,T+1}$, so the construction survives the truncation needed for actual circuit implementation.

Reading between the lines

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

An implication the authors leave implicit is that the two-phase proof only consumes the $O(1/N^2)$-random state scrambling property, so any scrambling family stable under one extra random permutation should plug into the same argument, making the result a template for PRU constructions.
The inverse-query proof sandwiches HPO between two scrambling blocks, one from the walk and one from Haar; the same sandwiching may give inverse-query security for other forward-secure PRU constructions whose path-recording oracle has two-sided invariance.
If the paper's suggested simplification—replacing the independent $2\times2$ rotations by one shared rotation—preserves the $O(1/N^2)$-RSS bound, the construction would become a local random circuit PRU, which would resolve an open question in quantum complexity.

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

Short version: this paper confirms the conjecture from LQS+24 that a linear number of parallel Kac's walk steps forms an adaptive-secure PRU, and it adds statistical strong security against inverse-query adversaries. The result is genuinely new: prior work had the PFC-based PRU and the Kac walk as a state scrambler, but not the PRU theorem. The proof is not a routine extension. The authors adapt MH24's path-recording machinery to a different ensemble, define the HP-relation states and compress isometry, and extend the invariance argument to two-sided queries. The main theorems have explicit quantitative bounds, and the chain from RSS to projection to path recording to Haar indistinguishability is coherent.

The largest soft spot is exactly what the stress-test note says. Theorem 4.3 is imported from LQS+24: HP_{n,T} with T=30n, d=5n is epsilon-RSS with epsilon=O(1/N^2). Lemma 3.1 and every projection step after it need that specific bound. The paper does not reproduce the proof or state the exact constants, so this is a load-bearing external dependency. I do not see it as circular: the RSS theorem is an independent prior result, and the authors are the same group that proved it, so the citation pattern is not hiding a gap. But a referee should verify the parameter conversion, or the paper should include a proof sketch of that theorem, because if the RSS bound fails the entire PRU conclusion collapses.

The other issues are smaller. Claim 5.25 has a misprinted inequality in the induction chain; the direction is wrong as printed, though the intended argument is recoverable. Lemma 4.2 has a small hybrid-index slip. Several lemmas are borrowed from MH24 without proof; that is acceptable if the field trusts MH24, but for a standalone paper I would want precise references with constants, especially for the twirling lemma and the two-sided invariance claim. None of these appear to break the central argument.

The paper is not an efficiency breakthrough; PFC remains comparable. But an alternative PRU built from one repeated module, with inverse-query security, is a meaningful contribution to quantum pseudorandomness. The audience is researchers in quantum cryptography and anyone extending the path-recording technique.

Recommendation: send it to peer review. Not a desk reject. Acceptance should be conditional on fixing the typos and making the dependence on LQS+24 Theorem 10 auditable, either by reproducing the proof or by stating its exact parameters and constants.

Referee Report

3 major / 4 minor

Summary. The paper studies the parallel Kac's walk distribution HP_{n,T} on the unitary group U(N), N=2^n. Its main theorems state that for T=30n and d=5n, the distribution HP_{n,T+1} is computationally indistinguishable from the Haar distribution (Theorem 4.4), and that HP_{n,2T+1} is statistically indistinguishable even against adversaries allowed to make inverse queries, with an explicit bound 2t(11t+20)/N^{1/8} (Theorem 5.1). The proof proceeds by (i) importing an epsilon-RSS bound with epsilon=O(1/N^2) for HP_{n,30n} from [LQS+24, Theorem 10]; (ii) proving a projection lemma (Lemma 3.1) that an RSS operator followed by a random permutation leaves the adversary's recorded state in the distinct-block subspace; (iii) using the path-recording technique of [MH24] to compare the real oracle with a path-recording oracle; and (iv) extending this to a two-sided path-recording oracle V for the inverse-query result. The paper also explains how to derandomize the construction using QPRFs and QPRPs to obtain an efficient PRU.

Significance. If the proof is correct, this is a substantial result: it provides the first alternative construction of an adaptive-secure PRU beyond the PFC ensemble, confirms a conjecture in [LQS+24], and adds a strong-security guarantee against inverse queries. The manuscript is explicit about the quantitative bounds it proves and is careful in setting up the purified oracles and relation states. Its main strength is a modular reduction to a published scrambling theorem and to the path-recording framework of [MH24]. The principal correctness risk is the reliance on a very strong imported RSS bound, and the Section 5 proof currently contains several formally incorrect displays. These issues are significant but appear repairable without changing the asymptotic security claims.

major comments (3)

[Section 4.1, Theorem 4.3] The entire proof is conditional on the claim that HP_{n,30n} is an O(1/N^2)-RSS distribution, imported from [LQS+24, Theorem 10]. This bound is used in Lemma 3.1 to obtain the O(t^2/N) projection error, and every later lemma inherits it. The manuscript does not state the exact version of the theorem, the constants, or the parameter adjustment, and it does not reproduce the proof. Because O(1/N^2) is far stronger than the mixing bounds stated elsewhere for Kac-type walks, I request that the authors either include the full statement and a self-contained proof of the needed epsilon-RSS bound for T=30n, d=5n, or provide a precise page/theorem reference with enough detail to verify the parameter regime. Without this, both main theorems rest on an unverified external assumption.
[Section 5.4.1, Claim 5.25] The displayed chain at the end of the induction is not a valid proof. After establishing a lower bound of the form Re(...) >= 1 - 38t^2/N^{1/4} - 6t^{3/4}/N^{1/4} - 32*sqrt(t(t+1)/N), the text continues with '<= 1 - ...', then '<= ...', then '>= ...', reversing the inequality direction without explanation and introducing an extra N^{-1/4} factor in the second line. As printed, the claim does not follow. The intended bound appears repairable: for t>=1, one has 6t^{3/4} <= 6t and 32*sqrt(t(t+1)/N) <= 32(t+1)/N^{1/4}, which would give a lower bound of 1 - O(t^2/N^{1/4}), but the proof must be rewritten with consistent inequality directions.
[Section 5.4.1, Lemma 5.27] The final bound '<= 9t/N^{1/8}' does not follow from the preceding inequalities. The proof invokes |||u><u| - |v><v|||_1 <= 2|||u> - |v>||_2 and obtains |||u> - |v>||_2^2 <= 76t^2/N^{1/4}, which would yield 2*sqrt(76)t/N^{1/8} ~ 17.4t/N^{1/8}. To obtain 9t/N^{1/8} one needs the pure-state inequality TD <= sqrt(2(1-Re<u|v>)) <= sqrt(76)t/N^{1/8}, which is not the stated fact. The asymptotic negligibility is unaffected, but the quantitative lemma as proved is incorrect and must be corrected.

minor comments (4)

[Lemma 4.8 and Appendix A] References to 'Theorem 4.9' in the proofs of Lemma 4.8 and in Appendix A should be to 'Lemma 4.9'.
[Appendix A] Appendix A contains duplicated case labels ('Case 2.1' and 'Case 2.1.2.2' appear twice), which makes the orthogonality argument harder to follow.
[Lemma 2.8] The right-invariance lemma is asserted as 'similar to [MH24, Lemma 4.3]' but the PR oracle here is modified (it excludes y in BIm(R) rather than y in Im(R)); please include the short proof or a precise statement of how the MH24 proof transfers.
[Section 2.4 heading] The section heading 'Cryptopgraphy' is a typo and should read 'Cryptography'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the PRU claim reduces to an independent RSS scrambling theorem and a genuine path-recording reduction, not to its own conclusion.

full rationale

Walking the derivation chain: HP_{n,T} is defined by T repetitions of parallel Kac's walk (Definition 4.1), not by the indistinguishability claim. The only imported load-bearing result is Theorem 4.3, taken from the same authors' [LQS+24, Theorem 10], asserting that HP_{n,T} is an O(1/N^2)-RSS distribution at T=30n and d=5n. This is a scrambling property about tensor powers of states, independent of Haar indistinguishability of unitaries; it has its own proof in the cited work and is not fitted to the PRU target. Lemma 3.1 uses only the RSS hypothesis to project the adversary state into the distinct-block subspace, and Lemma 4.15 uses that projection together with the MH24 path-recording oracle to compare Kac against Haar; this is a genuine reduction, not a restatement of RSS. The inverse-query strong security proof similarly uses HP_{n,T} as a twirling source, not as a PRU. The efficient construction replaces random f and sigma by QPRF/QPRP under standard assumptions. No equation defines the target distribution in terms of the distinction it is meant to predict, and no fitted parameter is renamed as a prediction. The central reliance on [LQS+24] is a same-author citation, but it is independent support: a prior theorem with stated parameters whose proof does not include the PRU conclusion. One can question whether the constants in Theorem 4.3 hold, but that is a correctness risk, not a circularity.

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

The central claim depends on three black-box inputs: the RSS mixing theorem from LQS+24 (same research group), the path-recording framework from MH24, and the existence of OWFs when turning the statistical construction into an efficient PRU. No free parameters are fitted to the target result; T and d are hand-picked to satisfy the inherited RSS bound. No new physical entities are postulated.

free parameters (2)

T = 30n
Number of sequential parallel Kac steps; hand-chosen so that HP_{n,T} is an O(1/N^2)-RSS distribution, taken from LQS+24, Theorem 10. It is a proof parameter, not fitted to data.
d = 5n
Number of bits used to discretize each 2x2 random rotation; chosen so the implementable H_f is negligibly close to the ideal H_f (Lemma 4.2).

assumptions (5)

domain assumption Post-quantum one-way functions exist, enabling QPRFs and QPRPs.
Needed only for the efficient PRU statement (Theorem 4.16), where random functions and permutations are replaced by QPRF/QPRP. The statistical theorems HP_{n,T+1} and HP_{n,2T+1} do not require it.
domain assumption HP_{n,T} with T=30n and d=5n is an O(1/N^2)-RSS distribution.
Imported as Theorem 4.3 from LQS+24, Theorem 10. It is the load-bearing mixing bound used in Lemma 3.1 and throughout the indistinguishability proof, and it is not re-proved here.
domain assumption Path-recording oracle PR satisfies the expansion (Fact 2.7) and right invariance (Lemma 2.8) from MH24.
These properties are stated without proof and are central to the compression argument connecting HPO to PR.
standard math Standard Haar twirling and symmetric-subspace identities, e.g., the twirl of the equality projector equals the EPR projector plus a correction.
Used in Lemma 3.1, Lemma C.3, and Appendices B/C; sourced to Harrow 2013 and MH24.
domain assumption Adversary is a BQP oracle algorithm with t=poly(n) sequential queries and an ancilla.
This is the security model in Definitions 2.3 and 2.4, used throughout.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Parallel Kac's Walk Generates PRU." pith.science (2026). https://pith.science/paper/4BYKIMRH

@misc{pith2026250414957,
  author       = {Pith},
  title        = {Pith review of: Parallel Kac's Walk Generates PRU},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4BYKIMRH}},
  note         = {Machine review of arXiv:2504.14957}
}

read the original abstract

Ma and Huang recently proved that the PFC construction, introduced by Metger, Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary family PRU. Their proof developed a new path recording technique [MH24]. In this work, we show that a linear number of sequential repetitions of the parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQSY+24], also forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it additionally satisfies strong security against adversaries making inverse queries. This gives an alternative PRU construction, and provides another instance demonstrating the power of the path recording technique. We also discuss some further simplifications and implications.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 18 canonical work pages

[1]

Pseudorandom isometries

Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin. Pseudorandom isometries. In Advances in Cryptology -- EUROCRYPT 2024 , pages 226--254, Cham, 2024. Springer Nature Switzerland

work page 2024
[2]

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 Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography , pages 237--265, Cham, 2022. Springer Nature Switzerland

work page 2022
[3]

Cryptography from pseudorandom quantum states

Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Advances in Cryptology -- CRYPTO 2022 , pages 208--236. Springer, 2022

work page 2022
[4]

Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality

Adam Bouland, Bill Fefferman, and Umesh Vazirani. Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality . In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume 151 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 63:1--63:2. Schloss Dagstuhl -- Leibniz-Zentrum ...

work page 2020
[5]

Brand \ a o, Aram W

Fernando G.S.L. Brand \ a o, Aram W. Harrow, and Micha Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics , 346:397--434, 2016

work page 2016
[6]

Real-valued somewhat-pseudorandom unitaries

Zvika Brakerski and Nir Magrafta. Real-valued somewhat-pseudorandom unitaries. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography , pages 36--59, Cham, 2025. Springer Nature Switzerland

work page 2025
[7]

( P seudo) random quantum states with binary phase

Zvika Brakerski and Omri Shmueli. ( P seudo) random quantum states with binary phase. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography , pages 229--250, Cham, 2019. Springer International Publishing

work page 2019
[8]

Scalable pseudorandom quantum states

Zvika Brakerski and Omri Shmueli. Scalable pseudorandom quantum states. In Advances in Cryptology -- CRYPTO 2020 , pages 417--440. Springer, 2020

work page 2020

Show all 23 references

[9]

Pseudorandomness from subset states

Tudor Giurgica-Tiron and Adam Bouland. Pseudorandomness from subset states. 2023. https://arxiv.org/abs/2312.09206

2023 arXiv
[10]

Aram W. Harrow. The church of the symmetric subspace, 2013. https://arxiv.org/abs/1308.6595

2013 arXiv
[11]

Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. Quantum advantage in learning from experiments. Science , 376(6598):1182--1186, 2022

2022
[12]

Pseudorandom quantum states

Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Advances in Cryptology -- CRYPTO 2018 , pages 126--152. Springer, 2018

2018
[13]

Pseudorandom and pseudoentangled states from subset states

Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu. Pseudorandom and pseudoentangled states from subset states. 2024. https://arxiv.org/abs/2312.15285

2024 arXiv
[14]

Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith

Vishesh Jain, Natesh S. Pillai, Ashwin Sah, Mehtaab Sawhney, and Aaron Smith. Fast and memory-optimal dimension reduction using Kac ’s walk . The Annals of Applied Probability , 32(5):4038 -- 4064, 2022

2022
[15]

Foundations of kinetic theory

Mark Kac. Foundations of kinetic theory. In Third Berkeley symposium on mathematical statistics and probability , volume 3, pages 171--197, 1956

1956
[16]

Quantum pseudorandom scramblers

Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Quantum pseudorandom scramblers. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography , pages 3--35, Cham, 2024. Springer Nature Switzerland

2024
[17]

How to construct random unitaries, 2024

Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries, 2024. https://arxiv.org/abs/2410.10116

2024 arXiv
[18]

Simple constructions of linear-depth t-designs and pseudorandom unitaries

Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Simple constructions of linear-depth t-designs and pseudorandom unitaries. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 485--492, 2024

2024
[19]

Kac's walk on n -sphere mixes in n n steps

Natesh S Pillai and Aaron Smith. Kac's walk on n -sphere mixes in n n steps. The Annals of Applied Probability , 27(1):631--650, 2017

2017
[20]

Random unitaries in extremely low depth, 2024

Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth, 2024. https://arxiv.org/abs/2407.07754

2024 arXiv
[21]

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
[22]

A note on quantum-secure P R P s

Mark Zhandry. A note on quantum-secure P R P s. Cryptology ePrint Archive, Paper 2016/1076, 2016

2016
[23]

How to construct quantum random functions

Mark Zhandry. How to construct quantum random functions. J. ACM , 68(5), 2021

2021

Pith tools

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

[1] [1]

Pseudorandom isometries

Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin. Pseudorandom isometries. In Advances in Cryptology -- EUROCRYPT 2024 , pages 226--254, Cham, 2024. Springer Nature Switzerland

work page 2024

[2] [2]

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 Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography , pages 237--265, Cham, 2022. Springer Nature Switzerland

work page 2022

[3] [3]

Cryptography from pseudorandom quantum states

Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Advances in Cryptology -- CRYPTO 2022 , pages 208--236. Springer, 2022

work page 2022

[4] [4]

Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality

Adam Bouland, Bill Fefferman, and Umesh Vazirani. Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality . In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume 151 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 63:1--63:2. Schloss Dagstuhl -- Leibniz-Zentrum ...

work page 2020

[5] [5]

Brand \ a o, Aram W

Fernando G.S.L. Brand \ a o, Aram W. Harrow, and Micha Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics , 346:397--434, 2016

work page 2016

[6] [6]

Real-valued somewhat-pseudorandom unitaries

Zvika Brakerski and Nir Magrafta. Real-valued somewhat-pseudorandom unitaries. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography , pages 36--59, Cham, 2025. Springer Nature Switzerland

work page 2025

[7] [7]

( P seudo) random quantum states with binary phase

Zvika Brakerski and Omri Shmueli. ( P seudo) random quantum states with binary phase. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography , pages 229--250, Cham, 2019. Springer International Publishing

work page 2019

[8] [8]

Scalable pseudorandom quantum states

Zvika Brakerski and Omri Shmueli. Scalable pseudorandom quantum states. In Advances in Cryptology -- CRYPTO 2020 , pages 417--440. Springer, 2020

work page 2020