REVIEW 1 major objections 1 minor 13 references
Scalable, quantum-accessible, and adaptive pseudorandom quantum state and pseudorandom function-like quantum state generators
T0 review · 1 major / 1 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read This paper constructs the first pseudorandom quantum function-like state generator that is simultaneously scalable, fully quantum-accessible (even on entangled ancilla-assisted queries), and adaptive, assuming quantum-secure one-way…
desk verdict Strong new construction for scalable, ancilla-assisted adaptive PRFS with a repairable proof gap in the Beta-splitting lemma. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the 'random amplitudes' isometric procedure. To prepare a state with coefficients equal to the square roots of independent chi-squared-2 random variables (so that normalized coefficients match Gaussian amplitudes), the algorithm recursively splits a total weight: at depth t, for each prefix z it samples an independent Beta($2^{{n-t-1}}$, $2^{{n-t-1}}$) variable and rotates the next qubit by the angle whose cosine-squared is that sample; the Beta-to-Gamma ratio identity then makes subtree weights follow chi-squared distributions, matching the Haar-random amplitude profile. The sampling is done in superposition by using the prefix as a seed to a classical Beta sampler and applying controlled rotations, giving an isometry rather than a state with discarded junk. A final random-phase step converts the real amplitudes into the complex Gaussian vector, and replacing the random function with a quantum-secure pseudorandom function turns the statistical closeness into computational pseudorandomness.
What would settle it
Simulate the random-amplitudes procedure for, say, n = 10 qubits with exact arithmetic, drawing independent Beta($2^{{n-t-1}}$, $2^{{n-t-1}}$) variables at the prescribed prefixes and forming the state; compare the empirical distribution of the squared coefficients to the normalized chi-squared-2 distribution over many samples, and separately test the first split where the initial total weight 1 is a constant rather than a chi-squared random variable. A statistically significant deviation, or a failure at that base case, would refute Lemma 4.3 and hence the core construction.
Extended reading notes
Core claim
The paper's main theorem states that, assuming a quantum-secure pseudorandom function family (which exists if quantum-secure one-way functions exist), there is a scalable, quantum-accessible, adaptive PRFS generator: for any polynomial input length m and output length n, a keyed family of isometries maps superposition inputs to an output register containing |x> followed by a state |ψ_x> that is computationally indistinguishable from a uniformly random (Haar-random) quantum state, and the adversary may query on states entangled with ancillas. The proof works through an asymptotically random state generator that, given oracle access to a random function, prepares a state within negligible trace distance of Haar-random, then replaces the random function by a quantum-secure PRF. For the PRFS, the input x is concatenated with each sampling prefix inside the oracle so that different inputs receive independent randomness; security against ancilla-assisted adversaries is obtained by bounding the diamond-norm distance through the Choi representation, paying a factor of 2^m that scalable parameters absorb.
Load-bearing premise
The construction rests on the identity that recursively splitting a fixed total weight of 1 by a binary tree of independent Beta random variables produces exactly the same distribution as the normalized squared amplitudes of independent Gaussian-square (chi-squared) variables; if that identity fails, the prepared states are no longer Haar-like.
Editorial extensions
If this is right
- A scalable, isometric PRS exists from quantum-secure PRFs, removing the logarithmic-qubit restriction of earlier phase-state PRS constructions.
- A scalable, fully quantum-accessible (ancilla-assisted), adaptive PRFS exists from quantum-secure PRFs, the first construction with all three properties together.
- The same PRFS construction yields long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS as corollaries, and through known implications gives PRS, SB-QCOM, pseudo-encryption, CCA1-qPKE with quantum ciphers, and PD-PRF.
- If a black-box separation between one-way functions and scalable PRFS is ever shown, this construction marks a natural boundary: a cryptography world without one-way functions that still contains all of those primitives.
Reading between the lines
- The Beta-splitting template is not tied to chi-squared amplitudes: any distribution whose prefix-sum ratios are independent and efficiently samplable would yield the same isometric preparation, so the same code could port to other target ensembles with different coefficient statistics.
- The ancilla-assisted security proof pays a 2^m factor from the Choi bound, and scalability is what absorbs it; a non-scalable version of the same isometry would be insecure against entangled queries, which helps explain why earlier non-scalable PRFS constructions stopped at pure-input access.
- A concrete stress test of the construction is whether the recursive Beta-splitting identity remains exactly true when the initial total weight is the constant 1 rather than a chi-squared random variable, since the appendix's induction treats that base case informally.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents an isometric procedure for generating quantum states that are statistically close to Haar-random states when given oracle access to a truly random function, and pseudorandom when the random function is replaced by a quantum-secure PRF. The construction prepares random amplitudes by sequential Beta splitting in superposition, then applies random phases, yielding a scalable and isometric PRS. The same procedure is extended to accept an m-qubit input register, giving a scalable, adaptive, and ancilla-assisted quantum-accessible PRFS. The claimed results are Theorem 5.1 (scalable isometric PRS from quantum-secure PRF) and Theorem 6.4 (scalable, quantum-accessible, adaptive PRFS from quantum-secure PRF, hence from quantum-secure OWF). The paper includes detailed hybrid arguments, finite-precision bounds, a diamond-norm analysis for the PRFS, and a long appendix with classical sampling algorithms for the rounded Beta distribution.
Significance. If the main theorems are correct, this is the first construction of a PRFS that is simultaneously scalable, adaptive, and quantum-accessible in the strong ancilla-assisted sense, and it unifies several previously separate PRFS variants. The technical core is appealing: the qubit-by-qubit Beta-splitting method inspired by Grover-Rudolph is a genuinely different route from prior rejection-sampling constructions, and it gives an isometry rather than a channel with junk. The paper is commendably detailed: it provides explicit finite-precision bounds, full hybrid proofs, and a self-contained classical algorithm for rounded Beta sampling with a rigorous error analysis in Appendix G. There are no fitted parameters, and the security benchmark is the standard Haar measure, so the construction is falsifiable in the usual cryptographic sense. However, the central theorem currently rests on a lemma whose proof has an invalid base case, and the main PRFS theorem contains a length-parameter inconsistency in the key generation step; both issues are local and appear patchable.
major comments (1)
- [Appendix G, Lemma G.5 and Lemma H.4] The sampling algorithm A_RB is presented as deterministic and polynomial-time, but its precision parameter m_1 is chosen as 3m+3+ceil(log2(eta+3)), where eta is the constant asserted to exist in Lemma H.4. Lemma H.4 proves existence of such an eta by a limiting argument but does not provide an explicit value or an effective bound. Without an explicit universal constant, the construction of A_RB is not fully explicit, although the proof could be made constructive by computing a numerical bound in Lemma H.4. This does not affect the asymptotic correctness of the reduction, but it should be addressed for the paper's claim of an explicit sampling algorithm.
minor comments (1)
- [Figure 2] The states in Figure 2 are labeled with strings such as '|000⟩' that appear multiple times in different branches, which makes the figure hard to parse; using explicit binary prefixes would improve clarity.
Circularity Check
No significant circularity; the derivation is self-contained given external QS-PRF/OWF assumptions, though Lemma 4.3's proof in Appendix C has a base-case flaw that is a correctness gap, not a circular dependency.
full rationale
The paper's central derivation reduces random-function-based ARS/ARFS to Haar-random states via standard facts (normalized complex Gaussian vector is Haar, Box-Muller, Beta/Gamma/chi-squared relationships), then replaces the random function by a quantum-secure PRF using the textbook hybrid argument. The PRFS security definition (Definition 3.33) benchmarks against Haar-random states, not against any quantity defined in the paper, so there is no self-definitional circularity. No parameter is fitted to data, and no prediction is statistically forced by a fit. The only external cryptographic dependency is Zhandry's theorem (Fact 3.28) that quantum-secure OWFs imply quantum-secure PRFs; this is an independent, published result, not a self-citation by the present authors. The paper does cite prior work for primitives, but none of those citations load-bear as a forbidden ansatz or uniqueness claim. One genuine issue, flagged by the manuscript's own proof structure, is the proof of Lemma 4.3 in Appendix C: the induction base sets W_{0,∅} (the initial total weight) to be chi-squared distributed, whereas the actual initial weight for |0>^⊗n is the constant 1. This invalidates the induction as written. However, this is a mathematical proof gap in a lemma about a true identity (sequential Beta splitting yields normalized chi-squared weights), not a reduction of the theorem to its own assumptions by construction. The gap is patchable; it does not make the construction's output equivalent to its input by definition, and it does not arise from fitted parameters or self-citation. Therefore the circularity score is 0.
Assumptions & free parameters
assumptions (6)
- domain assumption Quantum-secure one-way functions exist (equivalently, quantum-secure PRFs exist via Zhandry).
- domain assumption The QS-PRF can be evaluated by a polynomial-time reversible circuit and remains pseudorandom under superposition queries.
- standard math Beta, Gamma, and chi-squared distribution relations (Fact 3.8, Fact 3.10, Fact 3.23).
- standard math Marsaglia-Tsang rejection sampling and the rounded-Gaussian sampler from BS20 are correct and efficient.
- standard math Diamond-norm distance is bounded by the trace norm of the Choi representation difference (Fact 3.19).
- domain assumption n(lambda) and m(lambda) are polynomially bounded in lambda.
Cite this review
Pith. "Pith review of Scalable, quantum-accessible, and adaptive pseudorandom quantum state and pseudorandom function-like quantum state generators." pith.science (2026). https://pith.science/paper/NNV3F4RK
@misc{pith2026250722535,
author = {Pith},
title = {Pith review of: Scalable, quantum-accessible, and adaptive pseudorandom quantum state and pseudorandom function-like quantum state generators},
year = {2026},
howpublished = {\url{https://pith.science/paper/NNV3F4RK}},
note = {Machine review of arXiv:2507.22535}
}
read the original abstract
We show new constructions for pseudorandom quantum states (PRS) and pseudorandom function-like quantum state (PRFS) generators satisfying scalability, which means the security parameter can be much larger than the number of qubits, quantum accessibility, which means the adversary can provide quantum input, and adaptivity, which means the adversary can query it adaptively. We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). This naturally gives the first construction for scalable, quantum-accessible, and adaptive PRFS assuming quantum-secure one-way functions. Compared to prior PRFS works, we use a stronger definition of quantum accessibility in which the adversary can be ancilla-assisted, i.e., the input state may not be pure and could be entangled with other quantum registers. Thus, our result also gives the first (fully) quantum-accessible PRFS. Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS. This new construction may be helpful in simplifying the microcrypt zoo.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[1]
Construct RS O n,λ using the given oracleO
-
[2]
RunA, using RS O n,λ |0⟩⊗n as the oracle, and output the result. This gives Pr k←KeyGen(1n,1λ) h BUPRFk (1λ) = 1 i −Pr f←Y X h BUf (1λ) = 1 i =ν(λ), which contradicts that{PRF k}k is quantum-secure pseudorandom. Thus, we have Pr k←KeyGen(1n,1λ) h AVPRFk (1λ) = 1 i −Pr f←Y X h AVf (1λ) = 1 i =negl(λ).(8) From eq. (7) and eq. (8), we get Pr k←KeyGen(1n,1λ) ...
-
[3]
We have 1 2 J(E B′,U)−J(E B′,U′) 1 =MTD(|J B′,U⟩⟨JB′,U|,|J B′,U′⟩⟨JB′,U′|) =M q 1− ⟨JB′,U|JB′,U′⟩ 2 (From Theorem 3.15) =M vuuut1− 1 M X x∈[M] ⟨ψB′x,Ux|ψB′x,U′x⟩ 2 =M vuuut1− 1 M X x∈[M] X z∈[N] c′(x) z e2πi(u′(x) z −u(x) z ) 2 ≤M vuuut1− 1 M X x∈[M] X z∈[N] c′(x) z ℜ e2πi(u′(x) z −u(x) z ) 2 =M vuuut1− 1 M X x∈[M] X z∈[N] c′(x) z cos(2π(u′(x)...
-
[4]
Since CircuitGen is a PT algorithm, the size of the quantum circuitC r is polynomially bounded inλ
Output|ϕ r⟩=C r(). Since CircuitGen is a PT algorithm, the size of the quantum circuitC r is polynomially bounded inλ. The above algorithmGis indeed a polynomial-time quantum algorithm. To show the pseudorandomness, assume that there existst∈poly(λ) and a QPT distinguisherAsuch that Pr r←K A(|ϕr⟩⊗t) = 1 −Pr |ψ⟩←µn A(|ψ⟩⊗t) = 1 =ε(λ)/∈negl(λ). 40 Then we c...
-
[5]
Each pair of them behave the same, but the final output is different underm-bit precision, i.e. ⌊2ma/(a+b)⌉2 −m ̸=⌊2 m˜a/(˜a+˜b)⌉2−m, where ˜a,˜bare the outputs of ˜A⟨m1⟩ G in the same iteration as a, b. To detect the first one, we define a checkerCas follows (and chooseε= 2 −m1): •C(ε, α, x, u):
-
[6]
Letd=α− 1 3 , c= 1√ 9d , and ˜x=⌊x/ε⌋ε,˜u=⌊u/ε⌋ε
-
[7]
If1 (1 +cx) 3 >0 ̸=1 (1 +c˜x)3 >0 , output false
-
[8]
If1 u < es(x) ̸=1 ˜u < es(˜x) , output false
Lets(x) = 1 2 x2 +d−d(1 +cx) 3 +dln((1 +cx) 3). If1 u < es(x) ̸=1 ˜u < es(˜x) , output false
Show all 13 references
-
[9]
This checker checks whetherA G behaves the same, both accepting or both rejecting, when run on (α, x, u) versus (α,˜x,˜u) (seeAG Algorithm 3)
Otherwise, output true. This checker checks whetherA G behaves the same, both accepting or both rejecting, when run on (α, x, u) versus (α,˜x,˜u) (seeAG Algorithm 3). Thus, as long asC(2 −m1, α, x2i−1, u2i−1) outputs true, the branch taken by the if statement at line 3 is unaf...
-
[10]
In this case, a/(a+b)−˜a/(˜a+ ˜b) can be bounded, then the probability that they differ after rounding can be bounded
At least one ofaandbis not so close to 0. In this case, a/(a+b)−˜a/(˜a+ ˜b) can be bounded, then the probability that they differ after rounding can be bounded
-
[11]
The probability that this happens is small enough
Bothaandbare very close to 0. The probability that this happens is small enough. AB2 reaches line 24 only when bothaandbare not⊥. Letx a, xb be the value of inputxofA G foraand brespectively; i.e. a=d(1 +cx a)3, b=d(1 +cx b)3, whered, care defined inA G. Let ˜xa,˜xb be the rou...
-
[12]
RunA RN in Theorem G.3 multiple times to sample eachx i with fresh randomness
-
[13]
More formally, ARB(1m, α,˜U ′ 1|| ˜U ′ 2|| · · · ||˜U ′ 2m|| ˜U1|| ˜U2|| · · · ||˜U2m) def =A B3 1m, α,ARN (1m1,2m, ˜U ′ 1),· · ·,ARN (1m1,2m, ˜U ′ 2m), ˜U1,· · ·,˜U2m
RunA B3 with thosex i’s and a fresh uniform randomu i. More formally, ARB(1m, α,˜U ′ 1|| ˜U ′ 2|| · · · ||˜U ′ 2m|| ˜U1|| ˜U2|| · · · ||˜U2m) def =A B3 1m, α,ARN (1m1,2m, ˜U ′ 1),· · ·,ARN (1m1,2m, ˜U ′ 2m), ˜U1,· · ·,˜U2m . From Theorem G.3, we have ∆ ARN (1m1,2m, ˜U),N R(2−m...
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.