=1

=1

=1

=1

1 Introduction↩︎

In classical cryptography, computational pseudorandomness generated by pseudorandom generators (PRGs) and functions (PRFs) serves as a central resource. It can be used for many applications, such as commitments [1], digital signatures [2], and symmetric key encryptions. Furthermore, the existence of PRGs and PRFs is necessary for the existence of almost all cryptographic primitives with computational security, including one-way functions (OWFs) [3].

However, when we treat the world as operating under the laws of quantum mechanics, the notion of pseudorandomness must be revisited. Ji, Liu, and Song [4] proposed the first two inherently quantum pseudorandom primitives, pseudorandom state generators (PRSGs) and unitaries (PRUs). Quantum pseudorandomness has been shown to be useful for constructing many (quantum) cryptographic primitives, for example, PRSGs imply quantum commitments and oblivious transfers [5], [6]. On the other hand, Kretschmer showed that PRSGs and PRUs (with super-logarithmic output lengths) are potentially weaker primitives than classical pseudorandomness by presenting an oracle separation [7]. The dramatic interest in fundamentally quantum cryptographic primitives emerged as a new cryptographic direction possible even in the world without one-way functions.

Quantum pseudorandomness turns out to be quite different from its classical counterparts. To begin with, the length becomes an important parameter in quantum cryptography. Given an \(\lambda\)-bit input seed, [8] shows that \(c\log \lambda\)-length output PRSGs exist unconditionally for \(c\ll1\) whereas achieving \(c\ge1\) requires computational assumptions. We name \(c\log \lambda\)-length and superlogarithmic-length PRSGs by short PRSGs and long PRSGs, respectively. [9], [10] shows that long PRSGs cannot be used to construct short PRSGs, highlighting that the output lengths of PRSGs cannot be shrunk. Note that in the classical setting, the output length of PRGs can easily be shrunk and lengthened arbitrarily.

Contrary to the long PRSGs that are separated from classical cryptography, [11] shows that short PRSGs can be used to construct a variant of PRGs called pseudodeterministic quantum-computable PRGs (QPRGs) with an inverse-polynomial pseudodeterminism error. A QPRG \(G\) with an \(\varepsilon\) error is a QPT algorithm that, on \((1-\varepsilon)\)-fraction of the input seed, outputs the same value with probability \(1-\varepsilon\).³ When \(\varepsilon\) is negligible, we simply call \(G\) a QPRG. With an inverse-polynomial \(\varepsilon\), one can construct digital signatures and IND-CPA encryptions [12], although the proof technique is more complicated than the classical one.

[11] questioned if the error \(\varepsilon\) of QPRG can be reduced to be negligible. If it is possible, virtually classical Minicrypt can be recovered using the same technique. Thus, our main question is:

In particular, if the answer is affirmative, long PRSGs can be constructed from short PRSGs through QPRGs by using known constructions [4], [13]. Yet, if the answer is no, there is still a possibility of lengthening PRSG outputs without relying on classical cryptographic primitives, thus we ask:

We also consider another difference between classical and quantum in the landscape of pseudorandomness. For example, we do not know how to construct PRUs from PRSGs or even pseudorandom function-like state generators (PRFSGs) [6], [14], whereas classically PRGs can be used to construct PRFs and vice versa. We are left with an unsatisfactory state of affairs; unlike in classical pseudorandomness, there is no single assumption unifying quantum pseudorandomness. This makes us ask:

1.1 Our results↩︎

We provide negative evidence for the above questions by presenting new oracle worlds where one primitive exists, but the other does not exist, or at least is hard to construct, by showing that some natural constructions are insecure. Our results suggest that quantum pseudorandomness could behave fairly differently from classical pseudorandomness.

1.1.0.1 Common Haar function-like state model.

All of our separations are based on variants of the common Haar function-like state (CHFS) oracles where for each input \(x\in \{0,1\}^*\) the oracle outputs a Haar⁴ random state \(\ket{\phi_x}\) of length \(\ell(|x|)\) where \(|x|\) is the bit-length of \(x\). Note that this is an isometry. We also consider the unitary variants that instantiate this oracle.

Since the construction of PR(F)SGs with output length \(\ell(|x|)\) is straightforward with these oracles, our main contribution is to show that many other primitives are hard to construct even with the CHFS oracle (or its variants).

1.1.0.2 Separating QPRGs from short PRFSGs.

Using the CHFS oracles, we negatively answer the open problem of [11].⁵

Note that with the negligible errors, the classical constructions work well even for the quantum-computable counterparts. Therefore, this theorem says that QPRGs, as well as quantum-computable one-way functions (QOWFs) and quantum-computable pseudorandom functions (QPRFs), constructed from quantum primitives must suffer from inverse polynomial errors, as in the typical constructions using tomography.

This theorem has several interesting implications. First, it complements the classical–quantum cryptography separation of [7] along two incomparable dimensions. On the classical side, [7] considers primitives with perfect correctness (in particular, OWFs)⁶, whereas our separation continues to hold even when the primitive is allowed to have a negligible correctness error. On the quantum side, [7]’s separation requires long output length (in particular, \(\omega(\log \lambda)\)-length PRUs), while our oracle separation works even for short PRSGs. Thus, our result shows that the gap between classical and quantum cryptography persists even when correctness is relaxed and the quantum pseudorandomness assumption has a significantly shorter output length.

Secondly, it can be interpreted as finding a quantum-computable version of Pessiland, where there are hard-on-average languages in \(\mathbf{QCMA}\cap \mathbf{coQCMA}\) yet there are no QPRGs. To show this, we choose \(\ell = O(\log \lambda)\) and consider a state version of the decisional permutation inversion problem [16] that decides if the given input \(({\sf str},z)\) satisfies \(x\le z\) where \({\sf str}\) specifies a state \(\ket{\psi_{\sf str}}\) that is sufficiently close to the CHFS oracle’s output state \(\ket{\phi_x}\) for some \(x\). By appropriately choosing the output length \(\ell\), the uniqueness of \(x\) is ensured with overwhelmingly high probability. This result strengthens the worst-case hardness \(\mathbf{BQP}\neq \mathbf{QCMA}\) in a relativized world [9], [10]. We outline this language in 10. In the classical setting, [17] found a Pessiland oracle.⁷

On the other hand, however, we found that this oracle world is not too pessimistic. Recall that PRSGs with output length \(c\log \lambda\) for large enough \(c\) can be used to construct digital signatures and IND-CPA encryptions, with classical keys and outputs, using the notion of recognizable aborts [12]. This gives the following corollary in the world of quantum-computable classical-communication (QCCC) cryptography [10], which was separated from (classical-computable) classical cryptography in [18].⁸

We found this interesting, as it shows that OWFs and PRGs are stronger than the main applications, encryptions and signatures. This is possible because internal randomness in quantum machines cannot be extracted as random coins, unlike randomness in classical machines as observed in several previous works [19]–[22]. Consequently, our separation also separates efficiently-verifiable one-way puzzles (EV-OWPuzz) from QOWFs, confirming the belief of [10] that EV-OWPuzz could be the central primitive for QCCC cryptography.⁹ We refer the reader to 1 for further implications that can be derived from our main theorem.

1.1.0.3 On constructing PRUs from PRFSGs, without ancilla registers.

Finally, we study the hardness of constructing PRUs from PRFSGs. We prove that any candidate PRU whose generation algorithm does not use ancillary register fails to be secure. The formal statement is as follows.

Our oracle consists of the CHFS oracle for \(\ell(|x|)=|x|\) and the \(\mathbf{QPSPACE}\) oracle that computes the unitary polynomial-space circuit given as input. We believe the black-box separation between PRFSGs and PRUs without the no-ancilla condition also holds in the same oracle world, and leave this open question for future work.

Our impossibility shows that even the strongest form of PRFSGs cannot be used to construct the weakest form of PRUs in a black-box way without using ancillary registers.¹¹

This theorem, together with the potential extension, answers the first question negatively. If we draw an analogy between quantum and classical primitives—meaning that PRFSGs are somehow quantum counterparts of PRFs while PRUs are analogous to pseudorandom permutations (PRPs)—then our result highlights a drastic difference between quantum pseudorandomness and its classical counterparts, as we can construct PRPs from PRFs [24].

1.1.0.4 Length extension of PRSGs.

We now turn to the problem of extending the output length of PRSGs. There are already many approaches with some partial positive answers to this problem as summarized below. We consider another natural class of length extensions, including the extension algorithm that takes small PRSs non-adaptively as input and applies a unitary (e.g., \(G_k \to U_k(\ket{\phi_1}\otimes \ket{\phi_2})\) for smaller PRSs \(\ket{\phi_1},\ket{\phi_2}\)).

In fact, our result is stronger: any PRSG length extension of this form is impossible.¹² Moreover, the impossibility of long PRSGs also holds with adaptive queries for a certain type of algorithm that revert the ancilla to \(0\).

The proof for the adaptive queries requires new observations on the purity test, i.e., the swap test on two copies, for the state generated by the quantum algorithms we consider. We also include in 14 a possible path to extend the result to general algorithms with classical queries, which may give new insights into the purity of states generated by algorithms.

We note that there are still multiple ways to extend the length of PRSGs that our result does not cover. Two notable approaches¹³ showing that some PRSG length extensions are possible as follows:

• Construct QPRGs first using tomography [11] (with inverse polynomial errors) and then use them to construct new PRSGs. In [22], the authors show that the PRSG length extension is possible in the log-length regime, albeit with quantum key sampling (i.e., the keys are not uniformly distributed but quantumly sampled). This strategy is excluded from our result because of the no partial trace condition. Partial progress to construct long PRSGs from short PRSGs was also discussed in the same paper.

• Use quantum queries to the oracle. This is excluded because of our classical-accessible oracle model. In fact, for a length-\(\ell\) PRSG \(\{\phi_k\}\), the state \(\ket{0}\ket{\phi_a} + \ket{1}\ket{\phi_b}\) for two random keys \(a,b\) forms a length-\((\ell+1)\) PRSGs.

We believe the above strategies, allowing length extension up to log-length, are optimal.¹⁴ The full impossibility of PRSG length extension would complement the impossibility of shrinking the output length of PRSGs [9], [10], and suggests that both primitives are in fact incomparable. Moreover, given the construction of one-way state generators (OWSGs) from short PRSGs [26], [27], it provides evidence for the hardness of constructing PRSGs from OWSGs, while the other direction is possible [27]. The PRSG length extension may be the most challenging among the problems discussed in this paper. Any progress on this problem seems to give new interesting techniques.

A summary of our results is given in 1. =[-Stealth[length=3mm],thick,black] =[Stealth[length=3mm]-Stealth[length=3mm],thick,black] =[dotted,-Stealth[length=3mm],thick,black] =[dotted,-Stealth[length=3mm],thick,red] =[dotted,-Stealth[length=3mm],thick,orange] =[fill=white,midway]

1.2 Related works↩︎

1.2.0.1 Quantum oracle models.

The isometry CHFS oracle was first studied in [28] to show the (isometry oracle) separation between QCCC primitives and PRSGs. Recent works suggest different quantum oracle models. The common Haar state model [28], [29] represents a world where copies of a random single Haar random quantum state are easily generated. A similar model without restricting Haar randomness was also studied in [30]–[32]. The quantum Haar random unitary oracle model (QHROM) was suggested in [33], [34], and the applications are studied in [35], [36].

1.2.0.2 Quantum black-box impossibility.

Recently, various black-box impossibilities have been shown based on new oracles and new techniques. We briefly summarize this line of research.¹⁵ The separation between OWFs and quantum primitives relative to a quantum oracle [7] initiated this direction, and the same oracle later was shown to imply the hardness of shrinking PRSG output lengths [9], [10]. This result was later strengthened relative to a classical oracle [37] albeit for weaker quantum primitives. A separation between classical and quantum-computable OWFs is shown in [18].

Relative to the common Haar state oracles, various separations are implied, e.g., commitments (and EFI pairs [21]) and single-copy PRSGs exist but no OWSGs and (multi-copy) PRSGs [29], [38], [39]. In [38], they also show a black-box separation between quantum money and EFI pairs.

The isometry version of CHFS oracle provides a world with PRFSGs but without QCCC primitives [28]. On the other hand, an oracle world with QCCC key exchange where \({\boldsymbol{B}QP}={\boldsymbol{Q}CMA}\) holds was introduced in [40], with some more separations.

Finally, a very recent work [22] shows the black-box impossibility of constructing OWSGs from \(\bot\)-(Q)PRGs (that can be seen as a weaker version of the QPRGs with negligible correctness errors, see [12]). A difference between quantum sampling of the keys and uniformly random keys is also explored in the same paper; in this work, we only assume the uniform key setting.

1.2.0.3 Concurrent work.

A concurrent and independent work [41] shows the oracle separation between PRFSGs and PRUs using similar oracles but with different techniques. They also consider the separations regarding the pseudorandom isometries [42]. The full separations remain open as both papers consider the bounded-length ancilla. The results about the log-length CHFS oracles are unique to this paper.

=1

1.2.0.4 Acknowledgments.

We thank Takashi Yamakawa for the helpful discussion on the definition of \(\mathbf{QPSPACE}\) oracle, and Shoga Yamada and Yao-Ting Lin for noting a minor error in the previous version. MH is supported by Schmidt Sciences Polymath award to David Soloveichik. SBE is supported by PEPR integrated project EPiQ ANR-22-PETQ-0007 part of Plan France 2030 and by ANR JCJC TCS-NISQ ANR-22-CE47-0004.

In the previous version of this work, 10 was left as a geometric conjecture. We managed to prove this conjecture using tools from differential geometry and isoperimetric inequalities, with the assistance of ChatGPT 5.1 Thinking. The proof in this paper is fully written by the authors, yet the main idea is from ChatGPT 5.1 Thinking. =1 A more detailed log of the interactions with ChatGPT that supported the proof is provided in [app:chat_log].

2 Technical overview↩︎

2.0.0.1 (Unitarized) Common Haar function-like state oracles and PRFSGs.

All of our results are in a relativized world with (variants of) the common Haar function-like state (CHFS) oracles. The CHFS oracles with length \(\ell\) are defined as follows: it is a family of unitaries \(\{S_x\}_{x\in\{0,1\}^*}\) defined as follows: \[S_x: \begin{cases} \ket{0}\to \ket{\phi_x} & \\ \ket{\phi_x}\to \ket{0} & \\ \ket{\psi}\to \ket{\psi} & \text{ if }\ket{\psi} \notin {\sf span}(\ket0 ,\ket{\phi_x}), \end{cases}\] where \(\ket{\phi_x}\) is a predetermined Haar random state of length \(\ell(|x|)\), with \(|x|\) denoting the bit-length of \(x\). This oracle is inspired by the reflection/swap oracles in [29], [39].

In this overview, we assume that the algorithm accesses the unitaries \(S_x\) one by one, and also assume that \(\braket{0}{\phi_x}=0\) for simplicity, so that \(S_x\) can be understood as a reflection \[S_x= I - 2\ketbra{\phi_x-},\] where \(\ket{\phi-}=\frac{\ket0 -\ket{\phi_x}}{\sqrt2}.\)

The construction of PRFSGs with the CHFS oracles is rather straightforward: the generation algorithm, on input \((k,x)\) for key \(k\) and input \(x\) of length \(\lambda\), outputs \(\ket{\phi_{k||x}}\) by querying \(S_{k||x}\), where \(k||x\) is the concatenation of \(k\) and \(x\). Note that the output length of the PRFSGs is \(\ell(k||x)\). The security can be shown by the standard reduction to the unstructured search problem.

2.1 Separating QPRGs from short PRFSGs↩︎

We show that relative to some CHFS oracles with output length \(\ell(n)\), together with the PSPACE oracle, PRFSGs with output length \(\ell\) exist but QPRGs do not. But first, we discuss a technical hurdle we met.

2.1.0.1 Concentration inequality fails.

The concentration inequality for Haar measure (see 5) is the most common tool currently used for oracle separations. However, when the oracle outputs only \(\ell(n)=\Theta(\log n)\) qubits, the ambient dimension is too small (because \(2^\ell = \poly[n]\)) for these bounds to force the type of “almost-everywhere” behavior needed to rule out QPRGs.

We instead start from an extreme concentration phenomenon that any QPRG must satisfy. Consider a single-bit-output QPRG \(G^O\) relative to CHFS oracles \(O\) with negligible errors. For any fixed seed \(x\), the output distribution of \(G^O(x)\) must be almost deterministic for all but a negligible fraction of oracles \(O\): equivalently, defining \(f(O)=\Pr[G^O(x)\to 1]\), we must have \(f(O)\approx 0\) or \(f(O)\approx 1\) for almost all \(O\). These are the two extreme points in the concentration inequality. A natural question is thus whether these two extreme points can be simultaneously concentrated.

2.1.0.2 The new Barrier theorem.

We ask the following question: if \(f(O)\in[0,1]\) has substantial mass near both \(0\) and \(1\), what can we say about the geometry of the preimages \(f^{-1}([0,\varepsilon])\) and \(f^{-1}([1-\varepsilon,1])\) in oracle space? If \(G^O(x)\) for a fixed \(x\) can output both \(0\) and \(1\) with non-zero probability, both pre-image regions are large. We also expect the distance between the two pre-image regions to be large, since close oracles would likely induce close outputs. Our Barrier theorem (10) asserts that under such conditions, the intermediate region \(f^{-1}((\varepsilon,1-\varepsilon))\) must itself be large:

Now we turn back to the QPRGs \(G^O\) with negligible pseudodeterminism error. Leveraging the Barrier theorem, our key observation is that with such strong pseudodeterminism, for a fixed seed \(x\) the output cannot meaningfully depend on the CHFS oracles, otherwise we would see a noticeable “intermediate” mass of oracles where the output is not deterministic. In more detail, consider the first output bit of \(G^O\) denoted by \(G_1^O\) and let \(f(O)=\Pr_G[G_1^O(x)\to 1]\). The Barrier theorem rules out the case where \(S_0=f^{-1}([0,\varepsilon])\) and \(S_1=f^{-1}([1-\varepsilon,1])\) are both large, because it leads that \(G^O\) is not pseudodeterministic on the too large barrier \(X\setminus(S_0\cup S_1)\). This leads to a dichotomous intuition: either

1. \(G_1^O\) is not pseudodeterministic, or

2. \(G_1^O\) is essentially constant independent of \(O\).

That is, \(G_1^O\) must fail to achieve pseudodeterminism or security.

It turns out that this intuition is not quite true. One of the reasons is that the barrier theorem, even if the second statement miserably failed, only shows that the first statement holds only for a mildly large fraction of \(O\). A more correct dichotomy is as follows, considering all output bits. For a fixed security parameter, one of the following holds:

1. \(G^O\) is not pseudodeterministic on a (slightly) large fraction of \(O\), or

2. \(G^O\) outputs a fixed value for a (very) large fraction of \(O\).

We make an observation for each case. For the first case, we observe that the PRFSG construction \(\mathsf{Gen}:(k,x)\to\ket{\phi_{k||x}}\) is still secure even if we choose \(O\) from a slightly smaller sub-distribution of the product Haar random distributions (at parameter \(\lambda\)). It means we may hope to choose \(O\) such that \(\mathsf{Gen}\) is a secure PRFSG yet \(G\) is not pseudodeterministic.

For the second case, we observe that \(G^O\) can be estimated by \(G^{O'}\) for randomly chosen \(O'\), in which case we know how to simulate without querying \(O\) using known techniques.¹⁶ Let \(F\) be the simulated function, then given input \(y\), determining if there is \(x\) such that \(F(x)\) can be done in polynomial space (i.e., with the PSPACE oracle), breaking the pseudorandomness of \(G^O\).

Based on this observation, we sample oracle \(O\) (at parameter \(\lambda\)) depending on which case occurs: If \(G_i^O\) is pseudodeterministic with high probability over \(O\) for all \(i\), we just sample \(O\) from the product Haar random distribution, breaking the pseudorandomness. For the other case, the dichotomy says that a (slightly) large fraction of \(O\) makes \(G^O\) not pseudodeterministic, thus we sample \(O\) among one that makes \(G^O\) not pseudodeterministic yet \(\mathsf{Gen}\) is secure, given that the fractions for \(G\) not being pseudodeterministic are larger than the fractions for insecure \(\mathsf{Gen}\). This is indeed possible by adjusting parameters.

This, however, only ensures that a single candidate \(G\) is insecure or not pseudodeterministic at a single parameter. Our final proof of 1 proceeds by diagonalization, considering all uniform oracle-aided QPRG candidates \(\{G_j\}_{j\in\mathbb{N}}\) as follows.

1. Define \(\{G'_j\}_{j\in\mathbb{N}}\) so that for each \(i\) there are infinitely many \(j\)’s such that \(G_i=G'_j\) holds. For example, one can consider \(\{G_i\}_i\) as \(G_1,G_1,G_2,G_1,G_2,G_3,\dots\).

2. Choose a super-fast-growing sequence of security parameters \(\{\lambda_i\}_{i\in\mathbb{N}}\) (e.g. \(\lambda_{i+1}=2^{\lambda_i^{200}}\)) and blocks of oracle input lengths \(I_i=[\log(\lambda_i),\lambda_i^{100}]\) that are disjoint.

   Intuitively, the properties of \(G'_i\) at parameter \(\lambda_i\) essentially depend only on the oracle with input lengths in \(I_i\). This is because \(G'_i(1^{\lambda_i},\cdot)\) may never query too large input length \(|x|>\lambda_i^{100}\), and for the query \(|x|<\log (\lambda_i)\), it can be efficiently estimated by the adversary using tomography.

3. Fix an oracle \(O_{<i}\) up to input length \(<a_i\). Over the random choice of \(O\) with respect to the input length in \(I_i\), the dichotomy holds: either \((G'_i)^O\) is not pseudodeterministic with high probability over \(O\), or \((G'_i)^O\) can be simulated with high probability over \(O\) so that it is insecure. We sample \(O\) over the input length in \(I_i\) as above, according to which case occurs.

4. Proceed to the next block after sampling \(O\), by fixing \(O<{i+1}\).

The above procedure results in an oracle \((O,\mathbf{PSPACE})\) relative to which \(\mathsf{Gen}\) is a secure PRFSG, while any QPRG candidate \(G\) must be infinitely often insecure or infinitely often non-pseudodeterministic. Note that in the actual proof, we need to consider each oracle QPT adversary \(\mathcal{A}\) instead of the one-shot security argument of \(\mathsf{Gen}\), which further complicates the argument.

2.2 Separating PRUs without ancilla from PRFSGs↩︎

We consider the unitary CHFS oracles with output length \(\ell(n)=n\). As discussed above, we can easily construct PRFSGs relative to this oracle, but breaking the PRU constructions is quite involved. We sketch the outline of the proof here.

2.2.0.1 Breaking PRUs without ancilla.

To establish 2, we present an explicit attack for any PRU candidate without ancilla with respect to the CHFS oracle of length \(\ell(n)=n\).

We consider the following simplified form of the PRU algorithm \(\{G_k\}_{k\in \{0,1\}^*}\) on key \(k\in \{0,1\}^\lambda\) and input state \(\ket{\psi}\): \[G_k:\ket{\psi} \mapsto U^{(k)}_T\cdot S_{x_T^{(k)}} \cdot U^{(k)}_{T-1} \cdot \ldots \cdot U^{(k)}_1 \cdot S_{x_1^{(k)}} \cdot U^{(k)}_0 \ket{\psi},\] where \(U^{(k)}_T,\dots,U^{(k)}_0\) are some unitaries and \(S_{x_T^{(k)}},\dots,S_{x_1^{(k)}}\) are the CHFS oracle queries. In the main body of the paper, we consider a more general form of \(G_k\) that may include some intermediate measurements, and queries may be in superposition or adaptive.

Our main observation is as follows: for a Haar random state \(\ket{\rho}\) independently chosen from the oracle, the application of the reflection oracle does not change the state much, i.e., \[\begin{align} \label{eqn95intro:approx95ref} S_x \ket{\rho} \approx \ket{\rho}. \end{align}\tag{1}\] This is because the reflection \(S_x\) only makes a change on the tiny space spanned by \(\{\ket{\phi_x},\ket{0}\}\). Therefore, one may argue that \[G_k\ket{\rho} \approx U^{(k)}_T\cdot U^{(k)}_{T-1} \cdot \ldots \cdot U^{(k)}_1 \cdot U^{(k)}_0 \ket{\rho}\] because \(\ket{\rho_t} := U^{(k)}_t \cdot ...\cdot U^{(k)}_0 \ket{\rho}\) is a Haar random state independent of the oracle due to the invariant property of Haar measure. Unfortunately, this is not the case in general, as the loss in 1 is proportional to \(1/2^{|x|}\), so we cannot ignore \(S_x\) for small \(|x|\).

We instead learn all \(S_x\) to obtain \(S'_x\) for small \(|x|\) using process tomography [43]. We define \(\tilde{S}_x\) by \(S'_x\) for small \(|x|\) and \(I\) for large \(|x|\), and define \[F_k:\ket{\psi} \mapsto U^{(k)}_T\cdot \tilde{S}_{x_T^{(k)}} \cdot U^{(k)}_{T-1} \cdot \ldots \cdot U^{(k)}_1 \cdot \tilde{S}_{x_1^{(k)}} \cdot U^{(k)}_0 \ket{\psi}\] which now satisfies \(F_k\ket{\rho} \approx G_k\ket{\rho}\).

Now we describe the adversary that given oracle \(V\), distinguishes whether it is one of \(\{G_k\}\) or a true Haar random unitary. The adversary first prepares \(\Phi=(\ket{\rho}\otimes V\ket{\rho})^{\otimes M}\) for some large \(M\) and Haar random state \(\ket{\rho}\) (or a \(t\)-design for sufficiently large \(t\)) and defines:

\(P_k\):

on input \(\Phi=(\ket{\rho}\otimes V\ket{\rho})^{\otimes M}\), it applies \((F_k\otimes I)^{\otimes M}\), applies \(M\) swap tests on each copy; if sufficiently many copies pass the swap test, it returns 1. Otherwise, it returns 0.

We can show that \(P_k\) returns \(1\) if \(V=G_k\) with high probability, but \(P_k\) almost always returns \(0\) if \(V\) is a Haar random unitary. This satisfies the setting where the quantum OR tester [44] can be run with the \(\mathbf{QPSPACE}\) oracle¹⁷ as observed in [29]. By augmenting our world with the \(\mathbf{QPSPACE}\) oracle, we obtain a relativized world where PRFSGs exist but PRUs without ancilla do not, proving 2.

The attack even breaks the non-adaptive PRU security as \(V\) is only used to prepare \(\Phi\). Extending this to the quantum-accessible PRFSGs security requires considering the coherent version of CHFS oracles, which can be similarly done with some more computation.

=1 Due to space limitations, the formal presentation of this result is deferred to 6.

2.3 Length extension of PRSGs↩︎

Finally, we consider the output length extension for PRSGs. We first consider a simple but natural form with nonadaptive queries, and then discuss how to extend it to the adaptive case.

2.3.0.1 Non-adaptive case.

We again consider the CHFS oracle with \(\ell(|x|)=\lfloor\log |x|\rfloor\) together with the \(\mathbf{QPSPACE}\) oracle. Here, we consider the classical-accessible isometry version: a family of isometries \(\{O_x\}_{x\in \{0,1\}^*}\) where \(O_x\) takes input \(\ket{0}\) and outputs an \(\ell(|x|)\)-qubit Haar random state \(\ket{\phi_x}\). We do not allow querying the other input states.

We first consider the PRSGs that make nonadaptive queries to the oracle. Consider the following PRSG candidate that outputs on key \(k\) \[\label{eqn:32UsmallPRS} \rho_k = U_k \left(\ket{\phi_{x_1^{(k)}}}\otimes\dots\otimes \ket{\phi_{x_t^{(k)}}}\otimes \ket{0^*}\right),\tag{2}\] where we assume that the parameter \(t\) and the lengths of \(x_i^{(k)}\)’s are all the same for different keys for simplicity in this overview. Here \(\ket{\phi_{x_1^{(k)}}}\),…,\(\ket{\phi_{x_t^{(k)}}}\) are shorter PRSG outputs. We have that the state \[U_k^\dagger \rho_k = \ket{\phi_{x_1^{(k)}}}\otimes \dots\otimes \ket{\phi_{x_t^{(k)}}}\otimes \ket{0^*}\] is a product of many pure states. On the other hand, for a Haar random state \(\ket\psi\), \(\tilde{U}_k^\dagger \ket\psi\) definitely does not have such a product structure, as it is also Haar random by definition. Given the efficient product test algorithm [45], we can run the quantum OR tester with the \(\mathbf{QPSPACE}\) oracle as in the separation between PRUs and PRFSGs.

We remark that the separation in the CHS model [29] assumes non-adaptive queries to the oracle by default, without loss of generality. This can be done because there is only a linear number of oracles. As we have exponentially many oracles, we cannot make queries to all of them. We must consider adaptive queries, which introduce numerous technical difficulties. Another difficulty stems from the possibility of PRSGs with slightly mixed states.

2.3.0.2 Dealing with adaptive queries.

Now we explain how to deal with adaptive queries in similar PRS generation algorithms. Our observation is that the pseudorandom states must be close to pure because they are indistinguishable from Haar random states, which are always pure. This intuition can be formalized by observing that the swap test on two copies estimates the purity \(\require{physics} \Tr(\rho^2)\).

Our main technical tool here is that if a state \(\rho\) generated by an algorithm without partial traces passes this test with high probability, then all the intermediate projective measurements must be almost deterministic. The formal statement can be found in 15. Furthermore, recalling the implication of the Barrier theorem (4): if a quantum algorithm with access to the short CHFS oracle \(O\) outputs a fixed bit with high probability, then this bit is likely independent of \(O\). Therefore, we can apply the same strategy to learn the intermediate measurement outcomes. This allows the algorithm to fix the query inputs a priori. With some more work, we manage to show that any adaptive query PRS generation algorithm can be approximated with non-adaptive queries (see 2 ). Then, the same attack strategy applies.

The formal proof considers more general algorithms allowing partial traces that remove \(\ket{0^*}\). =1 Due to space limitations, the formal presentation of this result is deferred to 7. For the general ancillary registers possibly not \(\ket{0^*}\), we give some structural results in 14. These results are not sufficient to rule out general PRS length extension, but we believe they are interesting in their own right.

3 Preliminaries↩︎

3.0.0.1 Notations.

We use \(\lambda\in \mathbb{N}\) to denote the security parameter. For any \(m \in \mathbb{N}\), we use the notation \([m]\) to refer to the set \(\{1, \ldots, m\}\). For any finite set \(U\), we write \(x \gets U\) to denote that \(x\) is sampled uniformly at random from \(U\). For a distribution \(\mathcal{D}\), \(x\gets \mathcal{D}\) denotes that \(x\) is sampled from \(\mathcal{D}\). For a bit string \(x \in \left\{0,1\right\}^{*}\), we denote its bit-length by \(|x|\). We assume that all functions used to represent the lengths of the cryptographic primitives are QPT-computable. We assume the reader is familiar with the basics of quantum computation, and refer to [46] otherwise. We will also use standard notations from quantum information and cryptography.

3.1 Quantum states, channels, and trace↩︎

A \(d\)-dimensional quantum state is a positive semi-definite Hermitian density matrix \(\rho = \sum_{x\in[d]} p_x\ketbra{\phi_x}\), where the pure states \(\ketbra{\phi_x}\) have trace one, and \(p_1,\dots,p_d\) is a probability distribution, i.e., \(p_1,\dots,p_d \ge 0\) and \(p_1+\dots+p_d=1\). Pure states are the rank-1 quantum state that can be written as \(\ketbra{\phi}\). We sometimes write \(\ket{\phi}\) or just \(\phi\) to denote the pure state \(\ketbra{\phi}\) for simplicity. We can consider any positive semi-definite Hermitian matrix (with arbitrary unit trace) as an unnormalized quantum state, e.g., \(\Pi \rho \Pi\) for some projection \(\Pi\) and quantum state \(\rho\), and call them unnormalized states.

A quantum channel \(\Phi\) is a completely positive and trace-preserving operator, that can be represented by matrices \(B_1,\dots,B_k\) satisfying \[I-\sum_{i=1}^k B_i^\dagger B_i \ge0.\]

The matrices \(B_1,\dots,B_k\) are the Kraus operators of the channel, and with this notation, \(\Phi\) maps a quantum state \(\rho\) to \(\Phi(\rho) = \sum_{i=1}^k B_i \rho B_i^\dagger\). Quantum channels can represent unitary operations, projective measurements, or applying a projection \(\Pi\). We write the composition of two quantum channels \(\Phi,\Psi\) by \(\Phi\circ\Psi.\) For a unitary \(U\), the corresponding channel is represented by \(U(\rho)=U \rho U^{\dagger}\) or sometimes the calligraphic font \(\mathcal{U}(\rho)\).

The trace norm of a Hermitian matrix \(A\) is defined by \(\|A\|_1 := \sum_{i=1}^d |\lambda_i|\), where \(\lambda_1,\dots,\lambda_d\) are the eigenvalues of \(A\). If \(A\) is positive semi-definite, we can write \(\require{physics} \|A\|_1 = {\Tr(A)}.\) This induces the trace distance \(\|\rho-\sigma\|_{tr} = \frac{1}{2}\|\rho - \sigma\|_1\) between two (possibly unnormalized) mixed states, which forms a distance over (unnormalized) mixed states. A quantum channel \(\Phi\) does not increase the trace norm. That is, for any Hermitian matrix \(A\), it holds that \(\|\Phi(A)\|_1 \le \|A\|_1\). In particular, we have \(\require{physics} \Tr(\Phi(A)) \le \Tr(A)\) for any positive semi-definite matrix \(A\). For any two (possibly unnormalized) states \(\rho,\sigma\), \[\begin{align} \label{eqn:channel95does95not95decrease95trace95distance} \|\Phi(\rho)-\Phi(\sigma)\|_{tr}=\frac{1}{2}\|\Phi(\rho-\sigma)\|_1 \le \frac{1}{2}\|\rho-\sigma\|_1 = \|\rho-\sigma\|_{tr}. \end{align}\tag{3}\]

For a positive semi-definite matrix \(A\), it holds that \[\require{physics} \begin{align} \label{eqn:32TrA2} \Tr(A^2) \le \Tr(A)^2. \end{align}\tag{4}\]

We stress that most of the facts on the trace norm and distance also hold for unnormalized states, i.e., positive semi-definite Hermitian matrices.

3.2 Haar random states and unitaries↩︎

We write \(\mathbb{S}(N)\) and \(\mathbb{U}(N)\) to denote the set of \(N\)-dimensional pure quantum states and the group of \(N \times N\) unitary matrices. We denote by \(\sigma_{n}\) and \(\mu_n\) the Haar distribution over \(n\)-qubit states and \(n\)-qubit unitaries, i.e., over \(\mathbb{S}(2^n)\) and \(\mathbb{U}(2^n)\), respectively. When the dimension is clear from the context, we drop the parameter and use \(\sigma\) or \(\mu\). The Frobenius norm \(\|A\|_F\) of a matrix \(A\) is defined by \(\require{physics} \sqrt{\Tr(A^\dagger A)}.\)

In [7], the following statement is shown.

This lemma ensures that \(C\) is \(m\)-Lipschitz, thus applying 5, we obtain the desired result.

We simply write \(0\) to denote \(0^{m-n}\). We can write \(\mathbb{E}_{\ket{\phi} \gets \sigma_n} \bra{\phi,0}\Pi\ket{\phi,0}\) by \[\require{physics} \mathbb{E}_{\ket{\phi} \gets \sigma_n}\Tr(\Pi\cdot\ketbra{\phi,0} ) =\Tr(\Pi\cdot \frac{I\otimes \ketbra{0}}{2^{n}} ) \le \frac{1}{2^n}\Tr(\Pi) = \frac{D}{2^n},\] where the last equality follows from the fact that \(\Trace(\Pi) = \rank(\Pi)\). If \(m=n\), the inequality is saturated. The last statement can be shown by writing \(\rho = \sum_i p_i \ketbra{\psi_i}\) for \(\sum_i p_i=1\).

3.3 Cryptographic primitives↩︎

We define cryptographic primitives relative to an oracle \(O\).

From now on we will use PRSGs to refer to long PRSGs and short PRSGs for logarithmic output.

We by default consider the adaptively-secure PRFSGs defined as follows.

For pseudorandom unitaries, we only consider the super-logarithmic output length and without inverse oracle access. Unlike [4], we allow PRUs to not be unitary.

We also define quantum pseudorandom generators (QPRGs), which are algorithms whose output is indistinguishable from random, and is always the same with probability negligibly close to one.

=0

3.4 QPSPACE oracle↩︎

We recall the definition of the QPSPACE oracle that implements the arbitrary unitary operation described by polynomial size input [29], [38].

The quantum access to the QPSPACE oracle is done by allowing coherent \((M,t)\). For any unitary quantum circuit \(C\) that is output by a machine \(M\) after \(t\) steps, there is a QPT algorithm with \(\mathbf{QPSPACE}\) oracle that implements \(C^{-1}(\rho)\) on input \(\rho\) [38].

3.5 State property tests↩︎

3.5.1 Swap test↩︎

We review the basic results of the swap test, which can be used to test the purity of a state. We provide some lemmas about the swap test on a state that is close to pure states, which are essential to obtain our results.

For two quantum states \(\sigma,\rho\) stored in two different registers \({\mathbf{A}},{\mathbf{B}}\), the swap test is executed on the registers \({\mathbf{A}},{\mathbf{B}}\) and a control register \({\mathbf{C}}\) initialized to \(\ketbra{1}\). It applies Hadamard on \({\mathbf{C}}\), swaps \({\mathbf{A}}\) and \({\mathbf{B}}\) conditioned on \({\mathbf{C}}\), and measures \({\mathbf{C}}\) on the Hadamard basis.

When \(\sigma=\rho\), we sometimes call it a on \(\rho\), which outputs \(1\) with certainty if and only if \(\rho\) is a pure state.

Note that each test succeeds with probability \(\require{physics} (1+\Tr(\rho^2))/2\le 1-1/2T\), and is independent of each other. Applying Chernoff’s inequality (9) for \(\delta=1/2\), we obtain the desired result.

3.5.2 Product test↩︎

We first recall the product test to determine whether an \(n\)-partite state \(\ket{\phi}\) is a product state or far from any product state from [45], then give a bound on the success of the product test on Haar-random states.

For Haar-random states, the above formula is explicitly calculated for any partition \(S\cup\overline{S}\) of \([m]\) by [48]: \[\require{physics} \underset{\ket{\psi}\gets\sigma}{\mathbb{E}}\Tr[\rho_S^2]=\frac{d_S+d_{\overline{S}}}{d_S\cdot d_{\overline{S}}+1}.\] =1 As a consequence, we have the following bound for the success of the product test on Haar-random states, whose proof is given in 13.1. As a consequence, we have the following bound for the success of the product test on Haar-random states.

=0 =1 For every partition \(S\cup\overline{S}\) of \([m]\), the local dimension of each partition is given by \(d_S=\prod_{i\in S}d_i\). \[\require{physics} \begin{align} \underset{\ket{\psi}\gets\sigma}{\mathbb{E}}\Pr(1\gets\mathcal{A}_\mathtt{PTEST}(\ket{\psi}^{\otimes 2}))& =\underset{\ket{\psi}\gets\sigma}{\mathbb{E}}\left[\frac{1}{2^m}\sum_{S\subseteq[m]}\Tr[\rho_S^2]\right] \\ &=\frac{1}{2^m}\sum_{S\subseteq[m]}\frac{d_S+d_{\overline{S}}}{d_S\cdot d_{\overline{S}}+1}\le \frac{1}{2^m}\sum_{S\subseteq[m]}\frac{d_S+d_{\overline{S}}}{d_S\cdot d_{\overline{S}}} \\&=\frac{1}{2^m}\left(\sum_{S\subseteq[m]}\frac{1}{d_S} + \frac{1}{d_{\overline{S}}}\right) =\frac{2}{2^m}\left(\sum_{S\subseteq[m]}\frac{1}{d_S} \right) \\&=\frac{2}{2^m}\prod_{i\in[m]} \left(1+\frac{1}{d_i}\right) \leq \frac{2}{2^m}\prod_{i=1}^m\left(\frac{3}{2}\right)=2\left(\frac{3}{4}\right)^m, \end{align}\] where we use the fact that each \(d_i\geq 2\) to obtain the last inequality.

3.6 Quantum OR lemma↩︎

3.7 Useful lemmas↩︎

We have \(\|\mathcal{M}(\rho)-\Pi_0\rho\Pi_0\|_{tr}=\|\Pi_1\rho \Pi_1\|_{tr}\le \varepsilon,\) which gives the result.

3.7.1 Norms and Process tomography.↩︎

For a matrix \(M\), the operator norm is defined by \[\|M\|_{op}:= \sup_{\|\ket{\phi}\|_2=1} \|M\ket{\phi}\|_2,\] which satisfies \(\|M+N\|_{op}= \max(\|M\|_{op},\|N\|_{op})\) if \(M\) and \(N\) act on the orthogonal space. In particular, for \(M=\sum_x \ketbra{x} \otimes M_x\), it holds that \[\begin{align} \label{eqn:operator95norm95maximum} \|M\|_{op} = \max_{x} \|M_x\|_{op}. \end{align}\tag{5}\]

The diamond norm of an operator \(A\), denoted by \(\|A\|_\diamond\), is defined by: \[\require{physics} \|A(\cdot)\|_\diamond:= \sup_{\Tr(\rho)=1,\rho \ge 0} \|A\otimes I(\rho)\|_1,\] where \(I\) denotes the identity acting with the same dimension as \(A\). We sometimes omit \((\cdot)\) if it is clear from the context. We use the following fact about the diamond norm: for quantum channels \(A,B\) and a density matrix \(\rho\), it holds that \[\|A\otimes I(\rho) - B\otimes I(\rho)\|_{tr} \le\frac{1}{2} \|A(\cdot) -B(\cdot) \|_\diamond.\] We will also use the fact that for unitaries \(U,V\) and the corresponding channels \(\mathcal{U},\mathcal{V}\), it holds that \[\label{eqn:32diamond95bound95by95operator95norm} \|\mathcal{U}(\cdot) - \mathcal{V}(\cdot) \|_\diamond \le 2 \|U-V\|_{op}\tag{6}\] for the operator norm \(\|\cdot\|_{op}\) because \[\require{physics} \begin{align} \|\mathcal{U}(\cdot) - \mathcal{V}(\cdot)\|_\diamond & =\sup_{\Tr(\rho)=1,\rho \ge 0} \|(U\otimes I)(\rho)(U^\dagger \otimes I)-(V\otimes I)(\rho)(V^\dagger \otimes I)\|_1 \\ & \le \sup_{\Tr(\rho)=1,\rho \ge 0} \|(U-V)\otimes I\|_{op} \|\rho\|_1 \|U^\dagger \otimes I\|_{op} + \|V\otimes I\|_{op} \|\rho\|_1 \|(U^\dagger- V^\dagger) \otimes I\|_{op} \\&\le 2\|U-V\|_{op} \end{align}\] where we use \(\|A\rho B\|_1 \le \|A\|_{op} \|\rho\|_1 \|B\|_{op}\).

3.7.2 Chernoff bounds.↩︎

We use the following concentration inequalities.

4 Common Haar Function-like State Oracles↩︎

4.1 CHFS oracles and unitarization↩︎

We first recall the definition of swap (or reflection) oracles [29], [39].

We proceed to define the length-\(\ell\) common Haar-random function-like state (CHFS) oracle and its “unitarized” oracle. We fix a (QPT-computable) function \(\ell: \NN \to \NN\) representing the output length for each oracle, where we typically consider \(\ell(\lambda)=\Theta(\log \lambda)\) or \(\ell(\lambda)= \lambda\). We define two versions of the CHFS oracles as follows.

The (length-\(\ell\)) CHFS model is defined as follows. The randomness \(\Phi\) is chosen as an initialization. We note that the sets of randomness \(\Phi\) used to define the isometry and unitarized CHFS oracles are the same. We omit the superscript \(\Phi\) if the context makes it clear. Then, all parties have oracle access to the CHFS oracle \(O=O^\Phi\) or \(S=S^\Phi\). We call this the log-length CHFS model for \(\ell(\lambda) = \bigO{\log \lambda}\), and the standard CHFS model for \(\ell(\lambda) = \omega{\log \lambda}\).¹⁹

We call it the state (or isometry) CHFS model when the oracle is \(O^\Phi\), and the unitary (or swap/reflection) CHFS model when the oracle is \(S^{\Phi}\). We, however, occasionally use \(O\) to denote the (any) CHFS oracle if the context is clear.

4.2 Construction of PRFSGs in the CHFS model↩︎

We show that PRFSGs with output length \(\ell\) exist in the length-\(\ell\) CHFS model. Again, we stress that the PRFSGs are adaptively-secure by default. We only prove the uniform security here, and we can upgrade the classical advice adversaries following, e.g., [7].

We define the following \((\kappa,m,\ell)\)-PRFSGs. We explain the construction in the isometry CHFS model, but modifying it to the unitary CHFS model is obvious.

\(\mathsf{Gen}^O(k,\cdot)\):

On the \(m\)-qubit input register \({\boldsymbol{X}}\), it applies the map \[\ket{x}_{\boldsymbol{X}} \to \ket{x}_{\boldsymbol{X}}\otimes\ket{\phi_{k,x}}.\] This is done by, on input \(\rho_{\boldsymbol{X}Z}\), appending the \(\kappa\)-qubit register \(\ket{k}_{\boldsymbol{K}}\) and making a query to the oracle \(O^\Phi\) on the register \({\boldsymbol{K}X}\) and discarding the registers \({\boldsymbol{K}}\).

We have that \(|k|+|x|=m+\kappa=\poly\) thus \(\mathsf{Gen}\) can be implemented by a BQP algorithm with a single query to the CHFS oracle with \(m+\kappa\) length input.

We claim that this construction is a secure PRFSG. More precisely, we prove the following statement: For any algorithm \(A\) that makes \(q\) queries, it holds that \[\left|\Pr\left[ A^{\mathsf{Gen}(k,\cdot),O}\to 1 \right] -\Pr\left[ A^{G_{\sf Haar}(\cdot),O}\to 1 \right] \right| = \bigO{\frac{q^2}{2^\kappa}},\] where \(G_{\sf Haar}(x)\) outputs an \(\ell\)-qubit Haar random state \(\ket{\psi_x}\). When we consider the classical-accessible model, the upper bound becomes \(\bigO{q/2^\kappa}\).

This is done by reducing it to an unstructured search (cf. [7]). Formally, we consider a quantum oracle algorithm \(B^s\) for \(s\in \{0,1\}^{2^\kappa}\) as follows. Let \(\lambda':=\kappa+m.\) \(B\) samples independent \(\ell\)-qubit Haar random quantum states \(\ket{\tilde{\phi}_z}\) for each \(z\in\{0,1\}^{\lambda'}\) and \(G_{\sf Haar}(\cdot)\) as defined in 2. After the initialization, \(B\) runs \(A\), but the queries to the first oracle are answered by \(G_{\sf Haar}(\cdot)\), and the query \(z=(k',x) \in \{0,1\}^{\lambda'}\) for any \(x\) to the second oracle is answered by \(G_{\sf Haar}(x)\) if \(s_{k'}=1\) and \(\ket{\tilde{\phi}_z}\) if \(s_{k'}=0\).

Let \(e_k\) be the all-0 string except for the \(k\)-th entry \(1\), then it holds that =1 \[\begin{align} & \left|\Pr_{O}\left[ A^{\mathsf{Gen}(k,\cdot),O}\to 1 \right] -\Pr_{O,G_{\sf Haar}}\left[ A^{G_{\sf Haar}(\cdot),O}\to 1 \right] \right| \\ & =\left|\Pr_{k}\left[ B^{e_k}\to 1 \right] -\Pr\left[ B^{0^\kappa}\to 1 \right] \right| =\bigO{\frac{q^2 }{2^\kappa}} \end{align}\] \[\begin{align} \left|\Pr_{O}\left[ A^{\mathsf{Gen}(k,\cdot),O}\to 1 \right] -\Pr_{O,G_{\sf Haar}}\left[ A^{G_{\sf Haar}(\cdot),O}\to 1 \right] \right| =\left|\Pr_{k}\left[ B^{e_k}\to 1 \right] -\Pr\left[ B^{0^\kappa}\to 1 \right] \right| =\bigO{\frac{q^2 }{2^\kappa}}, \end{align}\] where the last inequality holds because of the BBBV theorem [16]. In particular, this implies that \[-2^{-\kappa/2}\le \mathbb{E}_O\left[\Pr\left[ A^{\mathsf{Gen}(k,\cdot),O}\to 1 \right] -\Pr_{G_{\sf Haar}}\left[ A^{G_{\sf Haar}(\cdot),O}\to 1 \right]\right] \le 2^{-\kappa/2}\] for large \(\lambda.\) By Markov inequality, \[\Pr_O\left[\left| \Pr\left[ A^{\mathsf{Gen}(k,\cdot),O}\to 1 \right] -\Pr_{G_{\sf Haar}}\left[ A^{G_{\sf Haar}(\cdot),O}\to 1 \right]\right| \ge 2^{-\kappa/4}\right] \le 2\cdot 2^{-\kappa/4}.\] Because \(\kappa=\omega(\log \lambda)\), \(\sum_\lambda 2\cdot 2^{-\kappa(\lambda)/4}\) converges and Borel-Cantelli lemma ensures that, with probability 1 over \(O\), \[\left| \Pr\left[ A^{\mathsf{Gen}(k,\cdot),O}\to 1 \right] -\Pr_{G_{\sf Haar}}\left[ A^{G_{\sf Haar}(\cdot),O}\to 1 \right]\right| \le 2^{-\kappa/4}\] holds for all but finitely many \(\lambda\in \mathbb{N}.\) As there are only countably many adversaries \(A\) with polynomially many queries, this concludes the existence of the PRFSGs in the isometry CHFS model. The security proof for the unitary CHFS model works by replacing \(O\) with \(S\).

5 Oracle Separation of QPRGs from PRFSGs↩︎

This section presents a separation between QPRGs and PRFSGs with various output lengths.

In the proof of this theorem, we use a novel geometric theorem about the product Haar measure on states, which we call the barrier theorem. We first present the oracle space which we work on, then present the barrier theorem and its proof in 5.1. The proof of the main separation is in 5.2.

5.0.0.1 Oracles and PRFSGs.

Fix \(\ell\le \lambda\) such that \(\ell=\Omega(\log \lambda)\). We consider the length-\(\ell\) unitary CHFS oracle \(O=O^{\Phi}\) for \(\Phi=\{\ket{\phi_x}\}_{x\in \{0,1\}^*}\)²⁰ sampled from a specific distribution to be specified and the \(\mathbf{PSPACE}\) oracle for a fixed PSPACE-complete problem.

We consider the following PRFSGs suggested in 4.2 with \(\kappa=m=\lambda\):

\(\mathsf{Gen}^O(k,x)\):

It outputs \(\ket{\phi_{k,x}}\).

We excerpt the following lemma from the proof of 8 for later use. The final statement is proven using the series \(\sum_{i=n}^{\infty} a^i = a^n/(1-a)\) for \(a=2^{-1/4}\).

5.1 The barrier theorem↩︎

Let \(X=\mathbb{S}(2^{n_1})\times \cdots \times \mathbb{S}(2^{n_k})\) be the product space of quantum states equipped with the product Haar measure \(\sigma:=\sigma_{n_1}\times \cdots \times \sigma_{n_k}\). For two elements \(\Phi=(\ket{\phi_1},\ldots,\ket{\phi_k}),\Psi=(\ket{\psi_1},\ldots,\ket{\psi_k})\) in \(X\), we define the max-trace distance \(d_{tr}(\Phi,\Psi)\vcentcolon=\max_{i\in [k]} \|\phi_i - \psi_i\|_{tr}\). For two subsets \(S,T\) of \(X\), we define their distance as \(d_{tr}(S,T):=\inf_{\Phi\in S,\Psi \in T} d_{tr}(\Phi,\Psi)\).

We will show the following theorem.

Intuitively, 10 states that if two sets have a distance gap between them, then there must be a non-negligible barrier of the whole space that they do not cover regardless of their shape.

5.1.0.1 Proof overview.

A worst-case candidate is to take a very small \(S_0\) and the maximal \(S_1\) subject to the conditions. Given this, a natural approach is

1. to show that the surface area of \(S_0\) or larger regions is bounded below, say by \(\varepsilon\);

2. to “integrate” the surface area along a path from \(S_0\) to \(S_1\) of length \(\Delta\), obtaining a \(\Omega(\varepsilon\Delta)\) lower bound.

This approach indeed works with some results from differential geometry. The most technical part is [item195con95overview], which is formalized by the notion of Cheeger isoperimetric constant. Roughly, the Cheeger isoperimetric constant \(h_X\) ensures that:

given \(\sigma(S_0),\sigma(S_1)\ge \Gamma\). This yields a lower bound of \(h_X \Gamma \Delta\).

The proof is completed by showing the dimension-free lower bound of \(h_X\). To do so, we use the results of Lichnerowicz and Buser, which assert that the Ricci curvature lower bound \(\mathbf{Ric}_X \ge c\cdot g_X\) for \(c>0\) implies the lower bound \(h_X =\Omega(\sqrt{c})\), where \(g_X\) is the Riemannian metric of the ambient space. The condition can be easily shown using some basic properties of the Ricci curvature of the product space (8 ). This differential geometric analysis shows the result for the \(\ell_2\) of the arc-cosine distance, and the desired result with the max-trace distance follows by simple calculation.

=1 The formal proof is given in 9. The formal proof is given below.

Recall that \(\mathbb{S}(2^n) = \mathbb{CP}^{2^n-1}\) denotes the space of \(n\)-qubit quantum states, i.e., the \(2^n\)-dimensional complex projective space. Our theorem is stated as follows. For two elements \(\Phi=(\ket{\phi_1},\ldots,\ket{\phi_k}),\Psi=(\ket{\psi_1},\ldots,\ket{\psi_k})\) in \(X=\mathbb{S}(2^{n_1})\times \cdots \times \mathbb{S}(2^{n_k})\), the max-trace distance is defined by \(d_{\infty}(\Phi,\Psi)\vcentcolon=\max_{i\in [k]} \|\phi_i - \psi_i\|_{tr}\).

5.1.0.2 Distances.

We consider various distances of quantum states. For two pure states, the trace distance is \[d_{tr}(\phi,\psi) = \|\phi -\psi\|_ {tr} = \sqrt{1-|\braket{\phi}{\psi}|^2}.\] In the complex projective space \(\mathbb{CP}^{n}\), the Fubini-Study (geodesic) distance, also known as the standard angle distance, is defined by \[d_{FS}(\phi,\psi) = \arccos|\braket{\phi}{\psi}|.\] We have \(d_{tr} (\phi,\psi)= \sin (d_{FS}(\phi,\psi)) \le d_{FS}(\phi,\psi)\) in \(\mathbb{S}(2^{n_i})\).

In the product space \(X\), we consider two distances. The first distance is the max-trace distance \(d_{\infty}\) defined above. The other distance is the \(\ell_2\) distance \[\begin{align} \label{eqn:defell2distance} d_2(\Phi,\Psi) = \sqrt{\sum_{i=1}^k d_{FS,i} (\phi_i,\psi_i)^2} \end{align}\tag{7}\] where \(d_{FS,i}\) is the Fubini-Study distance in \(\mathbb{S}(2^{n_i})\). We stress that the distance \(d_2\) is defined for the Fubini-Study distance, while \(d_\infty\) is defined for the trace distance. We will later use the following inequality: \[d_{\infty}(\Phi,\Psi) = \max_i d_{tr}(\phi_i,\psi_i) \le \max_i d_{FS}(\phi_i,\psi_i) \le d_2(\Phi,\Psi).\]

5.1.0.3 Riemannian manifolds and metrics, and Ricci curvature.

A Riemannian manifold is a pair of \((M,g)\), where \(M\) is a smooth manifold and \(g\) is a Riemannian metric²¹, which assigns a positive-definite symmetric bilinear form \(g_p: T_pM\times T_pM \to \mathbb{R}\) for each point \(p\in M\), where \(T_pM\) denotes the tangent space of \(M\) at \(p\). The Riemannian manifold gives rise to the geodesic distance \(d_g\). In the complex projective space \(\mathbb{CP}^{n}\), we define the Fubini-Study metric \(g_{FS}\) as the metric induced by the quotient \(\mathbb{S}^{2n+1}/\mathbb{S}\) with the standard Euclidean metric restricted to the unit hypersphere. The geodesic distance of \(g_{FS}\) is the Fubini-Study distance \(d_{FS}\) defined above. There is a natural notion of the products of Riemannian manifolds; the geodesic distance of the products of the projective spaces with the Fubini-Study metric gives the \(\ell_2\) distance defined in 7 . Looking ahead, we will prove the statement for \(d_2\) (instead of \(d_\infty\)) using the results from differential geometry below.

On the Riemannian manifold, the Ricci curvature tensor \(\mathbf{Ric}\) is uniquely determined and gives a symmetric bilinear form \(\mathbf{Ric}_p: T_pM\times T_pM \to \mathbb{R}\) for each point \(p\in M\). In the product of Riemannian manifolds \(S=\prod_{1\le i \le r}(M_i,g_i)\) and the point \({\boldsymbol{v}}=(v_1,...,v_r) \in S\), the Ricci curvature satisfies \[\begin{align} \label{eqn:Ricci95product} \mathbf{Ric}_S({\boldsymbol{v}},{\boldsymbol{v}}) = \sum_{i=1}^r {\mathbf{Ric}}_{M_i} (v_i,v_i). \end{align}\tag{8}\] The intrinsic Riemannian metric \({\boldsymbol{g}}=(g_1,...,g_r)\) satisfies a similar equality.

For a constant \(c\), we occasionally use the notation \[\begin{align} \label{eqn:Lic95condition} \mathbf{Ric}\ge c \cdot g \Longleftrightarrow \mathbf{Ric}_p - c\cdot g_p \geqslant 0~~ \forall p \in M \end{align}\tag{9}\] where \(\geqslant\) denotes the positive semi-definite inequality. Equivalently, it means \[\mathbf{Ric}_p(v,v) \ge c\cdot g_p(v,v)\] holds (as an inequality over real numbers) for all \(p \in M\) and \(v \in T_pM\). We note that \(\mathbf{Ric}\ge c \cdot g\) is usually denoted by \(\mathbf{Ric}\ge c\) in the literature.

We only use Riemannian manifolds and Ricci curvatures for our underlying space \(X=\mathbb{S}(2^{n_1})\times \cdots \times \mathbb{S}(2^{n_k})\) regarding the above relations, where we recall \(\mathbb{S}(2^{n})=\mathbb{CP}^{2^n-1}\). The complex projective space \(\mathbb{CP}^{n}\) satisfies \(\mathbf{Ric}=2(n+1) \cdot g_{FS}\) (i.e., an Einstein manifold) [51]. For our main interest \(X\) together with the product Fubini-Study metric, for \({\boldsymbol{v}} = (v_1,...,v_k) \in X\) it holds that \[\mathbf{Ric}_X({\boldsymbol{v}},{\boldsymbol{v}}) = \sum_{i=1}^k \mathbf{Ric}_{\mathbb{S}(2^{n_i})} (v_i,v_i) \ge \sum_{i=1}^k 2^{n_i+1}\cdot g_{FS,i}(v_i,v_i) \ge 4 \sum_i g_{FS,i} (v_i,v_i) = 4{\boldsymbol{g}}({\boldsymbol{v}},{\boldsymbol{v}}),\] which means \(X\) satisfies 9 for \(c=4.\)

Lichnerowicz’s theorem [52] states that (See e.g., [53]) for an \(n\)-dimensional compact Riemannian manifold \((M_n,g)\), if \(\mathbf{Ric}\ge c\cdot g\) for some \(c>0\), then the first nonzero eigenvalue of the Laplacian²² satisfies \[\begin{align} \lambda_1 \ge \frac{nc}{n-1} \ge c. \end{align}\] In particular, for \(X\) together with the product Fubini-Study metric, it holds that \[\begin{align} \label{eqn:minimum95nzeign} \lambda_1 \ge 4. \end{align}\tag{10}\]

5.1.0.4 Cheeger isoperimetric constant.

We use the modern exposition for isoperimetric inequalities from [54]. Consider a Riemannian manifold \((M,g)\) with the geodesic distance \(d\) and probability measure \(\sigma\) (i.e., \(\sigma(M)=1\)). We define the outer Minkowski boundary measure (or the area) of a measurable set \(E\) by \[\sigma^+(E)=\liminf_{r \downarrow 0} \frac{\sigma(E[r]) - \sigma(E)}{r}\] where \(E[r]:= \{p \in M: d(p,E)\le r\}\) is a closed neighborhood of \(E\). The Cheeger isoperimetric constant is \[\label{def:Cheeger} h_M := \inf_{E:\text{measurable}, 0<\sigma(E)<1} \frac{\sigma^+(E)}{\min(\sigma(E),1-\sigma(E))}.\tag{11}\]

Let \(\lambda_1\) be the smallest nonnegative eigenvalue of the Laplacian of \(M\). Buser’s inequality [55] says that if \(\mathbf{Ric}\ge -(n-1)a^2\) for some \(a\ge 0\), then it holds that \(\lambda_1\le 2a(n-1)h_M + 10h_M^2\). If \(\mathbf{Ric}\ge 0\), we have \(\lambda_1 \le 10h_M^2\). This implies that, for our \(X\), \[\begin{align} \label{eqn:32hXminimum} h_X \ge \sqrt{2/5} \end{align}\tag{12}\] holds because \(\mathbf{Ric}\ge 4 {\boldsymbol{g}} \ge 0\) in \(X\) and 10 .

5.1.0.5 Proof of 10.

We first work on the product space \(X\) together with the product Fubini-Study metric and the corresponding \(\ell_2\) distance \(d_2\). Let \(v(r):= \sigma(S_0[r])\) for \(0\le r\le \Delta\). Here, we assume that \(v\) is differentiable so that \(v'(r)=\sigma^+(S[r])\). This significantly simplifies the proof of 14 , and we provide the formal proof without this assumption in 9.1.

Note that in the definition of \(S_0[r]\) in \(X\), we use the natural distance \(d_2\) induced by the Riemannian manifold \(X\). Given the condition \(d_\infty(S_0,S_1) \ge \Delta\), we also have \(d_2(S_0,S_1) \ge d_\infty(S_0,S_1) \ge \Delta\). For any \(0\le r <\Delta\), \(S_0[r] \cap S_1 = \emptyset\) holds so that \(v(r)= \sigma(S_0[r]) \le 1-\sigma(S_1)\) and \(1-v(r) \ge \sigma(S_1) \ge \Gamma\). This implies \(\min(v(r),1-v(r)) \ge \Gamma.\)

The Cheeger constant ensures \[\label{eqn:v39lowerbound} v'(r) \ge h_X \min (v(r),1-v(r)) \ge h_X v(0) \ge h_X \Gamma.\tag{13}\] Integrating \(v'\) gives: \[\begin{align} \label{eqn:32after95integral} \sigma(S_0[\Delta]) - \sigma(S_0) = v(\Delta)-v(0) \ge \int_0^{\Delta} v'(r) dr \ge h_X \Gamma \Delta. \end{align}\tag{14}\] We also have \(\sigma(S_0[\Delta]) \le 1-\sigma(S_1)\) by taking \(r\to \Delta.\) This, together with 14 , gives: \[\sigma(X\setminus(S_0 \cup S_1))=1-\sigma(S_0) - \sigma(S_1)\ge \sigma(S_0[\Delta]) - \sigma(S_0) \ge h_X \Gamma \Delta\] where \(h_X \ge \sqrt{2/5}\) by 12 . This proves the desired result.

5.2 Impossibility of QPRGs↩︎

We can now prove the main result of this section.

We will construct (by diagonalization) a single unitary oracle \(O\) such that, relative to \((O,\mathbf{PSPACE})\), (i) short-PRFSGs exist for all sufficiently large \(\lambda\), yet (ii) no pseudodeterministic QPRG exists (i.e., for every candidate pseudodeterministic QPRG \(G\), there are infinitely many security parameters \(\lambda\) for which \(G\) is either non-pseudodeterministic or insecure). In the following, the unitary CHFS oracle \(S\) is indexed by an oracle-input length \(t\in\mathbb{N}\): on query inputs \(x\in\bin^t\) (possibly in superposition), the oracle applies a reflection \(S_{\ket{\psi_x}\ket{1}}\) on \(\ell(t)+1\) qubits (cf. 8).

Without loss of generality, we work in the uniform quantum circuit model with oracle gates for \(S\) and access to \(\mathbf{PSPACE}\). Thus, the set of uniform oracle-aided QPRG candidates is countable, and we fix an enumeration over these candidates as \(\{G_j\}_{j\in\NN }\). For each \(G_j\), let \(p_j(\lambda) = \poly\) be a polynomial upper bound on the running time of \(G_j(1^\lambda, \cdot)\) (including oracle queries). Fix a surjection \(u:\NN\to\NN\) such that every \(j\in\NN\) has infinitely many preimages:²³ \[\forall j\in\NN,\quad |\{i\in\NN : u(i)=j\}|=\infty.\] Intuitively, we diagonalize against the candidate \(G_{u(i)}\) at security parameter \(\lambda_i\).

We will define \(O\) for each index \(i \in \NN\). For index \(i\), we choose a security parameter \(\lambda_i\) and then fix the oracle \(O\) on a block of oracle-input lengths \(t\in I_i \mathrel{\vcenter{:}}= [a_i,b_i]\), which are defined as follows. Choose \(\lambda_1\) sufficiently large, and set \(\lambda_{i+1} \mathrel{\vcenter{:}}= 2^{2^{\lambda_i}}\) for \(i\ge 1\).

Define the parameters for each \(i\) as follows:

• \(\varepsilon_i (\lambda)\mathrel{\vcenter{:}}= \frac{d_i}{p_{u(i)}(\lambda)^8}\) for a constant \(d_i>0\) to be determined later.

• \(c_{i}\ge 1\) be a constant so that \(\lambda_i^2 \cdot 2^{-c_i/8} < \varepsilon_i(\lambda_i)\)

• \(a_i \mathrel{\vcenter{:}}= \left\lceil c_i \log \lambda_i\right\rceil\)

• \(b_i \mathrel{\vcenter{:}}= \max(p_{u(i)}(\lambda_i),\,a_i)\)

Note that \(b_i= \max(p_{u(i)}(\lambda_i),a_i)\) while \(a_{i+1}=\Theta(\log\lambda_{i+1})=\Theta(2^{\lambda_i})\), hence \(b_i<a_{i+1}\) for all \(i\), so the blocks \(I_i\) are disjoint and strictly increasing.

In the following, we assume that an oracle \(O_i\) is sampled so that it has the desired properties (to be explained) up to the \(i\)-th block. Our goal is to sample a new oracle that satisfies the properties up to the \((i+1)\)-th block, without hurting the previous blocks.

Let \(S^{(<t)}\) denote the restriction of \(O\) to oracle-input lengths \(<t\), and define the conditional distribution \(\mathcal{D}_{S^{(<t)}}\) in which we sample the CHFS oracles according to the product Haar random distribution conditioned on the fixed prefix \(S^{(<t)}\).

The procedure is as follows. Given \(O_i\), we fix \(S^{(<a_i)}\). This will never change in the later updates. We will sample \(O=O_{i+1}\) from \(\mathcal{D}_{S^{(<a_i)}}\). All probabilities below are with respect to this conditional distribution.

We fix an adversary \(\mathcal{A}\) for the PRFSG. Define the following event.

\(A_i{[\mathcal{A},O]}\):

This is the event that \(\mathcal{A}\) relative to \((O,\mathbf{PSPACE})\) against \(\mathsf{Gen}^O\) has an advantage at most \(2^{-\lambda/4}\) for the security game of PRFSGs with input length \(\lambda\) for all \(2\lambda\in [a_i,a_{i+1}-1] (\supset I_i)\).

By 10, we have: \[\begin{align} \label{eqn:32event32A32upper} \Pr[\neg A_i[\mathcal{A},O]] \le 11 \cdot 2^{-a_i/8} \le 11\lambda_i^{-c_i/8} < \frac{\varepsilon_i(\lambda_i)}{\lambda_i^2}, \end{align}\tag{15}\] for sufficiently large \(i\), where we use \(a_i = \left\lceil c_i \log \lambda_i\right\rceil\) and the upper bound of \(c_i\).

Now we analyze the candidate \(G_{u(i)}\) relative to \(O\gets \mathcal{D}_{S^{(<a_i)}}\). We consider its security at the security parameter \(\lambda_i\). Define the following event.

\(B_i{[O]}\):

This is the event that \(G_{u(i)}\) is pseudodeterministic with probability at least \(1- \varepsilon_i(\lambda_i)\) over the random choice of \(O\) (as in 4) at parameter \(\lambda_i\). In other words, this event occurs only when: for at least a \((1-\varepsilon_i(\lambda_i))\)-fraction of \(x \in \{0,1\}^{n(\lambda_i)}\), there exists \(y_{x,O}\) such that \(\Pr[G^O(x) \to y_{x,O}] \ge 1-\varepsilon_i(\lambda_i)\).

Note that \(\lnot B_i[O]\) means that \(G_{u(i)}\) fails to achieve the \((1-\varepsilon_i)\)-pseudodeterminism at least for the parameter \(\lambda_i\). We will need the following lemma whose proof is deferred to 5.3.

Roughly, it says that there is an adversary breaking the pseudorandomness of \(G_{u(i)}\) with very high probability over the oracle, as long as \(\Pr[B_i[O]]\) is big enough.

Regarding this, we consider the following two cases. We choose the oracle in the next block depending on them.

1. \(\Pr[\neg B_i[O]] \ge\varepsilon_i(\lambda_i)\). In this case, we sample the oracle \(O\) from \(\mathcal{D}_{S^{(<t)}}\) conditioned on \(\lnot B_i[O]\). This condition enforces that, for any \(\mathcal{A}\), \[\begin{align} \label{eqn:32adv95cA95case1} \Pr[A_i[\mathcal{A},O]|\lnot B_i[O]] \ge 1-\frac{1}{\lambda_i^2} \ge 1-\frac{1}{i^2} \end{align}\tag{16}\] holds for sufficiently large \(i\).

2. \(\Pr[\neg B_i[O]] < \varepsilon_i(\lambda_i)\). In this case, we sample the oracle \(O\) from \(\mathcal{D}_{S^{(<t)}}\) (without any condition). In this case, 11 says that the distinguisher \(\mathcal{B}=\mathcal{B}_G\) achieves an advantage 0.1 at parameter \(\lambda_i\) with probability at least \(1-\frac{1}{\lambda_i^2} \ge 1-\frac{1}{i^2}\) for sufficiently large \(i\). Also, in this case, it holds that \[\begin{align} \label{eqn:adv95cA95case2} \Pr[A_i[\mathcal{A},O]] \ge 1-\frac{\varepsilon_i(\lambda_i)}{\lambda_i^2} \ge 1-\frac{1}{i^2}. \end{align}\tag{17}\]

In any case, we define \(S^{(<a_{i+1})}\) by the chosen \(O\) up to input length less than \(a_{i+1}\). Our final oracle will be the oracle matching to \(S^{<a_{i}}\) up to length less than \(a_i\) for all \(i\in \mathbb{N}\).²⁴

The following claim holds because, for any \(\mathcal{A}\), regarding 17 16 with \(\sum_i 1/i^2 <\infty\), the Borel-Cantelli lemma says that the event \(\lnot A_i[\mathcal{A},O]\) occurs only finitely many times. Relative to \(O\) sampled above and \(\mathbf{PSPACE}\), \(\mathsf{Gen}^O\) is a secure PRFSG with probability 1.

Fix a QPRG candidate \(G=G_i\), and write \(u^{-1}(i)=\{i_1,i_2,...\}\). Because \(\lnot B_{i_j}[O]\) means \(G_i\) does not satisfy \((1-\varepsilon_i)\)-pseudodeterminism, the following is clear. Relative to \(O\) sampled above and \(\mathbf{PSPACE}\), if Case 1 occurs infinitely many times in \(u^{-1}(i)\), \(G\) does not satisfy the \((1-\varepsilon_i)\)-pseudodeterminism. In particular, it cannot be a QPRG with negligible errors.

On the other hand, 11 shows the following. Relative to \(O\) sampled above and \(\mathbf{PSPACE}\), if Case 2 occurs infinitely many times in \(u^{-1}(i)\), \(\mathcal{B}_G\) breaks the pseudorandomness of \(G\). This completes the proof.

5.3 Proof of 11↩︎

We will first state and prove the following lemma, which will be used in the proof of 11. It essentially says that if a quantum algorithm outputs a bit \(b_\Phi\) with high probability over the choice of the CHFS oracle \(\Phi\), then this output bit is independent of the oracle with high probability over \(\Phi\).

As in the setting of 11, we fix the CHFS oracle \(O\) up to the length \(<a_i\). For convenience, we write \(\Phi\gets \sigma\) to denote \(S=S^{\Phi}\) is sampled from the conditional distributions \(\mathcal{D}_{S^{(<a_i)}}\).

Given the running time bound \(p\), the algorithm only accesses the oracle up to the maximum query length \(p\). Let \(X=\mathbb{S}(2^{n_1})\times\cdots \times \mathbb{S}(2^{n_k})\) be the states²⁷ to define the CHFS oracle up to the length \(p\), with the corresponding product Haar measure \(\sigma=\sigma_{n_1}\times\cdots\times \sigma_{n_k}\). Let \(S_0,S_1\subseteq X\) be defined as =1 \[\begin{align} S_0\vcentcolon=\left\{ \Phi\in X \:\colon\: \Pr(A^{S^\Phi}(1^\lambda)\rightarrow 0)\geq2/3\right\}, \\ S_1\vcentcolon=\left\{ \Phi\in X \:\colon\: \Pr(A^{S^\Phi}(1^\lambda)\rightarrow 1)\geq2/3\right\}. \end{align}\] \[\begin{align} S_0\vcentcolon=\left\{ \Phi\in X \:\colon\: \Pr(A^{S^\Phi}(1^\lambda)\rightarrow 0)\geq2/3\right\},~~ S_1\vcentcolon=\left\{ \Phi\in X \:\colon\: \Pr(A^{S^\Phi}(1^\lambda)\rightarrow 1)\geq2/3\right\}. \end{align}\]

By the hypothesis in 18 , with probability at least \(1-\varepsilon(\lambda)\) over \(\Phi\leftarrow\sigma\), either \[\Pr[A^{S^\Phi}\rightarrow 1]\geq 2/3\quad\text{or}\quad\Pr[A^{S^\Phi}\rightarrow 0]\geq 2/3,\] thus \[\label{eqn:gap-upper} \sigma(X\setminus(S_0\cup S_1)) \leq \varepsilon(\lambda).\tag{19}\]

Choose arbitrary \(\Phi\in S_0\) and \(\Psi\in S_1\). The diamond distance between \(\mathcal{S}^\Phi\) and \(\mathcal{S}^\Psi\) can be bounded by \[\begin{align} \|S^\Phi(\cdot)-S^{\Psi}(\cdot)\|_{\diamond} & \le 2\|S^\Phi - S^{\Psi}\|_{op} \\ & = 2\|\sum_x \ketbra{x} \otimes (S_{\ket{\phi_x}}-S_{\ket{\psi_x}})\|_{op} \\ & = 2 \max_x \| (S_{\ket{\phi_x}}-S_{\ket{\psi_x}})\|_{op} \\ & = 4 \max_x\sqrt{1-|\bra{\phi_x}\ket{\psi_x}|^2} = 4\max_x \|\ket{\phi_x}-\ket{\psi_x}\|_{tr} = 4d_{tr}(\Phi,\Psi) \end{align}\] where we use 6 5 and \(\|S_{\ket{\phi}}-S_{\ket{\psi}}\|_{op}=2\sqrt{1-|\bra{\phi}\ket{\psi}|^2} =2 \|\ket{\phi}-\ket{\psi}\|_{tr}\).

This implies that the diamond distance of the unitary oracles \(S^\Phi\) and \(S^\Psi\) is bounded by \(\|S^\Phi(\cdot)-S^{\Psi}(\cdot)\|_{\diamond} \leq 4d_{tr}(\Phi,\Psi)\). On one hand, if the algorithm \(A\) makes \(T\) queries to the oracles, the subadditivity of the diamond norm under composition implies that \[\|A^{S^\Phi}-A^{S^\Psi}\|_\diamond\leq4T\cdot d_{tr}(\Phi,\Psi).\] On the other hand, by the definition of the diamond distance, we can lower bound this quantity by \[\begin{align} \|A^{S^\Phi}-A^{S^\Psi}\|_\diamond\geq\left|\Pr(A^{S^\Phi}\rightarrow1)-\Pr(A^{S^{\Psi}}\rightarrow1)\right|\geq\frac{1}{3}, \end{align}\] where the last inequality is obtained from \(\Phi\in S_0\) and \(\Psi\in S_1\). This implies that \[\label{eqn:proof95delta} \Delta=d_{tr}(S_0,S_1) \ge d_{tr}(\Psi,\Phi) \ge \frac{1}{12 T}\tag{20}\] which is inverse-polynomially bounded. Let \(\Gamma:=\min(\sigma(S_0),\sigma(S_1))\). We find therefore ourselves in the hypothesis of 10, thus there exists an absolute constant \(\kappa>0\) such that \[\label{eq:barrier} \sigma\bigl(X\setminus(S_0\cup S_1)\bigr) \geq \kappa\cdot \Gamma\cdot \Delta.\tag{21}\] We upper bound \(\Gamma\) by contradiction. Fix a sufficiently large absolute constant \(K>0\) and suppose that \[\label{eq:Gamma-contrad} \Gamma\;>\;K\,T\,\varepsilon.\tag{22}\] Combining 22 with 20 and 21 gives \[\sigma\bigl(X\setminus(S_0\cup S_1)\bigr) \;>\;\kappa\cdot (K\,T\,\varepsilon)\cdot \frac{1}{12T} \;=\;\frac{\kappa K}{12}\,\varepsilon.\] Choosing \(K\) large enough so that \(\frac{\kappa K}{12}>1\) yields \(\sigma(X\setminus(S_0\cup S_1))>\varepsilon\), contradicting 19 . Hence 22 is false, i.e., \[\label{eq:Gamma-ub} \Gamma\;=\;\min(\sigma(S_0),\sigma(S_1))\;\le\;\bigO{T\varepsilon}.\tag{23}\] Define \(b(\lambda)\in\arg\max_{b\in\bin}\Pr_{\Phi\leftarrow\sigma}\!\left[b=b_\Phi\right]\). Since \(S_0\) and \(S_1\) are disjoint and \(\sigma(S_0\cup S_1)\ge 1-\varepsilon\) by 19 , we have \[\begin{align} \Pr_{\Phi\leftarrow\sigma}[\,b=b_\Phi\,] =\sigma(S_b) &=\sigma(S_0\cup S_1)-\sigma(S_{1-b}) \\ &\ge (1-\varepsilon)-\min(\sigma(S_0),\sigma(S_1))\\ &\ge 1-\varepsilon-\bigO{T\varepsilon}, \end{align}\] where the last step uses 23 . This concludes the proof.

We also need the following lemma on \(t\)-designs, which will be used in the proof of 11 to simulate the CHFS oracle.

Recall 4 for the definition of the pseudodeterministic QPRG. Consider a QPRG candidate \(G=(G_\lambda)_\lambda\) that takes an \(n\)-bit seed and outputs an \(m\)-bit string relative to the CHFS oracles and \(\mathbf{PSPACE}\) that runs in polynomial queries. Let \(p(\lambda)\) be the upper bound of the running time of QPT \(G_\lambda\).

We say that an input \(x\in \{0,1\}^{n(\lambda_i)}\) is \(\varepsilon_\star\)-good if \[\label{eqn:pseudodeterministic32x} \Pr_{S}\Big[\exists\, y_{S,x} \text{ s.t. } \Pr\big[G^{S,\mathbf{PSPACE}}(x)\to y_{S,x}\big]\ge 1-\varepsilon_\star\Big] \ge 1-\varepsilon_\star.\tag{24}\] Furthermore, if the inner event holds for a particular \(S\) (i.e., there exists such a \(y_{S,x}\)), we say \((S,x)\) is good.

We write \(I_{S,x}\) to denote the indicator that \((S,x)\) is good. By the hypothesis that \(G\) satisfies \((1-\varepsilon(\lambda_i))\)-pseudodeterminism for \((1-\varepsilon(\lambda_i))\)-fraction of \(O\), \(\Pr_x[I_{S,x}=1]\ge 1-\varepsilon(\lambda_i)\), and therefore \[\mathbb{E}_{S,x}[I_{S,x}] \ge (1-\varepsilon(\lambda_i))^2 \ge 1-2\varepsilon(\lambda_i).\] Fix any \(\varepsilon_\star= (2\varepsilon)^{0.5}\). By Markov’s inequality (or the standard averaging argument), \[\Pr_x\Big[\mathbb{E}_S[I_{S,x}] \leq 1-\varepsilon_\star\Big] = \Pr_x\Big[1-\mathbb{E}_S[I_{S,x}] \geq \varepsilon_\star\Big] \le \frac{1-\mathbb{E}_{S,x}[I_{S,x}]}{\varepsilon_\star} \le \frac{2\varepsilon}{\varepsilon_\star} = \varepsilon_\star.\] Hence, for at least a \(1-\varepsilon_\star\) fraction of \(x\) we have \(\mathbb{E}_S[I_{S,x}] \ge 1-\varepsilon_\star\), i.e., \(x\) is \(\varepsilon_\star\)-good. We call such \(x\) semi-deterministic.

We will construct \(F^{\mathbf{PSPACE}}\) that agrees with \(G^{O,\mathbf{PSPACE}}\) with high probability on all semi-deterministic \(x\). We divide \(O\) into the input length \(< a_i\) (which is already fixed by \(S^{(<a_i)}\)) and \(\ge a_i\).

We first show that \(S^{(<a_i)}\) can be simulated up to negligible error in \(\poly[\lambda_i]\) time using tomography. Recall that the unitary CHFS oracle is indexed by an oracle-input length \(t<a_i\), and that on input \(x \in \bin^t\), it applies a reflection \(S_{t,x}=S_{\ket{\psi_x}\ket{1}}\) on \(\ell(t)+1\) qubits. That is, \(S_{t,x}\) acts on dimension \(d(t)\;=\;2^{\ell(t)+1}\le 2^{t+1}\le 2^{a_i} = \poly[\lambda_i]\) because \(a_i=O(\log \lambda_i).\)²⁸

For each fixed pair \((t,x)\) with \(t<a_i\), applying 7 to the black-box unitary \(S_{t,x}\) with \(\varepsilon_{\sf tom} \mathrel{\vcenter{:}}= \lambda_i^{-c'}\) (for a constant \(c'>0\) to be determined later) and \(\delta \mathrel{\vcenter{:}}= 2^{-2\lambda_i}\) yields an algorithm that outputs a classical description of a unitary \(\widetilde{S}_{t,x}\) such that, with probability at least \(1-\delta\), \[\abs{S_{t,x}-\widetilde{S}_{t,x}}_\diamond \le \varepsilon,\] using \(\bigO{\frac{d(t)^2}{\varepsilon_{\sf tom}}\log\frac{1}{\delta}} = \poly[\lambda_i]\) queries and time \(\poly[d(t),\frac{1}{\varepsilon_{\sf tom}},\log(\frac{1}{\delta})]=\poly[\lambda_i]\).

The number of such pairs \((t,x)\) is \(N_i = \sum_{t=1}^{a_i-1}2^t \le 2^{a_i} = \poly[\lambda_i]\). By a union bound over all \(N_i\) invocations, with probability at least \(1-N_i\delta \ge 1-\poly[\lambda_i]\cdot 2^{-2\lambda_i} = 1-\negl[\lambda_i]\), all tomography subroutines succeed simultaneously, producing descriptions \(\{\widetilde{S}_{t,x}\}_{t < a_i, x \in \bin^t}\) with diamond-error at most \(\varepsilon_{\sf tom}\) each. This shows that the trace distance between the output distribution can be bounded by \[\begin{align} \label{eqn:32tomography} \|G^S(\cdot) - G^{\widetilde{S}}(\cdot)\|_1 \le p(\lambda_i) \cdot \varepsilon_{\sf tom} = p(\lambda_i) \cdot \lambda_i^{-c'} \end{align}\tag{25}\] for any input, where we omit the other oracle queries that are identical for the left and right cases. We choose \(c'\) so that \(p(\lambda_i) \cdot \lambda_i^{-c'} \le \frac{1}{100n(\lambda_i) \lambda_i^2}\).

Now consider the oracle query length \(\ge a_i\). Let \(\delta=\frac{1}{100 p(\lambda_i)^2 2^{\lambda_i}}\). Let \(\mathcal{T}(\cdot)\) be the algorithm from 13 that, on input a uniform seed \(r\in\{0,1\}^{s(q)}\), outputs a (description of a) \(q\)-qubit state whose output state forms a \(\delta\)-approximate \(2p(\lambda_i)\)-design.²⁹

For each \(t\in[p(\lambda_i)]\), we sample a function \(h_t:\{0,1\}^t \to \{0,1\}^{s(\ell(t))}\) from a \(2p(\lambda_i)\)-wise independent family (independently for different \(t\)). By [57], we can assume that \(f_t\) is sampled from a truly random function as \(F\) and \(G\) make at most \(p(\lambda_i)\) quantum queries.

We now describe how \(F\) simulates \(G\)’s access to the unitary CHFS oracle \(S\), given the above data. On an oracle query with input \(x\in\{0,1\}^t\) (possibly in superposition), \(F\) proceeds as follows.

1. It uses \(\widetilde{S}\) instead of \(S\) for the input length \(t< a_i\). For the input length \(t\ge a_i\), it proceeds to the next step.

2. Coherently compute \(r_x := h_t(x)\in\{0,1\}^{s(\ell(t))}\).

3. Coherently compute \(\ket{\psi_x}:=T(r_x)\). Note that the parameters are such that on input \(x\in\{0,1\}^t\), \(h_t(x)\) is of size \(s(\ell(t))\), which is the size of the randomness needed to generate a \(\ell(t)\)-qubit \(\delta\)-error \(2p(\lambda_i)\)-design using \(\mathcal{T}(\cdot)\).

4. Apply the reflection \(S_{\ket{\psi_x}\ket{1}}\) on the \(\ell(t)+1\)-qubit register \({\boldsymbol{Y}}\) (cf. 8).

Equivalently, instead of querying the unitary CHFS oracle, \(F\) applies the unitary \[O':= \sum_{x\in \{0,1\}^{t}}\ketbra{x}_{\boldsymbol{X}} \otimes S_{\ket{\psi_x}\ket{1}},\] on \(\rho_{\boldsymbol{X}YZ}\) for \(|x|\ge a_i\), which is indistinguishable from the CHFS oracle up to some errors that we will now analyze.

We write \(f_i(x)\) for the \(i\)-th bit of \(F^{\mathbf{PSPACE}}(x)\), \(g_i(x)\) for the \(i\)-th bit of \(G^{S,\mathbf{PSPACE}}(x)\).

Fix a semi-deterministic \(x\). Applying 12 to \(g_i(x)\) (which makes at most \(T\le p(\lambda)\) oracle queries) given the fact that \(G(x)\) is pseudodeterministic with probability at least \((1-\varepsilon_\star)\) over the oracles, yields that \(g_i(x)\) must be fixed with probability at least \((1-O(p(\lambda_i) \varepsilon_\star))\) over the CHFS oracles.

Combining this with the \(\delta\)-approximate \(2p(\lambda_i)\)-design simulation error gives \[\begin{align} \Pr\left[g_i(x)=f_i(x) \right] & \ge\; 1-\bigO{p(\lambda_i)\varepsilon_\star} - \left(\sum_{t=1}^{p(\lambda_i)}\sum_{j=1}^{2^t}\delta\right) -\frac{1}{100\lambda_i^2 n(\lambda_i)} \\&\ge\; 1-\bigO{p(\lambda_i)\varepsilon_\star} - \frac{1}{100p(\lambda_i)}-\frac{1}{100 \lambda_i^2n(\lambda_i)}, \end{align}\] where the term \(\sum_{t=1}^{p(\lambda_i)}\sum_{j=1}^{2^t}\delta\) computes the total errors for \(x \in \cup_{t\in [a_i,p(\lambda_i)]}\{0,1\}^{t}\), and the term \(\frac{1}{100 \lambda_i^2n(\lambda_i)}\) is from the tomography error in 25 . By a union bound over \(i\in[n]\) and using \(n\le p(\lambda)\), we obtain \[\label{eq:closeFG} \Pr\left[G^{S,\mathbf{PSPACE}}(x)=F^{\mathbf{PSPACE}}(x)\right] \;\ge\;1-O({p(\lambda)^2\varepsilon_\star})-\frac{1}{50\lambda_i^2},\tag{26}\] for all \(\varepsilon_\star\)-semi-deterministic \(x\).

Recall the condition \(\varepsilon_\star(\lambda) = (2\varepsilon(\lambda))^{0.5} \le \frac{\sqrt{2c}}{p(\lambda)^4}\) for some small \(c>0\). We choose \(c\) so that the term \(O({p(\lambda)^2\varepsilon_\star})\) is bounded above by \(\frac{1}{50\lambda_i^2}\). This shows that the right-hand side of 26 is at least \(1-\frac{1}{4\lambda_i^2}\) for all sufficiently large \(\lambda\).

Now consider the language \[L_F := \left\{y\in\{0,1\}^{m(\lambda)} : \exists x\in\{0,1\}^{n(\lambda)} \text{ s.t. } \Pr\left[F^{\mathbf{PSPACE}}(x)=y\right]>1-\frac{1}{4\lambda^2}\right\}.\] For fixed \((x,y)\), a \(\mathbf{PSPACE}\) machine can approximate \(\Pr\left[F^{\mathbf{PSPACE}}(x)=y\right]\) to additive error \(o(\lambda^{-2})\) (since \(\mathbf{BQP}^{\mathbf{PSPACE}}\subseteq\mathbf{PSPACE}\)), and hence decide whether it exceeds \(1-1/4\lambda^2\). It follows that \(L_F\in\mathbf{PSPACE}\): on input \(y\), enumerate all \(x\in\{0,1\}^n\) using polynomial space and accept iff any \(x\) satisfies \(\Pr\left[F^{\mathbf{PSPACE}}(x)=y\right]>1-1/4\lambda^2\). Therefore, there exists a \(\mathbf{PSPACE}\)-oracle algorithm \(\mathcal{B}_0^{\mathbf{PSPACE}}\) that can decide membership in \(L_F\).

We define our adversary \(\mathcal{B}\) formally: it first computes the tomography for the input length \(<a_i\), \(2p(\lambda_i)\)-wise independent functions, and state designs described above as initialization. Then, given this, it runs \(\mathcal{B}_0^{\mathbf{PSPACE}}\).

We consider the advantage of \(\mathcal{B}\) against the pseudorandomness of \(G\). By 26 , for every semi-deterministic \(x\) it holds that \[\begin{align} \Pr_S\left[\mathcal{B}^{\mathbf{PSPACE}}(G^{S,\mathbf{PSPACE}}(x))=1\right]\ge 1- \frac{1}{4\lambda_i^2}. \end{align}\]

As a \((1-O(1/\lambda_i^2))\)-fraction of \(x\), with a sufficiently small constant, satisfies the above, we have \[\Pr_{S,x}\left[\mathcal{B}^{\mathbf{PSPACE}}(G^{S,\mathbf{PSPACE}}(x))=1\right]\ge 1- \frac{1}{3\lambda_i^2}.\]

The standard averaging argument says that \[\Pr_{S}\left[\left[\mathcal{B}^{\mathbf{PSPACE}}(G^{S,\mathbf{PSPACE}}(x))=1\right]\ge \frac{2}{3}\right] \ge 1- \frac{1}{\lambda_i^2}.\]

On the other hand, \(|L_F|\le 2^n\) (each \(x\) can contribute at most one such \(y\)), so for uniform \(y\gets\{0,1\}^m\) we have \(\Pr\left[\mathcal{B}^{\mathbf{PSPACE}}(y)=1\right]\le 2^{n-m}\le 1/2\) (using that \(m>n\) for a QPRG). This gives a constant distinguishing advantage of \(\mathcal{B}\) against \(G\) for the parameter \(\lambda_i\).

=0

6 Oracle Separation of PRUs from PRFSGs↩︎

In this section, we consider the length-\(\ell\) quantum-accessible unitarized CHFS oracle \(\mathcal{S}=\mathcal{S}_{\ell}\) for \(\ell(|x|)=|x|\) and the \(\mathbf{QPSPACE}\) oracle. We will prove the following theorem, which is the main result of this section.

The existence of the adaptively-secure quantum-accessible PRFSGs relative to the oracles is proven by 8. What remains is to prove that PRUs without ancilla do not exist in this model.

We prove the lemma by contradiction. Assume that \(\{G^{\mathcal{S},\mathbf{QPSPACE}}_{\lambda}(\cdot)\}_{\lambda}\) is a secure \(n(\lambda)\)-PRU construction relative to \((\mathcal{S},\mathbf{QPSPACE})\) for \(n(\lambda)=\omega(\log \lambda).\) For simplicity, we drop the \(\mathbf{QPSPACE}\) oracle and \(\lambda\) in notations and write \(G_{k}^{\mathcal{S}}\) to denote \(G^{\mathcal{S},\mathbf{QPSPACE}}_{|k|}(k)\). The adversary is given oracle access to the oracle \((V,\mathcal{S},\mathbf{QPSPACE})\) where \(V\) is either \(G_{k^{*}}^{\mathcal{S}}\) for some \(k^{*}\) or a Haar random unitary of the same size, and tries to determine which is the case with non-negligible probability.

We write \(\mathcal{S} = (S_{d})_{d\in \mathbb{N}}\) where \(S_{d}=\sum_{x\in \{0,1\}^{d}} \ketbra{x} \otimes S_{\ket{\phi_{x}}}\) to denote the unitary CHFS oracle, where \(S_{\ket{\phi_{x}}}\) denotes the swap oracle defined in 6 for some \(d\)-qubit Haar random quantum state \(\ket{\phi_{x}}\) and \(S_{d}\) acts on a \((2d+1)\)-qubit space.³⁰

Let \(m=\poly\) be the maximum number of oracle queries to \(\mathcal{S}\) that \(G^{\mathcal{S}}\) makes. We show that distinguishing \(G_{k}^{\mathcal{S}}\) from a Haar random unitary can be done efficiently based on swap tests. More concretely, we prove that the following algorithm \(\adv^{V,\mathcal{S},\mathbf{QPSPACE}}\) can guess with non-negligible probability whether \(V\) is \(G_{k}^{\mathcal{S}}\) for some random \(k\), (in which case it outputs \(1\)), or a truly Haar random unitary (in which case it outputs \(0\)). For simplicity, we omit the oracle notation and write \(\adv\) for \(\adv^{V,\mathcal{S},\mathbf{QPSPACE}}\).

The following claims summarize the main analysis of the algorithm, which will be proven at the end of this section. 2 is a \(\mathbf{BQP}^{V,\mathcal{S},\mathbf{QPSPACE}}\) algorithm, which makes non-adaptive queries to \(V\). If \(V=G_{k}^{\mathcal{S}}\) for some \(k\) and \(\require{physics} \Tr(G_{k}^{\mathcal{S}}(\phi)^{2})\ge 1-1/\lambda\), then \(\Pr[P_{k}(\Psi) \to 1] \ge 1-2^{-\lambda}\) holds with probability at least \(1-\frac{m+\tau}{2^{2\lambda}}\) over the randomness of the algorithm for sufficiently large \(\lambda\). If \(V\gets \mu_{n}\), then \(\Pr[P_{k}(\Psi) \to 1] \le 2^{-2\lambda}\) holds for all \(k\) with probability at least \(1-2^{-\lambda}\) over the randomness of the algorithm for sufficiently large \(\lambda\).

The efficiency of the algorithm relative to \(\mathcal{S},\mathbf{QPSPACE}\) is provided by [claim:32Sep1AlgBQP]. Also note that the algorithm breaks the non-adaptive security of PRUs, as the queries to \(V\) only occur in the first step and to prepare \(\Psi\) which are all non-adaptive queries.

The correctness of the algorithm can be shown by the case analysis. If \(V=G_{k}^{\mathcal{S}}\) for some \(k\) and if \(\require{physics} \Tr(G_{k}^{\mathcal{S}}(\phi)^{2})\le 1-1/\lambda\), the first step of \(\adv\) outputs 1 with probability at least \(1-2^{-\lambda}\) as shown in 4.

The other case, i.e., \(V=G_{k}^{\mathcal{S}}\) and \(\require{physics} \Tr(G_{k}^{\mathcal{S}}(\phi)^{2})\ge 1-1/\lambda\) or \(V\) is a true Haar random unitary is dealt with by the quantum OR lemma. In this case, by [claim:32Sep1Gk] and [claim:32Sep1Haar], the POVMs \(\{P_{k}\}_{k\in \{0,1\}^{\lambda}}\) and \(\Psi\) satisfy the conditions of the quantum OR lemma (7) unless with probability \(2^{\lambda}\cdot \frac{m+\tau}{2^{2\lambda}} +2^{-\lambda} \le 2/2^{\lambda}\) for large enough \(\lambda\), \(\varepsilon=1/2^{\lambda}\) and \(\delta=1/2^{2\lambda}\). Therefore, \(\adv\) outputs 1 with probability at least \(1/8\) if \(V=G_{k}^{\mathcal{S}}\) for some \(k\), but it outputs 1 with probability at most \(4/2^{\lambda}\) if \(V\gets \mu_{n}\), that is, \(\adv\) breaks the PRU security of \(\{G_{k}^{\mathcal{S}}\}\). This concludes the proof.

We now prove the claims. The first step takes polynomial time and \(32\lambda^{2}\) non-adaptive queries to the oracle \(V\). The second step has time and query complexity (to \(\mathcal{S}\)) equal to \(\tau \times {\sf poly}\left(d,\frac{1}{\varepsilon},\log \frac{1}{\delta}\right) = {\sf poly}\left(2^{\tau}, 2^{\tau}, \lambda\right) =\poly\). Note that it is clear that \(P_{k}\) can be executed by a quantum polynomial space machine. In the final step, the quantum OR tester can be executed by a \(\mathbf{QPSPACE}\)-aided BQP machine as noted in “Moreover” part of 7 with inputs the descriptions of \(S_{i}'\) for \(i\le \tau\) (prepared by the first step) as \(P_{k}\) can be implemented by a quantum polynomial-space machine.

We will show that \(G_{k}^{\mathcal{S}}(\ketbra\rho)\) and \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra\rho)\) are close with high probability, for a Haar random input state \(\ket{\rho}\) of size \(n\)-qubit. We will write \(\rho = \ketbra{\rho}\) as a short-hand.

We begin with the following two closeness properties for \(S_{d}\) and \(\tilde{S}_{d}\) from the later steps of the algorithm. First, for small dimensions \(d \le \tau < n\), 7 ensures that \[\begin{align} \label{eqn:32good295PRUPRFS} \|\tilde{S}_{d}\otimes I(\rho) - {S}_{d}\otimes I(\rho)\|_{tr}= \|S_{d}'\otimes I(\rho) - {S}_{d}\otimes I(\rho)\|_{tr} \le\frac{\varepsilon}{2}= \frac{1}{2^{\tau/2}}, \end{align}\tag{27}\] holds for any quantum state \(\rho\) with probability \(1-\delta = 1-\frac{1}{2^{2\lambda}}\). Thus all tomography outputs are \(1/2^{\tau/2}\)-close to the target unitaries with overwhelming probability \(1-p_{1}\), for \(p_{1}=\tau/2^{2\lambda}\). In the following, we assume it is the case.

For large dimensions \(d>\tau\), we show that \(S_{d}\) acts almost as the identity with high probability for a pure Haar quantum state \(\ket{\rho}=\sum_{x,z} \alpha_{x,z} \ket{x}\ket{\rho_{x,z}}\ket{z}\) such that \(\sum_{x,z} |\alpha_{x,z}|^{2}=1\), and \(\ket{\rho_{x, z}}\) is of size \(d\). We have \[\begin{align} & \mathbb{E}_{\mathcal{S}}\|\tilde{S}_{d} \otimes I(\ketbra\rho)-S_{d}\otimes I(\ketbra\rho)\|_{tr} \\& =\mathbb{E}_{\mathcal{S}}\|I(\ketbra\rho)-S_{d}\otimes I(\ketbra\rho)\|_{tr} \\&= \frac{1}{2}\sum_{x\in \{0,1\}^{d}} \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ \bra{\rho}(\ketbra{x} \otimes \left(I_{d+1} - S_{\ket{\phi_{x}}}\right)\otimes I )\ket{\rho}\right] \\&= \frac{1}{2}\sum_{x\in \{0,1\}^{d}} \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ \bra{\rho}(\ketbra{x}\otimes(\ketbra{1,\phi_{x}}{0}+\ketbra{0}{1,\phi_{x}}) \otimes I)\ket{\rho}\right] \\&\le \sum_{x\in \{0,1\}^{d},z} \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ |\bra{\rho}\ketbra{x}\otimes\ketbra{1,\phi_{x}}{0} \otimes \ketbra{z}\ket{\rho}|\right] \\&= \sum_{x\in \{0,1\}^{d},z} |\alpha_{x,z}|^{2} \cdot \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ |\bra{\rho_{x,z}}\ketbra{1,\phi_{x}}{0} \ket{\rho_{x,z}}|\right] \\&\le \sum_{x\in \{0,1\}^{d},z} |\alpha_{x,z}|^{2} \cdot \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ |\bra{\rho_{x,z}}\ket{1,\phi_{x}} |\right] \\&\le \sum_{x\in \{0,1\}^{d},z} |\alpha_{x,z}|^{2} \sqrt{\mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ |\braket{\rho_{x,z}}{1,\phi_{x}}|^{2}\right]}, \end{align}\] where we use 6 8 in the first few equalities. The factor \(1/2\) comes from the definition of the trace distance. The first inequality uses \((a+\bar a)=2{\sf Re}(a) \le 2|a|\) for \(a=\bra{\rho}(\ketbra x \otimes \ketbra{1,\phi_{x}}0\otimes I)\ket{\rho}\). The second inequality uses \(|\braket{0}{\rho_{x,z}}|\le 1\). The last inequality is \(\mathbb{E}[{X}]^{2} \le \mathbb{E}[{X}^{2}]\). This can be bounded by \[\begin{align} & \sum_{x\in \{0,1\}^{d},z} |\alpha_{x,z}|^{2} \sqrt{\mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ \braket{1,\phi_{x}}{\rho_{x,z}}\braket{\rho_{x,z}}{1,\phi_{x}}\right]} \\&\quad\quad\quad\le \sqrt{\mathbb{E}_{\phi_{x} \gets \sigma_{d}\forall x\in\{0,1\}^{d}}\left[\sum_{x,z}|\alpha_{x,z}|^{2} \cdot\braket{1,\phi_{x}}{\rho_{x,z}}\braket{\rho_{x,z}}{1,\phi_{x}}\right]}, \end{align}\] using Jensen’s inequality for \(f(x)=\sqrt x\). Let \[p=\mathbb{E}_{\phi_{x} \gets \sigma_{d}\forall x\in\{0,1\}^{d}}\left[\sum_{x,z}|\alpha_{x,z}|^{2} \cdot\braket{1,\phi_{x}}{\rho_{x,z}}\braket{\rho_{x,z}}{1,\phi_{x}}\right] \le {\frac{1}{2^{d}}} \le \frac{1}{2^{\tau}},\] by 2 for the projector \(\ketbra{\rho_{x,z}}\) with \(d\)-qubit Haar random state \(\ket{\phi_{x}}\). This can be written as the probability that an algorithm succeeds projection³¹, so we can apply 3 with \(t=1/2^{\tau}\), which gives \[\begin{align} \label{eqn:32close95large95d} \Pr_{\mathcal{S}_{>\tau}}\left[ \|I(\ketbra \rho)-S_{d}\otimes I(\ketbra \rho)\|^{2} _{tr}\ge \frac{2}{2^{\tau}} \right] \le \exp \left( -\frac{2^{n}-2}{24\cdot 2^{2\tau}} \right) \le \frac{1}{2^{2\lambda}}, \end{align}\tag{28}\] for sufficiently large \(n\).³² Here \(\mathcal{S}_{>\tau}\) denotes the oracle with dimension \(d>\tau\).

To bound the trace distance between \(G_{k}^{\mathcal{S}}(\ketbra{\rho})\) and \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\), we use the hybrid argument using the above two observations. Let \({\Phi_{j}}\) for \(0\le j \le m\) be equal to the outcome of \(G_{k}\) on input \(\ketbra{\rho}\) with the first \(j\) oracle queries are answered using \(\tilde{\mathcal{S}}\) and the other \(m-j\) queries are answered using \(\mathcal{S}\). We have that \({\Phi_{0}}\) is the state \(G_{k}^{\mathcal{S}}(\phi)\) and \({\Phi_{m}}\) is the state \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\).

Let \(\ket{\phi_{j}}\) be the intermediate state right after \(j\)-th oracle query when computing \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\). We have \(\|I(\phi_{j}) - (S_{d}\otimes I)(\phi_{j})\|_{tr} \le 2/2^{\tau/2}\) holds with probability \(1-\frac{1}{2^{2\lambda}}\) over the randomness of the oracle by 28 . Then, by the monotonicity of the trace distance, we have \[\begin{align} \left\|G_{k}^{\mathcal{S}} (\ketbra{\rho}) - G_{k}^{\tilde{\mathcal{S}}} (\ketbra{\rho}) \right\|_{tr} & \le \sum_{j=0}^{m-1}\|S_{d_{j}^{(k)}}\otimes I(\phi_{j})-\tilde{S}_{d_{j}^{(k)}}\otimes I(\phi_{j})\| _{tr} \\& \le \sum_{j=0}^{m-1} \max\left(\frac{\varepsilon}{2} , \frac{2}{2^{\tau/2}}\right) = \frac{2m}{2^{\tau/2}} = \frac{1}{8}, \end{align}\] with probability \(1-p_{2}\) for \(p_{2}=\frac{m}{2^{2\lambda}}\); we again focus on this case.

We finally analyze the success probability of a single swap test between \(G_{k}^{\mathcal{S}}(\ketbra{\rho})\) and \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\) succeeds in subroutine \(P_{k}\). Since =1 \[\begin{align} & \|G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\otimes G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})-G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\otimes G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\|_{tr} \\ & \quad\quad=\|G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho}) - G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\|_{tr} \le 1/8, \end{align}\] \[\begin{align} \|G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\otimes G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})-G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\otimes G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\|_{tr} =\|G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho}) - G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\|_{tr} \le 1/8, \end{align}\] we have \[\require{physics} \begin{align} \left| \frac{1+\Tr(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})G_{k}^{{\mathcal{S}}}(\ketbra{\rho}))}{2} - \frac{1+\Tr(G_{k}^{{\mathcal{S}}}(\ketbra{\rho})^{2})}{2} \right| \le \frac{1}{8}, \end{align}\] and using the fact that \(\require{physics} \Tr(G_{k}^{{\mathcal{S}}}(\ketbra{\rho})^{2})\ge 1-1/\lambda\), we have \[\require{physics} \frac{1+\Tr(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})G_{k}^{{\mathcal{S}}}(\ketbra{\rho}))}{2} \ge \frac{7}{8} - \frac{1}{2\lambda} \ge \frac{3}{4}.\] Therefore, by Chernoff’s inequality, the probability that at least \(\frac{2r}{3}\) tests succeed among \(r\) swap tests is bounded by \[1-\exp\left(-\frac{3r}{2\cdot 4\cdot 12^{2}}\right)=1-\exp\left(-\frac{r}{384}\right) \ge 1-2^{-\lambda}.\] Overall, if \(V=G_{k}^{{\mathcal{S}}}\) for some \(k\) and \(\require{physics} \Tr(G_{k}^{\mathcal{S}}(\phi)^{2})\ge 1-1/\lambda\), then it holds that \(\Pr[P_{k}(\Psi) \to 1] \ge 1-2^{-\lambda}\) with probability at least \(1-p_{1}-p_{2}=1-\frac{m+\tau}{2^{2\lambda}}\).

In this case, we can regard \(V({\ketbra{\rho}})\) as an independent Haar random pure state \(\ket{\psi}\). By 3, the expected success probability of the swap test between \(G_{k}^{\tilde{\mathcal{S}}}({\ketbra{\rho}})\) and \(V({\ketbra{\rho}})\) is =1 \[\require{physics} \begin{align} \underset{V\gets \mu_{n}}{\mathbb{E}}\left[\frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})V(\ketbra{\rho})]}{2}\right] & = \underset{\psi \gets \sigma_{n}}{\mathbb{E}}\left[\frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\ketbra{\psi}]}{2}\right] \\ & = \frac{1}{2} + \frac{1}{2^{n+1}}{} \end{align}\] \[\require{physics} \begin{align} \underset{V\gets \mu_{n}}{\mathbb{E}}\left[\frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})V(\ketbra{\rho})]}{2}\right] = \underset{\psi \gets \sigma_{n}}{\mathbb{E}}\left[\frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\ketbra{\psi}]}{2}\right] = \frac{1}{2} + \frac{1}{2^{n+1}}{} \end{align}\] where we use 2 in the last equality. Applying 3 for \(t=1/13\), we have \[\require{physics} \Pr\left[ \frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})V(\ketbra{\rho})]}{2} \ge \frac{7}{12} \right] \le \exp\left(-\frac{2^{n}-2}{4056}\right) \le \frac{1}{2^{2\lambda}}\] for sufficiently large \(n\). In other words, with probability at least \(1-\frac{1}{2^{\lambda}}\), the swap test between \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\) and \(V(\ketbra{\rho})\) succeeds with probability at most \(7/12\) for all \(k\). We only focus on such a case below. Chernoff inequality gives that \(\Pr[P_{k}(\Psi) \to 1]\) is at most \[\exp\left( -\frac{7r/12\cdot (1/12)^{2}}{(2+1/12)} \right)= \exp\left( -\frac{7r}{3600} \right) \le 2^{-2\lambda},\] for each \(k\). Therefore, if \(V\) is truly Haar random unitary, then it holds that \(\require{physics} \Tr\left[P_{k} \ket{\Psi}\right] \le 2^{-2\lambda}\) for all \(k\) with probability at least \(1-2^{-\lambda}\).

7 Toward Separating PRSGs from Short PRSGs↩︎

In this section we show that the output size of a pseudorandom state may be relevant, i.e., there exist short-PRSGs but PRSGs in a certain form do not exist.

7.1 Preparation↩︎

7.1.0.1 Universal oracle.

For a quantum oracle algorithm with access to the oracle \(O = \{O_{\lambda}\}_{\lambda \in \NN}\), we consider a universal oracle \(\tilde{O}\) that takes as input a state over two registers \(\boldsymbol{\Lambda} X\), measures the register \(\boldsymbol{\Lambda}\) to obtain \(\lambda\), then applies \(O_\lambda\) on (the first parts of) \(\boldsymbol{X}\). The (qu)bit-length \(n\) of \(\boldsymbol{\Lambda}\) may be specified by \(\tilde{O}_n\) if needed, in which case \(\tilde{O}_n\) can make queries up to \(O_{2^n}\).

We give the definition here because we explicitly discuss the measurement regarding \(\lambda\) here; the results in the previous section may use the universal oracles implicitly but are not changed.

7.1.0.2 Pure quantum algorithm, with the isometry CHFS oracles.

In this section, we consider quantum oracle algorithms without trace-out operators, which we refer to as pure algorithms, written as \[\begin{align} A(\cdot) = U_t \circ \tilde{O} \circ \mathcal{N}_t \circ \dots \circ U_1 \circ \tilde{O} \circ \mathcal{N}_1 \circ U_0 (\cdot), \end{align}\] where each measurement \(\mathcal{N}_i\) decides which oracle to query (the parameter \(\lambda\)) on what input \(x\).

Recall that the isometry CHFS oracle with input \(x\) outputs \(\ket{\phi_x}_{\boldsymbol{Y}}\) in a new register \(\boldsymbol{Y}\). For the pure algorithm \(A\) with the isometry CHFS oracles, we assume that the register \(\boldsymbol{Y}\) was included in the input register of \(A\) initialized by \(\ket{0}_{\boldsymbol{Y}}\), but it is never changed until the oracle query is applied. After the query, it becomes \(\ket{\phi_x}_{\boldsymbol{Y}}\) and arbitrary operation may be applied on \(\boldsymbol{Y}\).

When the universal oracle is considered, we assume that some register is initialized by \(\ket{0^n}\) for some \(n\) and the oracle query uses some qubits of them as \(\Lambda\), which is measured when the query to the universal oracle is made. Arbitrary operations may be applied to these qubits at any point.

7.2 Purity test on the output of pure algorithms↩︎

Recall that the purity of a quantum state \(\rho\) is defined by \(\require{physics} \Tr(\rho^2)\) and can be estimated by the swap test as shown in 3 on the two copies of \(\rho\). If the outcome of an algorithm is pure, then it can be shown that the initial or intermediate states must have also been pure and the intermediate measurements are deterministic (which is in fact nontrivial). This is the idea behind the following lemma, which states that if the output of a pure quantum algorithm is nearly pure, then the intermediate binary measurements are almost deterministic, and can be removed at the cost of a negligible difference in the output state.

Note that the measurements in the following lemmas are binary; when we apply this lemma, we may implicitly decompose the general measurements into binary measurements.

We rewrite the algorithm \(A\) in simpler terms for the proof by considering \[\begin{align} \mathcal{N}_i\vcentcolon=(\Pi_i ^0,\Pi_i^1),\quad\text{where}\quad\Pi_i^b\vcentcolon=U_0^\dagger\cdots U_{i-1}^\dagger (\ketbra{b}\otimes I)U_{i-1}\cdots U_0, \end{align}\] acting on any mixed input state \(\rho\) as \(\mathcal{N}_i(\rho) = \Pi_i ^0\rho\Pi_i ^0+\Pi_i^1\rho\Pi_i^1\). The algorithm \(A\) can be reformulated as follows³⁴: \[\begin{align} A(\rho) & = U_t\circ\cdots\circ U_0\circ \mathcal{N}_t \circ \cdots \circ \mathcal{N}_1(\rho) \nonumber \\ & = \sum_{b_1,\cdots,b_t \in \{0,1\}}U_t\cdots U_0 \Pi^{b_t}_t \cdots \Pi^{b_1}_1 \rho \Pi^{b_1}_1 \cdots \Pi^{b_t}_t U_0^\dagger\cdots U_t^\dagger.\label{eqn:algo95rep95simplified} \end{align}\tag{31}\] We also define the intermediate states \(\{\phi_i\}_{i\in[t]}\) after measurement \(\mathcal{N}_i\) as \[\phi_i\vcentcolon=\mathcal{N}_i \circ \cdots \circ \mathcal{N}_1 (\phi).\] The most probable outcomes for the original binary measurements are also simplified with this notation, in particular \(\require{physics} b_{i+1}=\argmax_{\substack{b\in\{0,1\}}} \Tr(\Pi_{i+1}^b\phi_{i})\), and we define the associated measurement operator \[\begin{align} \Lambda_{i+1}(\rho):= {\Pi^{b_{i+1}}_ {i+1}\rho\Pi^{b_{i+1}}_{i+1}}. \end{align}\]

Since the trace-norm is invariant under unitaries, in order to prove the theorem it is enough to show that \[\|\Lambda_t \circ \cdots \circ \Lambda_1 (\phi) - \mathcal{N}_t \circ \cdots \circ \mathcal{N}_1 (\phi)\|_{tr} \le t\varepsilon.\] It turns out that proving that “it also holds” part suffices for proving the above inequality. In the formulation of this proof, it can be written as follows. For every \(i\in[t]\) and measurement operator \(\Lambda_{i+1}:= {\Pi^{b_{i+1}}_ {i+1}\rho\Pi^{b_{i+1}}_{i+1}}.\), we have \[\require{physics} \Tr(\Lambda_{i+1}(\phi_i))\geq1-\varepsilon.\]

We prove that the claim implies the main inequality of the theorem, as the measurement channel and the operator associated with the most likely outcome are closely related. That is, their difference is just the operator associated with the least likely outcome, whose probability of occurring is bounded by [claim:purity95povm]: \[\require{physics} \begin{align} \|\Lambda_{i+1}(\phi_i) - \mathcal{N}_{i+1}(\phi_i)\|_1=\|\Pi^{1-b_{i+1}}_{i+1}\phi_i\Pi^{1-b_{i+1}}_{i+1}\|_1= 1-\Tr(\Pi^{b_{i+1}}_{i+1}\phi_i)\leq\varepsilon, \end{align}\] so that \(\|\Lambda_{i+1}(\phi_i) - \mathcal{N}_{i+1}(\phi_i)\|_{tr}\le \varepsilon\). The theorem follows by the triangle inequality as \[\begin{align} & \|\Lambda_{t}\circ \cdots\circ \Lambda_1(\phi) - \mathcal{N}_t \circ \cdots \circ \mathcal{N}_1 (\phi)\|_{tr} \\ & \quad\quad\le \| \Lambda_{t} \circ \cdots \circ\Lambda_{1}(\phi) - \Lambda_{t} \circ \cdots \circ \mathcal{N}_{1}(\phi) \|_{tr} \\ & \quad\quad\quad\quad\quad + \| \Lambda_{t} \circ \cdots \circ \Lambda_2\circ\mathcal{N}_{1}(\phi) - \Lambda_{t} \circ \cdots \circ \mathcal{N}_2 \circ \mathcal{N}_{1}(\phi) \|_{tr} \\ & \quad\quad\quad\quad\quad\quad\quad\quad + \cdots + \| \Lambda_{t} \circ \mathcal{N}_{t-1} \circ \cdots \circ\mathcal{N}_{1}(\phi) - \mathcal{N}_{t} \circ \mathcal{N}_{t-1}\circ \cdots \circ \mathcal{N}_{1}(\phi) \|_{tr} \\ & \quad\quad\leq \sum_{i=0}^{t-1}\|\Lambda_{i+1}(\phi_i)-\mathcal{N}_{i+1}(\phi_i)\|_{tr}\le \sum_{i=0}^{t-1} {\varepsilon} = t{\varepsilon}, \end{align}\] where we used the fact that a quantum channel does not increase the trace norm, see 3 , for the quantum channel \(\Lambda_j\) in the second inequality.

Note that measurement channels can only decrease purity, for all \(i\in[t]\): \[\require{physics} \begin{align} \Tr(\phi_{i+1}^2) & = \Tr(\mathcal{N}_{i+1}(\phi_i)^2) \\ & = \Tr(\left(\Pi_{i+1}^0\phi_i\Pi_{i+1} ^0+\Pi_{i+1}^1\phi_i\Pi_{i+1}^1\right)^2) \\ & =\Tr(\Pi_{i+1}^0\phi_i\Pi_{i+1}^0\phi_i\Pi_{i+1}^0+\Pi_{i+1}^1\phi_i\Pi_{i+1}^1\phi_i\Pi_{i+1}^1) \\ & \leq \Tr(\Pi_{i+1}^0\phi_i^2)+\Tr(\Pi_{i+1} ^1\phi_i^2) \\ & = \Tr(\phi_i^2), \end{align}\] where we use \(\require{physics} \Tr(C\rho C^\dagger)\leq\Tr(\rho)\) for any unnormalized state \(\rho=\phi_i\Pi_{i+1}^b\phi_i\) and quantum channel \(C(\cdot)=\Pi^b_{i+1}(\cdot)\Pi^b_{i+1}\), and the cyclicity of the trace.

Moreover, we know by hypothesis of 15 that the outcome of the algorithm \(A\) is pure with high probability, i.e.\(\require{physics} \Tr(\phi_t^2)\geq1-\varepsilon\). In particular, the above implies that for every \(i\in[t]\), the intermediate state \(\phi_i\) is pure with high probability, and hence the channel described by the most probable measurement element must have high probability \[\require{physics} \begin{align} 1-\varepsilon& \leq\Tr(\phi_t^2)\leq\Tr(\phi_{i+1}^2) \\ & \leq\Tr(\Pi_{i+1} ^0\phi_i\Pi_{i+1}^0)^2+\Tr(\Pi_{i+1}^1\phi_i\Pi_{i+1}^1)^2 \\ & \leq\Tr(\Pi_{i+1} ^{b_{i+1}}\phi_i\Pi_{i+1}^{b_{i+1}})\left(\Tr(\Pi_{i+1} ^0\phi_i\Pi_{i+1}^0)+\Tr(\Pi_{i+1}^1\phi_i\Pi_{i+1}^1)\right) \\ & \leq\Tr(\Pi_{i+1} ^{b_{i+1}}\phi_i\Pi_{i+1}^{b_{i+1}})\Tr(\phi_i) \\ & =\Tr(\Lambda_{i+1}(\phi_i)). \qedhere \end{align}\]

7.3 Conditional separation↩︎

In general, any quantum algorithm in the isometry oracle model, that makes \(t\) projective binary measurements described by \(\{U_0,\mathcal{M}_1,\ldots,\mathcal{M}_t,U_t\}\) for unitaries \(U_0,...,U_t\) and measurements \(\mathcal{M}_i = (\ketbra{0}\otimes I,\ketbra{1}\otimes I)\), can be written as

\[\require{physics} A(\cdot) = \Tr_{{\mathbf{B}}}\bigg[(U_t\circ \tilde{O}_{n_t}\circ\mathcal{N}_t)\circ\ldots\circ(U_1\circ \tilde{O}_{n_1}\circ\mathcal{N}_1) \circ U_0 (\ketbra{0}_{{\mathbf{A}}{\mathbf{B}}}^{\otimes u(\lambda)})\bigg].\] We denote \[\rho_{{\mathbf{A}}{\mathbf{B}}} = (U_t\circ \tilde{O}_{n_t}\circ\mathcal{N}_t)\circ\ldots\circ(U_1\circ \tilde{O}_{n_1}\circ\mathcal{N}_1) \circ U_0 (\ketbra{0}_{{\mathbf{A}}{\mathbf{B}}}^{\otimes u(\lambda)}).\] In this section, we will consider a particular type of quantum algorithms, which we call “ancilla-uncomputable quantum algorithms”, where a quantum algorithm \(A\) acts on two registers: the output register \(\boldsymbol{A}\), and the ancilla register \(\boldsymbol{B}\) ³⁵, and the output of \(A\) is of the following form: \[\require{physics} A(\cdot) = \Tr_{\boldsymbol{B}}({\rho_{\boldsymbol{A} B}}), \text{ where } {\rho_{\boldsymbol{A} B}} = {\psi}_{\boldsymbol{A}} \otimes \ketbra{0}_{\boldsymbol{B}}.\]

We now show the following theorem, which is the main result of this section.

The separating oracle \(\mathcal{O}\) consists of two oracles: the classical-accessible isometry CHFS oracle \(O_\ell\) for \(\ell(\lambda)=\lfloor 2\log \lambda\rfloor\) and the \(\mathbf{QPSPACE}\) oracle. The existence of short-PRFSGs follows immediately from 8. It remains to break long PRSGs with ancilla-uncomputable generation algorithm.

By contradiction, assume there exists a PRSG \(\mathsf{Gen}(\cdot)\) with an ancilla-uncomputable generation algorithm relative to \(\mathcal{O}\). Let \(u_k\) be the length of the ancilla register. We can assume w.l.o.g. that \(u_k = u\) is independent of \(k\), by considering \(u = \max_k{u_k}\) and adding ancilla that will not be used for the \(k\) such that \(u_k<u\). Because the generation algorithm is ancilla-uncomputable, the ancilla registers are reset to \(\ket{0}\) after the computation. We write \(d(\lambda)\) and \(\kappa(\lambda)\) to denote the output length and the key length of the PRSG. Since the \(\mathbf{QPSPACE}\) oracle is unitary, we can embed them in the unitaries and write the output state of the algorithm (before tracing out the ancilla) by \[\label{eq:decomp} (U_t^{(k)}\circ \tilde{O}^{(k)}_{n_t}\circ\mathcal{N}^{(k)}_t)\circ\ldots\circ(U^{(k)}_1\circ \tilde{O}_{n_1}\circ\mathcal{N}^{(k)}_1) \circ U_0^{(k)} (\ketbra{0}^{\otimes m(\lambda)}),\tag{32}\] where \(m(\lambda) = d(\lambda) + u\) is the dimension of the whole space where the computations are made. We omit the superscript \((k)\) when it is clear from the context. Here \(U_0,\dots,U_t\) denote unitary operations and \(\mathcal{N}_1,\dots,\mathcal{N}_t\) are measurements on some registers \({\boldsymbol{\Lambda}}_1{\boldsymbol{X}}_1,\dots,{\boldsymbol{\Lambda}}_t{\boldsymbol{X}}_t\), where \({\boldsymbol{\Lambda}}_j\) specifies the index for the CHFS oracle to be applied on \({\boldsymbol{X}}_j\). The values \(n_1,\dots,n_t\) denote the size of \({\boldsymbol{\Lambda}}_1,\dots,{\boldsymbol{\Lambda}}_t.\)

Let us denote by \(\rho_t^{(k)}=\rho^{(k)}\otimes\ketbra{0}^{\otimes u}\) the final state before tracing out the ancilla, and we denote by \(\rho_j^{(k)}\) the intermediate state right after applying the unitary \(U_j\) for \(j=0,\dots,t-1\). We consider the following adversary \(\adv\), given the polynomial copies of either \(\rho=\rho^{(k)}\) for some \(k\) (in which case it outputs 1) or Haar random state \(\rho\) (in which case it outputs 0). In the following, let \(r=10\lambda^2\) and \(T=20r^2(2td+1)^3\).

We first argue that the sub-protocol \(P_k\) can be implemented in polynomial time. This is because the \((\lambda_{i}^{(k)},x_{i}^{(k)})\) can be learned without making any query by 12.

If \(\rho=\rho^{(k)}\) and \(\require{physics} \Tr(\rho^2)\ge 1-1/T\), then \(\Pr[P_k(\Phi)] \ge 4/5.\) If \(\rho\) is a Haar random state, then \(\Pr[P_k(\Phi)\to 1] \le 1/2^{2\lambda}\) for all \(k\) with probability at least \(1-1/2^\lambda\). The same argument as in 6 concludes the proof. Indeed, if \(\rho=\rho^{(k)}\) for some \(k\) and \(\require{physics} \Tr(\rho^2) \le 1-1/T\), then 4 asserts that the first step outputs \(1\) with probability \(1-2^{-\lambda}\).

The other case, i.e., \(\rho=\rho^{(k)}\) and \(\require{physics} \Tr(\rho^2)\ge 1-1/T\) or \(\rho\) is a true Haar random state is dealt by the quantum OR lemma. In this case, by [clm:32rhorhok] and [clm:32rhoHaar], the POVMs \(\{P_k\}_{k\in \{0,1\}^\lambda}\) and \(\Psi\) satisfy the conditions of the quantum OR lemma (7) unless with probability \(1/2^{\lambda}\cdot\). Therefore, \(\adv\) outputs 1 with probability at least \(1/8\) if \(\rho=\rho^{(k)}\) for some \(k\), but it outputs 1 with probability at most \(4/2^{\lambda}\) if \(\rho\gets \nu_n\), that is, \(\adv\) breaks the PRSG security of \(\mathsf{Gen}(\cdot)\).

By the above claim, we can assume that \(\require{physics} \Tr(\rho^2)\ge 1-1/T\), otherwise 3 would have terminated at step 1 with probability at least \(1-2^{-\lambda}\). We can decompose the measurement \(\mathcal{N}_i\) by \(\mathcal{M}_{i,d_i}\circ ... \circ \mathcal{M}_{i,1}\) for some binary measurements \(\mathcal{M}_{i,1},...,\mathcal{M}_{i,d_i}\) where \(d_i \le d\), which is bounded by the number of qubits.

Let \(\tilde{\rho}_t^{(k)}\) be defined as \[(U_t^{(k)}\circ \tilde{O}_{n_t}\circ\ketbra{\lambda_t,x_t})\circ\ldots\circ(U_1^{(k)}\circ \tilde{O}_{n_1}\circ\ketbra{\lambda_1,x_1}) \circ U_0^{(k)} (\ketbra{0}^{\otimes m(\lambda)}),\] where we replaced \(\mathcal{N}_i\) by \(\ketbra{\lambda_i,x_i}\) in 32 . It is not hard to see that each bit of \((\lambda_i,x_i)\) coincides with some of \(b_j\) defined in 15 because \(td/T<1/2.\) By 15, we have \[\begin{align} \label{eqn:32final32td} \| \tilde{\rho}_t^{(k)}- \rho_t^{(k)}\|_{tr} \le \frac{td}{T}. \end{align}\tag{33}\] Now we give another representation of \(\tilde{\rho}_t^{(k)}\). Given fixed \((\lambda_i,x_i)\), the oracle \(\tilde{O}_{n_i}\) generates \(\ket{\phi_{x_i}}_{{\boldsymbol{Y}}_i}\) that is initialized by \(\ket{0}\) and never changed, so we can write \[\tilde{O}_{n_i}\circ\ketbra{\lambda_i, x_i}_{{\boldsymbol{\Lambda}}_i {\boldsymbol{X}}_i}\otimes\ketbra{0}_{{\boldsymbol{Y}}_i}= \ketbra{\lambda_i, x_i}_{{\boldsymbol{\Lambda}}_i {\boldsymbol{X}}_i}\otimes\ketbra{\phi_{x_i}}{0}_{{\boldsymbol{Y}}_i},\] which allows us to write \(\tilde{\rho}_t^{(k)}\) as \[U_t \circ \ketbra{\lambda_t,x_t}\circ\ldots\circ U_1\circ\ketbra{\lambda_1,x_1} \circ U_0 (\ketbra{\phi_{x_t},\dots,\phi_{x_1}}\otimes\ketbra{0}),\] where \(\ket{\phi_{x_t},\dots,\phi_{x_1}}\) is stored in the register \({\boldsymbol{Y}}_t\dots{\boldsymbol{Y}}_1\). Now let \(\tilde{\rho}_j^{(k)}\) be the state after applying \(U_j\) in the above equation. We have that \(\|\tilde{\rho}_j^{(k)}- \rho_j^{(k)}\|_{tr} \le \frac{2td}{T}\) using 33 for all \(j=0,\dots,t-1\) and the fact that the quantum channel never increases the trace distance.

By the part “it also holds” of 15, for any projector \(\Pi=\ketbra{b}\otimes I\) induced from \((\lambda_i,x_i)\)³⁶, it holds that \[\require{physics} \begin{align} \label{eqn:32gentle95inter} \Tr(\Pi\rho_{i-1}) \ge 1-1/T. \end{align}\tag{34}\] Using the triangular inequality, this gives \(\require{physics} \Tr(\Pi \tilde{\rho}_{i-1}) \ge 1-(2td+1)/T\). By applying 4 for each binary measurement, we can replace each projectors by identity and use the triangular inequality to derive \[\begin{align} \| \tilde{\rho}_t^{(k)} - U_t\circ \dots\circ U_0(\ketbra{\phi_{x_t},\dots,\phi_{x_1}}\otimes\ketbra{0})\|_{tr} \le 2td \cdot \sqrt{\frac{2td+1}{T}}. \end{align}\] Together with 33 , this implies that \[\begin{align} \label{eqn:32gengen} \|\rho_t^{(k)} - \tilde{\rho}_t^{(k)}\|_{tr} \le \frac{td}{T} + 2td \cdot\sqrt{\frac{2td+1}{T}}\le (2td+1)\cdot \sqrt{\frac{2td+1}{T}}. \end{align}\tag{35}\] Note that \(\Pr[P_k((\tilde{\rho}_t^{(k)})^{\otimes 2r})\to 1]=1\) by 5. This implies that \(P_k\) outputs 1 on input \(\Phi= (\rho^{(k)}\otimes\ketbra{0}^{\otimes u})^{\otimes 2r}\) with probability at least \[1-2r (2td+1)\cdot \sqrt{\frac{2td+1}{T}} \ge 4/5.\qedhere\]

Here, we need to show that the number of swap test done \(m_k\) in the product test is at least \(13\) for some large enough \(\lambda\). This is because \[\begin{align} m_k & = t + s_k \geq \frac{t \cdot 2\log\lambda + s_k}{2 \log\lambda} \geq \frac{\sum_{i=1}^{t}\ell(\lambda^{(k)}_i) + s_k}{2 \log\lambda} = \frac{\omega(\log\lambda)}{2\log \lambda} = \omega(1), \end{align}\] where we used the fact that the candidate PRS generator has output dimension \(d(\lambda) = \omega(\log\lambda)\).

By 6, we have that a single product test (for key \(k\)) succeeds with expected probability at most \(2\cdot (3/4)^{13}\le 0.05\). By the concentration inequality, we can show that with probability at least \(1-1/2^{2\lambda}\) over Haar random states, a single product test for \(k\) succeeds with probability at most \(0.1\). Using Chernoff’s inequality, we conclude that for each \(k\), \(\Pr[P_k(\Phi)\to 1] \le 1/2^{2\lambda}\).

=1

8 Preliminaries↩︎

8.1 QPSPACE oracle↩︎

We recall the definition of the QPSPACE oracle that implements the arbitrary unitary operation described by polynomial size input [29], [38].

The quantum access to the QPSPACE oracle is done by allowing coherent \((M,t)\). For any unitary quantum circuit \(C\) that is output by a machine \(M\) after \(t\) steps, there is a QPT algorithm with \(\mathbf{QPSPACE}\) oracle that implements \(C^{-1}(\rho)\) on input \(\rho\) [38].

8.2 State property tests↩︎

8.2.1 Swap test↩︎

We review the basic results of the swap test, which can be used to test the purity of a state. We provide some lemmas about the swap test on a state that is close to pure states, which are essential to obtain our results.

For two quantum states \(\sigma,\rho\) stored in two different registers \({\mathbf{A}},{\mathbf{B}}\), the swap test is executed on the registers \({\mathbf{A}},{\mathbf{B}}\) and a control register \({\mathbf{C}}\) initialized to \(\ketbra{1}\). It applies Hadamard on \({\mathbf{C}}\), swaps \({\mathbf{A}}\) and \({\mathbf{B}}\) conditioned on \({\mathbf{C}}\), and measures \({\mathbf{C}}\) on the Hadamard basis.

When \(\sigma=\rho\), we sometimes call it a on \(\rho\), which outputs \(1\) with certainty if and only if \(\rho\) is a pure state.

Note that each test succeeds with probability \(\require{physics} (1+\Tr(\rho^2))/2\le 1-1/2T\), and is independent of each other. Applying Chernoff’s inequality (9) for \(\delta=1/2\), we obtain the desired result.

8.2.2 Product test↩︎

We first recall the product test to determine whether an \(n\)-partite state \(\ket{\phi}\) is a product state or far from any product state from [45], then give a bound on the success of the product test on Haar-random states.

For Haar-random states, the above formula is explicitly calculated for any partition \(S\cup\overline{S}\) of \([m]\) by [48]: \[\require{physics} \underset{\ket{\psi}\gets\sigma}{\mathbb{E}}\Tr[\rho_S^2]=\frac{d_S+d_{\overline{S}}}{d_S\cdot d_{\overline{S}}+1}.\] =1 As a consequence, we have the following bound for the success of the product test on Haar-random states, whose proof is given in 13.1. As a consequence, we have the following bound for the success of the product test on Haar-random states.

=0 =1 For every partition \(S\cup\overline{S}\) of \([m]\), the local dimension of each partition is given by \(d_S=\prod_{i\in S}d_i\). \[\require{physics} \begin{align} \underset{\ket{\psi}\gets\sigma}{\mathbb{E}}\Pr(1\gets\mathcal{A}_\mathtt{PTEST}(\ket{\psi}^{\otimes 2}))& =\underset{\ket{\psi}\gets\sigma}{\mathbb{E}}\left[\frac{1}{2^m}\sum_{S\subseteq[m]}\Tr[\rho_S^2]\right] \\ &=\frac{1}{2^m}\sum_{S\subseteq[m]}\frac{d_S+d_{\overline{S}}}{d_S\cdot d_{\overline{S}}+1}\le \frac{1}{2^m}\sum_{S\subseteq[m]}\frac{d_S+d_{\overline{S}}}{d_S\cdot d_{\overline{S}}} \\&=\frac{1}{2^m}\left(\sum_{S\subseteq[m]}\frac{1}{d_S} + \frac{1}{d_{\overline{S}}}\right) =\frac{2}{2^m}\left(\sum_{S\subseteq[m]}\frac{1}{d_S} \right) \\&=\frac{2}{2^m}\prod_{i\in[m]} \left(1+\frac{1}{d_i}\right) \leq \frac{2}{2^m}\prod_{i=1}^m\left(\frac{3}{2}\right)=2\left(\frac{3}{4}\right)^m, \end{align}\] where we use the fact that each \(d_i\geq 2\) to obtain the last inequality.

8.3 Quantum OR lemma↩︎

8.4 Useful lemmas↩︎

We have \(\|\mathcal{M}(\rho)-\Pi_0\rho\Pi_0\|_{tr}=\|\Pi_1\rho \Pi_1\|_{tr}\le \varepsilon,\) which gives the result.

8.4.1 Norms and Process tomography.↩︎

For a matrix \(M\), the operator norm is defined by \[\|M\|_{op}:= \sup_{\|\ket{\phi}\|_2=1} \|M\ket{\phi}\|_2,\] which satisfies \(\|M+N\|_{op}= \max(\|M\|_{op},\|N\|_{op})\) if \(M\) and \(N\) act on the orthogonal space. In particular, for \(M=\sum_x \ketbra{x} \otimes M_x\), it holds that \[\begin{align} \label{fjxvtmuh} \|M\|_{op} = \max_{x} \|M_x\|_{op}. \end{align}\tag{36}\]

The diamond norm of an operator \(A\), denoted by \(\|A\|_\diamond\), is defined by: \[\require{physics} \|A(\cdot)\|_\diamond:= \sup_{\Tr(\rho)=1,\rho \ge 0} \|A\otimes I(\rho)\|_1,\] where \(I\) denotes the identity acting with the same dimension as \(A\). We sometimes omit \((\cdot)\) if it is clear from the context. We use the following fact about the diamond norm: for quantum channels \(A,B\) and a density matrix \(\rho\), it holds that \[\|A\otimes I(\rho) - B\otimes I(\rho)\|_{tr} \le\frac{1}{2} \|A(\cdot) -B(\cdot) \|_\diamond.\] We will also use the fact that for unitaries \(U,V\) and the corresponding channels \(\mathcal{U},\mathcal{V}\), it holds that \[\label{xinkozjc} \|\mathcal{U}(\cdot) - \mathcal{V}(\cdot) \|_\diamond \le 2 \|U-V\|_{op}\tag{37}\] for the operator norm \(\|\cdot\|_{op}\) because \[\require{physics} \begin{align} \|\mathcal{U}(\cdot) - \mathcal{V}(\cdot)\|_\diamond & =\sup_{\Tr(\rho)=1,\rho \ge 0} \|(U\otimes I)(\rho)(U^\dagger \otimes I)-(V\otimes I)(\rho)(V^\dagger \otimes I)\|_1 \\ & \le \sup_{\Tr(\rho)=1,\rho \ge 0} \|(U-V)\otimes I\|_{op} \|\rho\|_1 \|U^\dagger \otimes I\|_{op} + \|V\otimes I\|_{op} \|\rho\|_1 \|(U^\dagger- V^\dagger) \otimes I\|_{op} \\&\le 2\|U-V\|_{op} \end{align}\] where we use \(\|A\rho B\|_1 \le \|A\|_{op} \|\rho\|_1 \|B\|_{op}\).

8.4.2 Chernoff bounds.↩︎

We use the following concentration inequalities.

9 Formal Proof of the Barrier Theorem↩︎

=1

Recall that \(\mathbb{S}(2^n) = \mathbb{CP}^{2^n-1}\) denotes the space of \(n\)-qubit quantum states, i.e., the \(2^n\)-dimensional complex projective space. Our theorem is stated as follows. For two elements \(\Phi=(\ket{\phi_1},\ldots,\ket{\phi_k}),\Psi=(\ket{\psi_1},\ldots,\ket{\psi_k})\) in \(X=\mathbb{S}(2^{n_1})\times \cdots \times \mathbb{S}(2^{n_k})\), the max-trace distance is defined by \(d_{\infty}(\Phi,\Psi)\vcentcolon=\max_{i\in [k]} \|\phi_i - \psi_i\|_{tr}\).

9.0.0.1 Distances.

We consider various distances of quantum states. For two pure states, the trace distance is \[d_{tr}(\phi,\psi) = \|\phi -\psi\|_ {tr} = \sqrt{1-|\braket{\phi}{\psi}|^2}.\] In the complex projective space \(\mathbb{CP}^{n}\), the Fubini-Study (geodesic) distance, also known as the standard angle distance, is defined by \[d_{FS}(\phi,\psi) = \arccos|\braket{\phi}{\psi}|.\] We have \(d_{tr} (\phi,\psi)= \sin (d_{FS}(\phi,\psi)) \le d_{FS}(\phi,\psi)\) in \(\mathbb{S}(2^{n_i})\).

In the product space \(X\), we consider two distances. The first distance is the max-trace distance \(d_{\infty}\) defined above. The other distance is the \(\ell_2\) distance \[\begin{align} \label{gfkosjbq} d_2(\Phi,\Psi) = \sqrt{\sum_{i=1}^k d_{FS,i} (\phi_i,\psi_i)^2} \end{align}\tag{38}\] where \(d_{FS,i}\) is the Fubini-Study distance in \(\mathbb{S}(2^{n_i})\). We stress that the distance \(d_2\) is defined for the Fubini-Study distance, while \(d_\infty\) is defined for the trace distance. We will later use the following inequality: \[d_{\infty}(\Phi,\Psi) = \max_i d_{tr}(\phi_i,\psi_i) \le \max_i d_{FS}(\phi_i,\psi_i) \le d_2(\Phi,\Psi).\]

9.0.0.2 Riemannian manifolds and metrics, and Ricci curvature.

A Riemannian manifold is a pair of \((M,g)\), where \(M\) is a smooth manifold and \(g\) is a Riemannian metric³⁷, which assigns a positive-definite symmetric bilinear form \(g_p: T_pM\times T_pM \to \mathbb{R}\) for each point \(p\in M\), where \(T_pM\) denotes the tangent space of \(M\) at \(p\). The Riemannian manifold gives rise to the geodesic distance \(d_g\). In the complex projective space \(\mathbb{CP}^{n}\), we define the Fubini-Study metric \(g_{FS}\) as the metric induced by the quotient \(\mathbb{S}^{2n+1}/\mathbb{S}\) with the standard Euclidean metric restricted to the unit hypersphere. The geodesic distance of \(g_{FS}\) is the Fubini-Study distance \(d_{FS}\) defined above. There is a natural notion of the products of Riemannian manifolds; the geodesic distance of the products of the projective spaces with the Fubini-Study metric gives the \(\ell_2\) distance defined in 7 . Looking ahead, we will prove the statement for \(d_2\) (instead of \(d_\infty\)) using the results from differential geometry below.

On the Riemannian manifold, the Ricci curvature tensor \(\mathbf{Ric}\) is uniquely determined and gives a symmetric bilinear form \(\mathbf{Ric}_p: T_pM\times T_pM \to \mathbb{R}\) for each point \(p\in M\). In the product of Riemannian manifolds \(S=\prod_{1\le i \le r}(M_i,g_i)\) and the point \({\boldsymbol{v}}=(v_1,...,v_r) \in S\), the Ricci curvature satisfies \[\begin{align} \label{noskbqcv} \mathbf{Ric}_S({\boldsymbol{v}},{\boldsymbol{v}}) = \sum_{i=1}^r {\mathbf{Ric}}_{M_i} (v_i,v_i). \end{align}\tag{39}\] The intrinsic Riemannian metric \({\boldsymbol{g}}=(g_1,...,g_r)\) satisfies a similar equality.

For a constant \(c\), we occasionally use the notation \[\begin{align} \label{oykrniew} \mathbf{Ric}\ge c \cdot g \Longleftrightarrow \mathbf{Ric}_p - c\cdot g_p \geqslant 0~~ \forall p \in M \end{align}\tag{40}\] where \(\geqslant\) denotes the positive semi-definite inequality. Equivalently, it means \[\mathbf{Ric}_p(v,v) \ge c\cdot g_p(v,v)\] holds (as an inequality over real numbers) for all \(p \in M\) and \(v \in T_pM\). We note that \(\mathbf{Ric}\ge c \cdot g\) is usually denoted by \(\mathbf{Ric}\ge c\) in the literature.

We only use Riemannian manifolds and Ricci curvatures for our underlying space \(X=\mathbb{S}(2^{n_1})\times \cdots \times \mathbb{S}(2^{n_k})\) regarding the above relations, where we recall \(\mathbb{S}(2^{n})=\mathbb{CP}^{2^n-1}\). The complex projective space \(\mathbb{CP}^{n}\) satisfies \(\mathbf{Ric}=2(n+1) \cdot g_{FS}\) (i.e., an Einstein manifold) [51]. For our main interest \(X\) together with the product Fubini-Study metric, for \({\boldsymbol{v}} = (v_1,...,v_k) \in X\) it holds that \[\mathbf{Ric}_X({\boldsymbol{v}},{\boldsymbol{v}}) = \sum_{i=1}^k \mathbf{Ric}_{\mathbb{S}(2^{n_i})} (v_i,v_i) \ge \sum_{i=1}^k 2^{n_i+1}\cdot g_{FS,i}(v_i,v_i) \ge 4 \sum_i g_{FS,i} (v_i,v_i) = 4{\boldsymbol{g}}({\boldsymbol{v}},{\boldsymbol{v}}),\] which means \(X\) satisfies 9 for \(c=4.\)

Lichnerowicz’s theorem [52] states that (See e.g., [53]) for an \(n\)-dimensional compact Riemannian manifold \((M_n,g)\), if \(\mathbf{Ric}\ge c\cdot g\) for some \(c>0\), then the first nonzero eigenvalue of the Laplacian³⁸ satisfies \[\begin{align} \lambda_1 \ge \frac{nc}{n-1} \ge c. \end{align}\] In particular, for \(X\) together with the product Fubini-Study metric, it holds that \[\begin{align} \label{kxeoiybt} \lambda_1 \ge 4. \end{align}\tag{41}\]

9.0.0.3 Cheeger isoperimetric constant.

We use the modern exposition for isoperimetric inequalities from [54]. Consider a Riemannian manifold \((M,g)\) with the geodesic distance \(d\) and probability measure \(\sigma\) (i.e., \(\sigma(M)=1\)). We define the outer Minkowski boundary measure (or the area) of a measurable set \(E\) by \[\sigma^+(E)=\liminf_{r \downarrow 0} \frac{\sigma(E[r]) - \sigma(E)}{r}\] where \(E[r]:= \{p \in M: d(p,E)\le r\}\) is a closed neighborhood of \(E\). The Cheeger isoperimetric constant is \[\label{krdwxmgn} h_M := \inf_{E:\text{measurable}, 0<\sigma(E)<1} \frac{\sigma^+(E)}{\min(\sigma(E),1-\sigma(E))}.\tag{42}\]

Let \(\lambda_1\) be the smallest nonnegative eigenvalue of the Laplacian of \(M\). Buser’s inequality [55] says that if \(\mathbf{Ric}\ge -(n-1)a^2\) for some \(a\ge 0\), then it holds that \(\lambda_1\le 2a(n-1)h_M + 10h_M^2\). If \(\mathbf{Ric}\ge 0\), we have \(\lambda_1 \le 10h_M^2\). This implies that, for our \(X\), \[\begin{align} \label{enrmkzut} h_X \ge \sqrt{2/5} \end{align}\tag{43}\] holds because \(\mathbf{Ric}\ge 4 {\boldsymbol{g}} \ge 0\) in \(X\) and 10 .

9.0.0.4 Proof of 10.

We first work on the product space \(X\) together with the product Fubini-Study metric and the corresponding \(\ell_2\) distance \(d_2\). Let \(v(r):= \sigma(S_0[r])\) for \(0\le r\le \Delta\). Here, we assume that \(v\) is differentiable so that \(v'(r)=\sigma^+(S[r])\). This significantly simplifies the proof of 14 , and we provide the formal proof without this assumption in 9.1.

Note that in the definition of \(S_0[r]\) in \(X\), we use the natural distance \(d_2\) induced by the Riemannian manifold \(X\). Given the condition \(d_\infty(S_0,S_1) \ge \Delta\), we also have \(d_2(S_0,S_1) \ge d_\infty(S_0,S_1) \ge \Delta\). For any \(0\le r <\Delta\), \(S_0[r] \cap S_1 = \emptyset\) holds so that \(v(r)= \sigma(S_0[r]) \le 1-\sigma(S_1)\) and \(1-v(r) \ge \sigma(S_1) \ge \Gamma\). This implies \(\min(v(r),1-v(r)) \ge \Gamma.\)

The Cheeger constant ensures \[\label{devyfapg} v'(r) \ge h_X \min (v(r),1-v(r)) \ge h_X v(0) \ge h_X \Gamma.\tag{44}\] Integrating \(v'\) gives: \[\begin{align} \label{smhiwqnd} \sigma(S_0[\Delta]) - \sigma(S_0) = v(\Delta)-v(0) \ge \int_0^{\Delta} v'(r) dr \ge h_X \Gamma \Delta. \end{align}\tag{45}\] We also have \(\sigma(S_0[\Delta]) \le 1-\sigma(S_1)\) by taking \(r\to \Delta.\) This, together with 14 , gives: \[\sigma(X\setminus(S_0 \cup S_1))=1-\sigma(S_0) - \sigma(S_1)\ge \sigma(S_0[\Delta]) - \sigma(S_0) \ge h_X \Gamma \Delta\] where \(h_X \ge \sqrt{2/5}\) by 12 . This proves the desired result.

9.1 Removing differentiability assumption↩︎

In this section, we show how to prove 14 without assuming the differentiability of \(v(r)=\sigma(S_0[r])\). Recall that the Cheeger constant in 11 and the condition \(\sigma(S_0,S_1)\ge \Gamma\) implies that \[\sigma^+(S_0[r]) \ge h_X \Gamma\] for \(r\in [0,\Delta)\) as in 13 . Let \(\varepsilon>0\). The outer Minkowski measure says that for each \(r\), there exists \(\delta_r\) such that for any \(h\in [0,\delta_r)\) and \(r+h\le \Delta\), \[\label{eqn:Minkow95eps} \frac{\sigma(S_0[r+h]) - \sigma(S_0[r])}{h} \ge (h_X \Gamma-\varepsilon)\tag{46}\] where we use \(S_0[r][h]=S_0[r+h]\). Define the set \[G_\varepsilon:= \left\{ t\in[0,\Delta]: \sigma(S_0[t]) - \sigma(S_0) \ge t\cdot (h_X \Gamma-\varepsilon) \right\}.\]

We will prove that \(\Delta \in G_\varepsilon\). Assuming this, we have \[\label{eqn:G95eps95final} \sigma(S_0[\Delta]) - \sigma(S_0) \ge \Delta \cdot (h_X \Gamma-\varepsilon)\tag{47}\] thus choosing \(\varepsilon\to 0\) proves 14 .

Let \(a:=\sup G_\varepsilon\), which is well-defined because \(0\) is included in \(G_\varepsilon\). Let us assume that \(a\in G_\varepsilon\), which will be proven later. If \(a<\Delta\), for a sufficiently small \(h\), we have \[\begin{align} \sigma(S_0[a+h])-\sigma(S_0[0]) & =(\sigma(S_0[a+h])-\sigma(S_0[a]))+(\sigma(S_0[a])-\sigma(S_0[0])) \\& \ge h \cdot (h_X \Gamma-\varepsilon) + a \cdot (h_X \Gamma-\varepsilon) \\&= (h+a) \cdot (h_X \Gamma-\varepsilon) \end{align}\] where, to prove the inequality, we use 46 in the first term and the fact that \(a\in G_\varepsilon\) in the second term. This says that \(a+h\in G_\varepsilon\), which contradicts to \(a= \sup G_\varepsilon\). Therefore \(a=\Delta \in G_\varepsilon\), proving 47 .

It remains to prove that \(a\in G_\varepsilon\). By the definition of \(a\), there exists an increasing sequence \((a_n)_{n\in \mathbb{N}}\) that converges to \(a\). Since \(\sigma(S_0[r])\) is an increasing function, we have \[\sigma(S_0[a])\ge \sigma(S_0[a_n]) \ge a_n\cdot (h_X \Gamma-\varepsilon)\] where the last inequality holds because \(a_n \in G_\varepsilon\). Taking \(n\to \infty\) gives \[\sigma(S_0[a])\ge a\cdot (h_X \Gamma-\varepsilon),\] proving \(a\in G_\varepsilon\). This concludes the proof.

10 Average-case Hard Language↩︎

This section presents an average-case hard language in \(\mathbf{QCMA}\cap \mathbf{coQCMA}\) in the log-length unitary CHFS oracle model with a sketch of the analysis. The non-existence of QOWF is clear due to the main theorem.

We first formally define the samplable problem distributions and related quantum complexity, adapting [58].

We say that a samplable decisional problem \((\mathcal{L},\{D_n\})\) is quantumly easy-on-average if there exists a BQP algorithm \(A\), such that \[\Pr_{x \gets D_n}\left[ \Pr_A\left[A(x)\to \mathcal{L}(x)\right]\le 2/3 \right]=\negl[n].\] Otherwise, we say that \((\mathcal{L},\{D_n\})\) is hard-on-average. Our goal is to exhibit a samplable language \((\mathcal{L},\{D_n\})\) in \(\mathbf{sampQCMA}\cap \mathbf{sampcoQCMA}\) that is hard-on-average. Note that the existence of quantum-computable one-way functions implies the existence of a quantumly hard-on-average language in \(\mathbf{sampQCMA}\) by the Goldreich-Levin theorem.³⁹ The converse of this implication does not hold in our world, where quantum-computable one-way functions do not exist, yet there exists a quantumly hard-on-average language in \(\mathbf{sampQCMA}\), suggesting that our world is a quantum-computable version of Pessiland.

We consider the unitary CHFS oracle model with \(\ell(\lambda)= \lceil c\log \lambda\rceil\) for sufficiently large \(c\gg 1\). In other words, our CHFS oracle maps \(\ket{x,0,0}\) to \(\ket{x,1,\phi_x}\) for \(\ell (|x|)\)-qubit state \(\phi_x\). We have the following properties for the CHFS oracles.

• The output states are almost orthogonal. More precisely, with probability 1 over the choice of the CHFS oracle, \(|\braket{\phi_x}{\phi_{x'}}|^2\le 0.01\) holds for all \((x,x') \in \{0,1\}^\lambda \times\{0,1\}^\lambda\) for all sufficiently large \(\lambda\). This is because of 2 and 3.⁴⁰

• The output states admit polynomial-length classical descriptions. More precisely, there are two efficient procedures \(\sf Description\) that maps a (polynomial copies of) \(\ell(n)\)-qubit quantum state to a \(\poly[n]\)-length classical string and \(\sf Construct\) that maps a \(\poly[n]\)-length classical string to an \(\ell(n)\)-qubit quantum state such that: \[\|\rho -{\sf Construct}({\sf Description}(\rho))\|_1\le 2^{-|\rho|}.\] Furthermore, \({\sf Construct}\) is deterministic.⁴¹

Given these observations, we define the distribution ensembles that sample from \(D^{yes}\) with probability \(1/2\) and from \(D^{no}\) with probability \(1/2\). Here we use \(\le\) to denote the lexicographical order.

(\(D^{yes}\))

We pick a random pair \(x \le z\), and outputs \(({\sf Description}(\phi_x),z)\).

(\(D^{no}\))

We pick a random pair \(x > z\), and outputs \(({\sf Description}(\phi_x),z)\).

Define the language \(\mathcal{L}\) so that \(\mathcal{L}(y,z)=1\) only if \(\|{\sf Construct}(y)-\phi_x\|_1 \le 0.01\) for some \(x\) such that \(x \le z\). By definition, this language is in \(\mathbf{sampQCMA}\) using such an \(x\) as the witness.

To analyze, we recall that \(\ket{\phi_x}\) is almost orthogonal to \(\ket{\phi_x}\) for \(x'\neq x\), which implies that for each \(y\), there is at most a single \(x\) such that \(\|{\sf Construct}(y)-\phi_x\|_1 \le 0.01\). This shows that \(x\) can be a witness for \(\mathbf{coQCMA}\) as well, showing that the language is in \(\mathbf{sampcoQCMA}.\)

The proof of the quantum average-case-hardness is analogous to [16], who showed \(\mathbf{BQP}\notin {\boldsymbol{N}P}\cap {\boldsymbol{c}oNP}\) relative to the random permutation oracles. If the language is quantumly easy-on-average, we can find \(x\) from multiple copies of \(\ket{\phi_x}\) using the binary search on \({\sf Description}(\phi_x)\) for most of \(x\). This breaks the one-wayness of the map \(x\to \phi_x\) that is shown by the reduction to the quantum search.

=1

11 Oracle Separation of PRUs from PRFSGs↩︎

In this section, we consider the length-\(\ell\) quantum-accessible unitarized CHFS oracle \(\mathcal{S}=\mathcal{S}_{\ell}\) for \(\ell(|x|)=|x|\) and the \(\mathbf{QPSPACE}\) oracle. We will prove the following theorem, which is the main result of this section.

The existence of the adaptively-secure quantum-accessible PRFSGs relative to the oracles is proven by 8. What remains is to prove that PRUs without ancilla do not exist in this model.

We prove the lemma by contradiction. Assume that \(\{G^{\mathcal{S},\mathbf{QPSPACE}}_{\lambda}(\cdot)\}_{\lambda}\) is a secure \(n(\lambda)\)-PRU construction relative to \((\mathcal{S},\mathbf{QPSPACE})\) for \(n(\lambda)=\omega(\log \lambda).\) For simplicity, we drop the \(\mathbf{QPSPACE}\) oracle and \(\lambda\) in notations and write \(G_{k}^{\mathcal{S}}\) to denote \(G^{\mathcal{S},\mathbf{QPSPACE}}_{|k|}(k)\). The adversary is given oracle access to the oracle \((V,\mathcal{S},\mathbf{QPSPACE})\) where \(V\) is either \(G_{k^{*}}^{\mathcal{S}}\) for some \(k^{*}\) or a Haar random unitary of the same size, and tries to determine which is the case with non-negligible probability.

We write \(\mathcal{S} = (S_{d})_{d\in \mathbb{N}}\) where \(S_{d}=\sum_{x\in \{0,1\}^{d}} \ketbra{x} \otimes S_{\ket{\phi_{x}}}\) to denote the unitary CHFS oracle, where \(S_{\ket{\phi_{x}}}\) denotes the swap oracle defined in 6 for some \(d\)-qubit Haar random quantum state \(\ket{\phi_{x}}\) and \(S_{d}\) acts on a \((2d+1)\)-qubit space.⁴²

Let \(m=\poly\) be the maximum number of oracle queries to \(\mathcal{S}\) that \(G^{\mathcal{S}}\) makes. We show that distinguishing \(G_{k}^{\mathcal{S}}\) from a Haar random unitary can be done efficiently based on swap tests. More concretely, we prove that the following algorithm \(\adv^{V,\mathcal{S},\mathbf{QPSPACE}}\) can guess with non-negligible probability whether \(V\) is \(G_{k}^{\mathcal{S}}\) for some random \(k\), (in which case it outputs \(1\)), or a truly Haar random unitary (in which case it outputs \(0\)). For simplicity, we omit the oracle notation and write \(\adv\) for \(\adv^{V,\mathcal{S},\mathbf{QPSPACE}}\).

The following claims summarize the main analysis of the algorithm, which will be proven at the end of this section. 2 is a \(\mathbf{BQP}^{V,\mathcal{S},\mathbf{QPSPACE}}\) algorithm, which makes non-adaptive queries to \(V\). If \(V=G_{k}^{\mathcal{S}}\) for some \(k\) and \(\require{physics} \Tr(G_{k}^{\mathcal{S}}(\phi)^{2})\ge 1-1/\lambda\), then \(\Pr[P_{k}(\Psi) \to 1] \ge 1-2^{-\lambda}\) holds with probability at least \(1-\frac{m+\tau}{2^{2\lambda}}\) over the randomness of the algorithm for sufficiently large \(\lambda\). If \(V\gets \mu_{n}\), then \(\Pr[P_{k}(\Psi) \to 1] \le 2^{-2\lambda}\) holds for all \(k\) with probability at least \(1-2^{-\lambda}\) over the randomness of the algorithm for sufficiently large \(\lambda\).

The efficiency of the algorithm relative to \(\mathcal{S},\mathbf{QPSPACE}\) is provided by [claim:32Sep1AlgBQP]. Also note that the algorithm breaks the non-adaptive security of PRUs, as the queries to \(V\) only occur in the first step and to prepare \(\Psi\) which are all non-adaptive queries.

The correctness of the algorithm can be shown by the case analysis. If \(V=G_{k}^{\mathcal{S}}\) for some \(k\) and if \(\require{physics} \Tr(G_{k}^{\mathcal{S}}(\phi)^{2})\le 1-1/\lambda\), the first step of \(\adv\) outputs 1 with probability at least \(1-2^{-\lambda}\) as shown in 4.

The other case, i.e., \(V=G_{k}^{\mathcal{S}}\) and \(\require{physics} \Tr(G_{k}^{\mathcal{S}}(\phi)^{2})\ge 1-1/\lambda\) or \(V\) is a true Haar random unitary is dealt with by the quantum OR lemma. In this case, by [claim:32Sep1Gk] and [claim:32Sep1Haar], the POVMs \(\{P_{k}\}_{k\in \{0,1\}^{\lambda}}\) and \(\Psi\) satisfy the conditions of the quantum OR lemma (7) unless with probability \(2^{\lambda}\cdot \frac{m+\tau}{2^{2\lambda}} +2^{-\lambda} \le 2/2^{\lambda}\) for large enough \(\lambda\), \(\varepsilon=1/2^{\lambda}\) and \(\delta=1/2^{2\lambda}\). Therefore, \(\adv\) outputs 1 with probability at least \(1/8\) if \(V=G_{k}^{\mathcal{S}}\) for some \(k\), but it outputs 1 with probability at most \(4/2^{\lambda}\) if \(V\gets \mu_{n}\), that is, \(\adv\) breaks the PRU security of \(\{G_{k}^{\mathcal{S}}\}\). This concludes the proof.

We now prove the claims. The first step takes polynomial time and \(32\lambda^{2}\) non-adaptive queries to the oracle \(V\). The second step has time and query complexity (to \(\mathcal{S}\)) equal to \(\tau \times {\sf poly}\left(d,\frac{1}{\varepsilon},\log \frac{1}{\delta}\right) = {\sf poly}\left(2^{\tau}, 2^{\tau}, \lambda\right) =\poly\). Note that it is clear that \(P_{k}\) can be executed by a quantum polynomial space machine. In the final step, the quantum OR tester can be executed by a \(\mathbf{QPSPACE}\)-aided BQP machine as noted in “Moreover” part of 7 with inputs the descriptions of \(S_{i}'\) for \(i\le \tau\) (prepared by the first step) as \(P_{k}\) can be implemented by a quantum polynomial-space machine.

We will show that \(G_{k}^{\mathcal{S}}(\ketbra\rho)\) and \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra\rho)\) are close with high probability, for a Haar random input state \(\ket{\rho}\) of size \(n\)-qubit. We will write \(\rho = \ketbra{\rho}\) as a short-hand.

We begin with the following two closeness properties for \(S_{d}\) and \(\tilde{S}_{d}\) from the later steps of the algorithm. First, for small dimensions \(d \le \tau < n\), 7 ensures that \[\begin{align} \label{rfkthmcw} \|\tilde{S}_{d}\otimes I(\rho) - {S}_{d}\otimes I(\rho)\|_{tr}= \|S_{d}'\otimes I(\rho) - {S}_{d}\otimes I(\rho)\|_{tr} \le\frac{\varepsilon}{2}= \frac{1}{2^{\tau/2}}, \end{align}\tag{48}\] holds for any quantum state \(\rho\) with probability \(1-\delta = 1-\frac{1}{2^{2\lambda}}\). Thus all tomography outputs are \(1/2^{\tau/2}\)-close to the target unitaries with overwhelming probability \(1-p_{1}\), for \(p_{1}=\tau/2^{2\lambda}\). In the following, we assume it is the case.

For large dimensions \(d>\tau\), we show that \(S_{d}\) acts almost as the identity with high probability for a pure Haar quantum state \(\ket{\rho}=\sum_{x,z} \alpha_{x,z} \ket{x}\ket{\rho_{x,z}}\ket{z}\) such that \(\sum_{x,z} |\alpha_{x,z}|^{2}=1\), and \(\ket{\rho_{x, z}}\) is of size \(d\). We have \[\begin{align} & \mathbb{E}_{\mathcal{S}}\|\tilde{S}_{d} \otimes I(\ketbra\rho)-S_{d}\otimes I(\ketbra\rho)\|_{tr} \\& =\mathbb{E}_{\mathcal{S}}\|I(\ketbra\rho)-S_{d}\otimes I(\ketbra\rho)\|_{tr} \\&= \frac{1}{2}\sum_{x\in \{0,1\}^{d}} \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ \bra{\rho}(\ketbra{x} \otimes \left(I_{d+1} - S_{\ket{\phi_{x}}}\right)\otimes I )\ket{\rho}\right] \\&= \frac{1}{2}\sum_{x\in \{0,1\}^{d}} \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ \bra{\rho}(\ketbra{x}\otimes(\ketbra{1,\phi_{x}}{0}+\ketbra{0}{1,\phi_{x}}) \otimes I)\ket{\rho}\right] \\&\le \sum_{x\in \{0,1\}^{d},z} \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ |\bra{\rho}\ketbra{x}\otimes\ketbra{1,\phi_{x}}{0} \otimes \ketbra{z}\ket{\rho}|\right] \\&= \sum_{x\in \{0,1\}^{d},z} |\alpha_{x,z}|^{2} \cdot \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ |\bra{\rho_{x,z}}\ketbra{1,\phi_{x}}{0} \ket{\rho_{x,z}}|\right] \\&\le \sum_{x\in \{0,1\}^{d},z} |\alpha_{x,z}|^{2} \cdot \mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ |\bra{\rho_{x,z}}\ket{1,\phi_{x}} |\right] \\&\le \sum_{x\in \{0,1\}^{d},z} |\alpha_{x,z}|^{2} \sqrt{\mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ |\braket{\rho_{x,z}}{1,\phi_{x}}|^{2}\right]}, \end{align}\] where we use 6 8 in the first few equalities. The factor \(1/2\) comes from the definition of the trace distance. The first inequality uses \((a+\bar a)=2{\sf Re}(a) \le 2|a|\) for \(a=\bra{\rho}(\ketbra x \otimes \ketbra{1,\phi_{x}}0\otimes I)\ket{\rho}\). The second inequality uses \(|\braket{0}{\rho_{x,z}}|\le 1\). The last inequality is \(\mathbb{E}[{X}]^{2} \le \mathbb{E}[{X}^{2}]\). This can be bounded by \[\begin{align} & \sum_{x\in \{0,1\}^{d},z} |\alpha_{x,z}|^{2} \sqrt{\mathbb{E}_{\phi_{x} \gets \sigma_{d}}\left[ \braket{1,\phi_{x}}{\rho_{x,z}}\braket{\rho_{x,z}}{1,\phi_{x}}\right]} \\&\quad\quad\quad\le \sqrt{\mathbb{E}_{\phi_{x} \gets \sigma_{d}\forall x\in\{0,1\}^{d}}\left[\sum_{x,z}|\alpha_{x,z}|^{2} \cdot\braket{1,\phi_{x}}{\rho_{x,z}}\braket{\rho_{x,z}}{1,\phi_{x}}\right]}, \end{align}\] using Jensen’s inequality for \(f(x)=\sqrt x\). Let \[p=\mathbb{E}_{\phi_{x} \gets \sigma_{d}\forall x\in\{0,1\}^{d}}\left[\sum_{x,z}|\alpha_{x,z}|^{2} \cdot\braket{1,\phi_{x}}{\rho_{x,z}}\braket{\rho_{x,z}}{1,\phi_{x}}\right] \le {\frac{1}{2^{d}}} \le \frac{1}{2^{\tau}},\] by 2 for the projector \(\ketbra{\rho_{x,z}}\) with \(d\)-qubit Haar random state \(\ket{\phi_{x}}\). This can be written as the probability that an algorithm succeeds projection⁴³, so we can apply 3 with \(t=1/2^{\tau}\), which gives \[\begin{align} \label{kqtynwej} \Pr_{\mathcal{S}_{>\tau}}\left[ \|I(\ketbra \rho)-S_{d}\otimes I(\ketbra \rho)\|^{2} _{tr}\ge \frac{2}{2^{\tau}} \right] \le \exp \left( -\frac{2^{n}-2}{24\cdot 2^{2\tau}} \right) \le \frac{1}{2^{2\lambda}}, \end{align}\tag{49}\] for sufficiently large \(n\).⁴⁴ Here \(\mathcal{S}_{>\tau}\) denotes the oracle with dimension \(d>\tau\).

To bound the trace distance between \(G_{k}^{\mathcal{S}}(\ketbra{\rho})\) and \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\), we use the hybrid argument using the above two observations. Let \({\Phi_{j}}\) for \(0\le j \le m\) be equal to the outcome of \(G_{k}\) on input \(\ketbra{\rho}\) with the first \(j\) oracle queries are answered using \(\tilde{\mathcal{S}}\) and the other \(m-j\) queries are answered using \(\mathcal{S}\). We have that \({\Phi_{0}}\) is the state \(G_{k}^{\mathcal{S}}(\phi)\) and \({\Phi_{m}}\) is the state \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\).

Let \(\ket{\phi_{j}}\) be the intermediate state right after \(j\)-th oracle query when computing \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\). We have \(\|I(\phi_{j}) - (S_{d}\otimes I)(\phi_{j})\|_{tr} \le 2/2^{\tau/2}\) holds with probability \(1-\frac{1}{2^{2\lambda}}\) over the randomness of the oracle by 28 . Then, by the monotonicity of the trace distance, we have \[\begin{align} \left\|G_{k}^{\mathcal{S}} (\ketbra{\rho}) - G_{k}^{\tilde{\mathcal{S}}} (\ketbra{\rho}) \right\|_{tr} & \le \sum_{j=0}^{m-1}\|S_{d_{j}^{(k)}}\otimes I(\phi_{j})-\tilde{S}_{d_{j}^{(k)}}\otimes I(\phi_{j})\| _{tr} \\& \le \sum_{j=0}^{m-1} \max\left(\frac{\varepsilon}{2} , \frac{2}{2^{\tau/2}}\right) = \frac{2m}{2^{\tau/2}} = \frac{1}{8}, \end{align}\] with probability \(1-p_{2}\) for \(p_{2}=\frac{m}{2^{2\lambda}}\); we again focus on this case.

We finally analyze the success probability of a single swap test between \(G_{k}^{\mathcal{S}}(\ketbra{\rho})\) and \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\) succeeds in subroutine \(P_{k}\). Since =1 \[\begin{align} & \|G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\otimes G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})-G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\otimes G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\|_{tr} \\ & \quad\quad=\|G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho}) - G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\|_{tr} \le 1/8, \end{align}\] \[\begin{align} \|G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\otimes G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})-G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\otimes G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\|_{tr} =\|G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho}) - G_{k}^{{\mathcal{S}}}(\ketbra{\rho})\|_{tr} \le 1/8, \end{align}\] we have \[\require{physics} \begin{align} \left| \frac{1+\Tr(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})G_{k}^{{\mathcal{S}}}(\ketbra{\rho}))}{2} - \frac{1+\Tr(G_{k}^{{\mathcal{S}}}(\ketbra{\rho})^{2})}{2} \right| \le \frac{1}{8}, \end{align}\] and using the fact that \(\require{physics} \Tr(G_{k}^{{\mathcal{S}}}(\ketbra{\rho})^{2})\ge 1-1/\lambda\), we have \[\require{physics} \frac{1+\Tr(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})G_{k}^{{\mathcal{S}}}(\ketbra{\rho}))}{2} \ge \frac{7}{8} - \frac{1}{2\lambda} \ge \frac{3}{4}.\] Therefore, by Chernoff’s inequality, the probability that at least \(\frac{2r}{3}\) tests succeed among \(r\) swap tests is bounded by \[1-\exp\left(-\frac{3r}{2\cdot 4\cdot 12^{2}}\right)=1-\exp\left(-\frac{r}{384}\right) \ge 1-2^{-\lambda}.\] Overall, if \(V=G_{k}^{{\mathcal{S}}}\) for some \(k\) and \(\require{physics} \Tr(G_{k}^{\mathcal{S}}(\phi)^{2})\ge 1-1/\lambda\), then it holds that \(\Pr[P_{k}(\Psi) \to 1] \ge 1-2^{-\lambda}\) with probability at least \(1-p_{1}-p_{2}=1-\frac{m+\tau}{2^{2\lambda}}\).

In this case, we can regard \(V({\ketbra{\rho}})\) as an independent Haar random pure state \(\ket{\psi}\). By 3, the expected success probability of the swap test between \(G_{k}^{\tilde{\mathcal{S}}}({\ketbra{\rho}})\) and \(V({\ketbra{\rho}})\) is =1 \[\require{physics} \begin{align} \underset{V\gets \mu_{n}}{\mathbb{E}}\left[\frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})V(\ketbra{\rho})]}{2}\right] & = \underset{\psi \gets \sigma_{n}}{\mathbb{E}}\left[\frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\ketbra{\psi}]}{2}\right] \\ & = \frac{1}{2} + \frac{1}{2^{n+1}}{} \end{align}\] \[\require{physics} \begin{align} \underset{V\gets \mu_{n}}{\mathbb{E}}\left[\frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})V(\ketbra{\rho})]}{2}\right] = \underset{\psi \gets \sigma_{n}}{\mathbb{E}}\left[\frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\ketbra{\psi}]}{2}\right] = \frac{1}{2} + \frac{1}{2^{n+1}}{} \end{align}\] where we use 2 in the last equality. Applying 3 for \(t=1/13\), we have \[\require{physics} \Pr\left[ \frac{1+\Tr[G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})V(\ketbra{\rho})]}{2} \ge \frac{7}{12} \right] \le \exp\left(-\frac{2^{n}-2}{4056}\right) \le \frac{1}{2^{2\lambda}}\] for sufficiently large \(n\). In other words, with probability at least \(1-\frac{1}{2^{\lambda}}\), the swap test between \(G_{k}^{\tilde{\mathcal{S}}}(\ketbra{\rho})\) and \(V(\ketbra{\rho})\) succeeds with probability at most \(7/12\) for all \(k\). We only focus on such a case below. Chernoff inequality gives that \(\Pr[P_{k}(\Psi) \to 1]\) is at most \[\exp\left( -\frac{7r/12\cdot (1/12)^{2}}{(2+1/12)} \right)= \exp\left( -\frac{7r}{3600} \right) \le 2^{-2\lambda},\] for each \(k\). Therefore, if \(V\) is truly Haar random unitary, then it holds that \(\require{physics} \Tr\left[P_{k} \ket{\Psi}\right] \le 2^{-2\lambda}\) for all \(k\) with probability at least \(1-2^{-\lambda}\).

12 Toward Separating PRSGs from Short PRSGs↩︎

In this section we show that the output size of a pseudorandom state may be relevant, i.e., there exist short-PRSGs but PRSGs in a certain form do not exist.

12.1 Preparation↩︎

12.1.0.1 Universal oracle.

For a quantum oracle algorithm with access to the oracle \(O = \{O_{\lambda}\}_{\lambda \in \NN}\), we consider a universal oracle \(\tilde{O}\) that takes as input a state over two registers \(\boldsymbol{\Lambda} X\), measures the register \(\boldsymbol{\Lambda}\) to obtain \(\lambda\), then applies \(O_\lambda\) on (the first parts of) \(\boldsymbol{X}\). The (qu)bit-length \(n\) of \(\boldsymbol{\Lambda}\) may be specified by \(\tilde{O}_n\) if needed, in which case \(\tilde{O}_n\) can make queries up to \(O_{2^n}\).

We give the definition here because we explicitly discuss the measurement regarding \(\lambda\) here; the results in the previous section may use the universal oracles implicitly but are not changed.

12.1.0.2 Pure quantum algorithm, with the isometry CHFS oracles.

In this section, we consider quantum oracle algorithms without trace-out operators, which we refer to as pure algorithms, written as \[\begin{align} A(\cdot) = U_t \circ \tilde{O} \circ \mathcal{N}_t \circ \dots \circ U_1 \circ \tilde{O} \circ \mathcal{N}_1 \circ U_0 (\cdot), \end{align}\] where each measurement \(\mathcal{N}_i\) decides which oracle to query (the parameter \(\lambda\)) on what input \(x\).

Recall that the isometry CHFS oracle with input \(x\) outputs \(\ket{\phi_x}_{\boldsymbol{Y}}\) in a new register \(\boldsymbol{Y}\). For the pure algorithm \(A\) with the isometry CHFS oracles, we assume that the register \(\boldsymbol{Y}\) was included in the input register of \(A\) initialized by \(\ket{0}_{\boldsymbol{Y}}\), but it is never changed until the oracle query is applied. After the query, it becomes \(\ket{\phi_x}_{\boldsymbol{Y}}\) and arbitrary operation may be applied on \(\boldsymbol{Y}\).

When the universal oracle is considered, we assume that some register is initialized by \(\ket{0^n}\) for some \(n\) and the oracle query uses some qubits of them as \(\Lambda\), which is measured when the query to the universal oracle is made. Arbitrary operations may be applied to these qubits at any point.

12.2 Purity test on the output of pure algorithms↩︎

Recall that the purity of a quantum state \(\rho\) is defined by \(\require{physics} \Tr(\rho^2)\) and can be estimated by the swap test as shown in 3 on the two copies of \(\rho\). If the outcome of an algorithm is pure, then it can be shown that the initial or intermediate states must have also been pure and the intermediate measurements are deterministic (which is in fact nontrivial). This is the idea behind the following lemma, which states that if the output of a pure quantum algorithm is nearly pure, then the intermediate binary measurements are almost deterministic, and can be removed at the cost of a negligible difference in the output state.

Note that the measurements in the following lemmas are binary; when we apply this lemma, we may implicitly decompose the general measurements into binary measurements.

We rewrite the algorithm \(A\) in simpler terms for the proof by considering \[\begin{align} \mathcal{N}_i\vcentcolon=(\Pi_i ^0,\Pi_i^1),\quad\text{where}\quad\Pi_i^b\vcentcolon=U_0^\dagger\cdots U_{i-1}^\dagger (\ketbra{b}\otimes I)U_{i-1}\cdots U_0, \end{align}\] acting on any mixed input state \(\rho\) as \(\mathcal{N}_i(\rho) = \Pi_i ^0\rho\Pi_i ^0+\Pi_i^1\rho\Pi_i^1\). The algorithm \(A\) can be reformulated as follows⁴⁶: \[\begin{align} A(\rho) & = U_t\circ\cdots\circ U_0\circ \mathcal{N}_t \circ \cdots \circ \mathcal{N}_1(\rho) \nonumber \\ & = \sum_{b_1,\cdots,b_t \in \{0,1\}}U_t\cdots U_0 \Pi^{b_t}_t \cdots \Pi^{b_1}_1 \rho \Pi^{b_1}_1 \cdots \Pi^{b_t}_t U_0^\dagger\cdots U_t^\dagger.\label{tfmgdclu} \end{align}\tag{52}\] We also define the intermediate states \(\{\phi_i\}_{i\in[t]}\) after measurement \(\mathcal{N}_i\) as \[\phi_i\vcentcolon=\mathcal{N}_i \circ \cdots \circ \mathcal{N}_1 (\phi).\] The most probable outcomes for the original binary measurements are also simplified with this notation, in particular \(\require{physics} b_{i+1}=\argmax_{\substack{b\in\{0,1\}}} \Tr(\Pi_{i+1}^b\phi_{i})\), and we define the associated measurement operator \[\begin{align} \Lambda_{i+1}(\rho):= {\Pi^{b_{i+1}}_ {i+1}\rho\Pi^{b_{i+1}}_{i+1}}. \end{align}\]

Since the trace-norm is invariant under unitaries, in order to prove the theorem it is enough to show that \[\|\Lambda_t \circ \cdots \circ \Lambda_1 (\phi) - \mathcal{N}_t \circ \cdots \circ \mathcal{N}_1 (\phi)\|_{tr} \le t\varepsilon.\] It turns out that proving that “it also holds” part suffices for proving the above inequality. In the formulation of this proof, it can be written as follows. For every \(i\in[t]\) and measurement operator \(\Lambda_{i+1}:= {\Pi^{b_{i+1}}_ {i+1}\rho\Pi^{b_{i+1}}_{i+1}}.\), we have \[\require{physics} \Tr(\Lambda_{i+1}(\phi_i))\geq1-\varepsilon.\]

We prove that the claim implies the main inequality of the theorem, as the measurement channel and the operator associated with the most likely outcome are closely related. That is, their difference is just the operator associated with the least likely outcome, whose probability of occurring is bounded by [claim:purity95povm]: \[\require{physics} \begin{align} \|\Lambda_{i+1}(\phi_i) - \mathcal{N}_{i+1}(\phi_i)\|_1=\|\Pi^{1-b_{i+1}}_{i+1}\phi_i\Pi^{1-b_{i+1}}_{i+1}\|_1= 1-\Tr(\Pi^{b_{i+1}}_{i+1}\phi_i)\leq\varepsilon, \end{align}\] so that \(\|\Lambda_{i+1}(\phi_i) - \mathcal{N}_{i+1}(\phi_i)\|_{tr}\le \varepsilon\). The theorem follows by the triangle inequality as \[\begin{align} & \|\Lambda_{t}\circ \cdots\circ \Lambda_1(\phi) - \mathcal{N}_t \circ \cdots \circ \mathcal{N}_1 (\phi)\|_{tr} \\ & \quad\quad\le \| \Lambda_{t} \circ \cdots \circ\Lambda_{1}(\phi) - \Lambda_{t} \circ \cdots \circ \mathcal{N}_{1}(\phi) \|_{tr} \\ & \quad\quad\quad\quad\quad + \| \Lambda_{t} \circ \cdots \circ \Lambda_2\circ\mathcal{N}_{1}(\phi) - \Lambda_{t} \circ \cdots \circ \mathcal{N}_2 \circ \mathcal{N}_{1}(\phi) \|_{tr} \\ & \quad\quad\quad\quad\quad\quad\quad\quad + \cdots + \| \Lambda_{t} \circ \mathcal{N}_{t-1} \circ \cdots \circ\mathcal{N}_{1}(\phi) - \mathcal{N}_{t} \circ \mathcal{N}_{t-1}\circ \cdots \circ \mathcal{N}_{1}(\phi) \|_{tr} \\ & \quad\quad\leq \sum_{i=0}^{t-1}\|\Lambda_{i+1}(\phi_i)-\mathcal{N}_{i+1}(\phi_i)\|_{tr}\le \sum_{i=0}^{t-1} {\varepsilon} = t{\varepsilon}, \end{align}\] where we used the fact that a quantum channel does not increase the trace norm, see 3 , for the quantum channel \(\Lambda_j\) in the second inequality.

Note that measurement channels can only decrease purity, for all \(i\in[t]\): \[\require{physics} \begin{align} \Tr(\phi_{i+1}^2) & = \Tr(\mathcal{N}_{i+1}(\phi_i)^2) \\ & = \Tr(\left(\Pi_{i+1}^0\phi_i\Pi_{i+1} ^0+\Pi_{i+1}^1\phi_i\Pi_{i+1}^1\right)^2) \\ & =\Tr(\Pi_{i+1}^0\phi_i\Pi_{i+1}^0\phi_i\Pi_{i+1}^0+\Pi_{i+1}^1\phi_i\Pi_{i+1}^1\phi_i\Pi_{i+1}^1) \\ & \leq \Tr(\Pi_{i+1}^0\phi_i^2)+\Tr(\Pi_{i+1} ^1\phi_i^2) \\ & = \Tr(\phi_i^2), \end{align}\] where we use \(\require{physics} \Tr(C\rho C^\dagger)\leq\Tr(\rho)\) for any unnormalized state \(\rho=\phi_i\Pi_{i+1}^b\phi_i\) and quantum channel \(C(\cdot)=\Pi^b_{i+1}(\cdot)\Pi^b_{i+1}\), and the cyclicity of the trace.

Moreover, we know by hypothesis of 15 that the outcome of the algorithm \(A\) is pure with high probability, i.e.\(\require{physics} \Tr(\phi_t^2)\geq1-\varepsilon\). In particular, the above implies that for every \(i\in[t]\), the intermediate state \(\phi_i\) is pure with high probability, and hence the channel described by the most probable measurement element must have high probability \[\require{physics} \begin{align} 1-\varepsilon& \leq\Tr(\phi_t^2)\leq\Tr(\phi_{i+1}^2) \\ & \leq\Tr(\Pi_{i+1} ^0\phi_i\Pi_{i+1}^0)^2+\Tr(\Pi_{i+1}^1\phi_i\Pi_{i+1}^1)^2 \\ & \leq\Tr(\Pi_{i+1} ^{b_{i+1}}\phi_i\Pi_{i+1}^{b_{i+1}})\left(\Tr(\Pi_{i+1} ^0\phi_i\Pi_{i+1}^0)+\Tr(\Pi_{i+1}^1\phi_i\Pi_{i+1}^1)\right) \\ & \leq\Tr(\Pi_{i+1} ^{b_{i+1}}\phi_i\Pi_{i+1}^{b_{i+1}})\Tr(\phi_i) \\ & =\Tr(\Lambda_{i+1}(\phi_i)). \qedhere \end{align}\]

12.3 Conditional separation↩︎

In general, any quantum algorithm in the isometry oracle model, that makes \(t\) projective binary measurements described by \(\{U_0,\mathcal{M}_1,\ldots,\mathcal{M}_t,U_t\}\) for unitaries \(U_0,...,U_t\) and measurements \(\mathcal{M}_i = (\ketbra{0}\otimes I,\ketbra{1}\otimes I)\), can be written as

\[\require{physics} A(\cdot) = \Tr_{{\mathbf{B}}}\bigg[(U_t\circ \tilde{O}_{n_t}\circ\mathcal{N}_t)\circ\ldots\circ(U_1\circ \tilde{O}_{n_1}\circ\mathcal{N}_1) \circ U_0 (\ketbra{0}_{{\mathbf{A}}{\mathbf{B}}}^{\otimes u(\lambda)})\bigg].\] We denote \[\rho_{{\mathbf{A}}{\mathbf{B}}} = (U_t\circ \tilde{O}_{n_t}\circ\mathcal{N}_t)\circ\ldots\circ(U_1\circ \tilde{O}_{n_1}\circ\mathcal{N}_1) \circ U_0 (\ketbra{0}_{{\mathbf{A}}{\mathbf{B}}}^{\otimes u(\lambda)}).\] In this section, we will consider a particular type of quantum algorithms, which we call “ancilla-uncomputable quantum algorithms”, where a quantum algorithm \(A\) acts on two registers: the output register \(\boldsymbol{A}\), and the ancilla register \(\boldsymbol{B}\) ⁴⁷, and the output of \(A\) is of the following form: \[\require{physics} A(\cdot) = \Tr_{\boldsymbol{B}}({\rho_{\boldsymbol{A} B}}), \text{ where } {\rho_{\boldsymbol{A} B}} = {\psi}_{\boldsymbol{A}} \otimes \ketbra{0}_{\boldsymbol{B}}.\]

We now show the following theorem, which is the main result of this section.

The separating oracle \(\mathcal{O}\) consists of two oracles: the classical-accessible isometry CHFS oracle \(O_\ell\) for \(\ell(\lambda)=\lfloor 2\log \lambda\rfloor\) and the \(\mathbf{QPSPACE}\) oracle. The existence of short-PRFSGs follows immediately from 8. It remains to break long PRSGs with ancilla-uncomputable generation algorithm.

By contradiction, assume there exists a PRSG \(\mathsf{Gen}(\cdot)\) with an ancilla-uncomputable generation algorithm relative to \(\mathcal{O}\). Let \(u_k\) be the length of the ancilla register. We can assume w.l.o.g. that \(u_k = u\) is independent of \(k\), by considering \(u = \max_k{u_k}\) and adding ancilla that will not be used for the \(k\) such that \(u_k<u\). Because the generation algorithm is ancilla-uncomputable, the ancilla registers are reset to \(\ket{0}\) after the computation. We write \(d(\lambda)\) and \(\kappa(\lambda)\) to denote the output length and the key length of the PRSG. Since the \(\mathbf{QPSPACE}\) oracle is unitary, we can embed them in the unitaries and write the output state of the algorithm (before tracing out the ancilla) by \[\label{gxurkzef} (U_t^{(k)}\circ \tilde{O}^{(k)}_{n_t}\circ\mathcal{N}^{(k)}_t)\circ\ldots\circ(U^{(k)}_1\circ \tilde{O}_{n_1}\circ\mathcal{N}^{(k)}_1) \circ U_0^{(k)} (\ketbra{0}^{\otimes m(\lambda)}),\tag{53}\] where \(m(\lambda) = d(\lambda) + u\) is the dimension of the whole space where the computations are made. We omit the superscript \((k)\) when it is clear from the context. Here \(U_0,\dots,U_t\) denote unitary operations and \(\mathcal{N}_1,\dots,\mathcal{N}_t\) are measurements on some registers \({\boldsymbol{\Lambda}}_1{\boldsymbol{X}}_1,\dots,{\boldsymbol{\Lambda}}_t{\boldsymbol{X}}_t\), where \({\boldsymbol{\Lambda}}_j\) specifies the index for the CHFS oracle to be applied on \({\boldsymbol{X}}_j\). The values \(n_1,\dots,n_t\) denote the size of \({\boldsymbol{\Lambda}}_1,\dots,{\boldsymbol{\Lambda}}_t.\)

Let us denote by \(\rho_t^{(k)}=\rho^{(k)}\otimes\ketbra{0}^{\otimes u}\) the final state before tracing out the ancilla, and we denote by \(\rho_j^{(k)}\) the intermediate state right after applying the unitary \(U_j\) for \(j=0,\dots,t-1\). We consider the following adversary \(\adv\), given the polynomial copies of either \(\rho=\rho^{(k)}\) for some \(k\) (in which case it outputs 1) or Haar random state \(\rho\) (in which case it outputs 0). In the following, let \(r=10\lambda^2\) and \(T=20r^2(2td+1)^3\).

We first argue that the sub-protocol \(P_k\) can be implemented in polynomial time. This is because the \((\lambda_{i}^{(k)},x_{i}^{(k)})\) can be learned without making any query by 12.

If \(\rho=\rho^{(k)}\) and \(\require{physics} \Tr(\rho^2)\ge 1-1/T\), then \(\Pr[P_k(\Phi)] \ge 4/5.\) If \(\rho\) is a Haar random state, then \(\Pr[P_k(\Phi)\to 1] \le 1/2^{2\lambda}\) for all \(k\) with probability at least \(1-1/2^\lambda\). The same argument as in 6 concludes the proof. Indeed, if \(\rho=\rho^{(k)}\) for some \(k\) and \(\require{physics} \Tr(\rho^2) \le 1-1/T\), then 4 asserts that the first step outputs \(1\) with probability \(1-2^{-\lambda}\).

The other case, i.e., \(\rho=\rho^{(k)}\) and \(\require{physics} \Tr(\rho^2)\ge 1-1/T\) or \(\rho\) is a true Haar random state is dealt by the quantum OR lemma. In this case, by [clm:32rhorhok] and [clm:32rhoHaar], the POVMs \(\{P_k\}_{k\in \{0,1\}^\lambda}\) and \(\Psi\) satisfy the conditions of the quantum OR lemma (7) unless with probability \(1/2^{\lambda}\cdot\). Therefore, \(\adv\) outputs 1 with probability at least \(1/8\) if \(\rho=\rho^{(k)}\) for some \(k\), but it outputs 1 with probability at most \(4/2^{\lambda}\) if \(\rho\gets \nu_n\), that is, \(\adv\) breaks the PRSG security of \(\mathsf{Gen}(\cdot)\).

By the above claim, we can assume that \(\require{physics} \Tr(\rho^2)\ge 1-1/T\), otherwise 3 would have terminated at step 1 with probability at least \(1-2^{-\lambda}\). We can decompose the measurement \(\mathcal{N}_i\) by \(\mathcal{M}_{i,d_i}\circ ... \circ \mathcal{M}_{i,1}\) for some binary measurements \(\mathcal{M}_{i,1},...,\mathcal{M}_{i,d_i}\) where \(d_i \le d\), which is bounded by the number of qubits.

Let \(\tilde{\rho}_t^{(k)}\) be defined as \[(U_t^{(k)}\circ \tilde{O}_{n_t}\circ\ketbra{\lambda_t,x_t})\circ\ldots\circ(U_1^{(k)}\circ \tilde{O}_{n_1}\circ\ketbra{\lambda_1,x_1}) \circ U_0^{(k)} (\ketbra{0}^{\otimes m(\lambda)}),\] where we replaced \(\mathcal{N}_i\) by \(\ketbra{\lambda_i,x_i}\) in 32 . It is not hard to see that each bit of \((\lambda_i,x_i)\) coincides with some of \(b_j\) defined in 15 because \(td/T<1/2.\) By 15, we have \[\begin{align} \label{jgrmhkby} \| \tilde{\rho}_t^{(k)}- \rho_t^{(k)}\|_{tr} \le \frac{td}{T}. \end{align}\tag{54}\] Now we give another representation of \(\tilde{\rho}_t^{(k)}\). Given fixed \((\lambda_i,x_i)\), the oracle \(\tilde{O}_{n_i}\) generates \(\ket{\phi_{x_i}}_{{\boldsymbol{Y}}_i}\) that is initialized by \(\ket{0}\) and never changed, so we can write \[\tilde{O}_{n_i}\circ\ketbra{\lambda_i, x_i}_{{\boldsymbol{\Lambda}}_i {\boldsymbol{X}}_i}\otimes\ketbra{0}_{{\boldsymbol{Y}}_i}= \ketbra{\lambda_i, x_i}_{{\boldsymbol{\Lambda}}_i {\boldsymbol{X}}_i}\otimes\ketbra{\phi_{x_i}}{0}_{{\boldsymbol{Y}}_i},\] which allows us to write \(\tilde{\rho}_t^{(k)}\) as \[U_t \circ \ketbra{\lambda_t,x_t}\circ\ldots\circ U_1\circ\ketbra{\lambda_1,x_1} \circ U_0 (\ketbra{\phi_{x_t},\dots,\phi_{x_1}}\otimes\ketbra{0}),\] where \(\ket{\phi_{x_t},\dots,\phi_{x_1}}\) is stored in the register \({\boldsymbol{Y}}_t\dots{\boldsymbol{Y}}_1\). Now let \(\tilde{\rho}_j^{(k)}\) be the state after applying \(U_j\) in the above equation. We have that \(\|\tilde{\rho}_j^{(k)}- \rho_j^{(k)}\|_{tr} \le \frac{2td}{T}\) using 33 for all \(j=0,\dots,t-1\) and the fact that the quantum channel never increases the trace distance.

By the part “it also holds” of 15, for any projector \(\Pi=\ketbra{b}\otimes I\) induced from \((\lambda_i,x_i)\)⁴⁸, it holds that \[\require{physics} \begin{align} \label{jcwuaofz} \Tr(\Pi\rho_{i-1}) \ge 1-1/T. \end{align}\tag{55}\] Using the triangular inequality, this gives \(\require{physics} \Tr(\Pi \tilde{\rho}_{i-1}) \ge 1-(2td+1)/T\). By applying 4 for each binary measurement, we can replace each projectors by identity and use the triangular inequality to derive \[\begin{align} \| \tilde{\rho}_t^{(k)} - U_t\circ \dots\circ U_0(\ketbra{\phi_{x_t},\dots,\phi_{x_1}}\otimes\ketbra{0})\|_{tr} \le 2td \cdot \sqrt{\frac{2td+1}{T}}. \end{align}\] Together with 33 , this implies that \[\begin{align} \label{tpcqoyrj} \|\rho_t^{(k)} - \tilde{\rho}_t^{(k)}\|_{tr} \le \frac{td}{T} + 2td \cdot\sqrt{\frac{2td+1}{T}}\le (2td+1)\cdot \sqrt{\frac{2td+1}{T}}. \end{align}\tag{56}\] Note that \(\Pr[P_k((\tilde{\rho}_t^{(k)})^{\otimes 2r})\to 1]=1\) by 5. This implies that \(P_k\) outputs 1 on input \(\Phi= (\rho^{(k)}\otimes\ketbra{0}^{\otimes u})^{\otimes 2r}\) with probability at least \[1-2r (2td+1)\cdot \sqrt{\frac{2td+1}{T}} \ge 4/5.\qedhere\]

Here, we need to show that the number of swap test done \(m_k\) in the product test is at least \(13\) for some large enough \(\lambda\). This is because \[\begin{align} m_k & = t + s_k \geq \frac{t \cdot 2\log\lambda + s_k}{2 \log\lambda} \geq \frac{\sum_{i=1}^{t}\ell(\lambda^{(k)}_i) + s_k}{2 \log\lambda} = \frac{\omega(\log\lambda)}{2\log \lambda} = \omega(1), \end{align}\] where we used the fact that the candidate PRS generator has output dimension \(d(\lambda) = \omega(\log\lambda)\).

By 6, we have that a single product test (for key \(k\)) succeeds with expected probability at most \(2\cdot (3/4)^{13}\le 0.05\). By the concentration inequality, we can show that with probability at least \(1-1/2^{2\lambda}\) over Haar random states, a single product test for \(k\) succeeds with probability at most \(0.1\). Using Chernoff’s inequality, we conclude that for each \(k\), \(\Pr[P_k(\Phi)\to 1] \le 1/2^{2\lambda}\).

=1

13 Missing Proofs↩︎

13.1 Product test for Haar-random states↩︎

=1 For every partition \(S\cup\overline{S}\) of \([m]\), the local dimension of each partition is given by \(d_S=\prod_{i\in S}d_i\). \[\require{physics} \begin{align} \underset{\ket{\psi}\gets\sigma}{\mathbb{E}}\Pr(1\gets\mathcal{A}_\mathtt{PTEST}(\ket{\psi}^{\otimes 2}))& =\underset{\ket{\psi}\gets\sigma}{\mathbb{E}}\left[\frac{1}{2^m}\sum_{S\subseteq[m]}\Tr[\rho_S^2]\right] \\ &=\frac{1}{2^m}\sum_{S\subseteq[m]}\frac{d_S+d_{\overline{S}}}{d_S\cdot d_{\overline{S}}+1}\le \frac{1}{2^m}\sum_{S\subseteq[m]}\frac{d_S+d_{\overline{S}}}{d_S\cdot d_{\overline{S}}} \\&=\frac{1}{2^m}\left(\sum_{S\subseteq[m]}\frac{1}{d_S} + \frac{1}{d_{\overline{S}}}\right) =\frac{2}{2^m}\left(\sum_{S\subseteq[m]}\frac{1}{d_S} \right) \\&=\frac{2}{2^m}\prod_{i\in[m]} \left(1+\frac{1}{d_i}\right) \leq \frac{2}{2^m}\prod_{i=1}^m\left(\frac{3}{2}\right)=2\left(\frac{3}{4}\right)^m, \end{align}\] where we use the fact that each \(d_i\geq 2\) to obtain the last inequality.

14 On the Purity Test for General Algorithms↩︎

Our conditional separation presented in 7 is crucially based on 15, which states that 1) we can remove intermediate measurements with negligibly small changes in the output of the algorithm, because 2) all the intermediate measurements are almost deterministic.

This section presents some partial results to generalize 15 to the general algorithms that may include partial traces. We note, however, it is unclear how to extend the attack in the general case even with the perfectly generalized 15, which we do not know how to prove. This is due to the fact that in the attack, the adversary needs to apply the inverse of the generation algorithm to the challenge state and run the product test on the outcome, which is not possible in the general case due to the traced out registers. We still include our attempts as a technical step towards the solution for the general case as well, as we believe the results in this section may be of independent interest.

Our result states that for the general algorithms, 1) the purity test ensures that the state right before the final partial is close to some product state,⁴⁹ and 2) \(O(1)\) intermediate measurements are almost deterministic.

14.1 Product structure↩︎

We can prove the product structure of the output state as a consequence of the following lemmas.

Let \(\rho=\sum_{i=1}^r\lambda_i\ketbra{\psi_i}\) be the eigendecomposition of \(\rho\) and let \(i^*=\arg\max_{\substack{i\in[r]}}\{\lambda_i\}\), then we can decompose \(\rho\) as \[\begin{align} \rho=\lambda_{i^*}\ketbra{\psi_{i^*}}+(1-\lambda_{i^*})\sigma, \end{align}\] for some state \(\sigma\) orthogonal to \(\ket{\psi_{i^*}}\). By hypothesis and the above decomposition, \[\require{physics} \begin{align} \Tr(\rho^2)=\lambda_{i^*}^2+(1-\lambda_{i^*})^2\Tr(\sigma^2)\geq1-\varepsilon. \end{align}\] Since \(\require{physics} \Tr(\sigma^2)\leq1\) for every state, we have \(\lambda_{i^*}^2+(1-\lambda_{i^*})^2\geq1-\varepsilon\), and in particular it implies \(\lambda_{i^*}\geq\frac{1+\sqrt{1-2\varepsilon}}{2}\). Therefore, by the triangle inequality \[\|\rho-\ketbra{\psi_{i^*}}\|_1=\|(\lambda_{i^*}-1)\ketbra{\psi_{i^*}}+(1-\lambda_{i^*})\sigma\|_1\leq2(1-\lambda_{i^*})\leq1-\sqrt{1-2\varepsilon}=O(\varepsilon).\qedhere\]

Let \(\ket{\gamma}_{AB}=\sum_{i=1}^r s_i\ket{\psi_i}_A\otimes\ket{\phi_i}_B\) be the Schmidt decomposition of the pure state \(\ket{\gamma}_{AB}\). By hypothesis, we know that its reduced state \[\require{physics} \begin{align} \Tr_B(\ketbra{\gamma}_{AB})=\sum_{k=1}^r\sum_{i,j=1}^rs_is_j\ket{\psi_i}\bra{\psi_j}_A\otimes\bra{\phi_k}\ket{\phi_i}\bra{\phi_j}\ket{\phi_k}_B=\sum_{i=1}^r s^2_i\ketbra{\psi_i}_A \end{align}\] is almost pure, thus by 25 there exists \(i^*\in[r]\) such that \(s_{i^*}^2\geq\frac{1+\sqrt{1-2\varepsilon}}{2}\). The associated eigenstate approximates the target state with high precision, or more concretely, \[\begin{align} \|\ketbra{\gamma}_{AB}-\ketbra{\psi_{i^*}}_A\otimes\ketbra{\phi_{i^*}}_B\|_1&=\|\sum_{(i,j)\in[r]\times[r]\setminus(i^*,i^*)}s_is_j\ket{\psi_i}\bra{\psi_j}\otimes\ket{\phi_i}\bra{\phi_j}\|_1\\ &=\sum_{i\in[r]\setminus\{i^*\}}s^2_i=1-s_{i^*}^2\\ &\leq\frac{1-\sqrt{1-2\varepsilon}}{2}=O(\varepsilon).\qedhere \end{align}\]

Let \(\ket{\gamma}_{ABC}\) be a purification of \(\rho_{AB}\). We now have a pure quantum state \(\ket{\gamma}_{ABC}\) whose reduced state \(\require{physics} \Tr_{BC}(\ketbra{\gamma}_{ABC})=\rho_A\), by hypothesis, passes the purity test with high probability. Therefore, by 26 there exist pure states \(\ket{\psi}_A\) and \(\ket{\phi}_{BC}\) such that \[\begin{align} \|\ketbra{\gamma}_{ABC}-\ketbra{\psi}_A\otimes\ketbra{\phi}_{BC}\|_1\leq O(\varepsilon). \end{align}\] By the data processing inequality, taking the partial trace of the above states can only reduce their trace distance, thus \[\require{physics} \begin{align} \|\rho_{AB}-\ketbra{\psi}_A\otimes\Tr_C(\ketbra{\phi}_{BC})\|_1&=\|\Tr_C(\ketbra{\gamma}_{ABC})-\Tr_C(\ketbra{\psi}_A\otimes\ketbra{\phi}_{BC})\|_1\\ &\leq O(\varepsilon). \qedhere \end{align}\]

14.2 Almost-deterministic intermediate measurements↩︎

The above theorem in the case of a binary measurement \(\mathcal{M}\) applied to a state \(\rho_{AB}\) gives us that if \(\require{physics} \Tr(\Tr_B(\mathcal{M}(\rho))^2)\geq1-\varepsilon\), then there exists a state \(\ket{\varphi}_A\) such that \(\|\mathcal{M}(\rho)_{AB}-\ketbra{\varphi}_A\otimes\sigma_B\|_1\leq\varepsilon\). Can we deduce from this that \(\|\rho_{AB}-\ketbra{\varphi}_A\otimes\sigma'_B\|_1\leq\varepsilon\)? We prove a slightly weaker result here.

Case 1: Pure \(\rho\) and no error. Would help to consider the simple scenario where the initial state is pure \(\rho_{AB}=\ketbra{\psi}\) with \(\ket{\psi}=\sqrt{p_0}\ket{\psi_0}+\sqrt{p_1}\ket{\psi_1}\), where \(\ket{\psi_i}=\Pi_i\ket{\psi}\) are orthonormal and \(p_0+p_1=1\), thus \(\mathcal{M}(\rho_{AB})=p_0\ketbra{\psi_0}+p_1\ketbra{\psi_1}\).

If we take the case of the perfect equality, \[\begin{align} p_0\ketbra{\psi_0}_{AB}+p_1\ketbra{\psi_1}_{AB}=\ketbra{\varphi}_A\otimes\sigma_B, \end{align}\] thus \[\require{physics} \begin{align} p_0\Tr_B(\ketbra{\psi_0})+p_1\Tr_B(\ketbra{\psi_1})=\ketbra{\varphi}, \end{align}\] since pure states are the extreme points of the convex hull of all states, we necessarily have that either \(p_i=0\) for some \(i\in\{0,1\}\), or \(\require{physics} \Tr_B(\ketbra{\psi_0})=\Tr_B(\ketbra{\psi_1})=\ketbra{\varphi}\). If one of the probabilities is zero the result follows obviously, but otherwise we have that the two states after the projection must be of the form \[\begin{align} \ket{\psi_0}=\sum_is_i\ket{\varphi}_A\otimes\ket{\varphi_i}_B\quad\text{and}\quad\ket{\psi_1}=\sum_i\tilde{s}_i\ket{\varphi}_A\otimes\ket{\tilde{\varphi}_i}, \end{align}\] for some purifications. Therefore, the initial state must be of the form \[\begin{align} \ket{\psi}=\sqrt{p_0}\ket{\psi_0}+\sqrt{p_1}\ket{\psi_1}=\ket{\varphi}_A\otimes\sum_{i}\sqrt{p_0}s_i\ket{\varphi_i}+\sqrt{p_1}\tilde{s}_i\ket{\tilde{\varphi}_i}. \end{align}\]

Case 2: Pure \(\rho\) and error. If instead we have the imperfect equality \[\begin{align} \|p_0\ketbra{\psi_0}_{AB}+p_1\ketbra{\psi_1}_{AB}-\ketbra{\varphi}_A\otimes\sigma_B\|_1\leq\varepsilon, \end{align}\] thus by the data processing inequality \[\require{physics} \begin{align} \|p_0\Tr_B(\ketbra{\psi_0})+p_1\Tr_B(\ketbra{\psi_1})-\ketbra{\varphi}_A\|_1\leq\varepsilon. \end{align}\]

Let us denote by \(\sigma_b\) the state of the system after outcome \(b\in\{0,1\}\), which happens with probability \(p_b\), such that the state \(\rho_{AB}\) after measurement \(\mathcal{M}\) can be written as \(\mathcal{M}(\rho_{AB})=p_0\sigma_0+p_1\sigma_1\). We can distinguish two cases.

Case 1: Without loss of generality assume \(p_0\geq1-\sqrt{\varepsilon}\) and \(p_1\leq\sqrt{\varepsilon}\). Since \(\require{physics} \Tr(\Tr_B(\Pi_0\rho_{AB}\Pi_0))=\Tr(\Pi_0\rho_{AB}\Pi_0)=p_0\geq1-\sqrt{\varepsilon}\), by the almost as good as new 8 and the data-processing inequality, it holds that \[\require{physics} \begin{align} \|\Tr_B(\mathcal{M}(\rho_{AB}))-\Tr_B(\rho_{AB})\|_1\leq\|\mathcal{M}(\rho_{AB})-\rho_{AB}\|_1\leq1-\sqrt[4]{\varepsilon}. \end{align}\]

Case 2: Assume now that both \(\sqrt{\varepsilon}\leq p_0,p_1\leq 1-\sqrt{\varepsilon}\). Since \(p_0+p_1=1\), if \(1-\sqrt{\varepsilon}\geq p_0\geq\sqrt{\varepsilon}\), then \(p_0p_1=p_0(1-p_0)\geq\sqrt{\varepsilon}(1-\sqrt{\varepsilon})\). On the other hand, the hypothesis of the theorem asserts that \[\require{physics} \begin{align} \Tr(\Tr_B(\mathcal{M}(\rho_{AB}))^2)=\Tr((p_0\sigma_0+p_1\sigma_1)^2)=p_0^2\Tr(\sigma_0^2)+2p_0p_1\Tr(\sigma_0\sigma_1)+p_1^2\Tr(\sigma_1^2)\geq1-\varepsilon, \end{align}\] whilst \(\require{physics} \Tr(\sigma^2)\leq 1\) for every state \(\sigma\), thus \[\require{physics} \begin{align} 2p_0p_1\Tr(\sigma_0\sigma_1)\geq 1-\varepsilon- p_0^2\Tr(\sigma_0^2)-p_1\Tr(\sigma_1^2)\geq 1-\varepsilon-p_0^2-p_1^2=2p_0p_1-\varepsilon, \end{align}\] where in the last equality we used that \((p_0+p_1)^2=1\). From the above equation we can lower bound the overlap between the two outcome states, which from the hypothesis of Case \(2\) implies \[\require{physics} \begin{align} \Tr(\sigma_0\sigma_1)\geq1-\frac{\varepsilon}{2p_0p_1}\geq1-\frac{\sqrt{\varepsilon}}{2(1-\sqrt{\varepsilon})}\geq1-\sqrt{\varepsilon}, \end{align}\] where the last inequality only holds if \(\varepsilon\leq1/4\). There is an immediate relation between the trace of the product of two states and their trace distance \[\require{physics} \begin{align} \frac{1}{2}\|\sigma_0-\sigma_1\|_1\leq \sqrt{1-F(\sigma_0,\sigma_1)}\leq\sqrt{1-\Tr(\sigma_0\sigma_1)}\leq\sqrt[4]{\varepsilon}, \end{align}\] by the Fuchs-van de Graaf inequality and the fact that \(\require{physics} F(\sigma,\rho)\geq\Tr(\sigma\rho)\) for every pair of states \(\sigma,\rho\) Intuitively, the above result states that both possible outcome states are very similar, in particular \[\require{physics} \begin{align} \|\Tr_B(\mathcal{M}(\rho_{AB}))-\sigma_0\|_1&=\|p_0\sigma_0+p_1\sigma_1-\sigma_0\|_1\\ &\leq\|p_0\sigma_0-p_0\sigma_1\|+\|p_0\sigma_1+p_1\sigma_1-\sigma_0\|_1\\ &\leq p_0\|\sigma_0-\sigma_1\|_1+\|\sigma_0-\sigma_1\|_1\leq (1+p_0)2\sqrt[4]{\varepsilon}\\ &\leq (2-\sqrt{\varepsilon})\sqrt[4]{\varepsilon}.\qedhere \end{align}\]

References↩︎

---

1. This work was done while the author was affiliated at Sorbonne Université, CNRS, LIP6, France.↩︎

2. This work was done in part while the author was affiliated with KIAS, Korea, and UT Austin, USA.↩︎

3. The second error (for the same seed) can be arbitrarily reduced by the repetition. We use this notion following the original definition [11].↩︎

4. We sometimes choose the oracles from its sub-distribution, but we stick to use the name CHFS oracles for simplicity.↩︎

5. [15] partly resolves this question by showing a black-box impossibility. However, their notion of black-box reduction does not include tomography, which is the only known way to obtain classical strings from quantum states reliably.↩︎

6. Technically, they showed the stronger statement \({\boldsymbol{B}QP=QMA}\).↩︎

7. The authors noted that an unpublished work by Impagliazzo and Rudich gave the first Pessiland oracle.↩︎

8. More precisely, [18] constructed the oracle world relative to which \(\mathbf{P}= \mathbf{NP}\) yet quantum-computable trapdoor one-way functions exist.↩︎

9. We note that [10] does not exclude the possibility that QOWFs are equivalent to EV-OWPuzz. We provably refute this possibility.↩︎

10. In this paper, we assume that the algorithms can access unitary oracles and its inverses. We do not consider the controls, conjugates or transposes of the oracles, but we believe our results can be extended to them using a similar idea from [23].↩︎

11. The impossibility is shown by an explicit adversary that only uses PRU generation algorithms non-adaptively, so the other forms of PRUs are automatically impossible to construct without ancilla registers.↩︎

12. For example, for \(s>t\) and \(s=\Omega(\log \lambda)\), PRSGs with output length \(s\) cannot be constructed from PRSGs with output length \(t\) if the longer PRSGs follow the described algorithms.↩︎

13. We remark that there is another recent work [25] that discusses the possibility of the length extension of the PRSGs, but only for very specific forms. Furthermore, their work only shows how to do length extension from PRSGs with super-log output size.↩︎

14. More explicitly, the first approach gives PRSGs with any log-length output using classical queries to the other log-length output PRSGs. The second approach gives a length-\(s+O(\log \lambda)\) output PRSG given quantum access to the other length-\(s\) output PRSG.↩︎

15. For the full relations, we refer Microcrypt-zoo.↩︎

16. This is the final goal of the concentration inequality used in [7]!↩︎

17. This oracle, roughly, takes a quantum state \(\ket{\phi}\) and a succinct description of a quantum circuit \(C\) computable in polynomial space, and returns \(C\ket{\phi}\). See 5 for the formal definition.↩︎

18. Here we explicitly append \(\ket{1}\) to make the unitary CHFS oracle well-defined w.r.t. 6. We occasionally omit \(\ket{1}\) if there is no confusion.↩︎

19. We usually consider the standard CHFS model with \(\ell(\lambda) = \lambda\) for simplicity.↩︎

20. For convenience, we omit the ancilla \(\ket{1}\).↩︎

21. We stress that two notions, distance and metric, are used differently; the metric is used only for the Riemannian metric.↩︎

22. Here, the Laplacian refers the Laplace-Beltrami operator of Riemannian manifold is defined as the negative of the divergence of the gradient, i.e., \(-\Delta f =-{\sf div}({\sf grad} f) .\) Negative sign is the analysts’ convention which ensures the non-negativeness of the eigenvalues. The first eigenvalue is the smallest non-negative eigenvalue of \(-\Delta\), i.e., the smallest \(c>0\) such that \(-\Delta f = c f\) for some function \(f\).↩︎

23. E.g., any \(u\) such that \(u(n^2+j)=j\) for \(j\le n\) works.↩︎

24. The existence of this oracle is ensured by the non-emptiness of the infinite intersection of the nested compact sets (Cantor’s intersection theorem) and the compactness of any product of compact sets (Tychonoff’s theorem).↩︎

25. This premise holds for any polynomial space algorithms.↩︎

26. The bit \(b\) might depend on the parameter \(\lambda\), but we suppress this dependency for simplicity.↩︎

27. This is implicitly parameterized by \(\lambda\).↩︎

28. We use \(\ell(\lambda)\le \lambda\) here. It can be relaxed to \(\ell=O(\lambda)\).↩︎

29. The seed length \(s(q)\) depends also on \(p(\lambda_i)\) and \(\log(1/\delta)\); we suppress these dependencies for simplicity.↩︎

30. In the proof below, we consider the oracle queries to \(S_{d}\). The same proof can be extended to the oracle queries to \(S_{\ket{\phi_{x}}}\) for each \(x\), or more general cases. e.g., queries to \(\ketbra{0}\otimes S_{\ket{\phi_{x_{0}}}}+\ketbra{1}\otimes S_{\ket{\phi_{x_{1}}}}\) for any \(x_{1},x_{2}\) of the same length. We focus on the queries to \(S_{d}\) because it is the most complicated.↩︎

31. Where the algorithm randomly chooses \(x,z\) with probability \(|\alpha_{x,z}|^{2}\), prepare \(\ket{1,\phi_{x}}\) and apply the projector \(\Pi_{x,z}=\ketbra{\rho_{x,z}}\).↩︎

32. Here we use \(n=\omega(\log \lambda)\) and \(m=\poly\).↩︎

33. This is possible for the isometry oracle as we assume that the output register is not touched before the oracle queries.↩︎

34. Careful readers may be concerned about the isometry oracle implicit in \(U_i\)’s when using \(U_i^\dagger\). We note that the same proof applies to the original algorithm represented as in 29 ; we only use 31 for simplicity of the proof of [claim:purity95povm].↩︎

35. Wlog, the input register can be part of \(\boldsymbol{A}\) and \(\boldsymbol{B}\).↩︎

36. In other words, \(\Pi=\ketbra{\lambda_{ij}}\otimes I\) for \(\lambda_i=\lambda_{i1}...\lambda_{in}\) or \(\Pi=\ketbra{x_{ij}}\otimes I\) for \(x_i=x_{i1}...x_{im}\) with some rearrangement of the registers.↩︎

37. We stress that two notions, distance and metric, are used differently; the metric is used only for the Riemannian metric.↩︎

38. Here, the Laplacian refers the Laplace-Beltrami operator of Riemannian manifold is defined as the negative of the divergence of the gradient, i.e., \(-\Delta f =-{\sf div}({\sf grad} f) .\) Negative sign is the analysts’ convention which ensures the non-negativeness of the eigenvalues. The first eigenvalue is the smallest non-negative eigenvalue of \(-\Delta\), i.e., the smallest \(c>0\) such that \(-\Delta f = c f\) for some function \(f\).↩︎

39. Similarly, the one-way permutation implies a hard-on-average samplable language in \(\mathbf{sampQCMA}\cap \mathbf{sampcoQCMA}\).↩︎

40. This requires \(c\gg 1\) when using the union bound.↩︎

41. The description can be an approximation of all amplitudes.↩︎

42. In the proof below, we consider the oracle queries to \(S_{d}\). The same proof can be extended to the oracle queries to \(S_{\ket{\phi_{x}}}\) for each \(x\), or more general cases. e.g., queries to \(\ketbra{0}\otimes S_{\ket{\phi_{x_{0}}}}+\ketbra{1}\otimes S_{\ket{\phi_{x_{1}}}}\) for any \(x_{1},x_{2}\) of the same length. We focus on the queries to \(S_{d}\) because it is the most complicated.↩︎

43. Where the algorithm randomly chooses \(x,z\) with probability \(|\alpha_{x,z}|^{2}\), prepare \(\ket{1,\phi_{x}}\) and apply the projector \(\Pi_{x,z}=\ketbra{\rho_{x,z}}\).↩︎

44. Here we use \(n=\omega(\log \lambda)\) and \(m=\poly\).↩︎

45. This is possible for the isometry oracle as we assume that the output register is not touched before the oracle queries.↩︎

46. Careful readers may be concerned about the isometry oracle implicit in \(U_i\)’s when using \(U_i^\dagger\). We note that the same proof applies to the original algorithm represented as in 29 ; we only use 31 for simplicity of the proof of [claim:purity95povm].↩︎

47. Wlog, the input register can be part of \(\boldsymbol{A}\) and \(\boldsymbol{B}\).↩︎

48. In other words, \(\Pi=\ketbra{\lambda_{ij}}\otimes I\) for \(\lambda_i=\lambda_{i1}...\lambda_{in}\) or \(\Pi=\ketbra{x_{ij}}\otimes I\) for \(x_i=x_{i1}...x_{im}\) with some rearrangement of the registers.↩︎

49. To generalize the attack, we need to prove the product structure of the generation algorithm.↩︎