On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem Zvika Brakerski1 and Henry Yuen2
arXiv:2605.09957v1 [quant-ph] 11 May 2026
1
Weizmann Institute of Science 2 Columbia University
Abstract We consider the task of constructing pseudorandom unitaries (PRUs) with scalable security, i.e. families in which the security parameter may vary independently of the dimension (or input bit-length). It is not known whether scalable PRUs can be constructed. In this work we show that if scalable PRUs can be constructed via the prevailing paradigm for analyzing PRUs, then there would be a positive solution to the Aaronson-Kuperberg unitary synthesis problem, a longstanding question in quantum complexity theory about whether implementing arbitrary unitaries can be efficiently reduced to computing a Boolean function. Specifically, we formalize the notion of ROM-PRUs, which are statistically secure PRUs in the random oracle model (ROM). All prior known constructions of cryptographically secure PRUs are based on a ROM-PRU construction. We prove novel connections between ROMPRUs, approximate unitary designs, ϵ-nets over the unitary group, and the unitary synthesis problem. In particular, we prove that any unitary synthesis algorithm (and thus any ROMPRU) must use a classical oracle with input length (2 − o(1)) log d bits, where d is the dimension of the unitary to be implemented. This bound rules out all existing candidates for scalable PRUs in the literature. Together, these connections indicate that ROM-PRUs provide a fruitful idealized model for studying pseudorandom unitaries.
1
Introduction
A pseudorandom unitary (PRU) ensemble [JLS18] is a family of efficiently implementable unitaries {Us }s such that, for a random s, oracle access to Us is indistinguishable from oracle access to a Haar-random unitary. Whereas [JLS18] defined this object and proposed a few candidates, only recently was it shown by [MPSY24, MH25] that PRUs can be constructed. These constructions, as well as essentially all known constructions of quantum pseudorandom objects from cryptographic assumptions, follow the “ROM paradigm”. Namely, the PRU is first constructed and shown to be information-theoretically secure in the random oracle model (ROM), and then the oracle is replaced by a cryptographic pseudorandom function (PRF) to obtain a construction in the standard model under the assumption that post-quantum one-way functions exist. In particular, [MPSY24, MH25] constructed such ROM-PRUs and proved that an adversary making t queries to the PRU has statistical advantage ≲ t2 /d in distinguishing the construction from a Haar-random unitary, where d is the dimension of the Hilbert space of the unitary (i.e. the unitary acts on n = log d qubits). 1
This √ means that the proof provides no guarantee whenever the number of queries roughly exceeds d. When the number of qubits n is large, e.g. larger than the security parameter, the value t2 /d is negligible. What happens when n is small, or otherwise one wishes to reduce the error further? This property is known as scalability [BS20]. It was established in [MPSY24] that sequential repetition decreases the distinguishing gap, so it is possible to reduce the√statistical advantage to ≲ (t2 /d)k for any polynomial k. However, even in this case, once t ≳ d, there is no security guarantee whatsoever. We therefore define the query bound τ of a ROM-PRU construction as the value of t for which the statistical advantage equals 1/2. We note that the choice of constant here is arbitrary, in particular in light of the aforementioned sequential amplification technique. This is because a construction with advantage < 1/2k can be derived from one with advantage < 1/2, for any polynomial k. A scalable ROM-PRU should therefore be able to support arbitrarily high τ = poly(d, 2κ ), where κ is the security parameter. We posit the importance of studying the query bound of ROM-PRU constructions, and specifically the maximal achievable τ . In particular, we show that it has implications for the possibility of a unitary synthesis algorithm. Unitary synthesis addresses the question of whether the hardness of implementing arbitrary quantum unitaries can be reduced to the hardness of implementing arbitrary classical functions. Specifically, it asks whether there exists an efficient quantum reduction R such that, for any n-qubit unitary U , there exists a classical function f = fU such that Rf approximates U (say, to within some distance ϵ in operator norm). This question is attributed to Aaronson and Kuperberg in 2007 and is still open. A recent work [LMW24] gives evidence that the answer might be negative by showing that there is no such R that makes only a single query to f .
1.1
Our Results
Our first contribution, in Section 3, is a connection between ROM-PRUs and ϵ-nets. An ϵ-net over U(d) (the d-dimensional unitary group) is a set of unitaries N such that for all U ∈ U(d) there exists V ∈ N with ∥U − V ∥ ≤ ϵ, where ∥ · ∥ denotes the operator norm. We observe that this can be done by thinking of ROM-PRUs as unitary (approximate) t-designs. A t-design is a distribution over unitaries that is functionally identical to Haar-random unitaries for algorithms that make at most t queries. There are various ways to define approximate designs, but for the sake of this exposition we consider the so-called diamond approximation. A δ-approximate t-design is one where any adversary making at most t queries has at most δ statistical advantage in distinguishing the design from random. We call this diamond approximation since it corresponds to the diamond distance between the respective channels. A ROM-PRU with query bound τ induces (together with the distribution over the random oracle) an approximate τ -design, and therefore we seek a connection between such approximate designs and ϵ-nets. The question of quantitatively connecting unitary designs to ϵ-nets has only been studied recently [OSH21, SRS25], but to the best of our knowledge not in the context of diamond approximation. This notion, as we show, provides a more operational handle on the problem of finding a connection with ϵ-nets and in particular is more naturally manipulated using a cryptographic approach, as explained in the technical overview below. Specifically, we show that a diamond approximate t design, even for very mild δ, e.g. δ = 0.1, implies a notion that we call a relaxed ϵ-net, so long as t ≳ d2 /ϵ2 (or even d2 /ϵ, if δ = 0). A relaxed 2
ϵ-net can be thought of as an average-case property, or as a net that does not cover the entire group U(d), but rather only guarantees that with high probability over a Haar random U ∈ U(d), there exists a V ∈ N s.t. ∥U − V ∥ ≤ ϵ. It is then simple to show that if we compose a relaxed net with itself (i.e. take all matrices of the form V1 V2 , where V1 , V2 ∈ N ), we get a proper ϵ-net. We provide a detailed technical comparison of our results to the prior works [OSH21, SRS25] in Section 3.1. Translating these results back to ROM-PRUs (Section 4), we get that if τ ≳ d2 /ϵ2 (or d2 /ϵ under a stronger definition than diamond approximation), composing the ROM-PRU with itself implies an ϵ-net. We then observe that an ϵ-net in an oracle model trivially implies unitary synthesis. Specifically, the reduction R is an application of the ROM-PRU (composed with itself), and we have a guarantee that for all U there exists an instantiation of the random oracle to a function f such that Rf is close to U . This concludes our first result. + We √ recall that existing constructions of PRU [MPSY24, MH25, LQS 25] are all proven with τ ≳ d (we note that for “strong” PRU where the adversary has access to the inverse, transpose and conjugate of the unitary, existing proofs only show τ ≳ d1/32 [MH25, SML+ 25]). This means that “only” a polynomial improvement stands in the way of affirmatively resolving the unitary synthesis problem, contrary to the evidence in [LMW24]. Indeed, it may be the case that such a polynomial improvement is impossible, which would imply that some unknown consideration prevents us from achieving stronger unitary pseudorandomness. We believe that exploring this gap would shed light on the nature of this important class of primitives. Given that the gap√between what is known and what is sought is only polynomial, it makes sense to check whether the d bound in existing constructions is tight, or whether existing constructions come even closer to the d2 tipping point. We consider the now-famous PFC construction of PRUs, introduced in [MPSY24] and proven adaptively secure in [MH25]. √ We show in Section 6 that for this construction, it is possible to violate security using roughly d queries; furthermore, it suffices to query the unitary on the same input√|0⟩ in all queries. This result sharpens the motivation to find any construction that breaks the d barrier. We note in this context that there are many ways to tweak the construction so that our techniques no√longer work as is, even just sequential repetition. It remains an open problem whether there is a d upper bound for more general classes of constructions. Lastly, in Section 5, we analyze existing and prospective constructions of ROM-PRUs from an entropic standpoint. In particular, we show that relatively simple bounds impose strong constraints on what is achievable using standard techniques. We start by recalling some bounds from the literature on the cardinality of t-designs. We plug them into a simple counting argument for a ROM-PRU that uses an oracle f : {0, 1}m → {0, 1}. The support size of such a construction is m therefore at most 22 . It follows that such a construction can only implement an approximate t-design if m ≳ log t + loglog (d2 /t). Since in all known constructions it is only known how to use m ≤ log d, we get a bound t ≲ d. Indeed, such constructions cannot be scalable or even √ approach 2 the t = d tipping point. Note the intriguing gap between this bound and the actual t = d result that can be proven. We notice that the aforementioned bound only holds for t ≪ d2 (for larger values loglog (d2 /t) is undefined). Indeed, we are not aware of any lower bound in the literature that applies for t ≫ d2 . We therefore proceed to develop such a lower bound. We provide two proofs of similar statements: one from first principles using representation theory, and the other almost immediately from our previous results, using the connection to relaxed ϵ-nets that we described above. We find it quite satisfactory that this bound essentially matches the best known bound, using a very different
3
approach. We proceed to show that approaching t = d2 requires techniques different from those in the literature. Specifically, we show that relaxed ϵ-nets in an oracle model require the oracle’s input to have length at least 2 log d−o(log d). That is, in order to achieve unitary synthesis for n qubits, it is essential to use classical functions with input length roughly 2n. Such a claim follows immediately from a counting argument if we consider only classical functions with binary output. However, our results apply even in a generalized model that allows classical functions with infinite output length. Indeed, quantum access to a binary classical function is equivalent to access to a diagonal unitary with ±1 values (and whose dimension is 2n × 2n ). Likewise, if the range of the function is [q], then a q-ary root of unity replaces (−1). We may therefore allow arbitrary diagonal unitary gates, which would allow infinite precision in the description of the roots of unity along the diagonal, and potentially provide the necessary degrees of freedom required to construct ROM-PRUs and unitary synthesis. We show that this hope cannot be realized: even in the diagonal matrix model, it is impossible to achieve relaxed nets, and therefore also unitary synthesis and ROM-PRUs with τ ≫ d2 . This result in particular applies to all existing candidates for PRUs. No known polynomial-size construction manages to utilize oracles of large input length. The state-of-the-art unitary synthesis √ algorithm due to Rosenthal [Ros21] requires the circuit R to have size √ d, and it indeed uses an oracle with input length 2 log d. Viewed from our perspective, the d queries in that work are required to uncompute half of the 2 log d-qubit register provided to the oracle, in order to recover an output of length log d. It is quite curious that there are no known techniques for nontrivially utilizing classical functions of input length greater than log(d), and we highlight this as a challenge for future ROM-PRU constructions.
1.2
Technical Overview
We now provide an overview of the techniques used in the paper. Connections between ROM-PRU, Unitary Designs and Nets. In Section 3 we show connections between diamond designs and ϵ-nets. As explained above, working with diamond designs allows us to take a cryptographic approach to relating them to ϵ-nets. Indeed, a δ-approximate t-design in the diamond norm is simply a distribution that is δ-statistically indistinguishable from Haar random using t nonadaptive queries. Our intuition, therefore, is to show that if our design is not an ϵ-net, then it can be efficiently distinguished from the uniform distribution. A straightforward test that a set N is not an ϵ-net is to sample a random unitary U and calculate its distance to all elements in N ; if the unitary is ϵ-far from all elements in N , then N is not an ϵ-net. Likewise, if the probability of being far from all elements in N is high, then we do not even have a relaxed ϵ-net, as we explained above. Since we are only given query access to U , our strategy is to first learn U and obtain a unitary Û that has some guarantee of resembling U , and then compare Û against all elements of N , which does not require any additional queries. We use the learning algorithm of [HKOT23], which requires ≈ d2 log(1/η)/ϵ adaptive queries or 2 d log(1/η)/ϵ2 non-adaptive queries to learn U to within distance ϵ with probability at least 1 − η. We consider a distinguisher that makes the necessary number of queries to obtain Û , compares it against all elements in N , and returns 1 if and only if there is no element in N that is ϵ-close to Û . When drawing U from the approximate t-design, the probability of output 1 is at most η, essentially by definition. This means, using the indistinguishability property, that the probability 4
of returning 1 on a random U is at most η + δ. It follows that the support N induced by our approximate design is also a relaxed ϵ-net, with a fraction of at most η + δ of the unitary group not being covered. To go from a relaxed net to an ϵ-net we use composition. Indeed, this can be seen as a version of the worst-case to average-case reduction of the unitary synthesis question. Let N be a relaxed net that covers most of the unitary group, i.e. with probability > 0.5, for a random U , there exists a V that is ϵ-close to U . Now consider an arbitrary unitary T and the two dependent random variables U † and U T , where U is Haar random. Since both marginals are Haar random, by the union bound there is a positive probability that both are within ϵ distance from N . Therefore, there exist V1 , V2 ∈ N such that V1 − U † ≤ ϵ and ∥V2 − U T ∥ ≤ ϵ. It follows from submultiplicativity that ∥V1 V2 − T ∥ ≤ 2ϵ. Therefore, N · N is a full 2ϵ-net. Our results establish a direct relation between diamond-designs and ϵ-nets. This is different in terms of techniques and incomparable in terms of the final result from prior work that relied in the notion of “tensor-product extractors”. We provide a comparison and discussion in Section 3.1. Section 4 focuses on the notion of ROM-PRU, and in particular its scalable version. We provide a definition of scalable ROM-PRU and use the aforementioned results to show that a ROM-PRU with a sufficiently large τ would affirmatively resolve the unitary synthesis problem. √ An Upper Bound for Existing Constructions. In Section 6, we show that using roughly d queries to the PFC construction, we can distinguish it from uniform. Furthermore, this is done by simply querying the PFC construction on the fixed input 0, and measuring the resulting state in the computational basis. The property used for distinguishing is the number of collisions in this experiment. That is, if we make t queries, how many of the 2t pairs of strings have the same value? To understand why this test could be useful, let us zoom into the specifics of the PFC construction. As the name suggests, this construction contains 3 components. First, the input runs through a random Clifford C. Then it runs through a random phase gate |x⟩ → ω f (x) |x⟩, where ω is a root of unity (either (−1) as in [MPSY24], or a higher order root), and f is a random classical function with the proper domain and range. Finally, it runs through a random permutation P . The crucial observation is that if we are just looking at collisions on computational basis elements, then F and P are irrelevant, since they do not affect whether a collision occurs or with what probability. Therefore, for the sake of the collision-counting problem, the PFC construction is equivalent to a random Clifford, which at least intuitively should be quite different from a Haar-random unitary. For a Haar random unitary, the state U |0⟩ is a Haar random state, and its statistical properties are very well known. In particular, the probability of collision between two measurements of copies of the same string is roughly 2/d, and this value is extremely well √ concentrated. Namely, with 2 t probability close to 1 over U , we expect d 2 collisions. For t ≈ d, this becomes a noticeable quantity. For a Clifford, however, the state C |0⟩ is a random stabilizer state. Measuring a stabilizer state in the standard basis induces a uniform distribution over an affine F2 subspace of dimension k, where k depends on the specific Clifford C, i.e. a collision probability of 2−k . Indeed, we show that the event k = log(d) has constant probability. Therefore, with constant probability there is a constant gap between the number of collisions expected in the two experiments. In order to have a statistically significant test, we use the Median of Means estimator and show (by analyzing the variance of the collision number) that by performing the test correctly we have
5
a constant distinguishing gap between Haar and PFC. Entropy-Based Bounds for Designs and Unitary Synthesis. We show our lower bounds in Section 5. As explained above, we derive a new lower bound for the cardinality of the support of an approximate t-design, for t ≫ d2 in two ways. The first relies on representation theory and we will not survey it here. The second is quite straightforward given our work. If t ≫ d2 , then a unitary t-design is also a relaxed ϵ-net, i.e. it ϵ-covers some 1 − η fraction of the volume of the unitary group. Showing a lower bound on the cardinality of a relaxed net is trivial using volume 2 considerations: since the volume of an ϵ-ball is roughly ϵd , the cardinality of a relaxed design is d 2 at least (1 − η) 1ϵ . Our transformation requires t ≈ d2 /ϵ2 for diamond designs, which implies a d2 /2 bound of roughly (1 − η) dt2 , where η is related to δ. This turns out to be very similar (up to some constants and low order terms) to the bound that we get from representation theoretic analysis. As explained above, unitary synthesis is equivalent to having an ϵ-net in the classical oracle model. Therefore, the cardinality bound for ϵ-nets immediately implies that unitary synthesis with a binary function requires an input length of roughly 2 log d. Next, for our diagonal matrix result we again employ a simple principle. Any diagonal matrix ℓ , where ω = e 2πi K in U(d) can be approximated by a diagonal matrix with elements of the form ωK K and ℓ ∈ [K]. Note that ℓ can be represented by k = log K bits. It can be shown that the quality of this approximation scales with K1 . If we consider a candidate for unitary synthesis, then the number of calls to the diagonal oracle is bounded by the circuit size of the reduction R, which is polynomial (we can handle super-polynomial reductions as well); denote its size by s. Then so long as Ks is sufficiently small, the outcome of running R with a diagonal oracle versus a Ktruncated diagonal oracle should not be noticeable. For concreteness let us take k = polylog d so that K = dpolylog d . Then even a huge reduction size cannot notice the truncation. However, the truncated version corresponds to oracle access to a classical function with polylog d + O(1) output bits, which is equivalent to having a binary function whose input size increases additively by loglog d + O(1). Therefore, even working with diagonal matrices of infinite precision cuts only an additive loglog d factor from the required input length, compared to the binary-function setting. For example, for unitary synthesis, even in the diagonal matrix model, we require input length of at least 2 log d − loglog d − O(1).
2
Preliminaries
Throughout the paper we use approximate equalities (“≈”) and inequalities (“≲” and “≳”) to indicate relationships between two quantities without specifying universal constants or potentially 2 uninteresting logarithmic factors. For example, for variables t, d we might write t ≳ dϵ2 to mean 2 that there are universal constants c > 0 and C ≥ 1 such that t ≥ c dϵ2 + C. We let U(d) denote the unitary group over Cd , and 1d denote the identity element. We slightly abuse notation and let U ∈ U(d) also denote the quantum channel U (·)U † over Cd (which is a superoperator over Cd×d ). We let Haar(d) denote the Haar measure over U(d); we sometimes omit the d when it is clear from context. A distribution of unitaries ν is symmetric if ν † = ν; that is, sampling a unitary U ∼ ν and taking its Hermitian conjugate U † yields the same distribution ν. For a superoperator T we consider the following norms.
6
Definition 2.1. For a superoperator T , the k → k norm is defined as ∥T (X)∥k X̸=0 ∥X∥k
∥T ∥k→k = sup
where ∥X∥k denotes the Schatten-k norm (for k = 2 this is the Frobenius norm) of an operator X. Some important special cases include the 2 → 2 norm (expander norm) and the 1 → 1 norm. An important derived norm is the completely bounded 1 → 1 norm, also known as the diamond norm defined as ∥T ∥⋄ = sup ∥T ⊗ 1m ∥1→1 . m∈N
2.1
Nets
For any set of unitaries N , we let N † denote {V : V † ∈ N }. If N1 , N2 are two sets then N1 · N2 = {V1 · V2 : V1 ∈ N1 , V2 ∈ N2 }. We sometimes denote singleton sets {U} simply by U. We now define a metric to quantify how much a set of unitaries “covers” the entire unitary group. We say that a unitary is covered by the set N if it is sufficiently close to N . The usual definition of ϵ-nets requires that all unitaries are ϵ-close to N . For our purposes it is important to consider a refinement that we call an (ϵ, η)-net, where all but η-measure of the unitary group is ϵ-covered. A formal definition follows. Definition 2.2. The ϵ-coverage of a set of unitaries N ⊆ U(d) is defined as n o C (N ) = Cϵ (N ) = U ∈ U(d) : ∃ V ∈ N such that ∥U (·)U † − V (·)V † ∥⋄ ≤ ϵ . The ϵ-exposure of N is defined as the measure of unitaries that are not covered: h i η(N ) = ηϵ (N ) = Pr U ̸∈ C (N ) . U ∼Haar(d)
A set N is an (ϵ, η)-net if ηϵ (N ) ≤ η. We sometimes denote vol(N ) = volϵ (N ) = Haar(Cϵ (N )). Note that volϵ (N ) = 1 − ηϵ (N ). The notion of (ϵ, 0)-net coincides with the usual notion from the literature of ϵ-nets.1 We note that one can use a different distance measure for defining ϵ-closeness, however most relevant distance metrics would differ by a poly(d) factor, which for our purposes is usually not significant. We proceed by providing a counting argument for the minimal cardinality of a net. Proposition 2.3 (Fact 2 in [OSH21]). There exists a universal constant c⋄ > 0 such that the Haar 2 volume of an ϵ-ball in diamond norm over d dimensional unitary channels is at most (ϵ/c⋄ )d −1 . The following is an immediate consequence. Corollary 2.4. Let N be an (ϵ, η)-net. Then N ≥ (1 − η)
c d2 −1 ⋄
ϵ
.
1 This is not completely straightforward from the definition, since on the face of it, there could exist an exposed measure 0 set of unitaries that is not empty. However, since any exposed set is necessarily an open set, such a degeneracy is not possible.
7
2.2
Unitary Designs
A unitary (approximate) t-design is a distribution ν over unitary matrices that is similar to the Haar random measure so long as the associated channel is only invoked t times. There are various definitions for this object. In this work, we almost always use the notion of “diamond-design” (see below), but we sometimes compare with other notions in order to put our results in context. Definition 2.5 (Approximate unitary designs). Let ν be a distribution over U(d) and define the moment operator h i Φν,t (·) = E U ⊗t (·)U ⊗t,† . U ∼ν
We say that ν is: 1. A (t, δ)-diamond-design if: ∥Φν,t − ΦHaar,t ∥⋄ ≤ δ . 2. A (t, δ)-TPE (tensor-product expander) if: ∥Φν,t − ΦHaar,t ∥2→2 ≤ δ . 3. A (t, δ)-relative-design if: (1 − δ)ΦHaar,t ≤ Φν,t ≤ (1 + δ)ΦHaar,t . Some relations between the different notions are provided below. Proposition 2.6. Let ν be a distribution and t be some integer. Let λ, δ, ϵ be such that ν is a (t, δ)-diamond-design, (t, λ)-TPE and (t, ϵ)-relative-design. Then the following hold. 1. δ ≤ ϵ 2. λ ≤ dt/2 δ. 3. δ ≤ dt λ 4. ϵ ≤ d2t λ The proofs for the different relations appear in [Low10, BHH16, Mel24, CHH+ 24]. The following proposition can be derived as a corollary of [CHH+ 24, Corollary 2.11]; we provide an elementary proof for completeness. Proposition 2.7. If ν is a symmetric (meaning ν = ν † ) (t, δ)-diamond design, then it is also a (t, δ)-TPE. Proof. Let m be some integer, and consider νm as the m-composition of ν. Namely, each entry in νm is a sequential composition of m i.i.d elements from ν. Let λm , δm denote its t-design approximation with respect to the 2 → 2 and diamond norms respectively. Then it holds that λm ≤ dt/2 δm by the definitions of the norms (see e.g. [Mel24, Proposition 42]). Furthermore, if ν is symmetric then it holds that λm = λm (see e.g. [Mel24, Footnote 4]). Lastly, it holds that δm ≤ δ m [MPSY24, Lemma 4.11]. We conclude that for all m, λm = λm ≤ dt/2 δm ≤ dt/2 δ m . That is, for all m, λ ≤ dt/(2m) δ, which implies that λ ≤ δ. 8
Finally, the following gives operational consequences of the definitions of diamond and relative error designs. Proposition 2.8. The following relations exist between designs and distinguishability via quantum query algorithms. 1. A distribution ν is a (t, δ)-diamond-design if and only if for any non-adaptive t-query oracle algorithm A with {0, 1} output it holds that U
E [A ] −
U ∼ν
E
[AU ] ≤ δ .
U ∼Haar
2. A distribution ν is a (t, δ)-relative-design only if for any (possibly adaptive) t-query oracle algorithm A with {0, 1} output it holds that U
E [A ] −
U ∼ν
E
[AU ] ≤ δ .
U ∼Haar
Here, the algorithm A can only query controlled-U (but not its inverse). Note that there is no equivalence between relative-designs and indistinguishability by algorithms here, only a forward implication. Proof. The first item follows directly by definition. For the second item see [Kre21, Lemma 25].
3
From Designs to Nets
In this section, we present a new method for converting (approximate) designs into ϵ-nets. Our approach differs from previous works in two main respects. First, whereas previous works relied on TPE properties, we use the diamond norm or relative distance. Indeed, we show that even an extremely mild approximation under these metrics implies ϵ-nets. Second, we do not seek to show that the support of the approximate design itself constitutes an ϵ-net, as in previous work. Instead, we allow simple transformations of the approximate design, such as squaring or closing the set under inverse. In terms of techniques, we show a very elementary connection between approximate designs and (ϵ, η)-nets, and then show how (standard) ϵ-nets follow in a straightforward manner. A central building block for our construction is the family of channel tomography procedures from Haah et al. [HKOT23]. Proposition 3.1 (Unitary Tomography [HKOT23]). There are procedures Ti,ϵ,η,d that make oracle queries to an unknown unitary U ∈ U(d) and produce a classical description of a unitary Û such that ∥U (·)U † − Û (·)Û † ∥⋄ ≤ ϵ with probability at least 1 − η, with the following parameters: 2
1. T1,ϵ,η,d makes t = Θ( dϵ2 ln η1 ) non-adaptive queries to U . 2
2. T2,ϵ,η,d makes t = Θ( dϵ ln η1 ) adaptive queries to U . We sometimes remove some of the subscripts when they are clear from the context. We can now state and prove our first technical lemma, which converts approximate designs into relaxed nets. 9
Lemma 3.2 (Designs to nets). Let ν be a distribution over U(d) and N = support(ν). Let 2 ϵ ∈ (0, 1). Then if ν is a (t, δ)-diamond-design (respectively relative-design), for t = Θ( dϵ2 ln η10 ) 2
δ+η0 (respectively t = Θ( dϵ ln η10 )) then N is an (ϵ, η)-net, for η = 1−η . In particular if η0 ≤ 1/6 and 0 δ ≤ 1/6 then η ≤ 2/5.
Proof. We use a tomography argument. Suppose N were not an (ϵ, η)-net. Then there must exist a set S ⊆ U(d) of measure at least η such that every V ∈ S is at least ϵ-far, in diamond distance, from every unitary in N . Consider the following statistical test A to distinguish ν from the Haar measure, set i = 1 for the diamond-design setting and i = 2 for the relative-design setting. U 1. Run the algorithm Ti,ϵ/3,η from Proposition 3.1 to obtain Û . 0 ,d
2. If Û is within ϵ/3 of a point in S, then output 1. Otherwise, output 0. By Proposition 3.1 and Proposition 2.8, it follows that in both settings of this lemma statement, A is a distinguisher for the (t, δ) design, according to the respective metric. Furthermore, the invocation of T within A outputs Û at distance at most ϵ/3 from its input U with probability at least 1 − η0 . We now analyze the acceptance probability of A on the distributions Haar and ν. When U is drawn from the Haar measure, then E
U ∼Haar
[AU ] ≥ (1 − η0 )η .
(1)
This is the probability of the tomography algorithm succeeding, and conditioned on it succeeding, the probability that it samples a unitary U ∈ S which is at least η. By definition the estimated unitary Û is at most ϵ/3-far from S. On the other hand, when U is sampled from ν, then U
E [A ] ≤ η0
(2)
U ∼ν
because if the tomography procedure succeeds, the estimated unitary Û will be within ϵ/3 of U ∈ N , which by definition is at least (2ϵ/3)-far from S. Thus the procedure A can only accept when the tomography algorithm fails. Thus the statistical test can distinguish between ν and the Haar measure with advantage at least (1 − η0 )η − η0 . We get a contradiction if this value is larger than δ. Namely, we have that N δ+η0 is an (ϵ, η)-net with η = 1−η . In particular, if η0 < 1/6 and δ < 1/6, then η < 2/5. 0 Up to this point, we have shown that the support of a design constitutes a relaxed ϵ-net. We now show an extremely simple composition lemma that allows us to go from a relaxed net to a full net. In particular, we show how to compose two relaxed nets into a full net. Lemma 3.3. Let Ni be an (ϵi , ηi )-relaxed net for i = 1, 2. If η1 + η2 < 1, then N1 · N2† is an (ϵ1 + ϵ2 )-net. Proof. Let U be a unitary, and consider the nets N1 and U ·N2 . It holds that ηϵ1 (N1 )+ηϵ2 (U N2 ) = η1 + η2 < 1. Therefore, Cϵ1 (N1 ) ∩ Cϵ2 (U N2 ) is nonempty. Let T be a unitary in this intersection. Then by definition there exist V1 ∈ N1 , V2 ∈ N2 such that both ∥T (·)T † − V1 (·)V1† ∥⋄ ≤ ϵ1 and 10
∥T (·)T † − (U V2 )(·)(U V2 )† ∥⋄ ≤ ϵ2 . By triangle inequality we have ∥V1 (·)V1† − (U V2 )(·)(U V2 )† ∥⋄ ≤ ϵ1 + ϵ2 . By unitary invariance of the metric, we have ∥(V1 V2† )(·)(V1 V2† )† − U (·)U † ∥⋄ ≤ ϵ1 + ϵ2 . It follows that U ∈ Cϵ1 +ϵ2 (N1 N2† ) and the lemma follows. Using the above, if we have a good enough net, we can compose it with its inverse, or even with itself. Proposition 3.4. If N is an (ϵ, η)-relaxed net, then N † is also (ϵ, η)-relaxed. Proof. Consider the following derivation Pr [U ̸∈ Cϵ (N † )] =
U ∼Haar
=
Pr [U † ̸∈ Cϵ (N )]
U ∼Haar
Pr [U ̸∈ Cϵ (N )]
U ∼Haar
where the first equality follows from the inverse-symmetry of the diamond norm, and the second equality follows from the symmetry of the Haar measure. We get the following corollaries as a direct implication of Lemma 3.3. Corollary 3.5. Let N denote a (ϵ, η)-net, η < 1/2. Then N 2 and N N † are 2ϵ-nets.
3.1
Comparison with Prior Work
The quantitative connection between unitary designs and nets was first studied in [OSH21], and then improved upon by [SRS25]. The main result of [SRS25] is the following: Theorem 3.6 (TPE implies nets [OSH21, SRS25]). Let ν be a (t, λ)-TPE with t≳
d5/2 , ϵ
λ≲
ϵ d2 −1 d1/2
then support(ν) is an ϵ-net. Here, “≳” and “≲” hide log-factors in d and ϵ−1 as well as constants. We point out several important differences. First, the hypothesis of Theorem 3.6 assumes a tensor-product expander (TPE), rather than a diamond-design as in our result Lemma 3.2. Using Theorem 3.6 to relate diamond designs to nets would yield the following: a symmetric2 (t, δ)2 diamond-design yields a (relaxed) ϵ-net only if t ≳ d5/2 ϵ−1 and δ ≲ (ϵd−1/2 )d −1 , which is (in some ways) weaker than our Lemma 3.2, which handles any δ and requires t ≳ d2 ϵ−2 (i.e., a better dependence on d, but a worse dependence on ϵ). Second, our result relating diamond-designs to nets can be used to give a relatively simple proof of a statement very similar to Theorem 3.6. Corollary 3.7. Let ν be a (t, λ)-TPE with t≳
d2 1 ln , 2 ϵ η0
λ ≤ d−t δ
δ+η0 for some η0 , δ > 0, then support(ν) is a (ϵ, η)-net for η = 1−η . 0 2
We recall that a distribution ν is symmetric if ν = ν † .
11
Proof. If ν is a (t, λ)-TPE, then by Proposition 2.6, it is also a (t, dt λ)-diamond-design. The corollary statement follows directly from Lemma 3.2. In this corollary, the dependence on d in the lower bound for t is better, but the dependence on ϵ in the upper bound on λ is worse (ϵ appears in the exponent of d−t ). The result is also a relaxed net rather than a bona fide net (although Corollary 3.5 shows how this can be used to build an ϵ-net). Finally, we observe that the techniques used to prove Lemma 3.2 are very different from those used to prove Theorem 3.6 in [OSH21, SRS25], which were highly analytical and geometrical. Our proof is arguably much more intuitive and operational (e.g., using channel tomography as part of the argument). It is an interesting question whether our techniques can be used to completely recover the statement of Theorem 3.6.
4
ROM-PRUs and Scalability
A pseudorandom unitary (PRU) ensemble [JLS18] is a distribution over efficiently implementable unitaries that cannot be distinguished from Haar-random by a computationally efficient distinguisher that makes few queries to the unitary. The security of PRUs (as defined) requires a cryptographic hardness assumption, such as the existence of post-quantum one-way functions. All prior PRUs with security based on standard cryptographic assumptions are analyzed in two steps: first, the PRU is implemented as an algorithm that has access to a random Boolean function, and shown to be information-theoretically secure against a distinguisher that makes few queries. Notably, the distinguisher is not required to be computationally efficient. Then, the PRU implementation is made efficient by replacing the random Boolean function with the output of a post-quantum pseudorandom function (PRF), and consequently the PRU is secure against computationally bounded distinguishers. We formalize the object constructed in the first part of these analyses; we call it a ROM-PRU. Definition 4.1 (ROM-PRU). A family of d-dimensional unitaries U = {Uf }f indexed by boolean functions f : {0, 1}m → {0, 1} is a ROM-PRU with • Dimension d, • Construction query complexity q, • ROM input length m, • Implementation error α, • Security against t-query adversaries with distinguishing advantage δ, if and only if 1. (Efficient computability). There exists a q-query algorithm A such that for all f : {0, 1}m → {0, 1}, ∥Af (·) − Uf (·) Uf† ∥⋄ ≤ α .
12
2. (Pseudorandomness). For all t-query distinguishers D, Pr[DUf = 1] − f
Pr
[DU = 1] ≤ δ .
U ∼Haar(d)
Here, the first probability is over a uniformly random function f : {0, 1}m → {0, 1}. We compare this with the typical definition of PRU from [JLS18, MPSY24, MH25] and note several key differences. 1. The algorithms A (implementing the PRU) and D (distinguishing the PRU from Haarrandom) are only required to be query-bounded, not computationally bounded. 2. The algorithm A implementing the PRU queries a random boolean function f : {0, 1}m → {0, 1}, which can be thought of as analogous to the “key” in the standard definition of PRU from [JLS18]. 3. The PRUs in [MPSY24, CDX+ 24, MH25, LQS+ 25, SML+ 25] are assumed to be implemented by quantum algorithms with zero error, whereas in our definition of ROM-PRU we allow for some implementation error. Remark 4.2. In our definition of ROM-PRU, the distinguisher D only has query access to the unitary Uf , and not directly to the random function f . This is slightly different from the standard use of the ROM terminology in cryptography. In the context of PRUs, this seemingly weaker security definition is sufficient when the goal is to instantiate the random oracle f using a PRF. Remark 4.3. The reader may wonder about the purpose of the implementation error parameter α; after all, couldn’t it be folded into the distinguishing advantage? This parameter is used to capture cases in which the implementing algorithm A does not implement a unitary exactly, but rather some channel (for example, it might weakly entangle the input with some ancillas). Note that in our definition, a ROM-PRU is a finite set of unitaries indexed by Boolean functions, all of the same dimension. We can consider an asymptotic family of ROM-PRUs, indexed both by dimension and by a security parameter, and define what it means for such a family to be scalable. Definition 4.4 (Scalable ROM-PRU). A family {Ud,κ }d,κ∈N of uniformly-generated ROM-PRUs is a scalable ROM-PRU family if each Ud,κ = {Ud,κ,f }f is a d-dimensional ROM-PRU with 1. Construction query complexity and ROM input length poly(log d, κ), 2. Implementation error 2−κ , 3. Security against 2κ -query adversaries with distinguishing advantage at most 2−κ . Here, “uniformly-generated” means that there is a single uniform quantum algorithm A that, when it gets parameters d, κ as input, implements the ROM-PRU Ud,κ . Informally, a family of ROM-PRUs is scalable if the security (the adversary query budget and the distinguishing advantage) can be tuned independently of the dimension, and furthermore the PRU is efficient (i.e., polynomial in log d and κ) to implement.
13
4.1
Prior constructions of ROM-PRUs
We summarize known constructions of ROM-PRUs. Cryptographically-secure PRUs. A recent line of works established the existence of cryptographicallysecure PRUs (i.e., PRUs in the plain model, without a random oracle) [MPSY24, CDX+ 24, MH25, LQS+ 25, SML+ 25]. Peering into the construction and analysis of these PRUs, however, reveals that they all (essentially) constructed ROM-PRUs first3 , and then instantiated the random oracle with a post-quantum secure PRF. All of these ROM-PRU constructions have the following parameter settings: 1. Construction query complexity and ROM input length poly(log d). 2. No implementation error. 3. Security against t-query adversaries with distinguishing advantage O(tc /d) for some constant c ≥ 2. While the construction is efficient in terms of query complexity and ROM input length, note that the number of queries tolerable by the adversary is at most d1/c ≤ d1/2 . Therefore these constructions are not proved to be scalable; in fact, we show in Section 5 that these constructions are inherently not scalable. Is there any construction of a scalable ROM-PRU, for any parameter regime? We next present what we call a “trivial” construction of a scalable ROM-PRU. A trivial scalable ROM-PRU. This trivial construction relies on the existence of, for every dimension d and integer t, an exact unitary t-design ν (which is both a diamond- and relative-error design) with support size 2 2 d +t−1 . |support(ν)| = d2 − 1 This follows from [RS09, Theorem 11]. In what follows, we will set t = 2κ . The second item of Proposition 2.8 implies that ν is completely indistinguishable from the Haar measure by any quantum algorithm making t queries (even adaptive ones). We now describe the construction. Here, the random oracle is used as a source of randomness to specify a unitary from support(ν) = {Uj }j (we assume there is a canonical ordering of the unitaries), and the construction algorithm A queries the random oracle bit-by-bit to obtain the index j, requiring log |support(ν)| queries (one query for each bit of the index). The ROM input length is thus log log |support(ν)| (the length needed to represent an index into the binary representation of j). Once the index j is known, the construction algorithm A can directly implement Uj , which we assume has been precomputed beforehand (we do not track computational complexity in this setting). The implementation error is 0, and the security is against adversaries making 2κ queries; these cannot distinguish ν from Haar at all. This yields a ROM-PRU family (indexed by dimension and the security parameter) with implementation error 0, security against 2κ -query adversaries, with distinguishing advantage 0. Therefore 3
In certain cases, such as in the CPFC construction of [MH25], the random oracle might have higher-arity outputs (rather than bits) or be a permutation over a large alphabet; we still call these ROM-PRUs for convenience.
14
it would constitute a scalable ROM-PRU family according to the definition, except that the construction query complexity is 2 d +t−1 e(d2 + t − 1) 2 log |support(ν)| = 2 log ≤ 2(d − 1) log . d2 − 1 d2 − 1 For t = 2κ this is at most O(d2 · κ) = poly(d, κ), rather than poly(log d, κ). This leaves open the question of whether there is an efficient construction of a scalable ROMPRU in terms of the dimension dependence – if not polynomial in log d, then at least with better than d2 dependence. Question 1. Is there a scalable ROM-PRU where the construction query complexity q and the ROM input length m satisfy qm ≪ dc · poly(log d) · poly(κ)
4.2
ROM-PRUs, Unitary Designs, and the Unitary Synthesis Problem
In this section we relate ROM-PRUs with approximate unitary designs, and the unitary synthesis problem of Aaronson and Kuperberg [AK07]. First, ROM-PRUs are diamond designs. Proposition 4.5 (ROM-PRUs are diamond designs). Let U = {Uf }f denote a ROM-PRU with security against t-query adversaries with distinguishing advantage δ. Then U is also a (t, δ)diamond-design. Proof. This follows by Definition 4.1 (definition of ROM-PRU) and Proposition 2.8 (which relates the definition of diamond design to distinguishability by query algorithms). Next, we show that an efficient construction of a scalable ROM-PRU would imply a positive solution to the unitary synthesis problem. This is a question of whether there is an efficient quantum oracle algorithm that can implement any unitary, given access to a classical oracle that depends on the unitary. Definition 4.6 (Unitary synthesis). We say a query algorithm A solves the unitary synthesis problem for dimension-d unitaries with query complexity t, oracle input length m, and error ϵ if for all unitaries U ∈ U(d) there exists a boolean function f : {0, 1}m → {0, 1} such that A makes t queries to f and implements U up to diamond distance error ϵ. Aaronson and Kuperberg [AK07] asked the following question: Question 2 (Unitary synthesis problem). Is there an efficient quantum algorithm that solves the unitary synthesis problem with query complexity t, oracle input length m, and error 1/2 satisfying tm ≤ poly(log d)? We note that there are two trivial quantum algorithms for solving unitary synthesis: one with query complexity t ≈ d2 and oracle input length m ≈ log d (i.e., reading the classical description of the unitary bit-by-bit), and one with query complexity t = 1 and oracle input length m ≈ d2 (i.e., using the Bernstein-Vazirani trick as described in [LMW24]). The best algorithm for unitary synthesis √ known so far is due to Rosenthal [Ros21], who presented an algorithm with query complexity t ≈ d and oracle input length m ≈ poly(log d). Our next observation is that for a sufficiently small δ, a scalable ROM-PRU would imply a solution to the unitary synthesis problem per Definition 4.6. 15
Lemma 4.7. Suppose there exists a scalable ROM-PRU family. Then there exists an algorithm B that solves the unitary synthesis problem with error 12 and query complexity and oracle input length poly(log d). Proof. Let {Ud,κ }d,κ be the hypothesized scalable ROM-PRU family. Fix a dimension d and set κ = c log d for a large constant c ≥ 2 to be set later. By definition, Ud,κ = {Ud,κ,f }f is a ROMPRU with construction query complexity q = poly(log d) and ROM input length m = poly(log d), implementation error at most d−c , and security against dc -query adversaries with distinguishing advantage at most d−c . Let ν denote the uniform distribution over Ud,κ . By Proposition 4.5 it follows that ν is a c , d−c )-diamond-design. By Lemma 3.2 the set U (d d,κ is a (ϵ, η)-net for some η ≤ 2/5 and ϵ = p 2 is a 2ϵ-net. Henceforth 2 c Cd /d for some universal constant C ≥ 1. Then by Theorem 3.5 Ud,κ we omit d, κ subscripts for clarity. Let V ∈ U(d). Since U 2 is a 2ϵ-net, there exist unitaries Uf1 , Uf2 ∈ U for Boolean functions f1 , f2 : {0, 1}m → {0, 1} such that V is 2ϵ-close, in diamond distance, to the product Uf2 Uf1 . Consider the following unitary synthesis algorithm B: it runs the construction algorithm A with query access to f1 , and then runs A again with query access to f2 (we can combine f1 , f2 into a single Boolean function with an extra input bit as a “switch”). Each invocation of A incurs implementation error at most d−c , so by the triangle inequality B synthesizes a unitary that is (2ϵ + 2d−c )-close to V . Furthermore, the query complexity is poly(log d) and the oracle input length is poly(log d). We can choose a constant c ≥ 2 such that for sufficiently large d, we have 2ϵ + 2d−c ≤ 12 . In fact, by taking c sufficiently large as a function of any fixed a > 0, the same argument gives synthesis error at most d−a , while keeping query complexity and oracle input length poly(log d). Remark 4.8. The previous lemma only requires ROM-PRUs that are secure against distinguishers making non-adaptive queries to U (inverse queries U † and adaptive queries are not needed). Remark 4.9. The reader may note that the scalability property is much more than is necessary; the connection between ROM-PRUs and the unitary synthesis problem holds the moment the ROMPRU is secure against adversaries making t ≳ d2 queries, and the ROM-PRU construction query complexity and ROM input length translate directly to the unitary synthesis solver’s query complexity and oracle input length.
5
Lower Bounds for Designs and ROM-PRUs
In this section we present some lower bounds on approximate unitary designs and ROM-PRUs. The lower bounds on ROM-PRUs, in particular, place nontrivial constraints on the space of possible constructions of scalable ROM-PRUs. We start in Section 5.1 by stating cardinality lower bounds for t-designs from previous works, followed by our own contribution for the setting of t ≫ d2 . Using these bounds, together with the volume bound on ϵ-nets from Corollary 2.4, we derive in Section 5.2 a lower bound on the size of binary functions required to obtain families of designs and nets. Finally, in Section 5.3, we show that using diagonal matrices, which supposedly have infinite entropy, does not actually change the picture significantly.
16
5.1
Cardinality Lower Bounds for Approximate Designs
In this section we prove new lower bounds for the support size of approximate t-designs. Prior work [BHH16, BCH+ 21] proved the following lower bound: let ν be a (t, δ)-diamond-design. Then n d+t−1 2 1 d2t o |support(ν)| ≥ max (1 − δ) , . (3) t 1 + δ t! The first part of the bound follows from [BHH16, Lemma 26], and the second part follows from [BCH+ 21, Lemma 5]. We note that this bound is roughly optimal for t ≤ d; from [RS09, Theorem 11] we have that 2 2 there exist exact t-designs with cardinality at most d +t−1 . Up to a polynomial this is close to t d+t−1 2 the lower bound of (1 − δ) t in the regime that t ≤ d. However when t ≳ d, omitting the dependence on δ, this first bound is at most d+t−1 2 d + t − 1 2 e(d + t − 1) 2(d−1) ct 2d ≤ = ≤ d−1 d t d−1 for some constant c. For the regime d ≲ t ≲ d2 , the first bound is superseded by the second bound, which is at least d2t 1 ed2 t ≈√ t! 2πt t where we used Stirling’s approximation of t!. However, when t ≫ d2 , this second bound becomes vacuous. Are there better support size bounds for the regime that t ≫ d2 ? We address this next. Lower Bounds from Epsilon Net Arguments. We leverage the connection between approximate t-designs and ϵ-nets that we established in Section 3. The approximate design lower bound then follows from well-known lower bounds on the sizes of ϵ-nets. Lemma 5.1 (Lower Bounds for Approximate Designs for t ≳ d2 ). There exists a constant C > 0 such that the following holds. Let ν be a (t, δ)-diamond-design for some 0 ≤ δ < 1. Then !(d2 −1)/2 2 − 2δ Ct 1 |support(ν)| ≥ . · · 1 3+δ d2 ln (1−δ)/4 Proof. Let ν be a (t, δ)-diamond-design. Set η0 = (1 − δ)/4. Then η=
δ + η0 1 + 3δ = 1 − η0 3+δ
By Lemma 3.2 there exists a constant c such that N = support(ν) is a (ϵ, η)-net with s cd2 1 ϵ= ln . t η0 The claimed support size bound then follows from Corollary 2.4, which gives a lower bound on the size of (ϵ, η)-nets. Note that for the regime t ≳ d2 , with δ bounded away from 1, Lemma 5.1 gives bounds of size 2 at least eΩ(d ) , which are better than the bounds (3) given in prior work. 17
5.2
Entropy Bounds on Constructions with a Classical Oracle
Consider a family of unitaries U = {Uf }f ⊆ U(d) where f : {0, 1}m → {0, 1} is a classical function. m Since such a family has cardinality at most 22 we can derive the following conclusions. Remark 5.2. Without loss of generality, the above also has implications if instead of a single binary function f , U has access to functions g1 , . . . , gk , where gi : P {0, 1}m → {0, 1}ℓi . This is m+⌈log ℓ⌉ equivalent to a single function f : {0, 1} → {0, 1}, where ℓ = i ℓi . This is because f can use ⌈log ℓ⌉ bits to indicate which output bit (of which function gi ) it wishes to access. We derive the following corollaries by plugging in our cardinality bounds for designs and nets, suppressing lower-order additive constants. The logarithmic expressions below are interpreted in the parameter regimes where they are well-defined. Corollary 5.3. If U contains the support of some (t, δ)-diamond-design then m ≥ log(t) + loglog (d2 /t) − O(1) ,
(4)
and also (assuming 1 − δ = Ω(1)): m ≥ 2 log(d) + loglog (t/d2 ) − O(1) .
(5)
Corollary 5.4. If U is an (ϵ, η)-net and 1 − η = Ω(1), then m ≥ 2 log d + loglog (1/ϵ) − O(1) .
(6)
Implications for Existing PRU Constructions and Candidates. We can derive a conclusion regarding all existing PRU candidates in the oracle model (whether proven or not) [JLS18, MPSY24, MH25, LQS+ 25]. In particular, all such constructions rely on random oracles with input length log d and output length at most polylog d. They may also use up to polylog d different functions. It follows, therefore, that such a construction can potentially be a (t, δ)-diamond design only for t at most d polylog d. Nor can such constructions be an ϵ-net, or even a relaxed net, for any nontrivial parameters; therefore, they cannot be used as unitary synthesis solutions.
5.3
Diagonal Matrices Do Not Add Much Entropy
We show that the use of diagonal matrices with infinite precision does not provide a viable way to get around the entropy barrier. In particular, diagonal matrices with infinite precision can be replaced by classical binary functions of similar dimension. Theorem 5.5. Let {U D1 ,...,Dℓ }D1 ,...,Dℓ be a family of unitaries with oracle access to ℓ diagonal unitaries of dimension 2m , and let s be an upper bound on the number of oracle calls made by U (note that ℓ ≤ s without loss of generality). Then for all ϵ there exists a classical-oracle implementation ′ family {V f }f , with f : {0, 1}m → {0, 1} and m′ ≤ m + log s + loglog ((s/ϵ) + O(1)), such that for all D1 , . . . , Dℓ there exists f satisfying U D1 ,...,Dℓ − V f
18
⋄
≤ϵ.
We now derive corollaries similar to the above for the diagonal setting. We consider a family of unitaries D = {U D1 ,...,Dℓ }D1 ,...,Dℓ ⊆ U(d) where each Di ∈ U(2m ) is a diagonal matrix (note that this family has uncountable cardinality), and let s = poly(log d, κ) for some security parameter κ. The theorem above asserts that this family can be d− log d -approximated by a family of cardinality m′ 22 for m′ = m + O(loglog d + log κ). Hence the following holds. Corollary 5.6. If D contains the support of some (t, δ)-diamond-design with 1 − δ = Ω(1) then m ≥ log(t) + loglog (d2 /t) − O(loglog d + log κ) ,
(7)
m ≥ 2 log(d) + loglog (t/d2 ) − O(loglog d + log κ) .
(8)
and also
Corollary 5.7. If D is an (ϵ, η)-net and 1 − η = Ω(1), then m ≥ 2 log d + loglog (1/ϵ) − O(loglog d + log κ) .
(9)
We now prove the theorem. Theorem 5.5. For a real value x ∈ (−1, 1] we denote ⌈x⌋k = 2−k ⌈2k x⌋, where ⌈·⌋ is rounding to the nearest integer, breaking ties upwards. We note that |x − ⌈x⌋k | ≤ 2−(k+1) . If f : X → (−1, 1] is some function, then we define ⌈f ⌋k to be the function where ⌈f ⌋k (x) = P ⌈f (x)⌋k . For any function iπf (x) |x⟩⟨x|. We say m f : {0, 1} → (−1, 1], we let Df denote the diagonal unitary Df = xe that D⌈f ⌋k is the “k-truncation” of Df . Note that a k-truncated function can be expressed as a {0, 1}m → {0, 1}k+1 function. It follows from [HKOT23, Definition 1.5, Proposition 1.6] that Df − D⌈f ⌋k ⋄ ≤ 2−k π , since it holds that maxx |θx | ≤ π2−(k+1) . Let us now consider the family U D1 ,...,Dℓ . Let fi (x) be such that Di = Dfi and let gi = ⌈fi ⌋k , ′ Di = Dgi . Then by the union bound over the (at most) s oracle calls of U : ′
′
U D1 ,...,Dℓ − U D1 ,...,Dℓ
⋄
≤ s2−k π .
Therefore, by choosing k = log(s/ϵ) + O(1) with a sufficiently large additive constant, this distance is at most ϵ. We point out that each gi is determined by a function in {0, 1}m → {0, 1}k+1 . By Remark 5.2 it ′ ′ therefore holds that U D1 ,...,Dℓ can be implemented using V f , where f : {0, 1}m+log(s(k+1)) → {0, 1}. Plugging in the expression for k from above, the claim follows.
6
Optimal distinguisher for PFC
The so-called “PFC” ensemble for unitary designs and PRUs was first introduced by [MPSY24], which showed that if P is a random 2n × 2n permutation matrix, F is a random diagonal unitary matrix, and √ C is a uniformly random n-qubit Clifford operator, then the t-th moments of P F C are O(t/ d)-close in trace distance to those of a Haar-random unitary, where d = 2n . The proof 19
of [MPSY24] thus only shows that the PFC ensemble is indistinguishable from Haar random when √ t ≪ d. The arguments from Section 5 imply that PFC cannot be a secure ROM-PRU for t ≳ d. This √ left open whether the t-th moments of PFC are still indistinguishable from Haar for the range d ≤ t ≤ d. √ In √ this section we exhibit an optimal distinguisher for the PFC ensemble for t = Θ( d). That is, Θ( d) nonadaptive queries to the PFC ensemble are enough to distinguish PFC from Haar random with constant advantage. The distinguisher is as follows. Set parameters √ t = ⌈ d⌉ ,
α=
1 , 4
k = 100000 .
1. Non-adaptively query the unitary oracle U on the all zeroes state, kt times, to obtain |ψ⟩⊗kt . 2. Divide the kt copies into k blocks of t copies each. For the r’th block: Measure all of the t (r) (r) copies of |ψ⟩ in the standard basis to obtain classical strings x1 , . . . , xt ∈ {0, 1}n . Let M (r) =
X
(r)
1{xi
(r)
= xj }
i<j
denote the number of collisions in the r’th block. P 3. Let M = k1 kr=1 M (r) denote the empirical average of the number of collisions in each block. Fix a threshold α, to be set later. If t 2 M− ≤α 2 d+1 then output “Haar”. Otherwise, output “PFC”. The following technical lemma argues that the estimator M concentrates around the average two-way collision probability (meaning measuring two copies of the state |ψ⟩ yields the same string), and the concentration also depends on the three-way collision probability. Lemma 6.1. Let |ψ⟩ be a state with the two- and three-way collision probabilities X X pψ = | ⟨x|ψ⟩ |4 and qψ = | ⟨x|ψ⟩ |6 . x∈{0,1}n
x∈{0,1}n
Then defining µ=
t pψ 2
we have that for all β > 0 Pr
τ = t2 pψ + 2t3 qψ ,
and
τ M −µ ≥β ≤ kβ 2 (r)
where the randomness is over the samples {xj }1≤r≤k,1≤j≤t .
20
(r)
Proof. Consider a fixed block r. For 1 ≤ i < j ≤ t, let Eij denote the indicator variable for P (r) (r) (r) whether xi = xj . Then M (r) = i<j Eij by definition. (r)
In what follows, all probabilities are over the randomness of sampling {xi }i ; the state |ψ⟩ is fixed. The expectation µ of M (r) is X t (r) (r) µ = EM = pψ E Eij = 2 i<j
Now we calculate the variance of M (r) with respect to the randomness of sampling x1 , . . . , xt . X (r) (r) (r) 2 Eij Ei′ j ′ . E(M ) = E i<j i′ <j ′
We can divide the above sum into three cases: {i, i′ , j, j ′ } has two, three, or four distinct indices. Suppose that it is two; then the sum becomes X (r) t Eij = pψ . E 2 i<j
When there are three distinct indices, the expected value corresponds to the three-way collision probability: X X t t (r) (r) Eij Ei′ j ′ = qψ ≤ 2 (t − 2) = 6 qψ . E 2 3 ′ ′ ′ ′ i<j,i <j |{i,i′ ,j,j ′ }|=3
i<j,i <j |{i,i′ ,j,j ′ }|=3
When there are four distinct indices, we have X (r) (r) Eij Ei′ j ′ = E i<j,i′ <j ′ |{i,i′ ,j,j ′ }|=4
X
i<j,i′ <j ′ |{i,i′ ,j,j ′ }|=4
p2ψ =
t−2 2 t pψ . 2 2
Thus the variance of M (r) is 2 t t t t t−2 2 2 p2ψ σ = pψ + 6 qψ + pψ − 2 2 3 2 2 ≤ t2 pψ + 2t3 qψ := τ where in the last line we used that t−2 ≤ 2t . 2 The variance of the average number of collisions in each block is thus k 1 X σ2 τ Var M (r) ≤ ≤ . k k k r=1
Thus, as we average the number of collisions across the k blocks, we obtain an estimate that is concentrated around the mean µ. By Chebyshev’s inequality the probability that the average 1 P number of collisions M = k r M (r) deviates from µ by more than β is bounded by τ Pr M − µ ≥ β ≤ . kβ 2
21
Now we argue for an appropriate choice of α, the estimator M for a Haar-random state that, t 2 |ψ⟩ is close to 2 d+1 with high probability. Lemma 6.2. For sufficiently large d, if U is sampled from the Haar measure, then the distinguisher outputs “Haar” with probability at least 0.99. Proof. When U is Haar-random, the state |ψ⟩ = U |0 · · · 0⟩ is Haar-random. In what follows, the probabilities will be taken over the randomness of sampling |ψ⟩. Expectation. Note that (2)
E pψ = E ψ
ψ
=
X
⟨x, x|ψ, ψ⟩ ⟨ψ, ψ|x, x⟩ =
X
x
d
⟨x, x|
x
=
d+1 2
Πsym (2)
|x, x⟩
Tr(Πsym )
2 . d+1
We used that averaging over two copies of a Haar-random state yields the maximally mixed state (2) on the symmetric subspace (whose projector is Πsym ). Similarly, we have (3)
ψ
X
Πsym
|x, x, x⟩ (3) Tr(Πsym ) 6 d = d+2 = . (d + 2)(d + 1) 3
E qψ =
⟨x, x, x|
x
Variance.
Note that X X 2 | ⟨x|ψ⟩ |4 · | ⟨y|ψ⟩ |4 = E ⟨x, x, y, y|ψ, ψ, ψ, ψ⟩ ⟨ψ, ψ, ψ, ψ|x, x, y, y⟩ E pψ = E ψ
ψ
=
ψ
x,y
1
X
d+3 4
x,y
⟨x, x, y, y| Π(4) sym |x, x, y, y⟩
x,y
(4)
where Πsym denotes the projector onto the four-fold symmetric subspace. We divide the sum into two cases. When x = y, the sum becomes d
=
d+3 4
4! (d + 3)(d + 2)(d + 1)
When x ̸= y, we have 1 Π(4) |x, x, y, y⟩ + |y, y, x, x⟩ + |x, y, x, y⟩ + |y, x, y, x⟩ + |x, y, y, x⟩ + |y, x, x, y⟩ . sym |x, x, y, y⟩ = √ 6 (4)
Therefore ⟨x, x, y, y| Πsym |x, x, y, y⟩ = 16 . Putting everything together, we have 2
E pψ = ψ
4! + 4(d − 1) (d + 3)(d + 2)(d + 1) 22
Thus the variance is 4! + 4(d − 1) 4 − (d + 3)(d + 2)(d + 1) (d + 1)2 4(d + 5)(d + 1) − 4(d + 3)(d + 2) = (d + 3)(d + 2)(d + 1)2 4(d − 1) = = Θ(d−3 ) . (d + 3)(d + 2)(d + 1)2
2 Varψ (pψ ) = E p2ψ − E pψ = ψ
ψ
Define |ψ⟩ to be good if 1 2 ≤ 100d 1. pψ − d+1
2. qψ ≤ d−3/2 . A state |ψ⟩ fails to be good only if either condition (1) or condition (2) fails to hold. By Chebyshev’s inequality, we have 1 2 ≥ ≤ Varψ (pψ ) · O(d2 ) = O(d−1 ) . Pr pψ − ψ d+1 100d Thus condition (1) fails to hold with probability at most O(1/d). By Markov’s inequality condition (2) fails to hold with probability at most O(d−1/2 ). Therefore |ψ⟩ is not good with probability at most O(d−1/2 ). Fix a good |ψ⟩. Now consider the 2distinguisher. The distinguisher is checking whether the empirical average M deviates from 2t d+1 by more than α; this implies the event that M deviates 2 1 t t from µ := 2 pψ by more than α − |µ − 2 d+1 | ≥ α − 2t 100d ≥ 81 =: β (this uses that |ψ⟩ is good and that d is sufficiently large). We can thus bound the probability as follows: t 2 τ Pr M − ≥ α : ψ good ≤ Pr M − µ ≥ β : ψ good ≤ 2 d+1 kβ 2 where we used Lemma 6.1. Then we have that τ Pr distinguisher outputs “Haar” ≥ Pr(ψ is good) 1 − kβ 2 τ ≥ (1 − O(d−1/2 )) 1 − . kβ 2 Now we compute an upper bound on τ := t2 pψ + 2t3 qψ . Since |ψ⟩ is good, we have that 2 1 pψ ≤ d+1 + 100d ≤ d3 and qψ ≤ d−3/2 . Thus τ≤
3t2 2t3 + 3/2 ≤ 5 d d
for all sufficiently large d. Thus for sufficiently large d, we have 320 Pr distinguisher outputs “Haar” ≥ 1 − − O(d−1/2 ) ≥ 0.99 k as claimed. 23
On the other hand, we show that the PFC ensemble is detected with probability at least 41 by the distinguisher. Lemma 6.3. For sufficiently large d, if U is sampled from the PFC ensemble, then the distinguisher outputs “PFC” with probability at least 1/4. Proof. Let U = P F C for a random permutation matrix P , random diagonal unitary F , and random Clifford C. Let |φ⟩ = C |0 · · · 0⟩. By definition |φ⟩ is a stabilizer state; for every fixed choice of C there exists an affine subspace A ⊆ Zn2 such that measuring |φ⟩ in the standard basis yields a uniformly random element of A: 1 X |φ⟩ = p αx |x⟩ |A| x∈A where αx are complex numbers on the unit circle. The state |ψ⟩ = P F C |0 · · · 0⟩ = P F |φ⟩ has the property that measuring it in the standard basis yields the uniform distribution over a set of size |A| (though the set need not be a subspace, because of the permutation P ). For a fixed |ψ⟩, the two- and three-way collision probabilities are straightforward to calculate: pψ =
1 |A|
and
qψ =
1 . |A|2
Condition on the event that |A| = d; in other words, the stabilizer state has full support. Then t2 and µ := 2t d1 ≤ 2d t2 2t3 τ= + 2 ≤2. d d By Lemma 6.1 we have that for all β > 0, τ Pr M − µ ≥ β : |A| = d ≤ . kβ 2 2 2 Set β := 81 . Since 2t d+1 − µ = 2t d+1 − d1 ≥ 13 for sufficiently large d, we have that Pr
M−
t 2 τ ≤ α : |A| = d ≤ Pr M − µ ≥ β : |A| = d ≤ . 2 d+1 kβ 2
This means that Pr(distinguisher outputs “PFC”) t 2 ≥ Pr(|A| = d) Pr M − ≥ α : |A| = d ψ 2 d+1 τ 128 ≥ Pr(|A| = d) 1 − ≥ Pr (|A| = d) 1 − . ψ ψ kβ 2 k Finally, we need to lower bound the probability that |A| = d. We do this by exhibiting a large family of stabilizer states with full support. Let M ∈ {0, 1}n×n be a matrix with zeros along the diagonal, and let u, v ∈ {0, 1}n . Define the state X ⊤ |ΓM,u,v ⟩ = 2−n/2 i u·x (−1)x M x+v·x |x⟩ . x∈{0,1}n
This is a stabilizer state because it is obtained from |+⟩⊗n by the following Clifford circuit: 24
1. Apply S to qubit i if ui = 1. 2. Apply CZij if Mij = 1. 3. Apply Z to qubit i if vi = 1. These states are distinct for every choice of M, u, v. Counting, there are 2n(n−1)/2 · 22n such states. On the other hand, it is well-known that the total number of n-qubit stabilizer states is 2
n
n Y
(2j + 1) .
j=1
Taking ratios we get that the number of full-support stabilizer states is at least Pr(|A| = d) ≥ ψ
n
n
j=1
j=1
X Y 2n(n−1)/2 · 22n 1 −j Q ≥ exp − = 2 ≥ e−1 . 2n nj=1 (2j + 1) 1 + 2−j
Putting everything together, we have that Pr(distinguisher outputs “PFC”) ≥
128 1 1 1− ≥ e k 4
as claimed. √ Lemma 6.4. There exists an adversary for the PFC ensemble that makes Θ( d) queries and distinguishes PFC from Haar with constant advantage. Proof. This follows from Lemma 6.2 and Lemma 6.3.
Acknowledgments Zvika Brakerski is supported by the Horizon Europe Research and Innovation Program via ERC Project ACQUA (Grant 101087742). Henry Yuen is supported by AFOSR award FA9550-23-10363, NSF awards CCF-2530159, CCF-2144219, and CCF-2329939, and by the Sloan Foundation.
References [AK07]
Scott Aaronson and Greg Kuperberg. “Quantum versus classical proofs and advice”. In: Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07). IEEE. 2007, pp. 115–128 (cit. on p. 15).
[BCH+ 21]
Fernando GSL Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill. “Models of quantum complexity growth”. In: PRX Quantum 2.3 (2021), p. 030316 (cit. on p. 17).
[BHH16]
Fernando GSL Brandao, Aram W Harrow, and Michal Horodecki. “Local random quantum circuits are approximate polynomial-designs”. In: Communications in Mathematical Physics 346.2 (2016), pp. 397–434 (cit. on pp. 8, 17).
25
[BS20]
Zvika Brakerski and Omri Shmueli. “Scalable Pseudorandom Quantum States”. In: Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part II. Ed. by Daniele Micciancio and Thomas Ristenpart. Vol. 12171. Lecture Notes in Computer Science. Springer, 2020, pp. 417–440. doi: 10.1007/978-3-030-568801\_15. url: https://doi.org/10.1007/978-3-030-56880-1%5C_15 (cit. on p. 2).
[CDX+ 24]
Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Fernando GSL Brandão, and Patrick Hayden. “Efficient unitary designs from random sums and permutations”. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2024, pp. 476–484 (cit. on pp. 13, 14).
[CHH+ 24]
Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. “Incompressibility and spectral gaps of random circuits”. In: CoRR abs/2406.07478 (2024). doi: 10.48550/ARXIV.2406.07478. arXiv: 2406.07478. url: https://doi. org/10.48550/arXiv.2406.07478 (cit. on p. 8).
[HKOT23]
Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang. “Query-optimal estimation of unitary channels in diamond distance”. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2023, pp. 363–390 (cit. on pp. 4, 9, 19).
[JLS18]
Zhengfeng Ji, Yi-Kai Liu, and Fang Song. “Pseudorandom Quantum States”. In: Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III. Ed. by Hovav Shacham and Alexandra Boldyreva. Vol. 10993. Lecture Notes in Computer Science. Springer, 2018, pp. 126–152. doi: 10.1007/978-3-319-96878-0\_5. arXiv: 1711.00385. url: https://doi.org/10.1007/978-3-319-96878-0%5C_5 (cit. on pp. 1, 12, 13, 18).
[Kre21]
William Kretschmer. “Quantum Pseudorandomness and Classical Complexity”. In: 16th Conference on the Theory of Quantum Computation, Communication and Cryptography. 2021 (cit. on p. 9).
[LMW24]
Alex Lombardi, Fermi Ma, and John Wright. “A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024. Ed. by Bojan Mohar, Igor Shinkar, and Ryan O’Donnell. ACM, 2024, pp. 979–990. doi: 10.1145/3618260.3649650. url: https://doi.org/10. 1145/3618260.3649650 (cit. on pp. 2, 3, 15).
[Low10]
Richard A Low. “Pseudo-randomness and learning in quantum computation”. In: arXiv preprint arXiv:1006.5227 (2010) (cit. on p. 8).
[LQS+ 25]
Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. “Parallel Kac’s Walk Generates PRU”. In: CoRR abs/2504.14957 (2025). doi: 10.48550/ARXIV. 2504.14957. arXiv: 2504.14957. url: https://doi.org/10.48550/arXiv.2504. 14957 (cit. on pp. 3, 13, 14, 18).
26
[Mel24]
Antonio Anna Mele. “Introduction to Haar Measure Tools in Quantum Information: A Beginner’s Tutorial”. In: Quantum 8 (May 2024), p. 1340. issn: 2521-327X. doi: 10.22331/q-2024-05-08-1340. url: https://doi.org/10.22331/q-2024-05-081340 (cit. on p. 8).
[MH25]
Fermi Ma and Hsin-Yuan Huang. “How to Construct Random Unitaries”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025. Ed. by Michal Koucký and Nikhil Bansal. ACM, 2025, pp. 806–809. doi: 10.1145/3717823.3718254. url: https://doi.org/10. 1145/3717823.3718254 (cit. on pp. 1, 3, 13, 14, 18).
[MPSY24]
Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. “Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries”. In: 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024. IEEE, 2024, pp. 485–492. doi: 10.1109/FOCS61266.2024.00038. url: https://doi.org/10.1109/FOCS61266.2024.00038 (cit. on pp. 1–3, 5, 8, 13, 14, 18–20).
[OSH21]
Michal Oszmaniec, Adam Sawicki, and Michal Horodecki. “Epsilon-nets, unitary designs, and random quantum circuits”. In: IEEE Transactions on Information Theory 68.2 (2021), pp. 989–1015 (cit. on pp. 2, 3, 7, 11, 12).
[Ros21]
Gregory Rosenthal. “Query and Depth Upper Bounds for Quantum Unitaries via Grover Search”. In: CoRR abs/2111.07992 (2021). arXiv: 2111.07992. url: https: //arxiv.org/abs/2111.07992 (cit. on pp. 4, 15).
[RS09]
Aidan Roy and Andrew J Scott. “Unitary designs and codes”. In: Designs, codes and cryptography 53.1 (2009), pp. 13–31 (cit. on pp. 14, 17).
[SML+ 25]
Thomas Schuster, Fermi Ma, Alex Lombardi, Fernando Brandao, and Hsin-Yuan Huang. “Strong random unitaries and fast scrambling”. In: CoRR abs/2509.26310 (2025). doi: 10 . 48550 / ARXIV . 2509 . 26310. arXiv: 2509 . 26310. url: https : / / doi . org / 10 . 48550/arXiv.2509.26310 (cit. on pp. 3, 13, 14).
[SRS25]
Oskar Slowik, Oliver Reardon-Smith, and Adam Sawicki. “Fundamental solutions of the heat equation on unitary groups establish an improved relation between epsilonnets and approximate unitary t-designs”. In: Journal of Physics A: Mathematical and Theoretical 58.44 (Oct. 2025), p. 445301. issn: 1751-8121. doi: 10.1088/1751-8121/ ae0edc. url: http://dx.doi.org/10.1088/1751-8121/ae0edc (cit. on pp. 2, 3, 11, 12).
27