On the Limits of Stretching Quantum Pseudorandomness

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

On the Limits of Stretching Quantum Pseudorandomness

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

arXiv:2606.24736v1 [quant-ph] 23 Jun 2026

On the Limits of Stretching Quantum Pseudorandomness Boyang Chen1 , Andrea Coladangelo2 , Yao-Ting Lin3 , Nikos Skoumios2 , Justin Tysdal2 , and Yiming Wang2 1

Department of Computer Science and Technology, Tsinghua University Paul G. Allen School of Computer Science & Engineering, University of Washington 3 UC Santa Barbara June 24, 2026

Abstract Pseudorandom states, introduced by Ji, Liu, and Song [JLS18], are quantum analogues of classical pseudorandom generators. A fundamental property of classical pseudorandom generators is that their output can be stretched to arbitrary polynomial length. Whether an analogous stretching property holds for quantum pseudorandom states remains unclear. In this work, we prove the first black-box separation between single-copy secure pseudorandom states (1PRS) with different output lengths. Specifically, we construct a quantum oracle relative to which 1PRS with output length m(n) = 1.1n exist, but 1PRS with output length m(n) = Ω(n2+ε ) do not, for any ε > 0. Our proof leverages the Common Haar Random State (CHRS) model introduced by Chen, Coladangelo, and Sattath [CCS25], and introduces a technique to bound the effective number of resource CHRS states utilized by any 1PRS generator in this model.

Contents 1

Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 The type of oracle in our separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Future directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 5 5

Technical Overview

Preliminaries 3.1 Notations and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Pseudorandom States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Quantum Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Properties of the Haar Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Property Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 13 13 14 15 16

Oracle Separation between m = 1.1n and m = Ω(n2+ε ) 4.1 Existence of a 1PRS with m = 1.1n relative to O . . . . . . . . . . . . . . . . . . . . . . . 4.2 Attack on Any 1PRS with m = Ω(n2+ε ) relative to O . . . . . . . . . . . . . . . . . . . . 4.2.1 Bounding the “Effective” Number of CHRS States Used by Any 1PRS . . . . . . . . 4.2.2 Description and Analysis of the Attack . . . . . . . . . . . . . . . . . . . . . . . .

16 17 18 18 23

Implication on Impossibilities of Black-box Constructions

A Time Complexity of Our Attack 43 A.1 Computing V in Lemma 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 A.2 Implementing the Projective Measurement Πk in Equation (9) . . . . . . . . . . . . . . . . 45

Introduction

One of the foundational challenges in cryptography is to understand the minimal assumptions under which cryptographic primitives can exist. In the classical world, this landscape is relatively well-understood: the existence of One-Way Functions (OWF) is regarded as the “minimal” computational assumption. It implies the existence of pseudorandom generators (PRGs), digital signatures, commitments, and symmetric-key encryption. Conversely, the existence of virtually any cryptographic primitive with computational security implies the existence of OWFs. The quantum setting, however, presents a starkly different picture. We now know of a variety of quantum cryptographic primitives that are sufficient for building secure protocols but are potentially weaker than OWFs. To capture this landscape, Morimae coined the term Microcrypt, extending Impagliazzo’s five worlds to include a world where quantum cryptography exists even if classical OWFs do not. One of the central primitives in Microcrypt are pseudorandom state generators (PRS), first introduced by Ji, Liu, and Song [JLS18]. These can be thought of as the quantum analogue of PRGs. A PRS is a family of efficiently generatable quantum states indexed by a classical key, which are computationally indistinguishable from Haar random states, given polynomially many copies. Following [JLS18], numerous other primitives populating Microcrypt have been introduced, including pseudorandom function-like states (PRFS) [AGQY22], EFI pairs (efficiently samplable statistically far-but-computationally-indistinguishable quantum states) [Yan22, BCQ23], one-way state generators (OWSG) [MY24], and one-way puzzles (OWPuzz) [KT24, CGG24]. Most of these primitives have been shown to be qualitatively weaker than OWFs (in the formal sense of a black-box separation), starting with a result of Kretschmer [Kre21]. In this work, we focus on quantum pseudorandomness. The concept of pseudorandomness is ubiquitous in classical cryptography and complexity theory. Similarly, it is becoming clear that quantum pseudorandomness plays a central role not only in quantum cryptography, but also beyond, thanks to connections with fundamental physics [BFNV19, BCHJ+ 21, KP23, EFL+ 24, Bra23]. Here, we focus more concretely on the notion of single-copy secure pseudorandom states (1PRS), formalized by Morimae and Yamakawa [MY22]. The notion of a 1PRS is analogous to that of PRS, the only difference being that indistinguishability from a Haar random state is only required to hold when the adversary is given a single copy of the a state from the family. It is easy to see that, in order for this notion to be non-trivial, the output length m(n) of states from the family must satisfy m(n) > n, where n is the key size. In other words, a 1PRS must be “stretching”. 1PRS are arguably one of the most fundamental primitives in Microcrypt, as they are “very close” to being minimal: recent work by Cavalar et al. [CCC+ 25] established that a non-uniform version of 1PRS is equivalent to EFI pairs, which are typically regarded as the minimal assumption required for quantum cryptography; and standard (i.e. uniform) 1PRS are implied by all other primitives mentioned above. The Challenge of Stretching Quantum Pseudorandomness. Many basic properties of classical pseudorandomness have been known since the early days and are now taken for granted (e.g., PRGs can be “shrunk” and “stretched”). Quantum pseudorandomness seems to be, in some respects, much more subtle. For example, while shrinking is trivial for a classical PRG (one can just discard bits of a pseudorandom string, and obtain a shorter pseudorandom string), this is not the case for a PRS: discarding one qubit of a pseudorandom state in general yields a mixed state! This barrier was formalized recently: work of Bouaziz–Ermann and Muguruza [BM24], as well as the combination of concurrent work by Chen et al. [CCS25] with work by Barhoush et al. [BBO+ 25], showed that the output of a PRS cannot be shrunk in a black-box way. What about stretching? In the classical setting, any PRG with a non-trivial stretch can be iteratively applied to extend the output to any arbitrary polynomial length. However, this iterative paradigm fails right

away in the quantum setting: the output of a 1PRS is a quantum state, not a classical bit string, so one cannot simply use the output state as a “seed” for the next iteration. Surprisingly, very little is known about whether stretching quantum pseudorandomness is possible in general or not. Here are some of the known results. Gunn et al. [GJMZ23] showed how to stretch the output of a PRS by an arbitrary polynomial, but at the cost of reducing the number of copies available to the adversary. So, to get 1PRS with long stretching, one needs to start with a multi-copy secure PRS, which is a qualitatively stronger object compared to 1PRS [CCS25, AGL24]. Cui et al. [CSBH25] and Levy and Vidick [LV24] introduced techniques to “glue” the generators of phase states together, obtaining stretching constructions for restricted types of PRS, namely (binary or general) phase PRS. However, their techniques rely heavily on the structure of the state families, and do not seem applicable to general unstructured PRS. Zhandry [Zha25] showed that if a 1PRS satisfies certain anti-correlation and junk-free properties, then its output length can be generically extended by one qubit. Schuster, Haferkamp, and Huang [SHH25] showed that, by “gluing” pseudorandom unitaries, one can produce a larger pseudorandom unitary. However, their proof extensively used properties of Haar random unitaries which do not appear applicable to pseudorandom states. Finally, on the negative side, Bouaziz–Ermann et al. [BHMV25] show the impossibility of black-box PRS stretching for constructions with certain structural restrictions, obtaining results incomparable to ours.1 For the general setting without any restrictions, the question has remained elusive, and the only known result is that 1PRS can be stretched in a black-box way by an additive nc , for any c < 1 [CCC+ 25] (i.e. going from a seed of length n to a state of length n + nc ). Thus, it remains a wide open question whether quantum pseudorandomness can be stretched to arbitrary polynomial length, like its classical counterpart. This leads us to the central question that we study in this work: Can 1PRS be stretched to arbitrary polynomial length in a black-box way?

1.1

Our Results

Our main result is a negative answer to the above question. We prove a black-box separation between 1PRS of different output lengths. Concretely, we construct a quantum oracle relative to which short-stretch 1PRS exist, but sufficiently long-stretch 1PRS do not. Theorem 1.1 (Informal). There exists a quantum channel2 oracle O relative to which 1PRS with output length m(n) = 1.1n exist, but 1PRS with output length m(n) = Ω(n2+ε ) do not exist, for any ε > 0. Our separating oracle is inspired by the Common Haar Random State (CHRS) oracle, previously used in other black-box separations [CCS25, AGL24, BCN25, BMM+ 25, GZ25] (e.g. to separate 1PRS from multi-copy PRS). The CHRS oracle provides access to a family of states {|ψi ⟩}i∈N , one for each length, sampled from the respective Haar measures. Here, we make a key modification to this oracle: we augment it so that it gives the ability to run very large quantum circuits on an exponential (in i) number of copies of each of the |ψi ⟩. Along the way, a key step in our proof, which may be of independent interest, is a new technique to bound the effective number of copies of a CHRS state utilized by any generator that always outputs a polynomial-sized pure state (Lemma 4.4). We refer to the Technical Overview (Section 2) for a much more detailed exposition. As a corollary, our oracle separation implies that one cannot stretch the output length of a 1PRS in a black-box way (when the construction is given coherent isometry access to the shorter 1PRS generator). 1

Specifically, they consider stretching for standard (multi-copy) PRS, starting from a shorter-output (multi-copy) PRS—a (potentially) strictly stronger primitive than an 1PRS of the same length. 2 We expand on the significance of such an oracle separation in Section 1.2.

Theorem 1.2 (Informal). There is no fully black-box construction of a 1PRS with output length m(n) = Ω(n2+ε ) from a 1PRS with output length m(n) = 1.1n, even when the construction is granted coherent (isometry) access to the shorter generator. Note that this rules out constructions that have isometry access to the shorter generator (meaning they have access to the generation procedure, but are not allowed to modify the state of the auxiliary registers, which must be set to zeros). This means that any construction that stretches the length of a 1PRS must either be non-black-box, or, if it is black-box, then it must query the shorter 1PRS generator with some non-zero ancilla qubits, or query the inverse of the generator. Our result does not rule out black-box constructions of the latter kind. We expand on this next.

1.2

The type of oracle in our separation

Our separation is relative to a quantum channel oracle. That is, the generation procedure as well as the adversary have access to a certain quantum channel. This kind of separation is less desirable than a unitary oracle separation for a few reasons outlined below (although we very much maintain that it is still a meaningful separation): • It only rules out black-box constructions where the security reduction has the following form: there is an adversary for the shorter 1PRS that has channel access to the adversary for the longer 1PRS (meaning a query to the latter adversary takes as input a challenge state for the 1PRS distinguishing task, and returns only the output bit, but not any work registers). We do not find this to be a significant restriction (compared to a security reduction that has unitary access to the adversary) since almost all known security reductions between adversaries for distinguishing games only utilize the decision bit of the first adversary on some suitably chosen distinguishing task (or a set of such tasks). • Our separation does not rule out constructions where the generation procedure of the longer 1PRS has unitary access (or inverse unitary access) to the generation procedure of the shorter one. Instead, as mentioned earlier, it only rules out constructions where the generation of the longer 1PRS has isometry access to the generation of the shorter one.3 While one could certainly imagine generation procedures that leverage unitary and inverse unitary access, our separation, for example, rules out a large class of natural constructions that behave as follows: generate a short 1PRS state |ϕk ⟩, or many copies of such a 1PRS (or a superposition over such states), and by acting on them (and some auxiliary registers) generate a 1PRS state with longer output. We refer the reader to Section 5 for a formal description of the connection between our oracle separation result and the corresponding impossibility of a black-box construction. The expert reader may wonder why one cannot apply techniques from, e.g. Goldin–Zhandry [GZ25] to lift our separating oracle to be a unitary (and its inverse). In short, we do not currently see how to apply these techniques in our setting, and we discuss this in more detail at the end of the technical overview (Section 2).

1.3

Future directions

Our work leaves open several directions for future research. Here are some of the most natural and compelling ones. 3

The reason why we rule out constructions that have isometry access, not just channel access, is that the 1PRS are, by definition, required to output pure states. We refer the reader to Section 5 for more details.

• Our result only rules out black-box constructions with isometry access to the shorter 1PRS. This is because our separating oracle is a quantum channel. Can one show a separation relative to a unitary oracle (with access to inverse, conjugate or transpose queries)? This would rule out a broader class of black-box constructions that have access to inverse, conjugate, or transpose queries. • Our result rules out black-box constructions that stretch 1PRS with output length 1.1n to Ω(n2+ε ) for any ε > 0. Is it possible to rule out black-box stretching by a linear amount? As pointed out earlier, it is already known, on the positive side, that 1PRS can be stretched in a black-box way by an additive nc , for any c < 1 [CCC+ 25] (i.e. going from a seed of length n to a state of length n + nc ). So, the question is whether one can extend this to c = 1, or whether there is a black-box impossibility.

Technical Overview

This section is organized as follows. We start by recalling the common Haar random state (CHRS) oracle model, the construction of a 1PRS in this model, and the impossibility of constructing PRS relative to the same oracle. We will then build (and significantly expand) on this idea to define an oracle relative to which 1PRS with a certain stretch exist, but 1PRS with much longer stretch do not. We will achieve this step by step, introducing several new ideas along the way. Common Haar Random State model (CHRS) The Common Haar Random State (CHRS) model can be viewed as a quantum state generalization of the Common Reference String (CRS) model introduced by [Can01]. In the CHRS model, introduced in [CCS25], we assume a trusted third party, who prepares a family of states S = {|ψm ⟩}m∈N , where |ψm ⟩ is sampled according to the Haar measure on m qubits µm . The states in the set S are called CHRS states. All parties in a protocol (including the adversary) have access to polynomially many (in the security parameter λ) copies of states from S. Formally, parties have access to m the family of isometries {Vm }m∈N , where Vm : C → C2 4 is such that Vm : |0⟩ 7→ |ψm ⟩ . Equivalently, for any state |α⟩ of any dimension, one query to Vm performs the map: |α⟩ 7→ |α⟩ |ψm ⟩ . We clarify that, in this model, parties cannot query the different isometries “in superposition”. Rather, they can query each Vm individually (provided they have enough space to store the m-qubit output state |ψm ⟩). The model is meant to capture the scenario where parties can request copies of |ψm ⟩, for any m of their choice, from the trusted third party, as long as they have enough space to store the requested state. Quantum pseudorandomness from common Haar random states. Recall that, informally, a 1PRS of input length n and output length m is a QPT algorithm that outputs |ϕk ⟩5 for each k ∈ {0, 1}n , such that E |ϕk ⟩⟨ϕk | ≈c k

1 2m

Notice that the domain is one-dimensional. Notice that in the definition of single-copy secure pseudorandom states we ask for the output of the generation algorithm to be pure in order to rule out the trivial construction of always outputting 1/2m . 5

where ≈c denotes computational indistinguishability. Chen, Coladangelo, and Sattath [CCS25] show that a 1PRS exists relative to the CHRS model, i.e. for some m(n) > n, there exists a family {Uk }k∈{0,1}n , such that |ϕk ⟩ = Uk |ψm ⟩ is a 1PRS. Concretely, the security guarantee is the following: 2 √ 1 (t + t m)5m−n † ⊗(t−1) ⊗(t−1) E E Uk |ψm ⟩⟨ψm | Uk ⊗ |ψm ⟩⟨ψm | − m ⊗ |ψm ⟩⟨ψm | =O . 2 |ψm ⟩ k 2n/2 1 This was improved by Ananth, Gulati, and Lin [AGL24], who show that the surprisingly simple family given N by Uk = Z k ⊗ 1, for k ∈ {0, 1}n , where Z k = ni=1 Z ki , already yields: 2 t 1 † ⊗(t−1) ⊗(t−1) =O . E E Uk |ψm ⟩⟨ψm | Uk ⊗ |ψm ⟩⟨ψm | − m ⊗ |ψm ⟩⟨ψm | 2 2n |ψm ⟩ k 1 Note that the 1PRS construction is simply |ϕk ⟩ = Uk |ψm ⟩ (i.e. it only uses one copy of the CHRS state) and the additional t copies of the CHRS state |ψm ⟩ should be thought of as given to the adversary. Note also that the guarantee above is statistical, rather than computational: security holds against any unbounded adversary, provided it only receives at most t = poly(n) copies of the CHRS state |ψm ⟩. Non-existence of multi-copy PRS in the CHRS model. Chen, Coladangelo, and Sattah [CCS25] also show that, while 1PRS exist in the CHRS model, (multi-copy) PRS do not. We review their attack here, which will be the starting point for our new oracle separation. Suppose there is a family of quantum algorithms {Genk }, such that {Genk |ψm ⟩} is a PRS family6 . To determine whether a challenge state |ϕ⟩ is Haar random or equal to Genk |ψm ⟩ for some k, the first idea that comes to mind, if one knew k, is to perform a SWAP test between |ϕ⟩ and Genk |ψm ⟩. If |ϕ⟩ = Genk |ψm ⟩, this passes the SWAP test with probability 1. Otherwise, a Haar random |ϕ⟩ passes the SWAP test with probability roughly 12 . This gap can be amplified since the adversary is allowed to obtain multiple copies of |ϕ⟩ (since we are considering a multi-copy PRS). By performing, say, 10n SWAP tests, the probability of passing all of them in the Haar random case is suppressed to o(2−n ). Crucially, of course, the adversary does not know k. However, one can still attack the PRS by leveraging the quantum OR lemma (Lemma 3.8), which says that there exists an algorithm (which we refer to as the OR tester) that, given a series of tests (that is, projections) {Πk }N k=1 and a state |ϕ⟩, distinguishes between the following two cases. • (“YES" case) There exists k such that |ϕ⟩ passes the test Πk with probability Ω(1); in this case the OR tester will accept with probability Ω(1). • (“NO" case) For every k, |ϕ⟩ passes the test Πk with probability o(1/N ); in this case the OR tester will accept with probability o(1). The adversary runs the OR tester with Πk corresponding to the test that creates 10n copies of Genk |ψm ⟩, and performs 10n SWAP tests with 10n copies of |ϕ⟩. In our case, N = 2n , and so 10n SWAP tests are enough to suppress the acceptance probability in the NO case to o(2−n ) for each k. 6

Technically, in full generality, Genk could act on multiple copies of |ψm ⟩, and even on common Haar states of different sizes, but, for simplicity, we focus on PRS of the form {Genk |ψm ⟩} in this technical overview, as the general case is similar.

Separating 1PRS with different stretch: the first attempt. Now, we turn our attention to separating 1PRS with different stretch. The first roadblock is that we can no longer run an OR tester as above, since the latter required 10n copies of the challenge state |ϕ⟩: a multi-copy PRS adversary can obtain that many copies, but a 1PRS adversary can only obtain one. Recall that the 10n copies were required because of an inherent limitation of the SWAP test, which accepts orthogonal pairs of states with probability 12 . Our goal is to modify the oracle in such a way that it still allows us to construct a secure 1PRS of small stretch (say 1.1n output length), but gives us enough power to break a longer stretch 1PRS. The question we need to address then is: what concrete difference between short stretch and long stretch 1PRS can we leverage? Our first key observation is the following. Recall that in the 1PRS construction from Ananth, Gulati, and Lin [AGL24], the (statistical) distinguishing advantage is O(t2 /2n ), where t is the number of copies of the common Haar state |ψm ⟩, and n is the key-length. Crucially, the security is a function of the key length n, and not of the output length m! Thus, regardless of the stretch, the [AGL24] 1PRS is secure as long as an (unbounded) adversary has o(2n/2 ) copies of the common Haar state. This suggests the following idea: consider an adversary with “access” to, say, 2m/3 copies of the common Haar state of length m. This number of copies is not enough to break an [AGL24] 1PRS with stretch m(n) = 1.1n, since 2m/3 = 21.1n/3 = o(2n/2 ). However, a 1PRS with stretch, say, m(n) = 10n is no longer guaranteed to be secure, since 2m/3 ≫ 2n/2 ! Now, is there actually an attack on any 1PRS with stretch m(n) = 10n in this model? Yes, one can build an attack based on a generalized version of the SWAP test, namely a “Permutation” test [KNY08], which checks overlap with the symmetric subspace on more than two registers. The Permutation test satisfies the following, for any pair of states |ϕ⟩ and |ξ⟩ of the same length i: 1 r−1 (i,r) Tr Πsym · |ϕ⟩⟨ϕ| ⊗ |ξ⟩⟨ξ|⊗(r−1) = + | ⟨ϕ|ξ⟩ |2 , r r

(1)

(i,r)

So, the OR tester is able to break the proposed 1PRS candidate. This discussion suggests that, if we wish to separate 1PRS with different stretch, we should “augment” the CHRS oracle so that it does not only provide one copy of a common Haar state |ψm ⟩ per query, but it additionally gives the ability to run an OR tester algorithm that uses exponentially many copies7 of the length-m state |ψm ⟩ for each m. Where the first attempt fails. So, let us imagine augmenting the oracle so that it provides access to exponentially many copies of the CHRS state (more precisely, imagine that the oracle allows one to prescribe a quantum circuit to run on that many copies, and obtain a short output). Does this work? Issue 1. The main outstanding issue that we have not considered is the following: whenever we give more power to the adversary, by considering a stronger oracle, a 1PRS generator also gains the same additional power. As a result, if the adversary is allowed to use 2m/3 copies of |ψm ⟩ thanks to the new oracle, the generator can also use the same number of copies. So, for instance, a candidate 1PRS may now be of the m/3 form |ϕk ⟩ = Genk |ψm ⟩⊗2 (where Genk is some CPTP map). Then, we run into a problem: previously, the OR tester relied on generating 2m/3 copies of |ϕk ⟩ to use in a Permutation test, with each copy costing only one copy of |ψm ⟩. Now, each copy of |ϕk ⟩ itself requires 2m/3 copies of |ψm ⟩ to generate, for a total of 2m/3 · 2m/3 copies of |ψm ⟩ needed by the adversary. However, we had started by stipulating that the oracle only provides 2m/3 copies of |ψm ⟩. If we try to strengthen the oracle so that it gives 2m/3 · 2m/3 copies, then the generator Genk can also use that many, and so on: it is an endless arms race! Issue 2. There is a second issue that we have not considered, namely that the 1PRS generator is not limited to using |ψm ⟩, but it can also use common Haar random states of other lengths. In particular, suppose the generator only uses a single copy of a “short” CHRS state, e.g. |ψ6 ⟩ (of 6 qubits), but nonetheless outputs a state of length m. The issue is that the oracle we considered gives access to a number of copies of each common Haar state that depends on its dimension, namely 2ℓ/3 copies of the state |ψℓ ⟩. This means that an adversary now only has access to 26/3 = 4 copies of the state |ψ6 ⟩. Thus, any Permutation test can at most involve 4 copies of |ϕk ⟩, rather than 2m/3 , and the acceptance probability on any state will be at least 15 . Resolving Issue 1: Bounding the “effective” number of CHRS states used by the generator. The key insight is that, while Genk may use an overall number of copies of CHRS states that is exponential in n, it is still required to output an m(n)-qubit state. So, whatever circuit it is running on the exponentially many copies (thanks to the help of the oracle) must output a pure state |ϕk ⟩ on the first m qubits (i.e. on a polynomial number of qubits). This is a very strong constraint. In fact, what we show (in Corollary 4.6) is that, with probability one over the choice of the CHRS state family {|ψi ⟩}i∈N , any Genk that outputs a pure g k that only uses polynomially many state on the first m qubits, must have an equivalent implementation Gen ⊗2m/3 copies of the CHRS states. So, for instance, if |ϕk ⟩ = Genk |ψm ⟩ (where Genk is some CPTP map g k such that whose output is just m qubits), then it is also the case that there is some other CPTP map Gen ⊗t(m) g k |ψm ⟩ |ϕk ⟩ = Gen for some polynomial t. An analogous statmement holds if Genk acts on states of different sizes. The intuition for this phenomenon is that any algorithm that acts non-trivially on too many copies of the CHRS states must either generate entanglement between the first m qubits and the rest, or the output state on the first m qubits only depends on a small poly(m) number of copies. 7

Here, “exponentially many" means an exponential in the number of qubits m, not in the security parameter.

Lemma 2.1 (Informal version of Corollary 4.6). There exists a fixed polynomial p such N that the following holds. Let s ∈ N. Let G be a quantum channel that takes as input a state of the form si=1 |ψi ⟩⊗r(i) , where r is a function that we only assume to be bounded by some exponential. Suppose G outputs a pure state on m qubits for all families {|ψi ⟩}i∈[s] . Then, there is a unitary UG acting on p(m) copies of states in the family, plus ancillas, that outputs the same pure state as G. Now, thanks to Lemma 2.1, we can consider an equivalent generation procedure that only uses poly(m) copies of |ψm ⟩. Thus, we can afford to generate, say, r = 2m/4 copies of |ϕk ⟩, which are sufficient to run the Permutation test with sufficiently good soundness (when m = 10n), by using “only” 2m/4 · poly(m) < 2m/3 copies of |ψm ⟩. So, our new candidate oracle, for now, allows one to prescribe a quantum channel to run on 2m/3 copies of the CHRS state |ψm ⟩, for all m (eventually, we will put a computational bound on the kinds of quantum channels that can be prescribed, but this is not important to understand the main ideas). Resolving Issue 2. The remaining issue to resolve is that the generator may use CHRS states of different lengths. In particular, it may use some short states (for which our oracle does not provide enough copies to run a sound enough Permutation test!). We start by changing our viewpoint. Lemma 2.1 tells us that we can think of the 1PRS state |ϕk ⟩ on m qubits as the state generated by applying a unitary Uk to a small number of copies of CHRS states |ψi ⟩. The fact that Uk is a unitary is very important. Now, suppose we apply Uk† on a challenge state. Then: • if the challenge state is generated by Uk acting on some CHRS states |ψi ⟩, we get the original CHRS states back; • if the challenge state is Haar random, then we get fresh Haar random states |ψi′ ⟩ on the registers corresponding to each CHRS original state |ψi ⟩.8 We will thus change our viewpoint and consider an attacker that runs an OR tester, where each test Πk corresponds to the following: first apply Uk† on the challenge state, and then run a Permutation test on many copies of the CHRS state |ψi ⟩ and the register that would correspond to |ψi ⟩ after applying Uk† . Now, recall the success probability of the Permutation test: if, in Equation (1), we take |ϕ⟩ to be Haar random and |ξ⟩ to be the fixed CHRS state |ψi ⟩, the success probability is upper-bounded by 1r + 21i , where r is the number of copies in the test, and i is the length of each state. In order for an OR test to be sound, the success probability of the Permutation test must be bounded by o(2−n ) when the challenge state is Haar random. If our oracle gives the attacker access to r = 2i/3 copies of the CHRS state |ψi ⟩, this kind of Permutation test will be sound as long as i ≥ (3 + δ)n for some δ > 0. What if i ≤ 3n? In this paragraph, we discuss how to deal with the case where Uk acts exclusively on CHRS states |ψi ⟩ with i ≤ 3n. We split this analysis into two cases: • The first case is that Uk uses a relatively large number of copies of a particular |ψi ⟩. In this case, we can actually use the original SWAP test, as in [CCS25]: if i ≥ log n, then with probability 1 − negl(n) over the sampling of a Haar random state |ψi′ ⟩, a two-register SWAP test between |ψi ⟩ and |ψi′ ⟩ passes with probability at most 9/10. More precisely, if Uk uses, say, 8n copies of some state |ψi ⟩, then after applying Uk† on |ϕ⟩ = |ψk ⟩, we expect to end up with 8n copies of |ψi ⟩, whereas if |ϕ⟩ is Haar 8 The latter is by the unitary invariance of the Haar measure: we can think of a Haar random state as the output of the unitary Uk acting on a Haar random input state.

random, we expect to end up with 8n copies of a fresh Haar random state |ψi′ ⟩. Thus, we can perform 8n SWAP tests between the unknown copies and the 8n copies of |ψi ⟩ (obtained via the oracle). The probability of passing all 8n SWAP tests in the Haar random case is (9/10)8n , which is o(2−n ). This means that, as long as Uk uses a linear number of copies of at least logarithmic-length states, the OR test is still sound. So, we have established that if |ϕk ⟩ is generated either using a CHRS state |ψi ⟩ with i ≥ 3n or using a linear number of copies of |ψi ⟩ with i ≥ log n, then we can find a corresponding projection that can distinguish |ϕk ⟩ from Haar random with advantage at least 1 − o(2−n ). This means that we can combine all of the projection tests for different k’s in an OR tester that breaks the 1PRS. We refer to this first case as Case A, as plotted in Fig. 1. • The second case is that Uk only uses CHRS states of length smaller than 3n, and it uses only a small number of copies of states |ψi ⟩ with i ≥ log n. We refer to this as Case B as plotted in Fig. 1. The key observation is that, in Case B, the degrees of freedom coming from the CHRS states are actually not enough, and there exists a projective measurement, independent of the CHRS states, that distinguishes the output of the 1PRS candidate from maximally mixed with high probability. This can be seen by a counting argument. The dimension of the subspace of ℓ copies of an i-qubit i i state is 2 2+ℓ−1 ≤ min{2iℓ , ℓ2 }. Then we can show that this is not enough: when ℓ = Θ(n) and i −1 2 i = Θ(n), the dimension of the symmetric subspace is 2O(ℓi) = 2O(n ) . In case that ℓ = poly(n) i and i ≤ log n, the dimension of the symmetric subspace is at most ℓ2 ≤ 2O(n log n) . As a result, we can conclude that when both the number of copies and the number of qubits are not large enough, the 2 symmetric subspace is of dimension 2O(n ) . Since, in Case B, the 1PRS generator only uses states of length up to O(n), the rank of the mixed state produced by the 1PRS generator (when average over 2

the key) has rank at most 2O(n ) = 2O(n ) . Now, as long as we take m(n) = Ω(n3+ε ), the output of the 1PRS can be distinguished from Haar random even without knowledge of the CHRS states. In fact, a more refined analysis of the above setting (which we carry out in Section 4.2.2) shows that the same attack works for any 1PRS with m(n) = Ω(n2+ε ). One small remaining subtlety is that whether Uk falls in Case A or Case B may vary across k’s, so some care needs to be taken in choosing the right distinguishing test that works on average over the k’s.

ℓ(i)

Case A many copies

Case B Θ(n)

Case A large i

Case B

log n

Θ(n)

Figure 1: A visualization of the four possible cases based on the lengths i and the copies ℓ(i) of the effective CHRS states used by the generation procedure. In Case A (black and blue areas) the adversary can achieve a noticeable advantage by using either Permutation tests or pairwise SWAP tests via the OR Lemma. In Case B, the degrees of freedom coming from the CHRS states are significantly less than those of an m-qubit state, and thus there is a successful distinguishing measurement that is independent of the CHRS states. Why the Goldin–Zhandry lifting technique does not directly apply. A natural question is whether one can use the Goldin–Zhandry technique [GZ25] to upgrade our separating oracle from a quantum channel oracle to a fully unitary oracle. The main obstruction is that our oracle has two components, which play very different roles. The first component is the CHRS isometry oracle, while the second component is a quantum channel that is used to implement the attack on large-stretch 1PRS candidate constructions. Crucially, the second component is allowed to use exponentially many copies of the CHRS states in its internal computation. The technique of [GZ25] does not seem to apply to such an oracle, at least without additional new ideas. In particular, since the adversary itself is required to be QPT, we outsource the exponential-size attack to the second component. If the second component were instead defined to be a unitary oracle, then it would have to coherently maintain and return its internal workspace, including registers containing exponentially many CHRS copies (or their variants). This would require the adversary to store and manipulate exponentially many qubits, which is is not something a QPT adversary can afford to do. Even if one is content with replacing first oracle component by a unitary oracle while keeping the second as a channel, the Goldin–Zhandry technique still does not immediately go through. The difficulty is that one of our key technical ingredients, stated informally as Lemma 2.1 above, and more formally as Lemma 4.4 (and Corollary 4.6) crucially relies on the fact that one can represent the adversary’s attack as a fixed unitary acting on copies of CHRS states. This representation is no longer available in the same form when the first component is replaced by a unitary oracle: the Goldin–Zhandry technique [GZ25] introduces an inverse-polynomial error, and our proof relies on the 1PRS being perfectly pure. Therefore, obtaining a fully unitary-oracle separation appears to require ideas beyond a direct application of the Goldin–Zhandry technique. 12

Preliminaries

3.1

Notations and Definitions

We will use the letter n to denote the security parameter. We will use the letter ε to denote an arbitrary positive small constant. We denote by µd the Haar measure in a 2d -dimensional Hilbert space. The notation |ψ⟩ ∼ µd denotes sampling a state according to µd . For any finite set K, we write k ← K to mean that k is sampled uniformly at random from K. For an operator H, we use the notation ∥H∥1 to denote its trace norm and ∥H∥op to denote its operator norm. We also use ∥u − v∥2 to denote the Euclidean distance between two vectors u, v. Let L ∈ N, then a function f : Cn → R is an L-Lipschitz function with the respect to the Euclidean distance, if |f (|ψ⟩) − f (|ϕ⟩)| ≤ L∥ |ψ⟩ − |ϕ⟩ ∥2 , for all states |ψ⟩ , |ϕ⟩ ∈ Cn . We use the notation A(·) to refer to an algorithm (classical or quantum) that makes queries to an oracle. For a Hilbert space H, (n,k) we denote the k-th symmetric tensor space of H by Symk H. We will use Πsym to refer to the projection n ⊗k from the k-th tensor product space (C ) onto the k-th symmetric tensor subspace Symk Cn . We will make use of the SWAP test (as defined, e.g. in [BCWdW01]) and its generalization, i.e. the Permutation test, a description of which can be found in [KNY08].

3.2

Pseudorandom States

Definition 3.1 (Pseudorandom States (PRS), adapted from [JLS18]). A pseudorandom state generator with output length m(·) is a QPT algorithm Gen that, on input (1n , k) with k ∈ {0, 1}n , outputs a pure state |ϕk ⟩ consisting of m(n) qubits, such that, for any polynomial t = t(n) and any QPT adversary A, there exists a negligible function negl such that for all n, Pr

k∈{0,1}n

i A(|ϕk ⟩⊗t(n) ) = 1 −

|ϕ⟩∼µm

i A(|ϕ⟩⊗t(n) ) = 1 = negl(n),

(2)

where µm is the Haar measure on m = m(n) qubits. Definition 3.2 (Single-copy Pseudorandom States (1PRS), adapted from [MY22]). A single-copy pseudorandom state generator (1PRS) with output length m(·) is a PRS (as in Definition 3.1) with m(n) > n, for every n ∈ N, except that the security definition in Equation 2 only holds for t = 1. Notice that the stretch requirement in the definition of 1PRS, i.e. m(n) > n for every n, is essential to rule out trivial constructions. For instance, one can easily verify that by simply setting |ϕk ⟩ = |k⟩, the uniform mixture of the states {|ϕk ⟩}k∈{0,1}m is computationally indistinguishable from the maximally mixed state on n qubits. Similarly, as discussed in Section 2, the requirement that the output state of a 1PRS is always pure is necessary to invalidate the algorithm that trivially outputs the maximally mixed state. Our separation in Section 4 will heavily- rely on this restricting property.

3.3

Quantum Information

In our proof, we will have to use sufficiently precise implementations of arbitrary unitary operators. In particular, we will use the well-known Solovay-Kitaev algorithm. Theorem 3.1 (Solovay-Kitaev). Any unitary that operates on an n-qubit system can be approximated, with accuracy ε with respect to the operator norm, by a circuit consisting of O(22n log4 (22n /ε)) gates selected from an universal gate set. 13

The following lemma shows that the precision of the implementation from Theorem 3.1 is an upper bound in the resulting difference in the measurement statistics. Lemma 3.2. Let U, V be two unitaries acting on n qubits. Then for any projection P acting on n qubits n and any n-qubit state |ψ⟩ ∈ C2 : Tr(U † P U |ψ⟩⟨ψ|) − Tr(V † P V |ψ⟩⟨ψ|) ≤ ∥U − V ∥op Proof. We have that 1 U |ψ⟩⟨ψ| U † − V |ψ⟩⟨ψ| V † 2 ≤ ∥U |ψ⟩ − V |ψ⟩ ∥2

Tr(U † P U |ψ⟩⟨ψ|) − Tr(V † P V |ψ⟩⟨ψ|) ≤

≤ ∥U − V ∥op . where the first inequality follows from the variational characterization of the trace distance, and the second inequality follows from the fact that the trace distance between pure states is bounded by their Euclidean distance. For completeness, we also provide proofs for some basic properties of density matrices. Lemma 3.3. The partial trace and purity are both polynomials in the coefficient of the inputs. Proof. Let ρ = (ρi,j )i,j∈[2d ] be a density matrix on d qubits, then for any l < d the result of tracing out the last l qubits is a density matrix l

2 X ρ = (1 ⊗ ⟨κ|)ρ(1 ⊗ |κ⟩) = (ρ′i,j )i,j∈[2d−l ] ′

κ=1

where ρ′i,j =

P2l

κ=1 ρ(i−1)2l +κ,(j−1)2l +κ , for every i, j ∈ [2 d

Tr(ρ ) =

d−l ]. Moreover, the purity of ρ is

2 X 2 X

ρi,j ρj,i

i=1 j=1

So, all entries of the partial trace of ρ and the purity of ρ are polynomials of the entries of ρ.

3.4

Probability

Our proof relies heavily on the following lemma from probability theory. Lemma 3.4 (Borel-Cantelli). Suppose {En }n∈N is a series of events in a probability space Ω. If X Pr(En ) < ∞ n∈N

then the probability that infinitely many of the events occur is 0. Proof. See, for example, [Dur19, Theorem 2.3.1]. 14

3.5

Properties of the Haar Measure

We will use the known fact that the probability that a Haar random state |ϕ⟩ has a noticeable overlap with any fixed state |ψ⟩ is negligible in the size of the states. Lemma 3.5 ([Kre21], Lemma 26). Let n ∈ N. Let µn be the Haar measure on n-qubit states. Then, for any n-qubit state |ψ⟩, n Pr | ⟨ϕ|ψ⟩ |2 ≥ ε < e−ε(2 −1) |ϕ⟩∼µn

We will also need the strong concentration of the Haar measure, as stated in [Led01]. Lemma 3.6 (Lévy’s lemma [Led01]). Let d ∈ N and f : Cd → R be an L-Lipschitz function with respect to the Euclidean distance in Cd . Then for every ε > 0, it holds that 2dε2 Pr f (|ϕ⟩) − E f (|ψ⟩) ≥ ε ≤ 4 exp − 3 2 9π L |ϕ⟩∼µd |ψ⟩∼µd In order to use Lemma 3.6, we prove that the accepting probability of any decision quantum algorithm that takes as input T copies of a quantum state is T -Lipschitz. Lemma 3.7. Let A be a quantum algorithm that takes as input T copies of a quantum state |ψ⟩ in Cd . Then, the function f : Cd → R defined by f (|ψ⟩) = Pr[A(|ψ⟩⊗T ) = 1] is T -Lipschitz with respect to the Euclidean distance in Cd . Proof. Let |ψ⟩ , |ϕ⟩ be two pure states in Cd . Define ρ = |ψ⟩⟨ψ| , σ = |ϕ⟩⟨ϕ|. The maximal probability of distinguishing ρ and σ is bounded by the trace distance. We have |f (|ψ⟩) − f (|ϕ⟩)| ≤ Next, we prove ρ⊗T − σ ⊗T ⊗T

1 ⊗T ρ − σ ⊗T . 2

(3)

≤ T ∥ρ − σ∥1 . This is because

−σ

⊗T

T −1 X

ρ⊗k ⊗ (ρ − σ) ⊗ σ ⊗T −k−1 .

k=0

Taking trace norm on both sides, and using the triangle inequality: ⊗T

−σ

⊗T 1

≤

T −1 X

ρ⊗k ⊗ (ρ − σ) ⊗ σ ⊗T −k−1 1 .

k=0

The trace norm is multiplicative under tensor products, so ρ⊗T − σ ⊗T

≤ T · ∥ρ − σ∥1 .

Therefore, f is T -Lipschitz under the trace distance of pure states. Note that for pure states, the trace distance is bounded by the Euclidean distance. Hence, (3) yields 1 |f (|ψ⟩ − f (|ϕ⟩)| ≤ T · ∥ρ − σ∥1 ≤ T ∥ |ψ⟩ − |ϕ⟩ ∥2 , 2 and f is T -Lipschitz with respect to the Euclidean distance of Cd . 15

3.6

Property Tests

As discussed in 2, our separation will rely on a variant of the quantum OR Lemma. Informally, the following theorem guarantees that there exists a quantum algorithm that given a set of projections and a single copy of some quantum state |ϕ⟩, decides whether |ϕ⟩ has significant overlap with one of the projections, or if it has small overlap with all the projections. Theorem 3.8. Given a set of operators {0 ⪯ Pi ⪯ 1}N i=1 , and a state |ϕ⟩, define pi = Tr(Pi |ϕ⟩⟨ϕ|). Define p↓ = max pi , p↑ = 1≤i≤N

N X

pi .

i=1

Then there exists an algorithm A such that p2↓ 7

≤ Pr[A(|ϕ⟩) = 1] ≤ 2p↑ .

Furthermore, if each two-outcome measurement {Pi , 1 − Pi } can be implemented in time T with S ancilla qubits, then the algorithm A can be implemented in time O(N T ) with at most poly(N, S) ancilla qubits. Proof. The algorithm runs as follows: it repeats N times, each time it chooses a random measurement Pi and performs the measurement on the current state. If any of the measurements accepts, it outputs 1. If none of the measurements accepts, it outputs 0. The proof of the bound on the probability of accepting can be found in [WB24, Theorem 29]. In Section 4, we will use the OR Lemma with projections that correspond to Permutation tests, as described in [KNY08]. The following lemma shows the exact probability that a state of the form |ϕ⟩ |ψ⟩⊗r−1 passes the Permutation test across r registers. Lemma 3.9. Let |ϕ⟩ , |ψ⟩ be two n-qubit states, then for every r ∈ N: 1 r−1 ⊗(r−1) Tr Π(n,r) = + | ⟨ϕ|ψ⟩ |2 sym |ϕ⟩⟨ϕ| ⊗ |ψ⟩⟨ψ| r r (n,r)

Proof. The projection Πsym is equivalent to the Permutation test described in [KNY08]. Notice that, as discussed in Section 2, the probability in Lemma 3.9 scales inverse-linearly with the number of registers r.

Oracle Separation between m = 1.1n and m = Ω(n2+ε )

We will describe an oracle O relative to which 1PRS with output length m(n) = 1.1n exist, but 1PRS with output length m(n) = Ω(n2+ε ) do not. Let {|ψi ⟩}i∈N be a family of quantum states, where |ψi ⟩ is an i-qubit state. We will call {|ψi ⟩}i∈N the CHRS states. We now define an oracle O with respect to this family of quantum states. For clarity, we think of O as a pair of oracles O = (O1 , O2 ). Eventually, we will show that, with probability 1 over sampling each state in the family from the Haar measure, O separates 1PRS with output length m(n) = 1.1n from 1PRS with output length m(n) = Ω(n2+ε ). Since the possible oracles O are in one-to-one correspondence with the family of states {|ψi ⟩}i∈N , we endow the set of all possible oracles with the Haar measure of quantum states. Therefore, whenever we say “the probability over O", we refer to the Haar measure over the family of states {|ψi ⟩}i∈N . 16

Separating Oracle.

We define the oracle O = (O1 = {O1,i }i∈N , O2 ) as follows:

• O1 is a family of isometries O1,i , where each O1,i , on input |0⟩, outputs the state |ψi ⟩. Note that this is the standard CHRS oracle from [CCS25] (discussed in Section 2), where the input to O1,i is 1-dimensional. • O2 takes as input – A number T expressed in unary as 1T . – A quantum state |ϕ⟩ (this is also allowed to be a mixed state). – The description of a Turing machine M , which outputs a quantum circuit C such that, syntactically, C operates on ! T O T ⊗22i/5 |ϕ⟩ ⊗ |ψi ⟩ ⊗ |0⟩⊗2 i=1

and outputs a bit. T

O2 runs M for at most 22 steps to obtain the quantum circuit C; it then runs ! ! T O 2i/5 T C |ϕ⟩ ⊗ |ψi ⟩⊗2 ⊗ |0⟩⊗2 → b, i=1

and outputs b. Remark 4.1. Note that for any quantum circuit Q making queries to O that outputs a k-qubit state, there is another circuit Q̄, acting on at most |Q| · 22i/5 copies of |ψi ⟩ for every i ≤ |Q| and at most |Q| · 2|Q| many ancillas, such that the (mixed) state of the first k qubits of the output of Q̄ is identical to that of Q.

4.1

Existence of a 1PRS with m = 1.1n relative to O

We start by showing that 1PRS with m = 1.1n exist relative to O. Our construction will naturally generalize the following construction of 1PRS in the CHRS model. Theorem 4.2 ([AGL24], Lemma 4.6). For any function m(·) such that m(n) > n for all n, the following is a 1PRS in the CHRS model (secure in the sense of Equation (4)): for k ∈ {0, 1}n , the generation procedure Genk uses a single copy of the CHRS state |ψm ⟩ of length m, and outputs the state |ϕk ⟩ = Genk (|ψm ⟩) = (Z k ⊗ 12m−n ) |ψm ⟩ , where Z k = ⊗ni=1 Z ki . Then, the following holds for all t ∈ N: E

k←{0,1}n |ψm ⟩∼µm

⊗t−1

|ϕk ⟩⟨ϕk | ⊗ |ψm ⟩⟨ψm |

−

|ψm ⟩∼µm 2m

⊗ |ψm ⟩⟨ψm |

⊗t−1

2 t =O . 2n 1

(4)

Note that Theorem 4.2 ensures the statistical security of a 1PRS in the CHRS model, as long as the number of CHRS states that the adversary can use is bounded. This leads to the following theorem. Theorem 4.3. With probability 1 over the choice of O, there exists a 1PRS with m = 1.1n relative to O. 17

Proof. We prove that the generation procedure Genk described in Theorem 4.2 is secure relative to O, with probability 1 over the choice of O. Notice that by Remark 4.1, any QPT adversary AO can be simulated by a circuit using at most poly(n)22m/5 < 20.45m = 20.495n copies of |ψm ⟩. Define T to be the number of copies of |ψm ⟩ required to simulate AO . Let adv(AO ) = Pr [AO (|ϕk ⟩) = 1] − Pr [AO (|ϕ⟩) = 1] . k←{0,1}n

|ϕ⟩∼µm

By Theorem 4.2, E

|ψm ⟩∼µm

adv(A ) = O

1 20.01n

To show that Genk is a 1PRS generator, it is required to fix a separating oracle O such that A cannot achieve non-negligible advantage. We use the following idea inspired by the proof of [Kre21, Theorem 30]. By Lemma 3.7 and the fact that the expectation of Lipschitz function is also Lipschitz, the function Prk←{0,1}n [AO (|ϕk ⟩) = 1] is a T -Lipschitz function in |ψm ⟩. The same applies to Pr|ϕ⟩∼µm [AO (|ϕ⟩) = 1], so adv(AO ) is a 2T -Lipschitz function in |ψm ⟩, where T < 20.495n . Applying Levy’s Lemma 3.6, we have h

|ψm ⟩∼µm

adv(AO ) −

|ψm ⟩∼µm

adv(AO ) ≥ 2−0.001n

2 · 2m · 2−0.002n ≤ 4 exp − 9π 3 · 4T 2

≤ O exp −20.1n

Hence, Pr

|ψm ⟩∼µm

i adv(AO ) ≥ 2−0.001n + Ω(2−0.01n ) ≤ O exp −20.1n .

P∞

Since n=1 exp −20.1n < ∞, by Borel-Cantelli Lemma 3.4, A achieves an advantage of at most 2−0.001n + O(2−0.01n ) for all but finitely many n ∈ N, with probability 1 over the choice of O. Thus, every QPT algorithm achieves a negligible advantage towards Genk with probability 1 over the choice of O.

4.2

Attack on Any 1PRS with m = Ω(n2+ε ) relative to O

Our proof of the existence of an attack against any 1PRS with output length m = Ω(n2+ε ) relative to O can be divided into two major steps. First, in “Bounding the ‘Effective’ Number of CHRS States Used by Any 1PRS”, we show a key structural property of any 1PRS relative to O: even though O gives access to exponentially many copies of a CHRS state (via O2 ), there must be an equivalent unitary implementation of the 1PRS that uses only polynomially many copies. Then, in “Description and Analysis of the Attack", we describe a concrete attack that leverages the structural property. 4.2.1

Bounding the “Effective” Number of CHRS States Used by Any 1PRS

Let GenO be the QPT generation algorithm of a 1PRS that on input k ∈ {0, 1}n outputs a pure m-qubit state |ϕk ⟩. Fixing n, k, we will simply write GenO k as the circuit corresponding to the security parameter n and input k, and GenO |0⟩ as its output. By Remark 4.1, we can view the action of GenO k k as a unitary Gk such that ! ! s O ⊗r(i) ⊗t Gk |ψi ⟩ ⊗ |0⟩ = |ϕk ⟩ ⊗ |ϕ̃k ⟩ (5) i=1

(·)

where s = poly(n) is the size of the circuit Genk , r(i) ≤ 22i/5 s, t ≤ 2s s, and |ϕ̃k ⟩ is some other state on the remaining registers. Crucially, the number of copies of each CHRS state is potentially exponential in n. As described informally in the technical overview, the key technical lemma that enables an attack on any 1PRS with sufficiently large stretch is that there is an equivalent implementation of Gk that only uses polynomially many CHRS states of each size. This is due to the strong constraint that Gk is required to output a pure state on the first m qubits for all9 choices of CHRS state families. The following is the key lemma, stated more generally as it may be of independent interest. The subsequent Corollary 4.6 is the result we will rely on going forward. Lemma 4.4. Let s, t, m ∈ N, and r(i) ∈ N for i ∈ [s]. Let U be an isometry such that, for all families of states {|θi ⟩}si=1 , where |θi ⟩ is an i-qubit state for all i, U |Θ⟩ = |ζΘ ⟩ ⊗ |ζ̃Θ ⟩ , where |Θ⟩ =

s ⊗r(i) i=1 |θi ⟩

⊗ |0⟩⊗t , and |ζΘ ⟩ , |ζ̃Θ ⟩ are states that can depend on {|θi ⟩}si=1 , |ζΘ ⟩ ∈ C2

and |ζ̃Θ ⟩ are of arbitrary dimension. Then, there exists an isometry V :

s O

Symℓ(i) C2 → C2

i=1

for some {ℓ(i)}si=1 with ℓ(i) ≤ r(i), such that for every {|θi ⟩}si=1 it holds that10 ! s O V |θi ⟩⊗ℓ(i) = |ζΘ ⟩ . i=1

Moreover, let c ∈ N be such that r(i) ≤ c · 2i for all i ∈ [s]. Then s X

ℓ(i) ≤ m2 + cm log m .

i=1

Proof. Let {|θi ⟩}si=1 , {|θi′ ⟩}si=1 be two sets of states, then every for every i ∈ [s], we can write the states |θi ⟩, |θi′ ⟩ in the form i −1 i −1 2X 2X i ′ |θi ⟩ = xj |j⟩ and |θi ⟩ = yji |j⟩ , j=0

where xij , yji ∈ C. So, let |Θ⟩ =

s ⊗r(i) i=1 |θi ⟩

j=0

(⟨Θ′ | U † )(U |Θ⟩) = ⟨Θ′ |Θ⟩ =

⊗ |0⟩⊗t and |Θ′ ⟩ =

s Y

r(i)

⟨θi′ |θi ⟩

i=1

s Y

s ′ ⊗r(i) i=1 |θi ⟩



i −1 2X

 i=1

⊗ |0⟩⊗t , then

r(i) xij yji 

j=0

9 The fact that this holds is not obvious: one could have a 1PRS relative to a fixed choice of oracle O (i.e. for a fixed family of CHRS states), which, in particular, only guarantees that the generation procedure outputs a pure state when querying this particular O. However, as we show in Lemma 4.5, with probability 1 over the choice of oracle O, if the generation procedure outputs a pure state when querying O, then it does so for every other choice O′ . 10 Note that there is a slight abuse of notation: |θi ⟩⊗ℓ(i) denotes the element inside the symmetric tensor space.

which is a polynomial in xij , yji and each term

P2i −1 j=0

xij yji is irreducible as a polynomial. On the other hand,

(⟨Θ′ | U † )(U |Θ⟩) = ⟨ζΘ′ |ζΘ ⟩ ⟨ζ̃Θ′ |ζ̃Θ ⟩ , where the terms ⟨ζΘ′ |ζΘ ⟩, ⟨ζ̃Θ′ |ζ̃Θ ⟩ are also polynomials in xij , yji . These equations hold for every choice of xij , yji , so there must exist some {ℓ(i)}si=1 with ℓ(i) ≤ r(i) and some constant c′ ∈ C such that ⟨ζΘ′ |ζΘ ⟩ = c′

s Y



i −1 2X

 i=1

ℓ(i) = c′

xij yji 

j=0

s Y

ℓ(i)

⟨θi′ |θi ⟩

i=1

Q for every xij , yji (i.e. every {|θi ⟩}si=1 , {|θi′ ⟩}si=1 ). In particular, since si=1 ⟨θi |θi ⟩ℓ(i) = ⟨ζΘ |ζΘ ⟩ = 1, we have c′ = 1. N i m This implies that there exists a function f : si=1 Symℓ(i) C2 → C2 , such that for every {|θi ⟩}si=1 , f n o N i i maps |Θ⟩ = si=1 |θi ⟩⊗ℓ(i) to |ζΘ ⟩. For every i ∈ [s], the set |θi ⟩⊗ℓ(i) : |θi ⟩ ∈ C2 spans Symℓ(i) C2 , and thus the set ( s ) O ⊗ℓ(i) 2i S= |θi ⟩ : |θi ⟩ ∈ C , i ∈ [s] i=1

spans i=1 Symℓ(i) C . Moreover, f preserves the inner product on S, since for every |Θ⟩ , |Θ′ ⟩ ∈ S we have that s Y ℓ(i) ′ † f (|Θ ⟩) f (|Θ⟩) = ⟨ζΘ′ |ζΘ ⟩ = ⟨θi′ |θi ⟩ = ⟨Θ′ |Θ⟩ . i=1

Hence, since every map that preserves the inner product can be extended to a linear isometry on the linear space spanned by the domain, there exists an isometry V :

s O

Symℓ(i) C2 → C2

i=1

such that V

s O

! |θi ⟩⊗ℓ(i)

i=1

s O

! |θi ⟩⊗ℓ(i)

= |ζΘ ⟩

i=1

for every set of states {|θi ⟩}si=1 . P Suppose now that c is a constant such that r(i) ≤ c · 2i . We prove the bound of si=1 ℓ(i) with a combinatorial argument. For i ≤ log m, since ℓ(i) ≤ r(i) we have that log Xm

ℓ(i) ≤ c2log m log m = cm log m .

i=1

For i > log m, note that the dimension of the domain of V is s Y

dim(Symℓ(i) C ) =

i=1

s i Y 2 + ℓ(i) − 1 i=1

ℓ(i)

Q i ≤ 2m . Now if there while the dimension of its codomain is 2m . So, it must be the case that si=1 2 +ℓ(i)−1 ℓ(i) exists some i > log m with ℓ(i) > m, then i mm em 2 + ℓ(i) − 1 m+m−1 mm √ √ ≥ ≥ > 2m ≥ ≥ m ℓ(i) m m! e1/12m 2πm m 2 2πm e where the fourth inequality is due to Stirling’s formula [Rob55]. Thus, ℓ(i) < m for all i ≥ log m. Moreover, Q i since 2 +ℓ(i)−1 ≥ 2i , for all i with ℓ(i) > 0, we must also have that i:ℓ(i)>0 2i ≤ 2m , which implies that ℓ(i) P P 2 i:ℓ(i)>0 i ≤ m. Hence, |{i : ℓ(i) > 0}| ≤ m, and therefore, i>log m ℓ(i) ≤ m , which completes the proof. Note that in Lemma 4.4, the hypothesis is very strong: the unitary should output a tensor product |ζ⟩⊗|ζ̃⟩ for all families of states {|θi ⟩}si=1 . In the context of our oracle separation, when we fix a separating oracle O (i.e. a particular family of states), and consider a 1PRS generation procedure GenO , we may only be guaranteed that GenO outputs a tensor product state (namely, the 1PRS state tensored with some auxiliary state) for this particular oracle O, not for all such oracles. Fortunately, a strong structural result holds: with probability 1 over sampling an oracle O, i.e., a family of states, if GenO outputs a tensor product state for this particular O, then it must do so for all possible O. This is the content of the following lemma, which we state a bit more generally. Lemma 4.5. Let G = {Gn } be a uniform family of quantum circuits11 . Let s, t : N → N, and r : N×N → N. There is a measure 1 set S of oracles O (i.e. families of states {|ψi ⟩}∞ i=1 ), independent of G, such that if, for all n and for all k ∈ {0, 1}n ,     s(n) O Gn |k⟩ ⊗  |ψi ⟩⊗r(n,i)  ⊗ |0⟩⊗t(n)  = |ϕk ⟩ ⊗ |ϕ̃k ⟩ (6) i=1 ′ ∞ for some pure states |ϕk ⟩ and |ϕ̃k ⟩ (that can depend on the {|ψi ⟩}∞ i=1 ), then for all families of states {|ψi ⟩}i=1 ,     s(n) O ⊗r(n,i)  Gn |k⟩ ⊗  |ψi′ ⟩ ⊗ |0⟩⊗t(n)  = |ζk ⟩ ⊗ |ζ̃k ⟩ , i=1

for some pure states |ζk ⟩ and |ζ̃k ⟩ (that can depend on the {|ψi′ ⟩}∞ i=1 ) of the same length as |ϕk ⟩ and |ϕ̃k ⟩ respectively. d Proof. Let M = S(2) × S(22 ) × · · · be the space that contains all families of states {|ψi ⟩}∞ i=1 , where S(2 ) is the set of quantum states on d qubits. Define syntactically that   s(n) O |Ψn ⟩ =  |ψi ⟩⊗r(n,i)  ⊗ |0⟩⊗t(n) . i=1 11 Here, we point out that take the term “uniform” to mean that there exists a Turing machine T , that on input 1n , outputs the circuit Gn in finite time. The more common use of the term “uniform” includes a requirement that these circuits are generated efficiently, which we do not impose here. In fact, in this lemma, the family of circuits may not be of polynomial size, since they may act on exponentially many states.

s(n)

Each entry in the density matrix |Ψn ⟩⟨Ψn | is a polynomial in the coefficients of {|ψi ⟩}i=1 and their complex conjugates. Let A, B be the register that |ϕk ⟩ , |ϕ̃k ⟩ lives in respectively, by Lemma 3.3, s(n)

QG,n,k ({|ψi ⟩}i=1 ) := −1 + purity(TrB (Gn (|k⟩⟨k| ⊗ |Ψn,k ⟩⟨Ψn,k |)G†n )) s(n)

is a polynomial in the coefficients of {|ψi ⟩}i=1 and their complex conjugates, for all uniform families of circuits G and n ∈ N, k ∈ {0, 1}n . Since for every i ∈ [s(n)], |ψi ⟩ are unit vectors, the zero locus Z of QG,n,k is either the whole domain Ms(n) := S(2) × S(22 ) × · · · × S(2s(n) ), or a zero-measure set in it. So, let ( ∅, o if Z(QG,n,k ) = Ms(n) RejectG,n,k = n s(n) {|ψi ⟩}∞ i=1 ∈ M | QG,n,k ({|ψi ⟩}i=1 ) = 0 , otherwise then RejectG,n,k ⊂ M is a zero-measure set. Hence Reject =

[[

[

RejectG,n,k

G n∈N k∈{0,1}n

is also a zero-measure set, since the descriptions of uniform families of circuits are countable. Now let S = M\Reject. Fix any family of states {|ψi ⟩}∞ i=1 ∈ S. Then, any uniform family of circuits s(n) G satisfying Equation (6) must satisfy QG,n,k ({|ψi ⟩}i=1 ) = 0, for any n ∈ N, k ∈ {0, 1}n . By the definition s(n) s(n) of Reject, QG,n,k ({|ψi′ ⟩}i=1 ) = 0 for all {|ψi′ ⟩}i=1 ∈ M. This proves the statement of the lemma. We now combine the previous lemmas to get a statement about the “effective” number of copies of CHRS states used by any 1PRS generation algorithm relative to the oracle O = (O1 , O2 ) defined at the start of Section 4. Corollary 4.6. Let Gen(·) be a QPT oracle algorithm. There is a measure 1 set S of oracles O (i.e. families O of states {|ψi ⟩}∞ i=1 ) such that, if Gen is a 1PRS with output length m for some O ∈ S, then the following holds. There exist functions s : N → N and ℓ : {0, 1}∗ × N → N with s(n) < p(n) for all n, and ℓ(k, i) < p(|k|) for all k, i, for some fixed polynomial function p, and unitaries   s(n) O i m(n) Uk :  Symℓ(k,i) C2  ⊕ Ca(k) → C2 i=1

Qs(n) i where a(k) = 2m(n) − i=1 dim(Symℓ(k,i) C2 ), such that: for all n ∈ N, k ∈ {0, 1}n , and oracles O′ , i.e. families of states {|ψi′ ⟩}∞ i=1 ,   s(n) O ′ ⊗ℓ(k,i) Uk  |ψi′ ⟩ ⊕ 0a(k)  = GenO k |0⟩ . i=1

Proof. The algorithm Gen is a QPT oracle algorithm, meaning that Gen is defined by an efficiently generatable family of oracle circuits whose size, for a security parameter n, is bounded by some fixed polynomial poly(n). Since Gen is a 1PRS, for every n ∈ N and k ∈ {0, 1}n , GenO k outputs an m(n)-qubit pure state |ϕk ⟩ By

Remark 4.1, Gen can also be seen as a uniform12 family of circuits G = {Gn }, along with parameters s, t : N → N and r : N × N → N, such that, for each n,     s(n) O Gn |k⟩ ⊗  |ψi ⟩⊗r(n,i)  ⊗ |0⟩⊗t(n)  = |ϕk ⟩ ⊗ |ϕ̃k ⟩ i=1

where s(n) ≤ poly(n), r(n, i) ≤ 22i/5 poly(n), t(n) ≤ poly(n) · 2poly(n) , and |ϕk ⟩ is the output of Genk (as the 1PRS state). Using Lemma 4.5, for all families of states {|ψi′ ⟩}∞ i=1 ,     s(n) O ⊗r(n,i)  |ψi′ ⟩ ⊗ |0⟩⊗t(n)  = |ϕ′k ⟩ ⊗ |ϕ̃′k ⟩ , Gn |k⟩ ⊗  i=1

for some pure states |ϕ′k ⟩ and |ϕ̃′k ⟩ of the same length as |ϕk ⟩ and |ϕ̃k ⟩ respectively. Now we apply Lemma 4.4 on Gn (|k⟩ ⊗ (·)) (note that the latter is an isometry). Then, there exist ℓ : {0, 1}∗ × N → N and isometries Vk :

s(n) O

m(n)

Symℓ(k,i) C2 → C2

i=1

such that Vk particular,

s(n) ′ ⊗ℓ(k,i) i=1 |ψi ⟩

= |ϕ′k ⟩ and

Ps(n)

i=1 ℓ(k, i)

≤ m(n)2 + poly(n) · m(n) log m(n). In

  s(n) O Vk  |ψi ⟩⊗ℓ(k,i)  = |ϕk ⟩ . i=1

Since any isometry can be extended to a unitary, we get a unitary   s(n) O i m(n) Uk :  . Symℓ(k,i) C2  ⊕ Ca(k) → C2 i=1

where Ca(k) is isomorphic to the orthogonal complement of Im Vk . 4.2.2

Description and Analysis of the Attack

We are now ready to present our attack against any 1PRS with output length m(n) = Ω(n2+ε ) relative to our separating oracle O (described at the start of Section 4). Theorem 4.7. With probability 1 over the choice of O, 1PRS with output length m(n) = Ω(n2+ε ) do not exist relative to O. The rest of this section is devoted to the proof of Theorem 4.7, which consists of describing an attack that breaks any 1PRS with m(n) = Ω(n2+ε ) by leveraging O. We refer the reader to Section 2 for an extended informal outline of this attack. The key is to leverage the oracle O2 to compute the “succinct” implementations 12

Again, our usage of “uniform” does not include an efficiency requirement, since the circuits act on potentially exponentially many states.

{Uk }k∈{0,1}n from Corollary 4.6. Recall that the {Uk }k∈{0,1}n are an equivalent implementation of the 1PRS generation procedure that, crucially, only uses a polynomial number of states from the CHRS family. In Appendix A, we briefly describe how to use the oracle O to find the unitaries Uk , using the doubleexponential power of O2 . More precisely, since Uk acts only on polynomially many qubits, a doubleek that approximate each Uk sufficiently exponential time Turing machine is sufficient to compute circuits U well. Then, we carefully describe how to use the family {Uk }k∈{0,1}n to break the 1PRS. As described in the Technical Overview, the specific type of attack depends on the types of CHRS states used in the succinct implementation via the Uk ’s. The description and analysis of the attack is thus divided into a number of cases, each requiring a different approach. We now begin the formal description of the attack and its analysis. Let {|ψi ⟩}∞ i=1 be a family of states, where each |ψi ⟩ is on i qubits. Let O be the corresponding oracle described at the start of Section 4 with respect to this family. Let Gen(·) be a QPT oracle algorithm such that GenO is a 1PRS under O with m(n) = Ω(n2+ε ). By Corollary 4.6, except for a measure zero set of possible oracles O, the following holds: • There exist functions s and ℓ with s(n) < p(n) for all n, and ℓ(k, i) < p(|k|) for all k, i, for some polynomial function p; • For all n, and k ∈ {0, 1}n , there exist unitaries   s(n) O i m Uk :  Symℓ(k,i) C2  ⊕ Ca(k) → C2

(7)

i=1

such that GenO k |0⟩ = Uk

s(n) ⊗ℓ(k,i) ⊕ 0a(k) i=1 |ψi ⟩

From here on, we fix a security parameter n. We will divide the analysis into two main cases, corresponding informally to the following: A. There is a noticeable (≥ n12 ) fraction of k such that: either Uk uses at least one copy of a “large” (at least linear length) state; or Uk uses many copies of some (at least) logarithmic-length states. B. There is only a < n12 fraction of k satisfying the above. We will show that a k satisfying either of the two “good” conditions in A allows us to distinguish GenO k |0⟩ from a Haar random state via a test based on the Permutation test. We will then combine these tests via an “OR test”. Formally, let   s(n)   X n S = k ∈ {0, 1} : (∃i ∈ [s(n)] s.t. (i ≥ 3n ∧ ℓ(k, i) > 0)) ∨ ℓ(k, i) ≥ 8n . (8)   i=log n

The two cases we consider are |S| ≥ 2n2 (Case A) and |S| < 2n2 (Case B). We will describe an adversary A that breaks the 1PRS in each case (note that, given queries to O, it is possible to determine efficiently whether S belongs to Case A or B, as we describe in more detail in Appendix A).

Case A. As we discussed informally in the Technical Overview (Section 2), we will define, for each k ∈ S, a projection Πk corresponding to a “generalized SWAP test”, which we explain below. We will show that such a test can be used to distinguish the state GenO k |0⟩ from a Haar random state with very good soundness. This enables us to carry out an OR test (Theorem 3.8) corresponding to the set of all projections {Πk }k∈S , which will achieve a non-negligible advantage in distinguishing a Haar random state from a state uniformly drawn from {GenO k |0⟩}k∈S . When the size of S is large enough, this attack achieves a non-negligible advantage in distinguishing a Haar random state from a state uniformly drawn from {GenO k |0⟩}k∈{0,1}n . As described informally in the Technical Overview, the generalized SWAP test that we consider is a “Permutation” test [KNY08], which checks overlap with the symmetric subspace on an arbitrary number r of registers. The Permutation test satisfies the following, for any pair of states |ϕ⟩ and |ξ⟩ of the same length m: 1 r−1 (m,r) Tr Πsym · |ϕ⟩⟨ϕ| ⊗ |ξ⟩⟨ξ|⊗(r−1) = + | ⟨ϕ|ξ⟩ |2 , r r (m,r)

where Πsym is the projection corresponding to acceptance in the Permutation test. Notice that the “soundness” of the test is controlled by the number of copies r (improving inverse-linearly with r), and the fidelity between |ϕ⟩ and |ξ⟩. A key property that we leverage is that, on average over a Haar random state |ϕ⟩, the fidelity scales inverse-exponentially with the number of qubits of the state. For k ∈ {0, 1}n , let Uk be the unitaries introduced in Equation (7), along with the functions s and ℓ with s(n) < p(n) for all n, and ℓ(k, i) < p(|k|) for all k, i, for some polynomial function p. Since Uk acts ek consisting of O(22m n4 m4 ) on exactly m qubits, by Theorem 3.1, for every k ∈ S there exists a circuit U −n 2-qubit gates, that approximates Uk with accuracy 2 , i.e. ek − Uk ∥op < 2−n . ∥U The attack to distinguish whether |ϕ⟩ is a state of the form GenO k |0⟩ for some k or a Haar random state is an “OR test”, defined using projections {Πk }k∈S , which we define next. Let k ∈ S. Ideally, we would like to define Πk as the projection corresponding to acceptance in e † (i.e. uncompute), perform a Permutation test between the resulting state and the following test: apply U k exponentially many |ψi ⟩ (concretely, 22i/5 copies of |ψi ⟩, provided by oracle O2 , plus 8n copies of |ψi ⟩, provided by the ability that the adversary A can also query O1 and give it as input to O2 ), where i ∈ [s(n)] satisfies the condition in Equation (8) with respect to k, i.e. |ψi ⟩ is either a “large enough” state or Uk uses many copies of |ψi ⟩ (and i is at least logarithmic). Note that the reason why we involve such a large number of copies, 22i/5 + 8n, is because the soundness of the Permutation test depends inverse-linearly with this number, as mentioned above. However, there are some obstacles. First, the domain of Uk is actually a direct sum of the desired Ns(n) i space i=1 Symℓ(k,i) C2 and the space Ca(k) . Second, and this is a bit more subtle, we must first apply i an “embedding” isometry that transforms the state in Symℓ(k,i) C2 (which can be thought of as being i represented in the Schur basis) to the corresponding state in (C2 )⊗ℓ(k,i) (which is on a number of qubits that is potentially larger than m). It is on the latter space that we can perform the usual Permutation test as in [KNY08]. We discuss this in more detail in Appendix A. To this end, we define two extra supporting maps Qk andVsch,k . We will see that composing the two Ns(n) 2i ⊕ Ca(k) ), to the space maps gives a transformation from the domain of Uk (namely i=1 Symℓ(k,i) C Ns(n) i ⊗ℓ(k,i) where the Permutation test directly acts on (namely i=1 C2 ).

Define Qk to be the orthogonal projection   s(n) s(n) O O i i Symℓ(k,i) C2  ⊕ Ca(k) → Symℓ(k,i) C2 . Qk :  i=1

i=1

Define Vsch,k :

s(n) O

Symℓ(k,i) C

i=1

→

s(n) O

⊗ℓ(k,i)

i=1 i

to be the “embedding” isometry that transforms a state in Symℓ(k,i) C2 to the corresponding state in i (C2 )⊗ℓ(k,i) . N m s(n) 2i )⊗(22i/5 +8n) , as follows:13 Now, define Πk , acting on C2 ⊗ (C i=1   s(n) O 2i/5 (i,ℓ(k,i)+2 +8n)  e † ⊗ 1) . (9) ek ⊗ 1)(Q† ⊗ 1)(V†  Πsym (Vsch,k ⊗ 1)(Qk ⊗ 1)(U Πk = (U sch,k ⊗ 1) k k i=1

As we discussed in Appendix A, the measurement {Πk , 1 − Πk } can be implemented efficiently given access to O2 . Next, we show that the projections {Πk } are good enough to run an “OR test” that distinguishes pseudorandom from Haar random states. To begin with, we show that using exponentially many copies of the CHRS states, the projections Πk overwhelmingly distinguish the states GenO k |0⟩ from Haar random states. For convenience, we will denote Ns(n) ⊗(22i/5 +8n) by |ξ⟩ = i=1 |ψi ⟩ the copies of the CHRS states that the Πk will operate on. Lemma 4.8. Let k ∈ S, Πk be the projection defined in Equation (9). If |ϕ⟩ = GenO k |0⟩, then Πk accepts −n+1 |ϕ⟩ ⊗ |ξ⟩ with probability 1 − 2 , and if |ϕ⟩ is Haar random, then Πk accepts |ϕ⟩ ⊗ |ξ⟩ with probability O(1/21.1n ) (on average over the sampling of |ϕ⟩). e Proof. In the case that |ϕ⟩ = GenO k |0⟩, using Lemma 3.2 and the fact that ∥Uk ⊗ 1 − Uk ⊗ 1∥op = −n ek − Uk ∥op < 2 , we have that ∥U Tr(Πk |ϕ⟩⟨ϕ| ⊗ |ξ⟩⟨ξ|) ≥ 1 − 2−n+1 . 13 It may not be obvious that Πk is a projection; the reason why Πk is indeed a projection is due to Equation (14). Notice that even if Πk was not a projection, we could still apply the OR test, because Lemma 3.8 is stated more generally, i.e. it holds for any two outcome measurements.

Suppose now that |ϕ⟩ is Haar random. Then E

|ϕ⟩∼µm

Tr (Πk |ϕ⟩⟨ϕ| ⊗ |ξ⟩⟨ξ|)  ek ⊗ 1)(Q† ⊗ 1)(V† Tr (U k sch,k

  s(n) O (i,ℓ(k,i)+22i/5 +8n)  Πsym ⊗ 1)  i=1

  s(n) O 2i/5 e † ⊗ 1) · |ϕ⟩⟨ϕ| ⊗  |ψi ⟩⟨ψi |⊗(2 +8n)  (Vsch,k ⊗ 1)(Qk ⊗ 1)(U k

i=1

 =

|ϕ⟩∼µm

† Tr (Q†k ⊗ 1)(Vsch,k

  s(n) O 2i/5 (i,ℓ(k,i)+2 +8n)  ⊗ 1)  Πsym

(10)

i=1

 (Vsch,k ⊗ 1)(Qk ⊗ 1) · |ϕ⟩⟨ϕ| ⊗ 

s(n) O

 ⊗(22i/5 +8n)

|ψi ⟩⟨ψi |



i=1



s(n)

=Tr 

(i,ℓ(k,i)+22i/5 +8n)

Πsym

i=1



s(n) O

≤ Tr 



!  s(n) O (i,ℓ(k,i)+22i/5 +8n) · Πsym

i=1

s(n)

Y i=1

|ϕi ⟩∼µi



s(n) † O Vsch,k Qk Q†k Vsch,k 2i/5  · ⊗ |ψi ⟩⟨ψi |⊗(2 +8n)  m 2 i=1

 E

|ϕi ⟩∼µi



|ϕi ⟩⟨ϕi |⊗ℓ(k,i)  ⊗ 

s(n) O

(11) 

2i/5 +8n)

|ψi ⟩⟨ψi |⊗(2

 (12)

i=1

2i/5 (i,ℓ(k,i)+22i/5 +8n) Πsym |ϕi ⟩⟨ϕi |⊗ℓ(k,i) ⊗ |ψi ⟩⟨ψi |⊗(2 +8n)

(13)

where (10) follows from the invariance of the Haar measure, (11) follows from linearity of the trace and the fact that E|ϕ⟩∼µm |ϕ⟩⟨ϕ| = 21m , and (12) follows from linearity of expectation and the fact that N s(n) † † † † Vsch,k V 1 i sch,k Vsch,k Qk Qk Vsch,k i=1 Symℓ(k,i) C2 Qk Qk † = Vsch,k m Vsch,k ⪯ Ns(n) Ns(n) 2 dim( i=1 Symℓ(k,i) C2i ) dim( i=1 Symℓ(k,i) C2i )   s(n) s(n) (i,ℓ(k,i)) 1Symℓ(k,i) C2i O O Πsym †   = Vsch,k Vsch,k = dim(Symℓ(k,i) C2i ) dim(Symℓ(k,i) C2i ) i=1 i=1 =

s(n) O i=1

|ϕi ⟩∼µi

|ϕi ⟩⟨ϕi |⊗ℓ(k,i) .

(14)

Note that, in the final expression of (13), for each i, the trace corresponds to the acceptance probability of 2i/5 a Permutation test on the state |ϕi ⟩⟨ϕi |⊗ℓ(k,i) ⊗ |ψi ⟩⟨ψi |⊗(2 +8n) . Now, since k ∈ S, we have, by definition Ps(n) of S, that either there exists some i ∈ [s(n)] such that i ≥ 3n and ℓ(k, i) > 0, or i=log n ℓ(k, i) ≥ 8n. We will show that in both cases, (13) can be upper bounded by O(1/21.1n ). • If there exists i ∈ [s(n)] such that i ≥ 3n and ℓ(k, i) > 0, then (i,ℓ(k,i)+22i/5 +8n)

Πsym

(i,1+22i/5 )

⪯ 1 ⊗ Πsym

⊗ 1,

and thus 2i/5 (i,ℓ(k,i)+22i/5 +8n) Tr Πsym |ϕi ⟩⟨ϕi |⊗ℓ(k,i) ⊗ |ψi ⟩⟨ψi |⊗(2 +8n) 2i/5 (i,1+22i/5 ) ≤ Tr Πsym |ϕi ⟩⟨ϕi | ⊗ |ψi ⟩⟨ψi |⊗2 . Using Lemma 3.9, we have 2i/5 (i,1+22i/5 ) Tr Πsym |ϕi ⟩⟨ϕi | ⊗ |ψi ⟩⟨ψi |⊗2 ≤

1 22i/5

+ | ⟨ϕi |ψi ⟩ |2 ,

and using Lemma 3.5 with ε = 2−2i/5 , we have h i −2i/5 (2i −1) 2i/5 Pr | ⟨ϕi |ψi ⟩ |2 ≥ 2−2i/5 < e−2 ≤ e−2 . |ϕ⟩∼µi

Hence, because i ≥ 3n, 2i/5 (i,ℓ(k,i)+22i/5 +8n) |ϕi ⟩⟨ϕi |⊗ℓ(k,i) ⊗ |ψi ⟩⟨ψi |⊗(2 +8n) E Tr Πsym |ϕi ⟩∼µi

≤

1 22i/5

−22i/5

≤O

1 21.1n

Substituting this back into Equation (13), we have E

|ϕ⟩∼µm

Tr (Πk |ϕ⟩⟨ϕ| ⊗ |ξ⟩⟨ξ|) ≤ O(2−1.1n ) .

Ps(n) Ps(n) • If i=log n ℓ(k, i) ≥ 8n, we define ℓ̄(k, i) = min{ℓ(k, i), 8n}. Trivially i=log n ℓ̄(k, i) ≥ 8n. We have (i,ℓ(k,i)+22i/5 +8n)

Πsym

⪯ 12

⊗(22i/5 +8n−ℓ̄(k,i))

⊗ 12 ⊗(ℓ(k,i)−ℓ̄(k,i)) (i,2) ⊗ℓ̄(k,i) ⊗(22i/5 +8n−ℓ̄(k,i)) ⪯ 12 ⊗ Vi† (π) Πsym Vi (π) ⊗ 12 ⊗(ℓ(k,i)−ℓ̄(k,i))

(i,2ℓ̄(k,i))

⊗ Πsym

where Vi (π) permutes the 2ℓ̄(k, i) registers according to the following permutation π: t in [ℓ̄(k, i)] maps to 2t − 1, and t in {ℓ̄(k, i) + 1, · · · , 2ℓ̄(k, i)} maps to 2(t − ℓ̄(k, i)) (this sounds complicated, but ℓ̄(k, i) is defined to ensure that the Permutation test can access ℓ̄(k, i) copies of the CHRS state |ψi ⟩, and Vi (π) is just ensuring that each of the ℓ̄(k, i) SWAP tests involves one copy of the Haar random state |ϕi ⟩ and one copy of |ψi ⟩). 2i/5

The above implies that the probability of the state |ϕi ⟩⟨ϕi |⊗ℓ(k,i) ⊗ |ψi ⟩⟨ψi |⊗(2 +8n) passing the generalised swap test is upper bounded by the probability that ℓ̄(k, i) copies of the state |ϕi ⟩ |ψi ⟩ pass all ℓ̄(k, i) swap tests. This probability is exactly

1 + | ⟨ϕi |ψi ⟩ |2 2

ℓ̄(k,i) .

Using Lemma 3.5 with ε = 4/5, we have that, for i ≥ log n, 4 i Pr | ⟨ϕi |ψi ⟩ |2 ≥ < e−4(2 −1)/5 ≤ e−4(n−1)/5 ≤ 2−1.15n . 5 |ϕi ⟩∼µi 28

Thus, for all i ≥ log n, E

|ϕi ⟩∼µi

2i/5 (i,ℓ(k,i)+22i/5 +8n) Πsym |ϕi ⟩⟨ϕi |⊗ℓ(k,i) ⊗ |ψi ⟩⟨ψi |⊗(2 +8n)

≤

9 10

ℓ̄(k,i)

+ 2−1.15n .

Hence, s(n)

|ϕ⟩∼µm

Tr (Πk |ϕ⟩⟨ϕ| ⊗ |ξ⟩⟨ξ|) ≤

Y i=log n

≤ ≤ ≤ ≤

9 10 9 10 9 10 9 10

9 10

ℓ̄(k,i) +2

Ps(n)

−1.15n

s(n)

i=log n ℓ̄(k,i)

1 + 2−1.15n − 1

(15)

i=log n

Ps(n)

i=log n ℓ̄(k,i)

Ps(n)

i=log n ℓ̄(k,i)

+ 1 + 2−1.15n −1.15n s(n)

+ e2

+ e · O(s(n) · 2−1.15n )

s(n)

−1

−1 (16)

≤ O(2−1.1n ) . 9 with 1 except the first term; and where (15) comes from expanding the product and replacing every 10 −1.15n (16) is due to the fact that 2 s(n) < 1 for sufficiently large n.

Therefore, in both cases, we have that E

|ϕ⟩∼µm

Tr (Πk |ϕ⟩⟨ϕ| ⊗ |ξ⟩⟨ξ|) ≤ O(2−1.1n ) .

Now consider the 1PRS adversary AO that on input (1n , |ϕ⟩) runs the OR test from Theorem 3.8 on |ϕ⟩ ⊗ |ξ⟩ with projections {Πk }k∈S . Then, AO achieves a non-negligible distinguishing advantage in the current Case A, as we show in Lemma 4.9 below. Lemma 4.9. Let n ∈ N such that |S| ≥ 2n /n2 (i.e. Case A). Then, the OR test algorithm (from Theorem 3.8) with projections {Πk }k∈S and challenge state |ϕ⟩⊗|ξ⟩ achieves an advantage of at least 8n1 2 in distinguishing |ϕ⟩ of the form GenO k |0⟩ for some k, from a Haar random |ϕ⟩. Proof. Let A be the OR test algorithm from Theorem 3.8 with projections {Πk }k∈S and challenge state |ϕ⟩ ⊗ |ξ⟩. Then, for every k ∈ S, the probability of |ϕ⟩ ⊗ |ξ⟩ passing the k-th test is exactly pk = Tr(Πk |ϕ⟩⟨ϕ| ⊗ |ξ⟩⟨ξ|) . Thus, using Lemma 4.8, E

|ϕ⟩∼µm

p↑ =

X k∈S

|ϕ⟩∼µm

pk ≤ O

|S| 21.1n

≤O

1 20.1n

Therefore, using Theorem 3.8,

Pr [A (|ϕ⟩ ⊗ |ξ⟩) = 1] ≤ 2

|ϕ⟩∼µm

p↑ ≤ O

1 20.1n

In the case that |ϕ⟩ = GenO k |0⟩ for some k ∈ S, using Lemma 4.8, O † −n+1 p↓ ≥ Tr(Πk (GenO . k |0⟩)(Genk |0⟩) ⊗ |ξ⟩⟨ξ|) ≥ 1 − 2

Hence, Pr

k←{0,1}n

[AO ((GenO k |0⟩) ⊗ |ξ⟩) = 1] ≥

|S| (1 − 2−n+1 )2 1 − 2−n · . ≥ 2n 7 7n2

Note that the entire analysis of Case A holds for any O that lie in the measure 1 set S of oracles (originating from Corollary 4.6). We will now analyze Case B, where we will describe an attack that, 1 instead, succeeds “only” with 1 − O n2 probability over the choice of oracle O. At the very end, we will argue via Borel-Cantelli Lemma 3.4, that this suffices to identify a fixed oracle O relative to which our attack works. n

Case B. In this case, we assume |S| < 2n2 . We will show that, on average over the choice of oracle GenO , the uniform mixture of the states generated by GenO is statistically far from the maximally mixed state on m qubits. Therefore, there is a projective measurement M that distinguishes the two with non-negligible advantage (on average over O). Informally, our approach to showing that the two distributions are statistically far is as follows. First, we will prove that the density matrix i h † O (17) (GenO ρGen = E E k |0⟩)(Genk |0⟩) O k←{0,1}n

can be sufficiently approximated by another density matrix with rank at most 2O(n ) (Lemma 4.10). Next, following the paradigm of [MY22], we show that ρGen is statically far from 21m (Lemma 4.11), using the fact that m = Ω(n2+ε ). Hence, we conclude that, with sufficiently high probability over the choice of O, applying a measurement that negligibly approximates the optimal distinguisher of ρGen from 1/2m , achieves a noticeable advantage in distinguishing the states generated by GenO from Haar random states (Lemma 4.12). 2

′ O(n ) . Lemma 4.10. There exists a density matrix ρ′Gen with ∥ρGen − ρ′Gen ∥1 ≤ 2|S| 2n and rank(ρGen ) ≤ 2

Proof. By Corollary 4.6,  ρGen =

 =

k←{0,1}n |ψ1 ⟩∼µ1 |ψ2 ⟩∼µ2

k←{0,1}n



Uk 

s(n) O

···

|ψs(n) ⟩∼µs(n)

1Symℓ(k,i) C2i

dim Symℓ(k,i) C2i i=1



Uk 

s(n) O



|ψi ⟩⟨ψi |⊗ℓ(k,i) ⊕ 0a(k)  Uk† 

i=1





⊕ 0a(k)  Uk†  .

So, let

      s(n) 1Symℓ(k,i) C2i X X O 1 Uk  ρ′Gen = n  ⊕ 0a(k)  Uk†  + |0⟩⟨0|⊗m  . 2 dim Symℓ(k,i) C2i k̸∈S

i=1

k∈S

Trivially, we have  E

|ψ1 ⟩∼µ1 |ψ2 ⟩∼µ2

···

|ψs(n) ⟩∼µs(n)



Uk 

s(n) O





|ψi ⟩⟨ψi |⊗ℓ(k,i) ⊕ 0a(k)  Uk†  − |0⟩⟨0|⊗m

i=1

≤ 2. 1

By a standard hybrid method, we have ∥ρGen − ρ′Gen ∥1 ≤ 2|S| 2n , and   s(n) O X 1Sym rank  ⊕ 0a(k)  + rank(|0⟩⟨0|⊗m ) rank(ρ′Gen ) ≤ C2i ℓ(k,i)

k̸∈S

=1+

i=1

 s(n) O rank  1



Symℓ(k,i) C2i

k̸∈S

(18)



i=1

Now, by the definition of S, for each k ̸∈ S, we have that ℓ(k, i) = 0 for all i ≥ 3n, and 8n. In addition, • If i < 3n, then

Ps(n)

i=log n ℓ(k, i) <

dim Symℓ(k,i) C2 ≤ dim(C2 )⊗ℓ(k,i) = 2i·ℓ(k,i) < 23n·ℓ(k,i) .

• If i < log n, by Remark 4.1, there exists a fixed polynomial p, such that ℓ(k, i) < 22i/5 · p(n). Hence, we have i 2 + ℓ(k, i) − 1 i 2i ≤ (2i + ℓ(k, i) − 1)2 −1 ≤ (n + n2/5 p(n))n = 2O(n log n) . dim Symℓ(k,i) C = 2i − 1 Therefore, for every k ̸∈ S,  s(n) O  rank 1Sym



s(n)

= 2i

ℓ(k,i) C

i=1

dim Symℓ(k,i) C2

i=1

log Yn

!  dim Symℓ(k,i) C2

·

i=1

3n Y



i=log n 2

≤ 2O(n log n) · 23n 2

P3n

i=log n ℓ(k,i) 2

≤ 2O(n log n)+24n = 2O(n ) . Equation (18) yields 2

rank(ρ′Gen ) ≤ 1 + (2n − |S|) · 2O(n ) ≤ 2O(n ) .

dim Symℓ(k,i) C2 

Using Lemma 4.10, we can show that ρGen is statistically far from the maximally mixed m-qubit state, since we have assumed that m = Ω(n2+ε ). Lemma 4.11. If m = Ω(n2+ε ) and |S| < 2n2 , then 12 ∥ρGen − 21m ∥1 ≥ 1 − n22 . n

Proof. Let ρ′Gen be the density matrix from Lemma 4.10, then using the following argument inspired by [MY22, Theorem 3.2], we can show that ρGen is statistically far from 21m : s 1 ′ ≥ 1 − F ρGen , m 2 1

1 ′ 1 ρGen − m 2 2

=1−

ξ X p i=1

1 λi √ |λi ⟩⟨λi | 2m

ξ √ X

(19) 1

λi 2m i=1 v v u ξ u ξ uX uX 1 t ≥1− λi t 2m i=1 i=1 √ ξ ≥1− √ 2m = 1 − negl(n)

=1−

√

(20)

(21)

P where in Equation (19), we define ξi=1 λi |λi ⟩⟨λi | to be the diagonalization of ρGen ; in Equation (20), we use the Cauchy-Schwarz inequality; and in Equation (21), we use the fact that m = Ω(n2+ε ) and 2 ξ = rank(ρ′Gen ) ≤ 2O(n ) (Lemma 4.10). n Hence, since |S| < 2n2 , we have 1 1 ρGen − m 2 2

≥ 1

1 ′ 1 ρGen − m 2 2

− 1

|S| 1 2 ρGen − ρ′Gen 1 ≥ (1 − negl(n)) − n ≥ 1 − 2 . 2 2 n

where the second inequality follows from (21) and Lemma 4.10. Lemma 4.12. Let {Q, 1 − Q} be the projective measurement that optimally distinguishes ρGen from 21m . e that negligibly approximates the measurement, achieves a noticeable advantage in Then, any circuit Q O 1 † 2 distinguishing Ek←{0,1}n (GenO k |0⟩)(Genk |0⟩) from 2m , except with probability 5/n over the choice of O. e be a circuit that approximates the measurement with precision 2−n , then Proof. Let Q h i 1 2 1 O O † e Tr Q E E (Genk |0⟩)(Genk |0⟩) − m ≥1− 2 − n , O k←{0,1}n 2 n 2 which implies that e E Tr Q O

h i 1 2 1 O O † E (Genk |0⟩)(Genk |0⟩) − m ≥1− 2 − n . n 2 n 2 k←{0,1} 32

Therefore, using Markov’s inequality we have h i 5 1 1 O O † e Pr Tr Q ≥1− 2 . ≥ E (Genk |0⟩)(Genk |0⟩) − m O 2 2 n k←{0,1}n e to the challenge state using O2 and outputs the outcome of the Hence, the adversary AO that applies Q measurement, achieves an advantage Pr

k←{0,1}n

[AO (GenO k |0⟩)] −

Pr [AO (|ϕ⟩)] ≥ |ϕ⟩∼µm e Tr Q

h E

k←{0,1}n

O † (GenO k |0⟩)(Genk |0⟩)

−

1 2m

≥

1 , 2

except with probability at most n52 over the choice of O. Summary of the attack, and putting everything together. Combining the attacks for cases A and B, we can construct an adversary that breaks the security of the 1PRS generator GenO . In particular, we consider the adversary AO that queries O2 with the the following input parameter: Nthe description of the Turing T T ⊗8n .14 That is, machine M as in Algorithm 1, a sufficiently large 1 , and the state |ϕ⟩ ⊗ i=1 (O1,i |0⟩) AO first asks the oracle O2 to compute the “succinct” implementations of Gen(·) (along with the appropriate parameters) so that it can decide whether Gen(·) on security parameter n is of Case A or B. Then, O2 runs the circuit that the Algorithm 1 returns, i.e. the OR test (Lemma 4.9) for Case A, and the circuit that implements the optimal distinguishing measurement (Lemma 4.12) for Case B. Proof of Theorem 4.7. Let Gen(·) be a QPT oracle algorithm. For all possible oracles O, if GenO is a 1PRS with output length m(n) = Ω(n2+ε ), then adversary AO : on input (1n , |ϕ⟩) Nwe can consider the following T (n) ⊗8n , M to O , where T (·) is a sufficiently large AO makes a single query 1T (n) , |ϕ⟩ ⊗ 2 i=1 (O1,i |0⟩) polynomial, of the Turing machine in Algorithm 115 , and AO can prepare the state N M is the description T (n) ⊗8n before its query to O by querying O 8nT (n) times; then AO outputs the |ϕ⟩ ⊗ 2 1 i=1 (O1,i |0⟩) outcome of O2 . From Corollary 4.6, we have that with probability 1 over the choice of O, Gen(·) on security parameter n indeed has the “succinct" implementations {Uk }k∈{0,1}n . Using Lemmas 4.9 and 4.12, we have that in both cases, AOP achieves a distinguishing advantage of at least 8n1 2 , except with probability n52 over the choice of 5 O. Since ∞ n=1 n2 < ∞, by Borel-Cantelli lemma (Lemma 3.4), with probability 1 over the choice of O, AO achieves an advantage of at least 8n1 2 , for all but finitely many n’s. This means that for each generator Gen(·) , with probability 1 over the choice of O, if GenO is a 1PRS with output length m(n) = Ω(n2+ε ), then there exists an adversary A(·) that achieves a non-negligible advantage. Since there are countably many descriptions of QPT oracle algorithms, with probability 1 over the choice of O, for any generator algorithm GenO such that GenO is a 1PRS with output length m(n) = Ω(n2+ε ), there exists an adversary AO that achieves a non-negligible advantage. 14 15

Recall that O1,i |0⟩ is the CHRS state |ψi ⟩; O2 runs the Turing machine M for 22 steps, and runs the circuit that M outputs. Notice that M can have T −1 (·) hard-coded so then O∈ can retrieve n from T (n).

Algorithm 1 The Turing machine M procedure M Let s(n) := T ▷ Increasing s(n) does not affect Lemma 4.4 n for k ∈ {0, 1} do (·) Classically simulate Genk to obtain the unitary Gk . (·) s(n) Compute the “succinct” implementation Uk of Genk and the corresponding values {ℓ(k, i)}i=1 , and a(k) (from Corollary 4.6), using the algorithm described in Appendix A. end for n o Ps(n) Set S = k ∈ {0, 1}n : (∃i ∈ [s(n)] s.t. (i ≥ 3n ∧ ℓ(k, i) > 0)) ∨ i=log n ℓ(k, i) ≥ 8n if |S| ≥ 2n /n2 then ▷ Case A for k ∈ S do ek such that ∥U ek − Uk ∥op < 2−n , using the Solovay-Kitaev algorithm (TheoFind a circuit U rem 3.1). Find the circuit that implements the measurement Πk as in Equation (9), using the method described in Appendix A. end for return The description of the OR test algorithm (Theorem 3.8) for the projections {Πk }k∈S . else ▷ Case B h N i s(n) † a(k) Classically compute ρGen = Ek←{0,1}n Uk ⊕0 Uk . i=1 1Sym C2i ℓ(k,i)

Compute the optimal distinguishing projective measurement {Q, 1 − Q} between ρGen and 21m using the spectral decomposition. e that implements the projective measurement with precision 2−n , using the SolovayFind a circuit Q Kitaev algorithm (Theorem 3.1). e return The description of Q. end if end procedure

Implication on Impossibilities of Black-box Constructions

In this section, we will clarify the implication of our channel oracle separation in the plain world. In particular, our oracle separation implies that we cannot stretch a 1PRS in a fully black-box way to an arbitrary output length, if we only have the isometry access to the generation algorithm and the adversary. We will see that “querying in superposition" means that the black-box construction can have isometry access to the shorter 1PRS, but the black-box security reduction can only use the adversary as a channel. We will first define some primitives that provide different kinds of access to the generator. Then, we will discuss the meaning of oracle separation under these primitives, and describe the similarities and differences to the various kind of black-box construction defined in [CCS25, Section 5]. To begin with, we need to recall the formal definition of cryptographic primitives and the fully black-box construction. Definition 5.1 ([CCS25], Theorem 5.9). A primitive P is a pair P = (FP , RP ) where FP is a set of quantum channels, and RP is a relation over pairs (G, A) of quantum channels, where G ∈ FP . A quantum channel G is an implementation of P if G ∈ FP . If G is additionally a QPT channel, then we say that G is an efficient implementation of P (in this case, we refer to G interchangeably as a QPT 34

channel or a QPT algorithm). A quantum channel A (usually referred to as the “adversary") P-breaks G ∈ FP if (G, A) ∈ RP . We say that G is a secure implementation of P if G is an implementation of P such that no QPT channel P-breaks it. The primitive P exists if there exists an efficient and secure implementation of P. Definition 5.2. A pair of QPT oracle algorithms (G(·) , S (·) ) is a fully black-box construction of Q with channel access to P if the following two condition holds: • (Black-box construction) For every (possibly inefficient) channel implementation V of P, GV is an implementation of Q. • (Black-box security reduction) For every channel implementation V of P , and every (possibly inefficient) channel adversary A that Q-breaks GV , it holds that S A P-breaks V . Theorem 5.1. Suppose there exists a fully black-box construction of primitive Q with channel access to primitive P. Then, for every quantum channel oracle O, if P exists relative to O, then Q also exists relative to O. Proof. This proof is essentially the same as the proof of [CCS25, Theorem 5.17]. Suppose there exists a fully black-box construction of Q with channel access to P. Then, by definition, there exist QPT oracle algorithms G(·) and S (·) such that the conditions in Definition 5.2 holds. Let O be a quantum channel oracle, relative to which P exists, that is, there exists a quantum channel C, efficiently computable relative to O, such that C is an efficient channel implementation of P. Moreover, C satisfies the security condition relative to O. By the black-box construction condition in Definition 5.2, GC is an implementation of Q. We show that the following QPT oracle algorithm G̃O is an efficient implementation relative to O. The algorithm G̃O runs as follows: implement GC by running G, and simulate each call to C with the oracle O. Since C is a QPT algorithm relative to O, G̃O is also a QPT algorithm relative to O. Since GC ∈ FQ , and GC is equivalent to G̃O , G̃O ∈ FQ . We need to show that G̃O is a secure implementation relative to O. Suppose for a contradiction that there exists a QPT oracle channel AO Q-breaks G̃O . Then, by the black-box security reduction condition O O in Definition 5.2, S A P-breaks C. Since S (·) and A(·) are QPT algorithms, S A is QPT relative to O. Thus, we constructed a QPT algorithm that P-breaks C, which contradicts the assumption that C is a secure implementation of P. Therefore, G̃O is secure. Theorem 5.1 immediately yields the following. Theorem 5.2. There is no fully black-box construction of 1PRS with input length n and output length m(n) = Ω(n2+ε ), with channel access to 1PRS with input length n and output length m(n) = 1.1n. Proof. If there exists such a black-box construction, then it relativizes to any quantum channel oracle. But that contradicts Theorem 4.3 and Theorem 4.7. But black-box construction with channel access is a very weak construction. In fact, there is no known black-box construction of bit commitment with channel access to 1PRS. We need to upgrade Theorem 5.2 to a stronger version that rules out more possibilities of fully black-box constructions.

Definition 5.3 (Isometry Pseudorandom States (IsometryPRS)). An isometry pseudorandom state generator with output length m(·) is a QPT algorithm Gen that takes as input (1n , |ζ⟩), where |ζ⟩ is an n-qubit quantum state, and has the following properties: • Generation in Superposition: For every k ∈ {0, 1}n , there exists a pure state |ϕk ⟩ consisting of m = m(n) qubits (intended to be the output) and (potentially) a state |ηk ⟩ (intended to be the ancillas) such that Gen(1n , |k⟩) = |k⟩ ⊗ |ϕk ⟩ ⊗ |ηk ⟩ . Pn Moreover, for any input |ζ⟩ = 2i=0−1 ci |i⟩, n

Gen(1 , |ζ⟩) =

n −1 2X

ci |i⟩ ⊗ |ϕi ⟩ ⊗ |ηi ⟩ .

i=0

• Security: For any polynomial t = t(n) and any QPT adversary A, there exists a negligible function negl such that for all n, h i h i Prk∈{0,1}n A(|ϕk ⟩⊗t(n) ) = 1 − Pr|ϕ⟩∼µ2m A(|ϕ⟩⊗t(n) ) = 1 = negl(n), where µ2m is the Haar measure on m qubits. Definition 5.4 (Single-copy Isometry Pseudorandom States (Isometry1PRS)). A single-copy isometry pseudorandom state generator with output length m(·) is an IsometryPRS (as in Definition 5.3) with m(n) > n, for every n ∈ N, except that the security property only holds for t = 1. One can verify that the construction in Theorem 4.3 is an Isometry1PRS. Hence, our result shows the following. Theorem 5.3. There is no fully black-box construction of 1PRS with input length n and output length m(n) = Ω(n2+ε ), with channel access to Isometry1PRS with input length n and output length m(n) = 1.1n. More generally, we have the following primitives that are easy to understand, and serve as alternatives to replace the various kind of black-box access introduced in [CCS25]. Definition 5.5. Given a primitive P, • The primitive IsometryP = (FIsometryP , RIsometryP ) is defined as follows: FIsometryP = {(G, Gisometry ) : G ∈ FP , Gisometry is an isometry implementation of G} RIsometryP = {(G, Gisometry , A) : (G, A) ∈ RP , (G, Gisometry ) ∈ FIsometryP } • The primitive UnitaryP = (FUnitaryP , RUnitaryP ) is defined as follows: FUnitaryP = {(G, Gunitary : G ∈ FP , Gunitary is a unitary implementation of G} RUnitaryP = {(G, Gunitary , A) : (G, A) ∈ RP , (G, Gunitary ) ∈ FUnitaryP } • The primitive InverseAccessP = (FInverseAccessP , RInverseAccessP ) is defined as follows: FInverseAccessP = {(G, Gunitary , G−1 unitary ) : (G, Gunitary ) ∈ FUnitaryP } −1 RInverseAccessP = {(G, Gunitary , G−1 unitary , A) : (G, A) ∈ RP , (G, Gunitary , Gunitary ) ∈ FInverseAccessP }

The primitive Isometry1PRS, introduced in Definition 5.4, is equivalent to IsometryP with P = 1PRS. We should notice that there is no straightforward fully black-box construction from P to IsometryP, UnitaryP, or InverseAccessP. For example, there is no straightforward fully black-box construction from 1PRS to Isometry1PRS, as the naive construction, that querying the Gen |k⟩ controlled on the input being |k⟩ where Gen is the generator of 1PRS, is not a QPT construction. We have the following lemma that characterize the black-box separation between IsometryP and Q. Lemma 5.4. Suppose there exists no fully black-box construction of Q with channel access to P. Denote any element in FIsometryP as (C, Cisometry ). Then any fully black-box construction of Q with channel access to IsometryP must query Cisometry ; that is, accessing the purification of the output of C. Lemma 5.5. Suppose there exists no fully black-box construction of Q with channel access to IsometryP. Denote any element in FUnitaryP as (C, Cunitary ), so that |ζ⟩ 7→ Cunitary (|ζ⟩ |0⟩) is an isometry implementation of C. Then any fully black-box construction of Q with channel access to UnitaryP must query Cunitary outside the subspace spanned by |ζ⟩ |0⟩; that is, querying on some non-zero ancilla input. Lemma 5.6. Suppose there exists no fully black-box construction of Q with channel access to UnitaryP. −1 ). Then any fully black-box construction of Q Denote any element in FInverseAccessP as (C, Cunitary , Cunitary −1 with channel access to InverseAccessP must query Cunitary . We will only prove Lemma 5.4. The proofs of Lemmas 5.5 and 5.6 are essentially the same. Proof of Lemma 5.4. Suppose G(·) and S (·) are QPT algorithms as in Definition 5.2. Then G(C,Cisometry ) is an implementation of Q, and for any adversary A that Q-breaks G(C,Cisometry ) , S A IsometryP-breaks (C, Cisometry ); that is, (C, Cisometry , S A ) ∈ RIsometryP . By the definition of IsometryP, (C, S A ) ∈ RP . Therefore, S A P-breaks C. Suppose for contradiction that G(·) does not query Cisometry . Then GC is an implementation of Q, so (G(·) , S (·) ) is a fully black-box construction of Q with channel access to P. That leads to contradiction. What is the relationship between the fully black-box construction from P with isometry access (resp. unitary access, access to the inverse) as introduced in [CCS25], and the fully black-box construction from IsometryP (resp. UnitaryP, InverseAccessP)? We have the following characterizations. Lemma 5.7. Suppose there is no fully black-box construction of Q with channel access to IsometryP, and there exists a fully black-box construction (G(·) , S (·) ) of Q with isometry access to P. Denote C as an isometry implementation of P, and A is an adversary that Q-breaks GC , A |ϕ⟩ = Tr1 ((⟨0|⊗ 1)Aisometry |ϕ⟩). Then S (·) must query Aisometry ; that is, using not only the first output qubits of Aisometry . Lemma 5.8. Suppose there is no fully black-box construction of Q with channel access to UnitaryP, and there exists a fully black-box construction (G(·) , S (·) ) of Q with unitary access to P. Denote C as a unitary implementation of P, and A is an adversary that Q-breaks GC , A |ϕ⟩ = Tr1 ((⟨0| ⊗ 1)Aunitary |ϕ⟩ |0η ⟩). Then S (·) must query Aunitary ; that is, using not only the first output qubits of Aunitary , or querying to Aunitary on some non-zero ancilla input. Lemma 5.9. Suppose there is no fully black-box construction of Q with channel access to InverseAccessP, and there exists a fully black-box construction (G(·) , S (·) ) of Q with access to the inverse to P. Denote −1 C as a unitary implementation of P, and A is an adversary that Q-breaks G(C,C ) , A |ϕ⟩ = Tr1 ((⟨0| ⊗ 1)Aunitary |ϕ⟩ |0η ⟩). Then S (·) must query Aunitary or its inverse; that is, using not only the first output qubits of Aunitary , or querying on some non-zero ancilla input, or querying A−1 unitary . 37

The proofs are essentially equivalent to Lemma 5.4. We will only prove Lemma 5.7. Proof of Lemma 5.7. Suppose G(·) and S (·) are QPT algorithms as in the definition of fully black-box construction with isometry access. Then G(C,Cisometry ) is an implementation of Q, and for any adversary (A, Aisometry ) that Q-breaks G(C,Cisometry ) , S (A,Aisometry ) P-breaks (C, Cisometry ); that is, (C, S (A,Aisometry ) ) ∈ RP . By the definition of IsometryP, (C, Cisometry , S (A,Aisometry ) ) ∈ RIsometryP . Therefore, S (A,Aisometry ) IsometryP-breaks C. Suppose for contradiction that S (·) does not query Aisometry . Then S A IsometryPbreaks C, so (G(·) , S (·) ) is a fully black-box construction of Q with channel access to IsometryP. That leads to contradiction. It is worth mentioning that the difference of P and the primitives introduced in Definition 5.5 is only meaningful from the black-box point of view. In the real world, if the primitive P exists, then the primitives in Definition 5.5 also exist, though there may not be a fully black-box way to construct IsometryP from P. Although in principle the situation in Lemmas 5.7, 5.8, or 5.9 could happen, and the black-box reduction can access the full adversary rather than only the first qubit, it is hard to give an instance of such situation. In fact, all fully black-box constructions known to the authors use the adversary as a channel. We argue by the following lemma that even in the oracle world, our point of view in terms of primitives is consistent with the point of view in terms of type of access in [CCS25]. Lemma 5.10. Under an isometry oracle O (resp. unitary oracle, unitary oracle and its inverse), if P exists, then IsometryP (resp. UnitaryP, InverseAccessP) exists. Proof. We will prove the statement for an isometry oracle O; the respective statement follows by replacing “isometry" in the proof with the corresponding terms. The primitive P exists under the isometry oracle O. By Definition 5.1, there exists a secure QPT algorithm C O that queries O, and C O ∈ FP . By the definition of a QPT algorithm, there exists a uniform family of quantum circuits of polynomial size, the gates in which are either the universal gates or queries to O. Since O is an isometry, and the universal gates are unitaries with inverse access, this family of circuits is a QPT isometry implementation of C O under the oracle O. The security of IsometryP is equivalent to the security of P. Therefore, we get a secure QPT implementation of IsometryP under the isometry oracle O. So, what does our separation result mean in the real world? It shows, there is no fully black-box construction to stretch the length of 1PRS by an arbitrary polynomial, if we have the isometry access to the generator of the 1PRS, and the channel access to the adversary. Thus we can conclude that any construction of long-stretching 1PRS from short-stretching 1PRS must be either non-black-box or with a stronger blackbox access model: the construction of the long-stretching 1PRS must use the code of the short-stretching 1PRS, or use the ancilla and/or the inverse of the generation algorithm.

References [AGL24]

Prabhanjan Ananth, Aditya Gulati, and Yao-Ting Lin. Cryptography in the common haar state model: Feasibility results and separations. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography - 22nd International Conference, TCC 2024, Milan, Italy, December 2-6, 2024, Proceedings, Part II, volume 15365 of Lecture Notes in Computer Science, pages 94–125. Springer, 2024. 4, 7, 8, 17

[AGQY22]

Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. Pseudorandom (functionlike) quantum state generators: New definitions and applications. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part I, volume 13747 of Lecture Notes in Computer Science, pages 237–265. Springer, 2022. 3

[BBO+ 25]

Mohammed Barhoush, Amit Behera, Lior Ozer, Louis Salvail, and Or Sattath. Signatures from pseudorandom states via ⊥-prfs. In Goichiro Hanaoka and Bo-Yin Yang, editors, Advances in Cryptology - ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, VIC, Australia, December 8-12, 2025, Proceedings, Part VIII, volume 16252 of Lecture Notes in Computer Science, pages 320–349. Springer, 2025. 3

[BCHJ+ 21]

Fernando GSL Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill. Models of quantum complexity growth. PRX Quantum, 2(3):030316, 2021. 3

[BCN25]

John Bostanci, Boyang Chen, and Barak Nehoran. Oracle separation between quantum commitments and quantum one-wayness. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part VII, volume 15607 of Lecture Notes in Computer Science, pages 3–22. Springer, 2025. 4

[BCQ23]

Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023, volume 251 of LIPIcs, pages 24:1–24:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 3

[BCWdW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87:167902, Sep 2001. 13 [BFNV19]

Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15(2):159–163, 2019. 3

[BHMV25]

Samuel Bouaziz–Ermann, Minki Hhan, Garazi Muguruza, and Quoc-Huy Vu. On limits on the provable consequences of quantum pseudorandomness. Cryptology ePrint Archive, 2025. 4

[BM24]

Samuel Bouaziz–Ermann and Garazi Muguruza. Quantum pseudorandomness cannot be shrunk in a black-box way. Cryptology ePrint Archive, Paper 2024/291, 2024. 3

[BMM+ 25]

Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. A new world in the depths of microcrypt: Separating owsgs and quantum money from QEFID. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part VII, volume 15607 of Lecture Notes in Computer Science, pages 23–52. Springer, 2025. 4 39

[Bra23]

Zvika Brakerski. Black-hole radiation decoding is quantum cryptography. In Annual International Cryptology Conference, pages 37–65. Springer, 2023. 3

[BT71]

W. S. Brown and Joseph F. Traub. On euclid’s algorithm and the theory of subresultants. J. ACM, 18(4):505–514, 1971. 45

[Can01]

Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, October 14-17, 2001, pages 136–145. IEEE Computer Society, 2001. 6

[CCC+ 25]

Bruno Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, and Xingjian Li. A meta-complexity characterization of minimal quantum cryptography. arXiv preprint arXiv:2510.07859, 2025. 3, 4, 6

[CCS25]

Boyang Chen, Andrea Coladangelo, and Or Sattath. The power of a single haar random state: Constructing and separating quantum pseudorandomness. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part VII, volume 15607 of Lecture Notes in Computer Science, pages 108–137. Springer, 2025. 1, 3, 4, 6, 7, 10, 17, 34, 35, 36, 37, 38

[CGG24]

Kai-Min Chung, Eli Goldin, and Matthew Gray. On central primitives for quantum cryptography with classical communication. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VII, volume 14926 of Lecture Notes in Computer Science, pages 215–248. Springer, 2024. 3

[CSBH25]

Laura Cui, Thomas Schuster, Fernando Brandao, and Hsin-Yuan Huang. Unitary designs in nearly optimal depth, 2025. 4

[Dur19]

Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019. 14

[EFL+ 24]

Netta Engelhardt, Åsmund Folkestad, Adam Levine, Evita Verheijden, and Lisa Yang. Cryptographic censorship. arXiv preprint arXiv:2402.03425, 2024. 3

[GJMZ23]

Sam Gunn, Nathan Ju, Fermi Ma, and Mark Zhandry. Commitments to quantum states. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1579–1588. ACM, 2023. 4

[GZ25]

Eli Goldin and Mark Zhandry. Translating between the common haar random state model and the unitary model. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part II, volume 16001 of Lecture Notes in Computer Science, pages 269–300. Springer, 2025. 4, 5, 12

[Har05]

Aram W. Harrow. Applications of coherent classical communication and the schur transform to quantum information theory, 2005. 45

[JLS18]

Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part III, volume 10993 of Lecture Notes in Computer Science, pages 126–152. Springer, 2018. 1, 3, 13

[KNY08]

Masaru Kada, Harumichi Nishimura, and Tomoyuki Yamakami. The efficiency of quantum identity testing of multiple states. Journal of Physics A: Mathematical and Theoretical, 41(39):395309, 2008. 8, 13, 16, 25, 45

[KP23]

Isaac H Kim and John Preskill. Complementarity and the unitarity of the black hole s-matrix. Journal of High Energy Physics, 2023(2):1–46, 2023. 3

[Kre21]

William Kretschmer. Quantum pseudorandomness and classical complexity. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2021, Virtual Conference, July 5-8, 2021, volume 197 of LIPIcs, pages 2:1–2:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. 3, 15, 18

[KT24]

Dakshita Khurana and Kabir Tomer. Commitments from quantum one-wayness. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 968–978. ACM, 2024. 3

[Lan12]

Serge Lang. Algebra, volume 211. Springer Science & Business Media, 2012. 43

[Led01]

Michel Ledoux. The concentration of measure phenomenon. Number 89. American Mathematical Soc., 2001. 15

[LV24]

Romi Levy and Thomas Vidick. Prs length expansion, 2024. 4

[MY22]

Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I, volume 13507 of Lecture Notes in Computer Science, pages 269–295. Springer, 2022. 3, 13, 30, 32

[MY24]

Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. In Frédéric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, Okinawa, Japan, September 9-13, 2024, volume 310 of LIPIcs, pages 4:1–4:21. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2024. 3

[Rob55]

Herbert Robbins. A remark on stirling’s formula. The American mathematical monthly, 62(1):26–29, 1955. 21

[SHH25]

Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth. Science, 389(6755):92–96, 2025. 4

[WB24]

Adam Bene Watts and John Bostanci. Quantum event learning and gentle random measurements. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, January 30 - February 2, 2024, volume 287 of LIPIcs, pages 97:1–97:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. 16

[Yan22]

Jun Yan. General properties of quantum bit commitments (extended abstract). In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part IV, volume 13794 of Lecture Notes in Computer Science, pages 628–657. Springer, 2022. 3

[Zha25]

Mark Zhandry. How to model unitary oracles. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part II, volume 16001 of Lecture Notes in Computer Science, pages 237–268. Springer, 2025. 4

Time Complexity of Our Attack

A.1

Computing V in Lemma 4.4

The time complexity of our attack essentially depends on finding the isometry V corresponding to a large unitary G, as in Lemma 4.4. However, Lemma 4.4 guarantees only the existence of the isometry V corresponding to G. We need to actually compute the linear isometry V , in order to use it in our future analysis. Let us first review the proof of Lemma 4.4. It states that for any ! s O ⊗r(i) |Θ⟩ = ⊗ |0⟩⊗t |θi ⟩ i=1

as the input of G, where |θi ⟩ =

P2i −1 j=0

G |Θ⟩ =

xij |j⟩, the resulting state G |Θ⟩ is always of the following form

m −1 2d −1 2X X

k=0

where |ζ⟩ =

m −1 2X

Akl (· · · , xij , · · · ) |k⟩ |l⟩ = |ζ⟩ ⊗ |ζ̃⟩

l=0

pk (· · · , xij , · · · ) |k⟩

|ζ̃⟩ =

d −1 2X

ql (· · · , xij , · · · ) |l⟩

l=0

k=0

Akl , pk , ql are homogeneous polynomials of the coefficients xij and d is the length of the state |ζ̃⟩. The key to compute V is that it suffices to find the coefficients of pk . Since we have already proved the i −1 existence of V , for every i ∈ [s], pk is homogeneous of degree ℓ(i) for every set of variables {xij }2j=0 . Thus, counting the degree of the polynomial pk , one can immediately get the parameters ℓ(i). i i We shall view xij as the dual element of the vector |j⟩ ∈ C2 . Define Polyℓ(i) C2 as the vector space i consisting of all degree-ℓ(i) homogeneous polynomials over C2 . Then, it is known that16 i

Polyℓ(i) C2 ∼ = Symℓ(i) (C2 )∨ = (Symℓ(i) C2 )∨ and the isomorphism is given by (xi0 )n0 (xi1 )n1 · · · (xi2i −1 )n2i −1 ∨



 i,ℓ(i)  7→ c · Πsym |0⟩ ⊗ · · · ⊗ |0⟩ ⊗ |1⟩ ⊗ · · · ⊗ |1⟩ ⊗ · · · ⊗ |2i − 1⟩ ⊗ · · · ⊗ |2i − 1⟩ | {z } | {z } {z } | n0 times

n1 times

n2i −1 times

(see, for instance, [Lan12, Chapter XVI, Section 8]). As one may notice, the right side is the dual of a Schur basis in the ℓ(i)-th symmetric tensor space. 2i −1 Since for every i ∈ [s], pk is homogeneous of degree ℓ(i) for every set of variables {xij }j=0 , pk can be Ns i seen as a multilinear form, thus a dual element of i=1 Symℓ(i) C2 , and each monomial in pk is dual to 16

For a linear space H, we use (H)∨ to denote its dual space.

N i a Schur basis of si=1 Symℓ(i) C2 . Therefore, writing pk as the sum of monomials immediately gives the k-th row of the matrix of V with the domain represented in the Schur basis. The polynomials Akl can be easily calculated, if one computes every entry of the matrix corresponding to the generator G. This computation requires exponential time in the number of qubits that G acts on. Once we have the exact representation of G, we can start searching for the polynomials pk using the equations given by G |Θ⟩ = |ζ⟩ ⊗ |ζ̃⟩, that is, for all k, l: Akl = pk ql . One way to compute the polynomials pk is by calculating for every k the polynomial greatest common d divisor (GCD) of {Akl }2l=0−1 . Indeed, we have the following lemma. Lemma A.1. For every k, let p̄k = gcd(Ak0 , Ak1 , · · · , Ak(2d −1) ). Then p̄k = Ck pk , where Ck is a constant (that does not depend on xij ). d

Proof. Consider a fixed k ∈ {0, 1}m . The polynomials {Akl }2l=0−1 have a common factor pk . Therefore, p̄pkk is a polynomial, with variables xij . We denote this polynomial by ∆k . Therefore, p̄k = ∆k pk . We have Akl = pk ql =

p̄k ql . ∆k

Since p̄k is a common factor of {Akl }2l=0−1 , ∆qlk is also a polynomial for every l. So, ∆k is a common d

factor of {ql }2l=0−1 , so it must be a common factor of {Ak′ l : 0 ≤ k ′ ≤ 2m − 1, 0 ≤ l ≤ 2d − 1}. Next we show that any common factor of {Ak′ l : 0 ≤ k ′ ≤ 2m − 1, 0 ≤ l ≤ 2d − 1} must be a constant. Indeed, by linearity, all the entries of G† (G |Θ⟩) = |Θ⟩ must be linear combinations of the polynomials Ak′ l . Thus, since each ∆k is a common divisor of all Ak′ l , then each ∆k must be a common divisor of the entries of |Θ⟩. But   ⊗r(i)  i −1 s 2X O   ⊗t  |Θ⟩ =  xij |j⟩  ⊗ |0⟩ . i=1

j=0

This means that the entries of |Θ⟩ consist of every polynomial of the form (x1j1 )r(1) (x2j2 )r(2) · · · (xsjs )r(s) , where jν ∈ {0, 1, . . . , 2ν − 1} for every ν ∈ [s]. The greatest common divisor of this type of polynomials is known to be a constant. By Lemma A.1, in order to compute the isometry V , it only needs to compute the multivariate polynomial GCD classically.17 This can be done by a sufficiently powerful classical pre-processing Turing machine. Let Gen(·) be a QPT oracle algorithm whose runtime is bounded by T (n), a polynomial in n. By T (n) definition, GenO can be simulated in time 22 . Our adversary AO simulates this process, and gains T (n) a quantum circuit G, where G runs on 2poly(n) qubits for at most 22 steps. To compute the matrix T (n) poly(n) corresponding to G we essentially have to compute the product of 22 matrices, each of size 22 . poly(n) 2 That can be done in time 2 . After that, we substitute the input to the circuit by a vector of monomials. The output vector is of poly(n) poly(n) poly(n) dimension 22 , each entry being a polynomial of 2poly(n) variables, 22 terms, and degree 22 . 17

Note that we need to compute the coefficients symbolically and accurately; this can be done by choosing a proper set of the universal gate set, for example {Toffoli, H ⊗ H}, where the coefficients of both gates are rational.

It turns out that a very conservative complexity bound for computing the GCD of N polynomials of T variables and degree D requires time O(Dpoly(T ) poly(N, D, T )), by the subresultant algorithm [BT71]. poly(n) Therefore, our algorithm requires 22 time to compute the polynomial GCD, and can be run inside O2 .

A.2

Implementing the Projective Measurement Πk in Equation (9)

In the previous section, we discussed how to compute Uk explicitly. This computation result is a matrix, whose domain is represented in the Schur basis. We need to convert that into the computational basis, so that the Permutation test in [KNY08] can be easily implemented. Note that there are two projections on the right hand side of Equation (9): the orthogonal projection Qk and the Permutation test Πsym . The measurement {Πk , 1 − Πk } can be implemented as follows: e † , perform the projective measurement Qk , apply Vsch,k , and perform the projective measurement apply U k Ns(n) (i,ℓ(k,i)+22i/5 +8n) corresponding to the Permutation test i=1 Πsym . The result of the measurement {Πk , 1−Πk } is the AND of both projective measurements. First, we need to implement the projective measurement Qk . This can be done by an (invertible) classical computation: Qk compares a number with 2m − a(k), and accepts if that number is less than 2m − a(k). Ns(n) i Next, we need to split a state in i=1 Symℓ(i,k) C2 into different registers, each register corresponds to i a space (C2 )ℓ(i,k) , but the elements in each register are represented in the Schur basis. This is also classical: a standard divide-and-modular algorithm suffices to do this conversion. i And finally, we need to convert each register (C2 )ℓ(i,k) from a state represented in the Schur basis to the computational basis. This is the inverse of the Schur transformation [Har05]. Combining these methods, we get an efficient circuit implementation of Vsch Qk . The circuit implementation of Permutation tests can be found on [KNY08], which uses only exponentially many gates and only polynomially many ancillas (in the number of registers).

Record · ID 303144 · SHA-256 3a51b7360c90a56c
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.