Natural proofs for quantum state preparation lower bounds

Christine Li; Natalie Parham

REVIEW

Natural proofs for quantum state preparation lower bounds

Christine Li, Natalie Parham

Quantum Physics · Submitted 5 Oct 2026 · 11 references

Pith's verdict: A solid quantum analogue of Razborov–Rudich with a careful construction; the main theorem is conditional on standard crypto and the exact MH level rests on the co-author's unpublished preprint, but the core argument and the natural-property catalog are real contributions.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 6, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 1 major objection · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2610.06826 (version 1)

Pith IDTA3FCRYC, Pith's permanent record of this paper and its review

CitationChristine Li, Natalie Parham. "Natural proofs for quantum state preparation lower bounds." arXiv:2610.06826 (2026). https://pith.science/paper/TA3FCRYC

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

You should know two things up front. First, this paper genuinely gives a quantum analogue of the Razborov–Rudich barrier for state preparation, and it does so with a clean, preprable-PRAL construction that the literature does not already contain. Second, every quantitative level in the main theorem depends on unverified lemmas from a co-author's arXiv preprint, and that dependency is load-bearing; the numerical MH level could shift if those depth counts are off.

What is new: the PRAL definition is distinct from scalable PRS (amplitude-list security, classical distinguishers with all amplitudes), the Gaussian sampler is explicit and finite, the loader is honest, and the catalog—Pauli expectations, approximate Pauli degree via felinity, unique-ground-state obstructions, mutual-information arguments—shows several known techniques are in fact natural. Theorem 2.1 is standard RR logic but cleanly adapted. The security reduction in Section 4 is careful about the subexponential budget; the failure-mode analysis in Lemma 4.3 and the parameter choices in Corollary 4.2.1 check out.

The soft spots, in order of real concern: (1) Theorem 5.6 inherits its exact MH level from three black-box facts in [Par25]—the nonclean A_4CQ AND, the exact OR construction, and the TC0 simulation. The reader and the stress-test note both flagged this. It is a genuine external dependency, not an internal inconsistency; if those lemmas are wrong only in constants, the barrier still holds at a higher fixed level, but the headline number changes. (2) The paper is honest about the absence of a unitary construction and about QAC0 not being covered, and those limitations are stated, so I do not count them as flaws. (3) The mutual-information example relies on [Par25, Thm 3.6], a cited published-ish preprint; that is acceptable, but the usefulness argument requires clean output, which narrows the model.

No circularity red flags: the free parameters are chosen to satisfy inequalities and the crypto assumption is standard and explicitly stated. The AI-disclosure note is odd but harmless.

Who is this for: complexity theorists working on quantum state preparation and QAC0 lower bounds, and anyone who wants a clean template for transporting RR-style barriers. A serious referee should look at the depth-count lemmas in [Par25] and check the A_4CQ/OR constants, but this paper deserves that referee time.

Recommendation: accept for review; the referee should be asked to verify the [Par25] dependency, not to re-verify the whole barrier.

Referee report

Significance

If it holds, this is the first genuine quantum analogue of the Razborov–Rudich barrier for state-preparation lower bounds, and it is obtained under an entirely classical cryptographic assumption, matching the assumption underlying the classical barrier against TC0. The abstract barrier in Section 2 is a clean, standard argument, and the quantitative claims that I checked are internally consistent: the density bound in Lemma 4.2 (C√N times 2^T boundaries times 2ρ times 2N coordinates gives C N^{3/2} 2^T ρ), the parameter accounting in Corollary 4.2.1 (β=1/√2, e^{-N/8} term, ε/4+ε/4 budget), and the subexponential-secure-PRF budget in Theorem 4.5 (m^a ≥ (n+4)^{da} with da>2 covering 2^{O(n)} time and 2^{-λ} advantage) all check out. The explicit sampler, loader, and their constant-depth accounting are concrete enough to audit, and the catalogue of natural existing techniques (Sections 6.1–6.4) is a valuable contribution in its own right.

Major objections (1)

[§5, Lemmas 5.3–5.5 and Corollary 5.5.2; Theorem 5.6] The exact level 8d_F+20 in Theorem 5.6 is inherited entirely from three black-box facts quoted from [Par25], which is cited as an arXiv preprint (arXiv:2504.19966, by a co-author) and is not peer-reviewed: the nonclean A_4CQ implementation of AND ([Par25, Lemma 6.5]) used in Lemma 5.3 and the selector computation of Lemma 5.5; the exact OR construction ([Par25, Lemma 6.1] combined with [TT16, Theorem 1]) used in the addressed lookup of Lemma 5.4; and the simulation of depth-d_F TC0 circuits in A_{4d_F}CQ ([Par25, Lemma 6.3]) used in Corollary 5.5.2. Because these depth counts are load-bearing for the headline quantitative claim (e.g., the level 52 in Corollary 1.1.1), the manuscript should not leave them as unverifiable black boxes: either reproduce the relevant statements in an appendix, cite a published version of [Par25], or restate Theorem 5.6's level as explicitly conditional on the exact constants of those lemmas. I am not claiming the cited lemmas are wrong; I am noting that the reader of this manuscript cannot verify the central quantitative claim as it stands, and an off-by-constant in any of the three constructions would shift the level (while preserving a fixed-level barrier).

Minor objections (5)

[§4.1] The sentence before Lemma 4.2 contains a typo: 'it ios useful' should read 'it is useful'.
[Claim 4.1, §4.1] Claim 4.1 and its proof use the notation |ψ_F⟩, while Definition 3.2 and the surrounding analysis use |ψ_H⟩; the notation should be made consistent.
[Definition 7.2, §7.1] The text reads 'there there exists' in the definition of ε-approximately efficient implementability; the second 'there' should be deleted.
[AI disclosure] There is a typo in 'optimize our prepration of the states'; it should be 'preparation'.
[§6.4] The usefulness result in Lemma 6.4 is stated for the clean-output model, and the paper acknowledges (end of §6.4) that a corresponding PRAL barrier in that model would require a clean-output-preparable PRAL family; this limitation is appropriately disclosed but worth flagging in a remark so that readers do not apply the mutual-information example to the main trace-distance-error barrier theorem.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Under a standard cryptographic assumption, no natural property of quantum states can prove superpolynomial, or even $e^{-n}$-approximate, state-preparation lower bounds against a fixed level of the magic hierarchy.

The reading

This paper extends the classical natural-proofs barrier to quantum state preparation. It defines a natural property of quantum states as one that holds for a non-negligible $2^{-cn}$ fraction of Haar-random states and can be tested efficiently by a classical algorithm given the full amplitude list. The main theorem says that, assuming a classically subexponentially secure pseudorandom function family computable by polynomial-size threshold circuits, no such natural property can prove that a state is hard to $e^{-n}$-approximately prepare within a fixed level of the magic hierarchy. The point is that the obstacle is the kind of proof, not the particular circuits: several existing lower-bound techniques, including approximate Pauli degree, unique-ground-state obstructions, and mutual information arguments, turn out to be natural in exactly this sense.

What carries the argument

The argument is carried by three components. First, a natural promise property of quantum states: a pair of phase-invariant sets of states that is constructive (a deterministic polynomial-time classical test on the truncated amplitude list) and large (accepts at least $2^{-cn}$ of Haar-random states). Second, a pseudorandom amplitude-list (PRAL) family, meaning state ensembles whose finite-precision amplitude lists look Haar-random to any polynomial-time classical distinguisher, together with the requirement that each member has its own small preparation circuit inside the target circuit model. Third, the explicit magic-hierarchy preparation, which combines a finite Poisson sampler that converts a random tape into an approximate complex Gaussian amplitude (reproducing the Gaussian radial tail through a Poisson number of points in the unit square) with an amplitude loader that turns computed amplitude encodings into a normalized superposition. Composed with a depth-$d_F$ threshold circuit evaluating the PRF, these components put every target state in $MH_{8d_F+20}$ and complete the barrier.

Extended reading notes

Core claim

The central claim is that a standard cryptographic assumption transfers the classical natural-proofs barrier from Boolean circuits to quantum state preparation. The paper constructs a family of states, built from a complex-Gaussian sampler fed by a pseudorandom function, whose full finite-precision amplitude lists are indistinguishable from those of Haar-random states to any polynomial-time classical algorithm, yet whose individual members can be approximately prepared by polynomial-size circuits at level $MH_{8d_F+20}$ of the magic hierarchy. Any natural property that is useful against those circuits would give an efficient classical distinguisher between the two ensembles, contradicting pseudorandomness. Consequently, proving superpolynomial state-preparation lower bounds at that level cannot be done by any natural argument without breaking the cryptographic assumption.

Load-bearing premise

The load-bearing premise is that a classically subexponentially secure pseudorandom function family computable by polynomial-size, constant-depth threshold circuits exists; the paper's reduction runs in $2^{O(n)}$ time and needs exactly that security budget to hide the amplitude lists from the natural-property tester.

Editorial extensions

If this is right

Techniques now known to be natural — approximate Pauli degree, unique-ground-state obstructions, and mutual information — cannot deliver superpolynomial state-preparation lower bounds against fixed levels of the magic hierarchy without breaking the cryptographic assumption.
With the concrete depth-four threshold-circuit PRF construction, the barrier already applies at level 52 of the magic hierarchy under subexponential security of that construction.
Because the obstruction transfers to any model that can simulate the PRAL preparation circuits, the barrier covers other constant-depth models, including circuits with fanout gates and bounded-round adaptive models.
For unitary implementation the barrier remains conditional on a pseudorandom-matrix object the paper does not construct, and a statistical version of its construction would resolve the unitary synthesis problem.

Reading between the lines

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

If the assumed PRF family exists, the same template plausibly extends to weaker constant-depth models: the paper notes that a $QAC^0$-computable pseudorandom-state construction with security beyond quasipolynomial time would yield a natural-proofs barrier for $QAC^0$, where known lower bounds are stuck near parity with barely superlinear ancillas.
The barrier sharpens the case that unconditional state-preparation lower bounds will need non-natural certificates; exact algebraic methods like transcendental-number arguments, which the paper identifies as non-constructible, are one escape route it leaves open.
Because Proposition 7.2 shows statistical matrix-description closeness would imply a resolution of unitary synthesis, a reader can infer that the unitary analogue probably needs a genuinely different construction, not a step-by-step copy of the state argument.

Original abstract

We identify a barrier that helps explain why proving stronger quantum state-preparation lower bounds has been so difficult. In particular, we establish a quantum analogue of the Razborov-Rudich natural proofs barrier for state-preparation lower bounds. We call a property of quantum states \emph{natural} if it holds for a sufficiently large fraction of Haar-random states and can be efficiently tested when given all of the state's amplitudes. Under a standard cryptographic assumption, we show that no natural property can prove superpolynomial state-preparation lower bounds even against a fixed level of the Magic Hierarchy. We show that several existing state-preparation lower-bound techniques are natural in our sense, including arguments based on approximate degree, not being a unique ground state of a local Hamiltonian, and mutual information.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-06: 1 request, 4,325 input tokens.

What the abstract itself states, as probabilities: claims first 0.11 · states limitation 0.59 · human participants 0.01 · controlled comparison 0.03 · randomized assignment 0.01 · states quantitative result 0.39 · compares with prior results 0.76 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We identify a barrier that helps explain why proving stronger quantum state-preparation lower bounds has been so difficult. In particular, we establish a quantum analogue of the Razborov-Rudich natural proofs barrier for state-preparation lower bounds. We call a property of quantum states \emph{natural} if it holds for a sufficiently large fraction of Haar-random states and can be efficiently tested when given all of the state's amplitudes. Under a standard cryptographic assumption, we show that no natural property can prove superpolynomial state-preparation lower bounds even against a fixed level of the Magic Hierarchy. We show that several existing state-preparation lower-bound techniques are natural in our sense, including arguments based on approximate degree, not being a unique ground state of a local Hamiltonian, and mutual information.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We identify a barrier that helps explain why proving stronger quantum state-preparation lower bounds has been so difficult.	contribution 0.60	0.91	0.32	asserted 0.84
s1	In particular, we establish a quantum analogue of the Razborov-Rudich natural proofs barrier for state-preparation lower bounds.	contribution 0.76	0.94	0.43	asserted 1.00
s2	We call a property of quantum states \emph{natural} if it holds for a sufficiently large fraction of Haar-random states and can be efficiently tested when given all of the state's amplitudes.	contribution 0.66	0.56	0.04	asserted 0.99
s3	Under a standard cryptographic assumption, we show that no natural property can prove superpolynomial state-preparation lower bounds even against a fixed level of the Magic Hierarchy.	result 0.98	0.94	0.74	asserted 1.00
s4	We show that several existing state-preparation lower-bound techniques are natural in our sense, including arguments based on approximate degree, not being a unique ground state of a local Hamiltonian, and mutual information.	result 0.80	0.82	0.06	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (11)

[1]

[CGW10] Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. “Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order”. In:Physical Re- view B—Condensed Matter and Materials Physics82.15 (2010), p. 155138. [Ros24] Gregory Rosenthal. “Efficient quantum state synthesis with one query”. In:Proceedings of th...

View on Pith 2010
[10]

arXiv:2604.02793 [quant-ph].url:https://arxiv.org/abs/2604. 02793. [VB96] Lieven Vandenberghe and Stephen Boyd. “Semidefinite programming”. In:SIAM review38.1 (1996), pp. 49–95. [ZS01] Karol Zyczkowski and Hans-J¨ urgen Sommers. “Induced measures in the space of mixed quantum states”. In:Journal of Physics A: Mathematical and General34.35 (2001), p. 7111....

View on Pith Pith review arXiv 1996
[137]

Graduate Texts in Mathematics. New York: Springer-Verlag, 2001.doi:10.1007/978-1-4757- 8137-3. [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. “How to Construct Random Functions”. In:Journal of the ACM33.4 (1986), pp. 792–807.doi:10.1145/6490.6503. [JPT12] Abhishek Jain, Krzysztof Pietrzak, and Aris Tentes. “Hardness Preserving Constructions ...

View on Pith doi:10.1007/978-1-4757- 1986
[334]

Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik, 2025, 131:1–131:21.doi:10.4230/LIPIcs.ICALP.2025.131. [Bre76] Richard P. Brent. “Fast Multiple-Precision Evaluation of Elementary Functions”. In:Journal of the ACM23.2 (Apr. 1976), pp. 242–251.doi:10.1145/321941.321944. [JW23] Yifan Jia and Mic...

View on Pith Pith review arXiv 2023
[392]

Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2026, 60:1–60:23.isbn: 978-3-95977-449-9.doi:10 . 4230 / LIPIcs . APPROX / RANDOM.2026.60.url:https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs. APPROX/RANDOM.2026.60. [Pad+20] Daniel Pad´ e et al.Depth-2QACcircuits c...

View on Pith doi:10.4230/lipics 2026
[1487]

[Fox+25] Ben Foxman et al. “Random unitaries in constant (quantum) time”. In:arXiv preprint arXiv:2508.11487 (2025). [GMW26] Daniel Grier, Jackson Morris, and Kewen Wu. “QAC 0 ContainsTC 0 (with Many Copies of the Input)”. In: (2026). arXiv:2601.03243 [cs.CC].url:https://arxiv.org/abs/2601.03243. [ABR01] Sheldon Axler, Paul Bourdon, and Wade Ramey.Harmoni...

View on Pith arXiv 2025
[2020]

arXiv:2005. 12169 [quant-ph]. [Ros21] Gregory Rosenthal. “Bounds on theQAC 0 Complexity of Approximating Parity”. In:12th In- novations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Pro- ceedings in Informatics (LIPIcs). 2021, 32:1–32:20.doi:10.4230/LIPIcs.ITCS.2021.32. [Jos+26] Malvika Raj Joshi et al. “Improved Lower Boun...

View on Pith doi:10.4230/lipics.itcs.2021.32 2005
[2025]

arXiv:2504.19966 [quant-ph].url:https://arxiv.org/abs/2504.19966. [NR04] Moni Naor and Omer Reingold. “Number-theoretic constructions of efficient pseudo-random functions”. In:Journal of the ACM (JACM)51.2 (2004), pp. 231–262. [KL02] Matthias Krause and Stefan Lucks. “Pseudorandom functions in TC0 and cryptographic limi- tations to proving lower bounds”. ...

View on Pith Pith review arXiv 2004
[2026]

arXiv:2605.09957 [quant-ph].url:https://arxiv.org/abs/2605.09957. [BS19] Zvika Brakerski and Omri Shmueli. “(Pseudo) random quantum states with binary phase”. In: Theory of Cryptography Conference. Springer. 2019, pp. 229–250. 43 [BS20] Zvika Brakerski and Omri Shmueli. “Scalable Pseudorandom Quantum States”. In:Advances in Cryptology – CRYPTO 2020: 40th ...

View on Pith Pith review arXiv 2013
[2534]

[RR97] Alexander A Razborov and Steven Rudich. “Natural Proofs”. In:Journal of Computer and Sys- tem Sciences55.1 (1997), pp. 24–35.issn: 0022-0000.doi:https://doi.org/10.1006/jcss. 1997.1494.url:https://www.sciencedirect.com/science/article/pii/S002200009791494X. [Par25] Natalie Parham.Quantum circuit lower bounds in the magic hierarchy

View on Pith doi:10.1006/jcss 1997
[7194]

Lecture Notes in Computer Science. Springer, 2012, pp. 369–382.doi:10.1007/978-3-642-28914-9_21. [Wan+21] Shengbin Wang et al. “Fast Black-Box Quantum State Preparation Based on Linear Combination of Unitaries”. In:Quantum Information Processing20, 270 (2021).doi:10.1007/s11128-021- 03203-z. arXiv:2105.06230 [quant-ph]. [TT16] Yasuhiro Takahashi and Seiic...

View on Pith Pith review arXiv 2021

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

[CGW10] Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. “Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order”. In:Physical Re- view B—Condensed Matter and Materials Physics82.15 (2010), p. 155138. [Ros24] Gregory Rosenthal. “Efficient quantum state synthesis with one query”. In:Proceedings of th...

View on Pith 2010

[2] [10]

arXiv:2604.02793 [quant-ph].url:https://arxiv.org/abs/2604. 02793. [VB96] Lieven Vandenberghe and Stephen Boyd. “Semidefinite programming”. In:SIAM review38.1 (1996), pp. 49–95. [ZS01] Karol Zyczkowski and Hans-J¨ urgen Sommers. “Induced measures in the space of mixed quantum states”. In:Journal of Physics A: Mathematical and General34.35 (2001), p. 7111....

View on Pith Pith review arXiv 1996

[3] [137]

Graduate Texts in Mathematics. New York: Springer-Verlag, 2001.doi:10.1007/978-1-4757- 8137-3. [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. “How to Construct Random Functions”. In:Journal of the ACM33.4 (1986), pp. 792–807.doi:10.1145/6490.6503. [JPT12] Abhishek Jain, Krzysztof Pietrzak, and Aris Tentes. “Hardness Preserving Constructions ...

View on Pith doi:10.1007/978-1-4757- 1986

[4] [334]

Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik, 2025, 131:1–131:21.doi:10.4230/LIPIcs.ICALP.2025.131. [Bre76] Richard P. Brent. “Fast Multiple-Precision Evaluation of Elementary Functions”. In:Journal of the ACM23.2 (Apr. 1976), pp. 242–251.doi:10.1145/321941.321944. [JW23] Yifan Jia and Mic...

View on Pith Pith review arXiv 2023

[5] [392]

Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2026, 60:1–60:23.isbn: 978-3-95977-449-9.doi:10 . 4230 / LIPIcs . APPROX / RANDOM.2026.60.url:https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs. APPROX/RANDOM.2026.60. [Pad+20] Daniel Pad´ e et al.Depth-2QACcircuits c...

View on Pith doi:10.4230/lipics 2026

[6] [1487]

[Fox+25] Ben Foxman et al. “Random unitaries in constant (quantum) time”. In:arXiv preprint arXiv:2508.11487 (2025). [GMW26] Daniel Grier, Jackson Morris, and Kewen Wu. “QAC 0 ContainsTC 0 (with Many Copies of the Input)”. In: (2026). arXiv:2601.03243 [cs.CC].url:https://arxiv.org/abs/2601.03243. [ABR01] Sheldon Axler, Paul Bourdon, and Wade Ramey.Harmoni...

View on Pith arXiv 2025

[7] [2020]

arXiv:2005. 12169 [quant-ph]. [Ros21] Gregory Rosenthal. “Bounds on theQAC 0 Complexity of Approximating Parity”. In:12th In- novations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Pro- ceedings in Informatics (LIPIcs). 2021, 32:1–32:20.doi:10.4230/LIPIcs.ITCS.2021.32. [Jos+26] Malvika Raj Joshi et al. “Improved Lower Boun...

View on Pith doi:10.4230/lipics.itcs.2021.32 2005

[8] [2025]

arXiv:2504.19966 [quant-ph].url:https://arxiv.org/abs/2504.19966. [NR04] Moni Naor and Omer Reingold. “Number-theoretic constructions of efficient pseudo-random functions”. In:Journal of the ACM (JACM)51.2 (2004), pp. 231–262. [KL02] Matthias Krause and Stefan Lucks. “Pseudorandom functions in TC0 and cryptographic limi- tations to proving lower bounds”. ...

View on Pith Pith review arXiv 2004

[9] [2026]

arXiv:2605.09957 [quant-ph].url:https://arxiv.org/abs/2605.09957. [BS19] Zvika Brakerski and Omri Shmueli. “(Pseudo) random quantum states with binary phase”. In: Theory of Cryptography Conference. Springer. 2019, pp. 229–250. 43 [BS20] Zvika Brakerski and Omri Shmueli. “Scalable Pseudorandom Quantum States”. In:Advances in Cryptology – CRYPTO 2020: 40th ...

View on Pith Pith review arXiv 2013

[10] [2534]

[RR97] Alexander A Razborov and Steven Rudich. “Natural Proofs”. In:Journal of Computer and Sys- tem Sciences55.1 (1997), pp. 24–35.issn: 0022-0000.doi:https://doi.org/10.1006/jcss. 1997.1494.url:https://www.sciencedirect.com/science/article/pii/S002200009791494X. [Par25] Natalie Parham.Quantum circuit lower bounds in the magic hierarchy

View on Pith doi:10.1006/jcss 1997

[11] [7194]

Lecture Notes in Computer Science. Springer, 2012, pp. 369–382.doi:10.1007/978-3-642-28914-9_21. [Wan+21] Shengbin Wang et al. “Fast Black-Box Quantum State Preparation Based on Linear Combination of Unitaries”. In:Quantum Information Processing20, 270 (2021).doi:10.1007/s11128-021- 03203-z. arXiv:2105.06230 [quant-ph]. [TT16] Yasuhiro Takahashi and Seiic...

View on Pith Pith review arXiv 2021