Unconditional Pseudorandomness Against Shallow Quantum Circuits

Ghosh, Soumik; Subramanian, Sathyawageeswar; Zhan, Wei

doi:10.4230/LIPIcs.ITCS.2026.70

Unconditional Pseudorandomness Against Shallow Quantum Circuits

Soumik Ghosh

University of Chicago, IL, USA Sathyawageeswar Subramanian

University of Oxford, UK Wei Zhan

University of Chicago, IL, USA

Abstract

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions.

In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that:

$\blacksquare$

Any quantum state $2$ -design yields unconditional pseudorandomness against both $\mathsf{QNC}^{0}$ circuits with arbitrarily many ancillae and $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits with nearly linear ancillae.
$\blacksquare$

Random phased subspace states, where the phases are picked using a $4$ -wise independent function, are unconditionally pseudoentangled against the above circuit classes.
$\blacksquare$

Any unitary $2$ -design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local $\mathsf{QNC}^{0}$ adversaries, even with limited $\mathsf{AC}^{0}$ postprocessing.

Our results stand in stark contrast to the standard guarantee of the $2$ -design property, which only ensures that they cannot be distinguished from Haar random ensembles using two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

Keywords and phrases:

quantum pseudorandomness, shallow quantum circuits, pseudorandomness, t-designs

Funding:

Sathyawageeswar Subramanian: funded by a Royal Society University Research Fellowship.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pseudorandomness and derandomization ; Theory of computation

\rightarrow

Quantum information theory ; Theory of computation

\rightarrow

Quantum complexity theory ; Theory of computation

\rightarrow

Quantum complexity theory

Related Version:

Full Version: https://arxiv.org/abs/2507.18796

Acknowledgements:

The authors would like to thank John Bostanci, Daniel Grier, Natalie Parham, Jack Morris, Francisca Vasconcelos, and Henry Yuen for stimulating discussions on related topics.

DOI:

10.4230/LIPIcs.ITCS.2026.70

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Randomness is fundamental to both classical and quantum computation, particularly in cryptography and algorithm design. However, true randomness is often scarce or computationally impractical. The theory of pseudorandomness studies deterministic objects that appear random to resource-bounded observers. For example, classical pseudorandom generators (PRGs) produce bit strings indistinguishable from random strings for computationally limited observers. A rich theory connects hardness to pseudorandomness for complexity classes such as $\mathsf{BPP}$ [48, 33].

Quantum pseudorandomness extends these ideas to quantum states and unitaries. Truly random quantum objects, described by the Haar measure over the unitary group [43], require exponential resources to generate. Two approaches have emerged for more efficient alternatives. First, the information-theoretic or statistical notion of efficient quantum $t$ -designs: ensembles of states or unitaries that match the first $t$ moments of the Haar measure, and can be prepared or implemented efficiently [18, 13, 12]. Second, the more recent computational approach: ensembles of quantum pseudorandom states (PRS) or unitaries (PRU) that appear Haar-random to computationally bounded quantum observers [35].

Classically, unconditional pseudorandomness has been successfully constructed against several restricted computational models such as constant-depth circuits [48, 14, 19], read-once branching programs [49, 33, 51], and low-degree polynomials [58, 8]. These results bypass the need for complexity theoretic assumptions, and have profound implications for cryptography [42], derandomization [53, 32], and lower bounds [31, 25].¹¹1Readers may refer to the survey by Hatami and Hoza [30] for a comprehensive review of the more recent developments on classical unconditional pseudorandomness.

In contrast, all existing quantum pseudorandom constructions target powerful adversaries such as polynomial-time quantum devices ( $\mathsf{BQP}$ ), and rely on cryptographic assumptions such as the existence of quantum-secure one-way functions. However, it is often conjectured that the requirement for quantum pseudorandomness is weaker than the classical, and there are plenty of relativized evidences that PRS and PRU might exist in a world without one-way functions [37, 38, 39, 9]. This leads to the main question we explore in this paper: Can we demonstrate unconditional quantum pseudorandomness against restricted computational models, with similar or even weaker requirement on the objects?

Our contributions.

We establish the first unconditional efficient quantum pseudorandomness results against shallow-depth circuit classes. Such circuits model near-term quantum devices with limited coherence times and gate counts. We show that efficient pseudorandom objects, including PRS, pseudoentanglement, and PRU secure against parallel queries, can be constructed unconditionally for shallow quantum circuits. Our key insight is that due to the depth constraints, each output qubit of shallow quantum circuits locally depends only on a subset of input qubits, thus fundamentally limiting the ability of such circuits to distinguish certain structured quantum objects from Haar-random ones.

A notable aspect of our results is that the only property needed for our constructions is that of being an (approximate) $2$ -design. A priori, the design property only imposes conditions on the behavior of the object when few (in this case exactly two) copies of the objects are present, while pseudorandomness is a property that concerns an arbitrary polynomial number of copies. Rather surprisingly, our results bridge this gap, showing that when the power of the adversaries is restricted, information-theoretic indistinguishability on two copies is strong enough to imply computational indistinguishability on polynomially many copies.

Our work raises several open questions, ranging from constructing new classes of unconditionally pseudorandom objects against other shallow circuit classes, to applying these results to quantum cryptography and complexity theory. We discuss some of these directions in Section 5, providing new perspectives for analyzing near-term quantum devices.

1.1 Main results

In this article we construct unconditionally secure efficient pseudorandom objects against two important shallow-depth quantum circuit classes – $\mathsf{QNC}^{0}$ and $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ .

1.2 PRS from state designs

We first demonstrate that unconditional pseudorandomness can be derived from state designs, whose security holds against circuits up to $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ .

Theorem 1 (Informal; See Corollary 21).

Every $2$ -design state ensemble is an unconditionally secure PRS against $\mathsf{QNC}^{0}$ circuits with arbitrarily many ancillae and almost linearly many bits of output.

Theorem 2 (Informal; See Corollary 28).

Every $2$ -design state ensemble is an unconditionally secure PRS against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits with almost linearly many ancillae.

We observe that the classical analogy of the above results does not hold. The classical counterpart to $2$ -designs, namely pairwise independent distributions, cannot be guaranteed to fool even $\mathsf{NC}^{0}$ circuits. Furthermore, while $k$ -wise independent distributions for $k=\log^{O(1)}(n)$ can fool $\mathsf{AC}^{0}$ circuits of fixed depth [14], no such construction with fixed $k$ can fool $\mathsf{AC}^{0}$ circuits of every depth, in contrast to our results above for quantum $2$ -designs. This gives yet another evidence that the requirement for quantum pseudorandom objects may be weaker than for classical ones.

We also note that our results stand in stark contrast to the case of BQP adversaries. For instance, in the case of random stabilizer states, which form a $3$ -design, a BQP adversary can distinguish between a state from this ensemble and a Haar random state [6, 27] using more than $3$ but still only $O(1)$ copies. In fact, Theorem 23 illustrates a stronger contrast: as we shall see, random phased subspace states form approximate $t$ -designs, but can be distinguished from Haar random by a simple adversary that performs computational basis measurements followed by $\mathsf{NC}^{2}$ postprocessing when given more than $t$ copies.

Pseudoentanglement refers to the phenomenon whereby ensembles of states having very low entanglement are indistinguishable from states having very high entanglement. We also prove that unconditional pseudoentanglement can be achieved against the above shallow quantum circuits.

Theorem 3 (Informal; See Corollary 29).

There exists efficiently constructible, unconditionally secure pseudoentanglement against $\mathsf{QNC}^{0}$ circuits, and against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits with poly-logarithmically many ancillae.

1.3 PRU from unitary designs

Similarly, we also prove that unitary $t$ -designs are unconditionally pseudorandom against geometrically local shallow quantum circuits when queried only in parallel (i.e. non-adaptively).

Theorem 4 (Informal; See Theorem 35).

Every unitary $2$ -design is an unconditionally non-adaptive secure PRU against $1$ -dimensional geometrically local $\mathsf{QNC}^{0}$ circuits with arbitrarily many ancillae, and almost linear depth $1$ -dimensional geometrically local $\mathsf{QNC}$ pre-processing.

We also extend this PRU construction to $\mathsf{QNC}^{0}$ circuits with $\mathsf{AC}^{0}$ post-processing, with the caveat that it must be weakened slightly since we do not have a natural means to deal with ancillae in the post-processing phase.

Theorem 5 (Informal; See Theorem 36).

Every unitary $2$ -design on $n$ -qubits is an unconditionally non-adaptive secure PRU against a subclass of $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits on a multiple of $n$ qubits, where the pre-processing $\mathsf{QNC}^{0}$ circuit before the queries is $1$ -dimensional geometrically local.

1.4 Proof techniques

A recurring tool that we use in our proofs is that, over any subsystem, the reduced states of a Haar random state are close to maximally mixed with high probability (see Corollary 18). Our PRU results require the analogue of this observation for the output of non-adaptive queries to a Haar random unitary (see Corollary 33). For this, we bound the expected norm of partial traces of off-diagonal terms $|v\rangle\langle w|$ conjugated by a Haar random unitary (see Lemma 32).

To prove our results for $\mathsf{QNC}^{0}$ with $\mathsf{AC}^{0}$ post-processing, we observe that when the number of ancillae in the pre-processing $\mathsf{QNC}^{0}$ circuit is small, the resulting output distribution has high entropy, although the output distributions are no longer $k$ -wise independent. To deal with this, we prove a generalization of Braverman’s result [14] that $\mathsf{AC}^{0}$ circuits cannot distinguish $k$ -wise independent distributions from uniform, showing that $\mathsf{AC}^{0}$ circuits also fail to distinguish $k$ -wise indistinguishable distributions with high min-entropy (see Lemma 26).

We achieve our pseudoentanglement construction using random phased subspace states, which are superpositions over the orthonormal basis vectors of a subspace with equal amplitudes and random $\pm 1$ phases. We show that such states, when instantiated with a $4$ -wise independent function for the random phase, are indistinguishable from Haar random by shallow circuits, and have low von Neumann entropy across any cut (see Corollary 29).

We believe these technical developments may be of independent interest.

1.5 Related work

Quantum computational notions of pseudorandomness were introduced in [35] and have been studied in a variety of recent works. For instance, many types of pseudoentangled states have been constructed against BQP distinguishers in recent work (for examples, see [1, 10, 11, 2, 24, 34, 20]). These notions have found a wide range of applications, from cryptography [4, 26, 3] to physics [59, 28, 21, 10, 15]. A number of recent works have also considered the problem of constructing highly efficient pseudorandom unitaries that are implementable in extremely low depth [54, 16].

However, all these constructions rely on complexity theoretic assumptions to obtain pseudorandomness against polynomial-sized quantum circuits. Usually, the assumption relates to the existence of quantum-secure one way functions [60], based on computational hardness assumptions like the quantum hardness of the learning with errors (LWE) problem [52].

In contrast to this line of work, in our work the adversary is a class of shallow-depth quantum circuits against which we would like our pseudorandom constructions to be secure, and our contribution lies in showing that pseudorandomness against such circuit classes can be obtained without making any complexity theoretic assumptions.

2 Preliminaries

We first define some commonly used notations. We use $[n]$ to denote the set $\{1,\ldots,n\}$ . For two distributions $\mathcal{D}$ and $\mathcal{D}^{\prime}$ over a set $X$ we use $\left\lvert\mathcal{D}-\mathcal{D}^{\prime}\right\rvert_{1}$ to denote their total variation distance. We denote a random sample $x$ drawn according to $\mathcal{D}$ by $x\sim\mathcal{D}$ , and we abuse the notation to denote $x$ drawn uniformly from a set $X$ by $x\sim X$ . The identity operator on $n$ qubits is denoted as $\mathbb{I}_{n}$ .

We use $\left\lVert\cdot\right\rVert_{p}$ to denote the Schatten- $p$ norms of Hermitian operators. Specifically, $\left\lVert\cdot\right\rVert_{1}$ , $\left\lVert\cdot\right\rVert_{2}$ and $\left\lVert\cdot\right\rVert_{\infty}$ respectively refers to the trace norm, Frobenius norm and operator norm.

We use the following shorthands for asymptotic growth: $\operatorname{poly}(n)=n^{O(1)}$ , $\operatorname{polylog}(n)=\log^{O(1)}n$ and $\operatorname{negl}(n)=n^{-\omega(1)}.$

We assume the readers are familiar with the definitions of the following polynomial-sized circuit classes: $\mathsf{QNC}$ for quantum bounded fan-in circuits, $\mathsf{AC}$ for classical circuits with unbounded fan-in $\mathsf{AND}$ gates, and $\mathsf{QAC}$ for quantum circuits with unbounded size $\mathsf{CZ}$ gates (but without unbounded fan-out gates). We use $\mathsf{QNC}^{0}$ , $\mathsf{AC}^{0}$ and $\mathsf{QAC}^{0}$ to denote their constant-depth subclasses respectively. Without loss of generality, we assume the bounded fan-in is at most $2$ (otherwise the constants in some of our results will be changed). For the purpose of this paper, we do not require the quantum circuits to compute cleanly: the ancillae could start with any specified state and also could end up in arbitrary states.

Following [55], we also consider the hybrid circuits with quantum pre-processing and classical post-processing:

Definition 6.

For a class of classical circuits $\mathcal{F}$ and a class of quantum circuits $\mathcal{C}$ , the circuit class $\mathcal{F}\circ\mathcal{C}$ consist of all circuits $F\circ C$ that are composed of a quantum circuit $C\in\mathcal{C}$ , followed by computational basis measurements on all output qubits of $C$ , and then with some $F\in\mathcal{F}$ applied on the measurement outcomes. The output distribution of $F\circ C$ with the input state $\rho$ is $F(C(\rho))$ .

The class that we are specifically interested in is $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ , which is justified in Section 3.2. It is shown in [55] that parity is hard to compute in this class, assuming either no ancillae or linear size of the $\mathsf{AC}^{0}$ circuit. It worth noting that we do not know yet whether $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ is comparable with $\mathsf{QAC}^{0}$ .

Quantum Pseudorandom Primitives

Below we generalize the commonly used definitions of quantum pseudorandom primitives to those with respect to specific classes of adversaries, rather than simply polynomial-time adversaries. The state and unitary ensembles are all discrete distributions, which we denote by their supports for succinctness.

Definition 7.

The state ensemble $\{|\psi_{i}\rangle\}$ on $n$ qubits is a pseudorandom state ensemble (PRS) against a class of quantum circuits $\mathcal{C}$ , if for the $n$ -qubit Haar random state $|\psi_{\mathsf{Haar}}\rangle$ , every $t=\operatorname{poly}(n)$ and every circuit $C\in\mathcal{C}$ , we have

\left\lvert\operatorname*{\mathbb{E}}_{{i}}\left[C\left(|\psi_{i}\rangle% \langle\psi_{i}|^{\otimes t}\right)\right]-\operatorname*{\mathbb{E}}\left[C% \left(|\psi_{\mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}|^{\otimes t}% \right)\right]\right\rvert_{1}=\operatorname{negl}(n).

Here $C(\rho)$ represents the output distribution with input state $\rho$ .

Definition 8.

We say two state ensembles $\{|\psi_{i}\rangle\}$ and $\{|\psi_{j}^{\prime}\rangle\}$ on $n$ qubits demonstrate pseudoentanglement against a class of quantum circuits $\mathcal{C}$ , if for every $t=\operatorname{poly}(n)$ and every circuit $C\in\mathcal{C}$ , we have

\left\lvert\operatorname*{\mathbb{E}}_{{i}}\left[C\left(|\psi_{i}\rangle% \langle\psi_{i}|^{\otimes t}\right)\right]-\operatorname*{\mathbb{E}}_{{j}}% \left[C\left(|\psi_{j}^{\prime}\rangle\langle\psi_{j}^{\prime}|^{\otimes t}% \right)\right]\right\rvert_{1}=\operatorname{negl}(n),

while across the same bipartition or cut of the qubits, the expected entanglement entropies of $\{|\psi_{i}\rangle\}$ and $\{|\psi_{j}^{\prime}\rangle\}$ are asymptotically different.

Definition 9.

The unitary ensemble $\{U_{i}\}$ on $n$ qubits is a pseudorandom unitary ensemble (PRU) against a class of quantum circuits $\mathcal{C}$ , if for the $n$ -qubit Haar random unitary $U_{\mathsf{Haar}}$ and every circuit $C^{U}\in\mathcal{C}^{U}$ on $t=\operatorname{poly}(n)$ input qubits, we have

\left\lvert\operatorname*{\mathbb{E}}_{{i}}\left[C^{U_{i}}(|0^{t}\rangle% \langle 0^{t}|)\right]-\operatorname*{\mathbb{E}}\left[C^{U_{\mathsf{Haar}}}(|% 0^{t}\rangle\langle 0^{t}|)\right]\right\rvert_{1}=\operatorname{negl}(n).

(1)

Here $C^{U}$ stands for a circuit $C$ which uses $U$ as oracle gates.

In this work we are concerned with the notion of PRU when $U$ is guaranteed to be applied in parallel, that is, (1) is only required to hold for circuits $C^{U}$ that apply all their $U$ gates in a single layer. In this case, we say $\{U_{i}\}$ on $n$ qubits is a parallel-query (or non-adaptive-query, as defined in [44]) secure PRU against $\mathcal{C}$ . We refer to the part of the circuit $C^{U}$ before the layer of $U$ gates as pre-processing, and the part after as post-processing.

We will also discuss some potential constructions of unconditional pseudorandom generators against shallow quantum circuits, defined as follows.

Definition 10.

The boolean function $G:\{0,1\}^{\ell}\rightarrow\{0,1\}^{n}$ is a $t$ -copy pseudorandom generator (PRG) against a class of quantum circuits $\mathcal{C}$ , if for every circuit $C\in\mathcal{C}$ , we have

\left\lvert\operatorname*{\mathbb{E}}_{{x\sim\{0,1\}^{\ell}}}\left[C\left(|G(x% )\rangle\langle G(x)|^{\otimes t}\right)\right]-\operatorname*{\mathbb{E}}_{{x% \sim\{0,1\}^{n}}}\left[C\left(|x\rangle\langle x|^{\otimes t}\right)\right]% \right\rvert_{1}=\operatorname{negl}(n).

In particular, $G$ is a pseudorandom generator against $\mathcal{C}$ if it is a $t$ -copy pseudorandom generator for every $t=\operatorname{poly}(n)$ .

State and Unitary Designs

Here we recall the definitions and properties of exact and approximate designs, which are statistical notions of pseudorandomness.

Definition 11 (State $t$ -design).

The state ensemble $\{|\psi_{i}\rangle\}$ on $n$ qubits is a $t$ -design, if for the $n$ -qubit Haar random state $|\psi_{\mathsf{Haar}}\rangle$ , we have

\operatorname*{\mathbb{E}}_{{i}}\left[|\psi_{i}\rangle\langle\psi_{i}|^{% \otimes t}\right]=\operatorname*{\mathbb{E}}\left[|\psi_{\mathsf{Haar}}\rangle% \langle\psi_{\mathsf{Haar}}|^{\otimes t}\right].

We say that $\{|\psi_{i}\rangle\}$ is an $\varepsilon$ -approximate $t$ -design, if instead we have

\left\lVert\operatorname*{\mathbb{E}}_{{i}}\left[|\psi_{i}\rangle\langle\psi_{% i}|^{\otimes t}\right]-\operatorname*{\mathbb{E}}\left[|\psi_{\mathsf{Haar}}% \rangle\langle\psi_{\mathsf{Haar}}|^{\otimes t}\right]\right\rVert_{1}\leq\varepsilon.

Lemma 12.

Let $\{|\psi_{i}\rangle\}$ be an $\epsilon$ -approximate state $2$ -design on $n$ qubits, and let $B$ be a subsystem of containing $n-k$ qubits. We have

\operatorname*{\mathbb{E}}_{{i}}\left[\left\lVert\operatorname{Tr}_{B}[|\psi_{% i}\rangle\langle\psi_{i}|]\right\rVert_{2}^{2}\right]\leq\operatorname*{% \mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B}[|\psi_{\mathsf{Haar}}\rangle% \langle\psi_{\mathsf{Haar}}|]\right\rVert_{2}^{2}\right]+\varepsilon.

Proof.

Denote the complementary subsystem to $B$ by $A$ , which contains $k$ qubits. Define the swap operator $R$ by the identity

\operatorname{Tr}[\operatorname{Tr}_{B}\rho_{1}\cdot\operatorname{Tr}_{B}\rho_% {2}]=\operatorname{Tr}\left[\left(\rho_{1}\otimes\rho_{2}\right)\cdot R\right],

where one can check that

R=\sum_{x,y\in\{0,1\}^{k}}|x\rangle\langle y|_{A}|y\rangle\langle x|_{A^{% \prime}}\otimes\mathbb{I}_{BB^{\prime}}.

Here $A^{\prime}$ and $B^{\prime}$ are identical copies of $A$ and $B$ respectively.

Since $R$ is a permutation matrix, the operator norm of $R$ is exactly $1$ . As a result, by Hölder’s inequality we have

		$\displaystyle\ \operatorname{\mathbb{E}}_{{i}}\left[\left\lVert\operatorname{% Tr}_{B}[\|\psi_{i}\rangle\langle\psi_{i}\|]\right\rVert_{2}^{2}\right]-% \operatorname{\mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B}[\|\psi_{% \mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}\|]\right\rVert_{2}^{2}\right]$
	$\displaystyle=$	$\displaystyle\ \operatorname{Tr}\left[\left(\operatorname{\mathbb{E}}_{{i}}% \left[\|\psi_{i}\rangle\langle\psi_{i}\|^{\otimes 2}\right]-\operatorname{% \mathbb{E}}\left[\|\psi_{\mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}\|^{% \otimes 2}\right]\right)\cdot R\right]$
	$\displaystyle\leq$	$\displaystyle\ \left\lVert\operatorname{\mathbb{E}}_{{i}}\left[\|\psi_{i}% \rangle\langle\psi_{i}\|^{\otimes 2}\right]-\operatorname{\mathbb{E}}\left[\|% \psi_{\mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}\|^{\otimes 2}\right]% \right\rVert_{1}\cdot\left\lVert R\right\rVert_{\infty}\leq\varepsilon.\$

$\hfill\blacktriangleleft$

Definition 13 (Unitary $t$ -design).

An ensemble $\mathcal{D}=\{U_{i}\}$ of $n$ -qubit unitaries is a unitary $t$ -design if, for the $n$ -qubit Haar-random unitary $U_{\mathsf{Haar}}$ , we have

\operatorname*{\mathbb{E}}_{{i}}\left[U_{i}^{\otimes t}\otimes(U_{i}^{\dagger}% )^{\otimes t}\right]=\operatorname*{\mathbb{E}}\left[U_{\mathsf{Haar}}^{% \otimes t}\otimes(U_{\mathsf{Haar}}^{\dagger})^{\otimes t}\right].

Defining the $t$ -th moment channels as

\Phi_{\mathcal{D}}^{(t)}(\rho)=\operatorname*{\mathbb{E}}_{{i}}\left[U_{i}^{% \otimes t}\cdot\rho\cdot(U_{i}^{\dagger})^{\otimes t}\right],\qquad\Phi_{% \mathsf{Haar}}^{(t)}(\rho)=\operatorname*{\mathbb{E}}\left[U_{\mathsf{Haar}}^{% \otimes t}\cdot\rho\cdot(U_{\mathsf{Haar}}^{\dagger})^{\otimes t}\right],

we call $\mathcal{D}$ is an $\varepsilon$ -approximate unitary $t$ -design, if for all operators $\rho$ with $\left\lVert\rho\right\rVert_{1}\leq 1$ we have

\left\lVert\Phi_{\mathcal{D}}^{(t)}(\rho)-\Phi_{\mathsf{Haar}}^{(t)}(\rho)% \right\rVert_{1}\leq\varepsilon.

Lemma 14.

Let $\{U_{i}\}$ be an $\epsilon$ -approximate unitary $2$ -design on $n$ qubits, and let $B$ be a subsystem of the $n$ qubits. For every two $n$ -qubit states $|v\rangle$ and $|w\rangle$ , we have

\operatorname*{\mathbb{E}}_{{i}}\left[\left\lVert\operatorname{Tr}_{B}[U_{i}|v% \rangle\langle w|U_{i}^{\dagger}]\right\rVert_{2}^{2}\right]\leq\operatorname*% {\mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B}[U_{\mathsf{Haar}}|v\rangle% \langle w|U_{\mathsf{Haar}}^{\dagger}]\right\rVert_{2}^{2}\right]+\varepsilon.

Proof.

Denote the complementary subsystem to $B$ by $A$ , and assume that $A$ contains $k$ qubits. Define the operator $R$ the same way as the proof above for Lemma 12, and we have

\left\lVert\operatorname{Tr}_{B}(U|v\rangle\langle w|U^{\dagger})\right\rVert_% {2}^{2}=\operatorname{Tr}\left[(U|v\rangle\langle w|U^{\dagger})^{\otimes 2}% \cdot R\right].

Similarly, since $\left\lVert R\right\rVert_{\infty}=1$ and $\left\lVert|v\rangle\langle w|^{\otimes 2}\right\rVert_{1}=1$ , by Hölder’s inequality we have

		$\displaystyle\ \operatorname{\mathbb{E}}_{{i}}\left[\left\lVert\operatorname{% Tr}_{B}[U_{i}\|v\rangle\langle w\|U_{i}^{\dagger}]\right\rVert_{2}^{2}\right]-% \operatorname{\mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B}[U_{\mathsf{% Haar}}\|v\rangle\langle w\|U_{\mathsf{Haar}}^{\dagger}]\right\rVert_{2}^{2}\right]$
	$\displaystyle=$	$\displaystyle\ \operatorname{Tr}\left[\left(\Phi_{\mathcal{D}}^{(t)}(\|v\rangle% \langle w\|^{\otimes 2})-\Phi_{\mathsf{Haar}}^{(t)}(\|v\rangle\langle w\|^{% \otimes 2})\right)\cdot R\right]$
	$\displaystyle=$	$\displaystyle\ \left\lVert\Phi_{\mathcal{D}}^{(t)}(\|v\rangle\langle w\|^{% \otimes 2})-\Phi_{\mathsf{Haar}}^{(t)}(\|v\rangle\langle w\|^{\otimes 2})\right% \rVert_{1}\cdot\left\lVert R\right\rVert_{\infty}\leq\varepsilon.\$

$\hfill\blacktriangleleft$

Schmidt Decomposition

We will need several facts about the Schmidt decomposition (listed below), whose proofs can be found in e.g. [47].

Definition 15.

Let $\mathcal{H}_{1},\mathcal{H}_{2}$ be two Hilbert spaces, and let $x\in\mathcal{H}_{1}\otimes\mathcal{H}_{2}$ . If we write

x=\sum_{i=1}^{r}\alpha_{i}\cdot v_{i}\otimes w_{i},

(2)

where $\alpha_{i}\in\mathbb{C}$ , $v_{i}\in\mathcal{H}_{1}$ and $w_{i}\in\mathcal{H}_{2}$ , we call (2) a tensor product decomposition of $x$ . Furthermore, if both $\{v_{i}\}$ and $\{w_{i}\}$ are orthonormal and each $\alpha_{i}$ is non-zero, we call (2) a Schmidt decomposition and $r$ the Schmidt rank of $x$ with respect to $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ .

Lemma 16.

Let $\mathcal{H}_{1},\mathcal{H}_{2}$ be two Hilbert spaces, and let $x\in\mathcal{H}_{1}\otimes\mathcal{H}_{2}$ . Then:

$\blacksquare$

In any tensor product decomposition of $x$ as in (2), the number of terms $r$ is at least the Schmidt rank of $x$ ;
$\blacksquare$

Let $\{v_{i}\}$ and $\{w_{j}\}$ be two orthonormal basis for $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ , respectively. If we write

$x=\sum_{i,j}\alpha_{ij}\cdot v_{i}\otimes w_{j},$

then the Schmidt rank of $x$ is exactly the rank of the matrix with entry $\alpha_{ij}$ at the $i$ -th row and $j$ -th column.
$\blacksquare$

The von Neumann entanglement entropy of $x$ , with respect to the subsystems $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ , is at most $\log_{2}r$ where $r$ is the Schmidt rank of $x$ .

3 Unconditional pseudorandomness from 2-designs

In this section, we focus on state designs which exploit the locality properties of shallow circuits in order to achieve unconditional pseudorandomness. At a high level, this resembles a quantum analog of small bias distributions (e.g. [46]), which can fool low-degree polynomials. We will begin with some facts about Haar random states, which relate the size of the subsystem with entanglement entropy, and allow us to approximate small subsystems with maximally mixed states.

Lemma 17 ([41, 40]).

Let $|\psi_{\mathsf{Haar}}\rangle$ be an $n$ -qubit Haar random state, and let $\rho_{A}$ be the reduced density matrix of $|\psi_{\mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}|$ on the subsystem $A$ with $|A|=k$ qubits. Then

\operatorname*{\mathbb{E}}[\operatorname{Tr}(\rho_{A}^{2})]=\frac{2^{k}+2^{n-k% }}{2^{n}+1}.

Corollary 18.

Let $|\psi_{\mathsf{Haar}}\rangle$ be an $n$ -qubit Haar random state. For any $t\geq 1$ , let $\rho_{A}$ be the reduced density matrix of $|\psi_{\mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}|^{\otimes t}$ over a subsystem $A$ . Then for every $\delta>0$ , with probability at least $1-n^{O(k)}\cdot 2^{-n/2}\cdot\delta^{-1}$ over $|\psi_{\mathsf{Haar}}\rangle$ , it holds for all $A$ with $|A|=k$ qubits that

\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{1}\leq\delta.

Proof.

First consider the case when $A$ is fully contained in one copy of the Haar random state. In this case from Lemma 17 we have

	$\displaystyle\operatorname*{\mathbb{E}}\left[\left\lVert\rho_{A}-\frac{1}{2^{k% }}\mathbb{I}_{k}\right\rVert_{1}\right]$	$\displaystyle\leq 2^{k/2}\cdot\operatorname*{\mathbb{E}}\left[\left\lVert\rho_% {A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{2}\right]$
		$\displaystyle\leq 2^{k/2}\cdot\operatorname*{\mathbb{E}}\left[\left\lVert\rho_% {A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{2}^{2}\right]^{1/2}$
		$\displaystyle=2^{k/2}\cdot\operatorname*{\mathbb{E}}\left[\operatorname{Tr}(% \rho_{A}^{2})-2^{-k}\right]^{1/2}$
		$\displaystyle=2^{k/2}\cdot\left(\frac{2^{k}-2^{-k}}{2^{n}+1}\right)^{1/2}$
		$\displaystyle\leq 2^{k-n/2}.$

By Markov’s inequality, we know that $\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{1}\leq\delta/k$ holds with probability at least $1-k\cdot 2^{k-n/2}\cdot\delta^{-1}$ . By a union bound, this holds for all $A$ with $|A|\leq k$ with probability at least $1-n^{O(k)}\cdot 2^{-n/2}\cdot\delta^{-1}$ .

When $A$ consists qubits from at most $k$ different copies, we denote the subsystems as $A=A_{1}\sqcup A_{2}\sqcup\cdots$ with $|A_{i}|=k_{i}$ . Since the copies are unentangled with each other, we have $\rho_{A}=\rho_{A_{1}}\otimes\rho_{A_{2}}\otimes\cdots$ , and thus

	$\displaystyle\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{1}$	$\displaystyle\leq\sum_{i}\left\lVert\rho_{A_{1}}\otimes\cdots\otimes\rho_{A_{i% }}-\rho_{A_{1}}\otimes\cdots\otimes\rho_{A_{i-1}}\otimes\frac{1}{2^{k_{i}}}% \mathbb{I}_{k_{i}}\right\rVert_{1}$
		$\displaystyle=\sum_{i}\left\lVert\rho_{A_{i}}-\frac{1}{2^{k_{i}}}\mathbb{I}_{k% _{i}}\right\rVert_{1}$
		$\displaystyle\leq\delta$

with probability at least $1-n^{O(k)}\cdot 2^{-n/2}\cdot\delta^{-1}$ . $\hfill\blacktriangleleft$

Notice that the proof of Corollary 18 only uses the second moment properties of $|\psi_{\mathsf{Haar}}\rangle$ , and therefore the conclusions immediately hold for approximate 2-designs with negligible error as well.

Corollary 19.

Let $\{|\psi_{i}\rangle\}$ be an $\varepsilon$ -approximate $2$ -design on $n$ qubits. For any $t\geq 1$ , let $\rho_{A}$ be the reduced density matrix of $|\psi_{i}\rangle\langle\psi_{i}|^{\otimes t}$ over a subsystem $A$ . Then for every $\delta>0$ , with probability at least $1-n^{O(k)}\cdot(\varepsilon+2^{-n})^{1/2}\cdot\delta^{-1}$ over $i$ , it holds for all $A$ with $|A|=k$ qubits that

\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{1}\leq\delta.

Proof.

By Lemma 12, the approximate design property implies that

\operatorname*{\mathbb{E}}\left[\operatorname{Tr}(\rho_{A}^{2})-2^{-k}\right]^% {1/2}\leq(\varepsilon+2^{k-n})^{1/2},

and thus

\operatorname*{\mathbb{E}}\left[\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_% {k}\right\rVert_{1}\right]\leq 2^{k}\cdot(\varepsilon+2^{-n})^{1/2}.

The rest of the proof follows the same arguments from Corollary 18. $\hfill\blacktriangleleft$

3.1 Pseudorandomness against $\mathsf{QNC}^{0}$

As a warm-up, we will use Corollary 18 and Corollary 19 to show that any $2$ -design is indistinguishable to a Haar random state, with respect to any $\mathsf{QNC}^{0}$ distinguisher.

Theorem 20.

Let $\{|\psi_{i}\rangle\}$ be an $\varepsilon$ -approximate $2$ -design on $n$ qubits for some $\varepsilon=\operatorname{negl}(n)$ . Then $\{|\psi_{i}\rangle\}$ is a PRS against $\mathsf{QNC}$ circuits with depth

d=\min(\log\log(1/\varepsilon),\log n)-\log\log n-\omega(1)

and a single-bit output. In particular, when $\varepsilon\leq 2^{-\Omega(n)}$ , $\{|\psi_{i}\rangle\}$ is PRS against $\mathsf{QNC}$ circuits up to depth $d=\log n-\log\log n-\omega(1)$ .

Proof.

The output bit of the depth- $d$ $\mathsf{QNC}$ circuit depends on at most $k=2^{d}$ input qubits and ancillae. Let $A$ be the subsystem of the input state on these qubits, and let $m$ be the number of ancillae touched. Denote the reduced density matrix, over the subsystem $A$ , of the Haar random state to be $\rho^{\mathsf{Haar}}_{A}$ and that of the state picked from $\{|\psi_{i}\rangle\}$ to be $\rho_{A}$ . Then for the channel $\Phi_{\mathcal{C}}$ that maps the subsystem $A$ to the output qubit, we have

\left\lVert\Phi_{\mathcal{C}}\left(\rho^{\mathsf{Haar}}_{A}\right)-\Phi_{% \mathcal{C}}\left(\rho_{A}\right)\right\rVert_{1}\leq\left\lVert\rho^{\mathsf{% Haar}}_{A}-\rho_{A}\right\rVert_{1}=\operatorname{negl}(n),

with probability at least $1-\operatorname{negl}(n)$ over the choice of the states. This follows from Corollary 18 and Corollary 19, and the observation that

n^{O(k)}\cdot(\varepsilon+2^{-n})^{1/2}\leq\operatorname{negl}(n)

is equivalent to

O(k)\leq\frac{\log(1/(\varepsilon+2^{-n}))}{2\log n}-\omega(1),

which is satisfied for every $d=\log k$ such that

d\leq\min(\log\log(1/\varepsilon),\log n)-\log\log n-\omega(1).\

$\hfill\blacktriangleleft$ The above theorem can be strengthened to work for the case when multiple output qubits are measured.

Corollary 21.

Let $\{|\psi_{i}\rangle\}$ be an $\varepsilon$ -approximate $2$ -design on $n$ qubits for some $\varepsilon=2^{-\Omega(n)}$ . Then $|\psi_{i}\rangle$ is a PRS against $\mathsf{QNC}$ circuits with depth $d$ and $k\leq 2^{-d}\cdot o(n/\log n)$ bits of output.

Proof.

The backward lightcone of the $k$ output qubits is of at most

k\cdot 2^{d}=o(n/\log n)

in size. The proof then follows from the same argument as Theorem 20. $\hfill\blacktriangleleft$

3.2 Pseudorandomness against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$

The lightcone argument in the previous section renders most parts of a $\mathsf{QNC}^{0}$ circuit and most input qubits unrelated. Naturally, it is more desirable to prove the statement against $\mathsf{QNC}^{0}$ circuits where all the output qubits are measured, that is, the output distribution is indistinguishable in total variation distance between $t$ -designs and Haar random states. However, our example below shows that this is too much to ask for, even when the $\mathsf{QNC}^{0}$ circuit does nothing and the input states get measured immediately.

Definition 22 (Random phased subspace states).

A $d$ -dimensional random phased subspace state on $n$ qubits is the following state:

|\psi_{S,f}\rangle=\frac{1}{2^{d/2}}\sum_{x\in S}(-1)^{f(x)}|x\rangle,

where $S\in\mathbb{F}_{2}^{n}$ is a random $d$ -dimensional linear subspace, and $f:S\rightarrow\{0,1\}$ is a random function.

Theorem 23.

For every $n>d>t$ , $\{|\psi_{S,f}\rangle\}$ is an $O(2^{t-d})$ -approximate $t$ -design, but $|\psi_{S,f}\rangle^{\otimes(d+1)}$ and $|\psi_{\mathsf{Haar}}\rangle^{\otimes(d+1)}$ are distinguishable when measured in the computational basis, with total variation distance $1-O(2^{d})/2^{n}$ .

Proof.

The proof that $\{|\psi_{S,f}\rangle\}$ is an approximate design is deferred to Appendix A. To distinguish $d+1$ copies of $\{|\psi_{S,f}\rangle\}$ from Haar random, notice that the measurement outcome in each copy is a random $x\in S$ , and thus the $d+1$ outcomes must be linearly dependent. On the other hand, the measurement outcomes from $d+1$ copies of a Haar random state, when all distinct, form a random $(d+1)$ -element subset of $\{0,1\}^{n}$ because of symmetry, and therefore are linearly dependent with probability at most

\frac{1}{2^{n}}+\frac{1}{2^{n-1}}+\cdots+\frac{1}{2^{n-d}}\leq\frac{1}{2^{n-d-% 1}}.

We also know that the collision probability for a Haar random state is $2/(2^{n}+1)$ [17], and thus the probability for the outcomes not being all distinct is at most $d(d+1)/2^{n}$ by the union bound. As a result, the total variation distance between the measurement outcomes of $|\psi_{S,f}\rangle^{\otimes(d+1)}$ and $|\psi_{\mathsf{Haar}}\rangle^{\otimes(d+1)}$ is at least $1-1/2^{n-d-1}-d(d+1)/2^{n}=1-O(2^{d})/2^{n}$ . $\hfill\blacktriangleleft$

Notice that not only does the distinguisher in Theorem 23 apply no quantum gates, the classical post-processing on the measurement outcomes is also quite simple. It checks linear dependence whose complexity is captured by $\mathsf{DET}$ , a complexity class between $\mathsf{NC}^{1}$ and $\mathsf{NC}^{2}$ containing all problems reducible to determinant. This motivates us to examine the case when the classical post-processing is restricted to some provably weaker class than $\mathsf{DET}$ . It turns out that for $\mathsf{AC}^{0}$ , $2$ -designs are indeed still pseudorandom in this case. We crucially make use of the follow result, first proved by Braverman [14], subsequentially improved by [56] and Harsha and Srinivasan [29], that almost $k$ -wise uniform distributions fools $\mathsf{AC}^{0}$ :

Lemma 24.

For every $\delta$ -almost $k$ -wise independent distribution on $m$ bits, any $\mathsf{AC}$ circuits with size $s$ and depth $d$ cannot distinguish it from the uniform distribution with advantage $\varepsilon+m^{k}\delta$ , for certain $k=(\log s)^{O(d)}\cdot\log(1/\varepsilon)$ .

We start out with the simple case, when no ancilla is allowed for the $\mathsf{QNC}^{0}$ circuit.

Theorem 25.

Let $\{|\psi_{i}\rangle\}$ be an $\varepsilon$ -approximate $2$ -design on $n$ qubits for some $\varepsilon=2^{-\log^{\omega(1)}n}$ . Then $|\psi_{i}\rangle$ is a PRS against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits with no ancilla.

Proof.

Suppose the circuit has size $s$ and depth $d$ . Fix some $k=(\log s)^{O(d)}\cdot\log^{2}n=\log^{O(1)}n$ according to Lemma 24.

The output of the $\mathsf{QNC}^{0}$ circuit, when all qubits are measured, is a distribution $\mathcal{D}_{|\psi\rangle}$ over $m=\operatorname{poly}(n)$ bits that depends on the input state $|\psi\rangle$ . By Corollary 19, for both $\mathcal{D}_{|\psi_{i}\rangle}$ and $\mathcal{D}_{|\psi_{\mathsf{Haar}}\rangle}$ , with probability $1-\operatorname{negl}(n)$ , the marginal distribution on every $k$ bits are $\delta$ -indistinguishable from the case when the input states are maximally mixed, for every $\delta>0$ such that $n^{O(k)}\cdot(\varepsilon+2^{-n})^{1/2}\cdot\delta^{-1}=\operatorname{negl}(n)$ .

Since there is no ancilla, the output distribution when the inputs are maximally mixed is the uniform distribution. Hence both $\mathcal{D}_{|\psi_{i}\rangle}$ and $\mathcal{D}_{|\psi_{\mathsf{Haar}}\rangle}$ are $\delta$ -almost $k$ -wise independent. By Lemma 24 both distributions are indistinguishable from the uniform distribution against the $\mathsf{AC}^{0}$ post-processing, as long as $m^{k}\delta=n^{O(k)}\delta$ is negligible. Our choice of $\varepsilon$ satisfies this, as

n^{O(k)}\cdot(\varepsilon+2^{-n})^{1/2}=2^{\log^{O(1)}n-\log^{\omega(1)}n}=% \operatorname{negl}(n).\

$\hfill\blacktriangleleft$

Notice that for exact $2$ -designs, that is when $\varepsilon=0$ , we only need $k=o(n/\log n)$ , and thus Theorem 25 can be strengthened to work against $\mathsf{AC}\circ\mathsf{QNC}$ circuits of polynomial size, $\mathsf{QNC}$ depth up to $o(\log n)$ and $\mathsf{AC}$ depth up to $o(\log n/\log\log n)$ .

The situation becomes more complicated when ancillae are allowed. In this case, although $\mathcal{D}_{|\psi_{i}\rangle}$ and $\mathcal{D}_{|\psi_{\mathsf{Haar}}\rangle}$ are still almost $k$ -wise indistinguishable (that the marginal distribution on every $k$ bits are close in total variation distance), they are no longer $k$ -wise independent and are not guaranteed to fool $\mathsf{AC}^{0}$ circuits when $k$ is small [7]. This happens because we have no knowledge of the output distribution of the $\mathsf{QNC}^{0}$ circuit with ancillae even when the inputs are maximally mixed. The saving grace is that, when the number of ancillae is small, the output distribution has high entropy and we can modify Braverman’s proof in [14] to suit such distributions:

Lemma 26.

For every two $\delta$ -almost $k$ -wise indistinguishable distributions $\mathcal{D}_{1},\mathcal{D}_{2}$ on $m$ bits, such that $\mathcal{D}_{1}$ has min-entropy at least $m-r$ , any $\mathsf{AC}$ circuits with size $s$ and depth $d$ cannot distinguish the two distributions with advantage $\varepsilon+4m^{k}\delta$ , for certain $k=(\log s)^{O(d)}\cdot(r+\log(1/\varepsilon))$ .

Proof.

We first consider the case when $\delta=0$ . Suppose the $\mathsf{AC}^{0}$ circuit with size $s$ and depth $d$ computes a boolean function $F$ , Braverman showed that [14, Lemma 11] there exists a boolean function $F^{\prime}$ and polynomial $f^{\prime}$ of degree $k=(\log s)^{O(d)}\cdot\log(1/\varepsilon^{\prime})$ , such that:

$\blacksquare$

$\Pr_{\mathcal{D}_{2}^{\prime}}[F\neq F^{\prime}]<\varepsilon^{\prime}$ ,
$\blacksquare$

$\Pr_{\mathcal{U}}[F\neq F^{\prime}]<\varepsilon^{\prime}$ ,
$\blacksquare$

$F^{\prime}\geq f^{\prime}$ on $\{0,1\}^{m}$ and $\operatorname*{\mathbb{E}}_{{\mathcal{U}}}\left[F^{\prime}-f^{\prime}\right]<% \varepsilon^{\prime}$ .

Here $\mathcal{U}$ stands for the uniform distribution over $\{0,1\}^{m}$ . Since $\mathcal{D}_{1}$ has min-entropy at least $m-r$ , we have $\Pr_{\mathcal{D}_{1}}[F\neq F^{\prime}]<2^{r}\varepsilon$ and $\operatorname*{\mathbb{E}}_{{\mathcal{D}_{1}}}\left[F^{\prime}-f^{\prime}% \right]<2^{r}\varepsilon$ . As a result,

	$\displaystyle\operatorname*{\mathbb{E}}_{{\mathcal{D}_{2}}}\left[F\right]$	$\displaystyle>\operatorname{\mathbb{E}}_{{\mathcal{D}_{2}}}\left[F^{\prime}% \right]-\varepsilon^{\prime}\geq\operatorname{\mathbb{E}}_{{\mathcal{D}_{2}}}% \left[f^{\prime}\right]-\varepsilon^{\prime}$
		$\displaystyle=\operatorname{\mathbb{E}}_{{\mathcal{D}_{1}}}\left[f^{\prime}% \right]-\varepsilon^{\prime}>\operatorname{\mathbb{E}}_{{\mathcal{D}_{1}}}% \left[F^{\prime}\right]-(2^{r}+1)\varepsilon^{\prime}$
		$\displaystyle>\operatorname*{\mathbb{E}}_{{\mathcal{D}_{1}}}\left[F\right]-(2^% {r+1}+1)\varepsilon^{\prime}.$

The bound in the reverse direction also holds by considering $1-F$ . Taking $\varepsilon^{\prime}=\varepsilon/(2^{r+1}+1)$ gives us $\left\lvert\operatorname*{\mathbb{E}}_{{\mathcal{D}_{1}}}\left[F\right]-% \operatorname*{\mathbb{E}}_{{\mathcal{D}_{2}}}\left[F\right]\right\rvert<\varepsilon$ .

For $\delta>0$ , we can assume that $m^{k}\delta<1$ , as otherwise the lemma is trivial. By [7], there exists two $k$ -wise indistinguishable distributions $\mathcal{D}_{1}^{\prime},\mathcal{D}_{2}^{\prime}$ on $m$ bits such that $\left\lvert\mathcal{D}_{1}-\mathcal{D}_{1}^{\prime}\right\rvert_{1}\leq 2m^{k}\delta$ and $\left\lvert\mathcal{D}_{2}-\mathcal{D}_{2}^{\prime}\right\rvert_{1}\leq 2m^{k}\delta$ . Furthermore, the construction ensures that $\left\lVert\mathcal{D}_{1}^{\prime}\right\rVert_{\infty}\leq\left\lVert% \mathcal{D}_{1}\right\rVert_{\infty}+2m^{k}\delta\cdot 2^{-m}$ , and thus $\mathcal{D}_{1}^{\prime}$ still has min-entropy at least $m-O(r)$ . Applying the previous claim on $\mathcal{D}_{1}^{\prime},\mathcal{D}_{2}^{\prime}$ we have $\left\lvert\operatorname*{\mathbb{E}}_{{\mathcal{D}_{1}^{\prime}}}\left[F% \right]-\operatorname*{\mathbb{E}}_{{\mathcal{D}_{2}^{\prime}}}\left[F\right]% \right\rvert<\varepsilon$ , and thus $\left\lvert\operatorname*{\mathbb{E}}_{{\mathcal{D}_{1}}}\left[F\right]-% \operatorname*{\mathbb{E}}_{{\mathcal{D}_{2}}}\left[F\right]\right\rvert<% \varepsilon+4m^{k}\delta$ . $\hfill\blacktriangleleft$

Theorem 27.

Let $\{|\psi_{i}\rangle\}$ be an $\varepsilon$ -approximate $2$ -design on $n$ qubits for some $\varepsilon=2^{-\log^{\omega(1)}n}$ . Then $|\psi_{i}\rangle$ is a PRS against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits with $a=\operatorname{polylog}(n)$ ancillae.

Proof.

The forward lightcone of the ancillae touches at most $r=2^{d}a=\log^{O(1)}n$ output qubits. We called the these qubits corrupted, denoted as the subsystem $R$ . We define $\mathcal{R}$ as the distribution over $\{0,1\}^{r}$ following the measurement outcome on the corrupted qubits when the input states are maximally mixed.

Similar to the proof of Theorem 25, suppose the circuit has size $s$ and depth $d$ , and we fix some $k=(\log s)^{O(d)}\cdot(r+\log^{2}n)=\log^{O(1)}n$ according to Lemma 26. Denote the output distribution of the $\mathsf{QNC}^{0}$ circuit as $\mathcal{D}_{|\psi\rangle}$ with the input state $|\psi\rangle$ . Let $\delta>0$ satisfies $n^{O(k)}\cdot(\varepsilon+2^{-n})^{1/2}\cdot\delta^{-1}=\operatorname{negl}(n)$ . We claim that with probability $1-\operatorname{negl}(n)$ , both $\mathcal{D}_{|\psi_{i}\rangle}$ and $\mathcal{D}_{|\psi_{\mathsf{Haar}}\rangle}$ are $\delta$ -almost $k$ -wise indistinguishable from $\mathcal{U}\otimes\mathcal{R}$ , where $\mathcal{U}$ is the uniform distribution over the uncorrupted output bits.

Figure 1: An illustration of the proof of Theorem 27, with partial systems and unitary lightcones in an

\mathsf{QNC}^{0}

circuit.

To prove the claim, let $A$ be the ancilla qubits, and $\rho_{A}$ be the initial state of the ancillae. Let the unitary operator $U_{R}$ consist of all gates in the $\mathsf{QNC}^{0}$ circuit that belongs to the lightcone of the ancillae. Fixing any $k$ output qubits $K$ , we extending $K$ to $K\cup R$ so that it contains all the corrupted qubits, and denote $U_{B}$ as the unitary operator that consists of all gates in the backward lightcone of $K$ but outside $U_{R}$ . Notice that we can think of $U_{R}$ as being applied after $U_{B}$ . At the input, the backward lightcone of $K$ touches the set of non-ancillae qubits $B$ with $|B|=b$ , and we let $\rho_{B}$ be the state of $B$ when the input states are copies of $|\psi\rangle$ .

Now the output state on $K$ is a partial trace of

(\mathbb{I}_{A\cup B\setminus R}\otimes U_{R})(U_{B}\rho_{B}U_{B}^{\dagger}% \otimes\rho_{A})(\mathbb{I}_{A\cup B\setminus R}\otimes U_{R}^{\dagger}),

(3)

and it suffices to show that no matter if $|\phi\rangle$ is drawn from $\{|\psi_{i}\rangle\}$ or $|\psi_{\mathsf{Haar}}\rangle$ , with high probability the above state is close to the case when $\rho_{B}$ is maximally mixed. Indeed, by Corollary 18 and Corollary 19, in both former cases with probability $1-\operatorname{negl}(n)$ we have $\left\lVert\rho_{B}-2^{-(k-a)}\mathbb{I}_{B}\right\rVert_{1}\leq\delta$ . This means that the state in (3) if $\delta$ -close in trace distance to

(\mathbb{I}_{A\cup B\setminus R}\otimes U_{R})(2^{-b}\mathbb{I}_{B}\otimes\rho% _{A})(\mathbb{I}_{A\cup B\setminus R}\otimes U_{R}^{\dagger})=\ 2^{-(a+b-r)}% \mathbb{I}_{A\cup B\setminus R}\otimes 2^{-(r-a)}U_{R}(\mathbb{I}_{R\setminus A% }\otimes\rho_{A})U_{R}^{\dagger}.

Notice that $2^{-(r-a)}U_{R}(\mathbb{I}_{R\setminus A}\otimes\rho_{A})U_{R}^{\dagger}$ is exactly the output state on $R$ when the input states are maximally mixed, and therefore the measurement outcome has the distribution $\mathcal{R}$ . Meanwhile $2^{-(a+b-r)}\mathbb{I}_{A\cup B\setminus R}$ is maximally mixed and will be measured to the uniform distribution. Thus we conclude that the output distributions on the $k$ bits are $\delta$ -close to $\mathcal{U}\otimes\mathcal{R}$ , for both $\mathcal{D}_{|\psi_{i}\rangle}$ and $\mathcal{D}_{|\psi_{\mathsf{Haar}}\rangle}$ .

Now we use the fact that $\mathcal{U}\otimes\mathcal{R}$ , as a distribution over $\{0,1\}^{m}$ , has min-entropy at least $m-r$ . By Lemma 26, both $\mathcal{D}_{|\psi_{i}\rangle}$ and $\mathcal{D}_{|\psi_{\mathsf{Haar}}\rangle}$ are indistinguishable from $\mathcal{U}\otimes\mathcal{R}$ against the $\mathsf{AC}^{0}$ post-processing, as long as $m^{k}\delta=n^{O(k)}\delta$ is negligible. Similar to the proof of Theorem 25, this is satisfied by our choice of $\varepsilon$ . $\hfill\blacktriangleleft$ Similar to the case of Theorem 25, for exact $2$ -designs, Theorem 27 can be strengthened to work against $\mathsf{AC}\circ\mathsf{QNC}$ circuits of polynomial size, $\mathsf{QNC}$ depth up to $o(\log n)$ and $\mathsf{AC}$ depth up to $o(\log n/\log\log n)$ . On the other hand, for constant depth circuits the number of ancillae can be strengthened close to linear.

Corollary 28.

Let $\{|\psi_{i}\rangle\}$ be an exact $2$ -design on $n$ qubits. Then $|\psi_{i}\rangle$ is a PRS against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits with $a=n/\log^{\omega(1)}n$ ancillae.

Proof.

In the proof of Theorem 27, when $\varepsilon=0$ we can take $\delta=2^{-n/4}$ , and thus to have $m^{k}\delta=\operatorname{negl}(n)$ for any $m=\operatorname{poly}(n)$ we only need $k=o(n/\log n)$ . When $d=O(1)$ , this is satisfies by any $a=2^{-d}r=n/\log^{\omega(1)}n$ . $\hfill\blacktriangleleft$

3.3 Pseudoentanglement against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$

In contrast to prior works that constructed pseudoentanglement from quantum secure one-way functions, here we prove that unconditional pseudoentanglement is possible against shallow circuits, using random phased subspace states (see Definition 22). We will show that such states form good enough approximate $t$ -designs, even when the phases are picked using a $2t$ -wise independent function, and thus yield pseudorandomness by our previous results.

Corollary 29.

Let $\{|\psi_{S,f}\rangle\}$ be the ensemble of $d$ -dimensional random phased subspace states, instantiated with a $4$ -wise independent function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ . Then the following properties hold:

$\blacksquare$
The ensemble is indistinguishable from a Haar random ensemble against:
- –
  
  $\mathsf{QNC}^{0}$ circuits, when $d=\omega(\log n)$ ;
- –
  
  $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits with $\operatorname{polylog}(n)$ ancillae, when $d=\log^{\omega(1)}n$ ;
$\blacksquare$

The von Neumann entanglement entropy across any cut is at most $d$ .

Proof.

First notice that even when $f$ is $4$ -wise independent (or in general, $2t$ -wise independent) instead of truly random, the proof of the design property of $\{|\psi_{S,f}\rangle\}$ in Appendix A still holds. Specifically, in Equation 9:

\operatorname*{\mathbb{E}}_{{f}}\left[|\psi_{S,f}\rangle\langle\psi_{S,f}|^{% \otimes t}\right]=\frac{1}{2^{dt}}\sum_{\begin{subarray}{c}x_{1},\ldots,x_{t}% \in S\\ y_{1},\ldots,y_{t}\in S\end{subarray}}\operatorname*{\mathbb{E}}_{{f}}\left[(-% 1)^{f(x_{1})+\ldots+f(x_{t})+f(y_{1})+\ldots+f(y_{t})}\right]|x_{1}\cdots x_{t% }\rangle\langle y_{1}\cdots y_{t}|,

When $f$ is $2t$ -wise independent, the expectation of $(-1)^{f(x_{1})+\ldots+f(x_{t})+f(y_{1})+\ldots+f(y_{t})}$ is the same as if $f$ is truly random. As a result, $|x_{1}\cdots x_{t}\rangle\langle y_{1}\cdots y_{t}|$ still has non-zero coefficient out only when each element of $S$ appears even number of times in $(x_{1},\ldots,x_{t},y_{1},\ldots,y_{t})$ . The rest of the proof is exactly the same as in Appendix A. Specifically for $t=2$ , since $\{|\psi_{S,f}\rangle\}$ is an $O(2^{-d})$ -approximate $2$ -design, the indistinguishability from Haar random states follows from Theorem 20 and Theorem 27.

On the other hand, with $d$ the dimension of the subspace, note that the states are given by

\frac{1}{2^{d/2}}\sum_{x\in S}(-1)^{f(x)}|x\rangle.

(4)

For any cut of the qubits, Equation 4 gives a tensor product decomposition of the state with at most $2^{d}$ terms. Hence, by Lemma 16, the Schmidt rank of the state is at most $2^{d}$ and the corresponding von Neumann entanglement entropy is at most $d$ . $\hfill\blacktriangleleft$

Preparing phased subspace states.

Subspace states are known to be efficiently preparable with $\mathcal{O}(nd)$ gates [36]. The $4$ -wise independent function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ can be constructed from seeds of length $O(n)$ in $\operatorname{poly}(n)$ time (see e.g. [57, Section 3.5]). The phases are put into the state using an efficient controlled operation.

4 Parallel-query secure PRU against local $\mathsf{QNC}^{0}$

In previous sections we examined the pseudorandom properties of state designs against shallow quantum circuits. In this section we turn to unitary designs and show that they are also pseudorandom when queried in parallel, but against the more restricted class of circuits that are geometrically local. Specifically, we consider the distinguisher to be a circuit $C^{\prime}\cdot(U^{\otimes t}\otimes\mathbb{I})\cdot C$ , where $C,C^{\prime}$ are both 1-dimensional geometrically local $\mathsf{QNC}^{0}$ circuits, and $U$ is either a unitary 2-design or a Haar random unitary applied on $n$ consecutive qubits. The following folklore fact about geometrically local $\mathsf{QNC}^{0}$ circuits is crucial for us:

Lemma 30.

Let $C$ be an 1-dimensional local $\mathsf{QNC}$ circuit of depth $d$ on $n$ qubits. Then for every $k\in[n-1]$ , the Schmidt rank of the state $C|0^{n}\rangle$ between the first $k$ qubits and the remaining $(n-k)$ qubits is at most $4^{d}$ .

Proof.

We prove this by an induction over $d$ , and the base case when $d=0$ is trivial. Suppose that after the first $d$ layer of gates we have the Schmidt decomposition $\sum_{i=1}^{4^{d}}\alpha_{i}|v_{i}\rangle|w_{i}\rangle$ , where $|v_{i}\rangle$ is on $k$ qubits and $|w_{i}\rangle$ is on $(n-k)$ qubits. In layer $d+1$ , only the gate $U$ (if it exists) that acts on the $k$ -th and the $(k+1)$ -th qubits would affect the Schmidt rank. We can write $U$ with an arbitrary tensor product decomposition $U=\sum_{j=1}^{4}A_{j}\otimes B_{j}$ where $A_{j},B_{j}\in\mathbb{C}^{2\times 2}$ , so that the state after applying $U$ becomes

\sum_{i=1}^{4^{d}}\sum_{j=1}^{4}\alpha_{i}(A_{j}|v_{i}\rangle)\otimes(B_{j}|w_% {i}\rangle).

By Lemma 16 we know that the above state has Schmidt rank at most $4^{d+1}$ , and it is not affected by the remaining gates in the same layer. $\hfill\blacktriangleleft$ We will make use of a stronger statement that allows us to perform the Schmidt decomposition recursively on the $t$ blocks of $n$ qubits (a notion that we borrow from [22]):

Lemma 31 (Recursive Schmidt Decomposition).

Let $C$ be a 1-dimensional local $\mathsf{QNC}$ circuit of depth $d$ on $t n$ qubits. Then we can write the state $C|0^{tn}\rangle$ as

C|0^{tn}\rangle=\sum_{i_{1},\ldots,i_{t}=1}^{r}\alpha_{i_{1},\ldots,i_{t}}% \cdot|v_{1,i_{1}}\rangle\otimes|v_{2,i_{1},i_{2}}\rangle\otimes\cdots\otimes|v% _{t,i_{1},\ldots,i_{t}}\rangle

(5)

where the Schmidt rank $r\leq 4^{d}$ , and $|v_{\tau,i_{1},\ldots,i_{\tau}}\rangle$ is an $n$ -qubit state. For every $\tau\in[t]$ , $i_{1},\ldots,i_{\tau}\in[r]$ and $i_{\tau}^{\prime}\neq i_{\tau}$ , we have the orthogonality condition

\langle v_{\tau,i_{1},\ldots,i_{\tau-1},i_{\tau}}|v_{\tau,i_{1},\ldots,i_{\tau% -1},i_{\tau}^{\prime}}\rangle=0,

and the complex numbers $\alpha_{i_{1},\ldots,i_{t}}$ satisfy $\sum|\alpha_{i_{1},\ldots,i_{t}}|^{2}=1$ .

Proof.

Let $r$ be the maximum Schmidt rank between the first $\tau n$ and the remaining $(t-\tau)n$ qubits, for any $\tau\in[t]$ . By Lemma 30 we have $r\leq 4^{d}$ . The recursive application of the Schmidt decomposition starts with the cut between the first $n$ qubits and the remaining $(t-1)n$ qubits:

C|0^{tn}\rangle=\sum_{i_{1}=1}^{r}\alpha_{i_{1}}\cdot|v_{1,i_{1}}\rangle% \otimes|w_{1,i_{1}}\rangle.

The next step is to perform a Schmidt decomposition over each $|w_{1,i_{1}}\rangle$ , for which we need an upper bound on the Schmidt rank. We can also write $|w_{1,i_{1}}\rangle$ in the computational basis to get

C|0^{tn}\rangle=\sum_{i_{1}=1}^{r}\sum_{x\in\{0,1\}^{n}}\sum_{y\in\{0,1\}^{(t-% 2)n}}\alpha_{i_{1}}\beta_{i_{1},x,y}\cdot|v_{1,i_{1}}\rangle|x\rangle|y\rangle.

Since $\{|v_{1,i_{1}}\rangle\}$ can be expanded into an orthonormal basis on the first $n$ qubits, so can $\{|v_{1,i_{1}}\rangle|x\rangle\}$ on the first $2n$ qubits. As a result, the Schmidt rank of $C|0^{tn}\rangle$ between the first $2n$ and the remaining $(t-2)n$ qubits is exactly the rank of the $2^{n}r\times 2^{(t-2)n}$ matrix $M$ , where

M((i_{1},x),y)=\alpha_{i_{1}}\beta_{i_{1},x,y}.

On the other hand, whenever $\alpha_{i_{1}}\neq 0$ , the Schmidt rank of $|w_{1,i_{1}}\rangle$ on the same cut is the rank of the submatrix of $\alpha_{i_{1}}^{-1}M$ , with the row index $i_{1}$ fixed, and thus is at most $r$ . Therefore we get

C|0^{tn}\rangle=\sum_{i_{1},i_{2}=1}^{r}\alpha_{i_{1},i_{2}}\cdot|v_{1,i_{1}}% \rangle\otimes|v_{2,i_{1},i_{2}}\rangle\otimes|w_{2,i_{1},i_{2}}\rangle.

Continuing the process for every $\tau\in[t]$ results in a tree-like structure as in (5), and the sum of squares of the coefficients is guaranteed to be $1$ by the orthogonality of the states. $\hfill\blacktriangleleft$

We also need the following lemma in analogy to Lemma 17, but on cross (off-diagonal) terms conjugated with Haar random unitaries.

Lemma 32.

\operatorname*{\mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B}[U|v\rangle% \langle w|U^{\dagger}]\right\rVert_{2}^{2}\right]\leq 2^{k-n}.

Proof.

Without loss of generality, we can assume that $U|w\rangle=|0^{n}\rangle$ , and $U|v\rangle=|u\rangle$ is a uniformly random state orthogonal to $|0^{n}\rangle$ . In this case, we can write

	$\displaystyle\operatorname{Tr}_{B}[U\|v\rangle\langle w\|U^{\dagger}]$	$\displaystyle=\sum_{x\in\{0,1\}^{n-k}}(\mathbb{I}_{A}\otimes\|x\rangle\langle x% \|_{B})\|u\rangle\langle 0^{n}\|(\mathbb{I}_{A}\otimes\|x\rangle\langle x\|_{B})$
		$\displaystyle=(\mathbb{I}_{A}\otimes\|0^{n-k}\rangle\langle 0^{n-k}\|_{B})\|u% \rangle\langle 0^{n}\|.$

And thus,

	$\displaystyle\left\lVert\operatorname{Tr}_{B}[U\|v\rangle\langle w\|U^{\dagger}]% \right\rVert_{2}^{2}$	$\displaystyle=\operatorname{Tr}\left[(\mathbb{I}_{A}\otimes\|0^{n-k}\rangle% \langle 0^{n-k}\|_{B})\|u\rangle\langle 0^{n}\|0^{n}\rangle\langle u\|(\mathbb{I}_% {A}\otimes\|0^{n-k}\rangle\langle 0^{n-k}\|_{B})\right]$
		$\displaystyle=\operatorname{Tr}\left[(\mathbb{I}_{A}\otimes\|0^{n-k}\rangle% \langle 0^{n-k}\|_{B})\|u\rangle\langle u\|\right]$
		$\displaystyle=\sum_{x\in\{0,1\}^{k}}\left\lvert\langle x_{A}0^{n-k}_{B}\|u% \rangle\right\rvert^{2}.$

As a side note, this directly implies that

\left\lVert\operatorname{Tr}_{B}[U|v\rangle\langle w|U^{\dagger}]\right\rVert_% {2}\leq 1

(6)

regardless of the choice of $|v\rangle$ , $|w\rangle$ or $U$ , which will be useful later on.

Since $|u\rangle$ is a uniformly random state orthogonal to $|0^{n}\rangle$ , for every $x\in\{0,1\}^{n}\setminus\{0^{n}\}$ , $\langle x|u\rangle$ has the same distribution. Therefore every term in the summation above, except $\left\lvert\langle 0^{n}|u\rangle\right\rvert^{2}$ , has the same expectation which is $1/(2^{n}-1)$ . Therefore we conclude that

\operatorname*{\mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B}[U|v\rangle% \langle w|U^{\dagger}]\right\rVert_{2}^{2}\right]=\frac{2^{k}-1}{2^{n}-1}<2^{k% -n}.\

$\hfill\blacktriangleleft$

The above result allows us to show that the output of non-adaptive queries of a Haar random unitary has the property that every subsystem of $k$ qubits are almost maximally mixed, similar to Corollary 18, when the input state admits the recursive Schmidt decomposition.

Corollary 33.

Let $U$ be an $n$ -qubit Haar random unitary. For $t\geq 1$ , let $|\psi\rangle$ be a $t n$ -qubit state that admits the recursive Schmidt decomposition with rank $r$ as in Lemma 31. Let $\rho_{A}$ be the reduced density matrix of $U^{\otimes t}|\psi\rangle\langle\psi|U^{\dagger\otimes t}$ over a subsystem $A$ with $|A|=k$ qubits. Then for every $\delta>0$ , with probability at least $1-O(r)\cdot 2^{k-n/2}\cdot\delta^{-1}$ over $U$ , it holds that

\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{1}\leq\delta.

Proof.

To take the partial trace for subsystem $A$ , we assume that $A$ consists of $k_{1},\ldots,k_{t}$ qubits in each block of $n$ qubits respectively, and let $B_{\tau}$ be the part outside $A$ in the $\tau$ -th block. With the recursive Schmidt decomposition (5) we can write

U^{\otimes t}|\psi\rangle\langle\psi|U^{\dagger\otimes t}=\sum_{\begin{% subarray}{c}i_{1},\ldots,i_{t},\\ j_{1},\ldots,j_{t}=1\end{subarray}}^{r}\alpha_{i_{1},\ldots,i_{t}}\overline{% \alpha_{j_{1},\ldots,j_{t}}}\cdot U|v_{1,i_{1}}\rangle\langle v_{1,j_{1}}|U^{% \dagger}\otimes\cdots\otimes U|v_{t,i_{1},\ldots,i_{t}}\rangle\langle v_{t,j_{% 1},\ldots,j_{t}}|U^{\dagger}.

(7)

In addition, we can also write the decomposition (5) only to a certain level $\tau<t$ to get

|\psi\rangle=\sum_{i_{1},\ldots,i_{\tau}=1}^{r}\alpha_{i_{1},\ldots,i_{\tau}}% \cdot|v_{1,i_{1}}\rangle\otimes|v_{2,i_{1},i_{2}}\rangle\otimes\cdots\otimes|v% _{\tau,i_{1},\ldots,i_{\tau}}\rangle\otimes|w_{\tau,i_{1},\ldots,i_{\tau}}\rangle,

where $|w_{\tau,i_{1},\ldots,i_{\tau}}\rangle$ is a state on $(t-\tau)n$ qubits such that

\alpha_{i_{1},\ldots,i_{\tau}}|w_{\tau,i_{1},\ldots,i_{\tau}}\rangle=\sum_{i_{% \tau+1},\ldots,i_{t}=1}^{r}\alpha_{i_{1},\ldots,i_{t}}\cdot|v_{\tau+1,i_{1},% \ldots,i_{\tau+1}}\rangle\otimes\cdots\otimes|v_{t,i_{1},\ldots,i_{t}}\rangle.

Notice that it also implies

|\alpha_{i_{1},\ldots,i_{\tau}}|^{2}=\sum_{i_{\tau+1},\ldots,i_{t}=1}^{r}|% \alpha_{i_{1},\ldots,i_{t}}|^{2}.

This way, we can group the summands in (7) depending on the smallest coordinate $\tau$ such that $i_{\tau}\neq j_{\tau}$ (when $\tau=t+1$ , it means that $(i_{1},\ldots,i_{t})$ is identical to $(j_{1},\ldots,j_{t})$ ), and have

	$\displaystyle U^{\otimes t}$	$\displaystyle\|\psi\rangle\langle\psi\|U^{\dagger\otimes t}=\ \sum_{\tau=1}^{t+1% }\sum_{i_{1},\ldots,i_{\tau}=1}^{r}\sum_{j_{\tau}\neq i_{\tau}}\alpha_{i_{1},% \ldots,i_{\tau}}\overline{\alpha_{i_{1},\ldots,i_{\tau-1},j_{\tau}}}\cdot U\|v_% {1,i_{1}}\rangle\langle v_{1,i_{1}}\|U^{\dagger}\otimes\cdots$
		$\displaystyle\ \ldots\otimes U\|v_{\tau,i_{1},\ldots,i_{\tau}}\rangle\langle v_% {\tau,i_{1},\ldots,i_{\tau-1},j_{\tau}}\|U^{\dagger}\otimes U^{\otimes(t-\tau)}% \|w_{\tau,i_{1},\ldots,i_{\tau}}\rangle\langle w_{\tau,i_{1},\ldots,i_{\tau-1},% j_{\tau}}\|U^{\dagger\otimes(t-\tau)}.$		(8)

Now consider each summand in (8) with $\tau\leq t$ . By Lemma 32, we have

\operatorname*{\mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B_{\tau}}[U|v_{% \tau,i_{1},\ldots,i_{\tau}}\rangle\langle v_{\tau,i_{1},\ldots,i_{\tau-1},j_{% \tau}}|U^{\dagger}]\right\rVert_{2}^{2}\right]\leq 2^{k_{\tau}-n}.

Therefore, after taking the partial trace, with the bound (6) on the Frobenius norms of the other blocks, we can bound the expected Frobenius norm of the entire summand by $\left\lvert\alpha_{i_{1},\ldots,i_{\tau}}\overline{\alpha_{i_{1},\ldots,i_{% \tau-1},j_{\tau}}}\right\rvert\cdot 2^{(k_{\tau}-n)/2}$ . Thus by linearity of expectation and triangular inequality, these summands in total has expected Frobenius norm of at most

		$\displaystyle\ \sum_{\tau=1}^{t}\sum_{i_{1},\ldots,i_{\tau}=1}^{r}\sum_{j_{% \tau}\neq i_{\tau}}\left\lvert\alpha_{i_{1},\ldots,i_{\tau}}\overline{\alpha_{% i_{1},\ldots,i_{\tau-1},j_{\tau}}}\right\rvert\cdot 2^{(k_{\tau}-n)/2}$
	$\displaystyle=$	$\displaystyle\ \sum_{\tau=1}^{t}\sum_{i_{1},\ldots,i_{\tau-1}=1}^{r}\left(\sum% _{i_{\tau}=1}^{r}\left\lvert\alpha_{i_{1},\ldots,i_{\tau}}\right\rvert\right)^% {2}\cdot 2^{(k_{\tau}-n)/2}$
	$\displaystyle\leq$	$\displaystyle\ \sum_{\tau=1}^{t}\sum_{i_{1},\ldots,i_{\tau}=1}^{r}\left\lvert% \alpha_{i_{1},\ldots,i_{\tau}}\right\rvert^{2}\cdot r\cdot 2^{(k_{\tau}-n)/2}$
	$\displaystyle\leq$	$\displaystyle\ r\cdot 2^{(k-n)/2}.$

The remaining summands are those with $(i_{1},\ldots,i_{t})=(j_{1},\ldots,j_{t})$ , whose sum is exactly

\sum_{i_{1},\ldots,i_{t}=1}^{r}\left\lvert\alpha_{i_{1},\ldots,i_{t}}\right% \rvert^{2}\cdot U|v_{1,i_{1}}\rangle\langle v_{1,i_{1}}|U^{\dagger}\otimes% \cdots\otimes U|v_{t,i_{1},\ldots,i_{t}}\rangle\langle v_{t,i_{1},\ldots,i_{t}% }|U^{\dagger}.

By Lemma 17, similarly to the deduction in Corollary 18, we know that the partial trace in each block, denoted by $M_{\tau}=\operatorname{Tr}_{B_{\tau}}[U|v_{\tau,i_{1},\ldots,i_{\tau}}\rangle% \langle v_{\tau,i_{1},\ldots,i_{\tau}}|U^{\dagger}]$ ,satisfies that

\operatorname*{\mathbb{E}}\left[\left\lVert M_{\tau}-\frac{1}{2^{k_{\tau}}}% \mathbb{I}_{k_{\tau}}\right\rVert_{2}\right]\leq 2^{(k_{\tau}-n)/2}.

Thus by a hybrid argument, we have

	$\displaystyle\operatorname*{\mathbb{E}}\left[\left\lVert M_{1}\otimes\cdots% \otimes M_{t}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{2}\right]$	$\displaystyle\leq\sum_{\tau=1}^{t}\operatorname*{\mathbb{E}}\left[\left\lVert M% _{1}\otimes\cdots\otimes M_{\tau-1}\otimes\left(M_{\tau}-\frac{1}{2^{k_{\tau}}% }\mathbb{I}_{k_{\tau}}\right)\right\rVert_{2}\right]$
		$\displaystyle\leq\sum_{\tau=1}^{t}2^{(k_{\tau}-n)/2}\leq 2^{(k-n)/2}.$

Since $\sum\left\lvert\alpha_{i_{1},\ldots,i_{t}}\right\rvert^{2}=1$ , we conclude that

\operatorname*{\mathbb{E}}\left[\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_% {k}\right\rVert_{1}\right]\leq 2^{k/2}\cdot\operatorname*{\mathbb{E}}\left[% \left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{2}\right]\leq(r% +1)\cdot 2^{k-n/2}.

By Markov’s inequality, we know that $\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{1}\leq\delta$ holds with probability at least $1-(r+1)\cdot 2^{k-n/2}\cdot\delta^{-1}$ . $\hfill\blacktriangleleft$ Since the proof of Corollary 33 only uses the second moment properties of $U$ (Lemma 17 and Lemma 32 to be exact), using Lemma 14 we can also conclude the following for approximate unitary 2-designs.

Corollary 34.

Let $\{U_{i}\}$ be an $\varepsilon$ -approximate unitary $2$ -design on $n$ qubits. For $t\geq 1$ , let $|\psi\rangle$ be a $t n$ -qubit state that admits the recursive Schmidt decomposition with rank $r$ as in Lemma 31. Let $\rho_{A}$ be the reduced density matrix of $U_{i}^{\otimes t}|\psi\rangle\langle\psi|U_{i}^{\dagger\otimes t}$ over a subsystem $A$ with $|A|=k$ qubits. Then for every $\delta>0$ , with probability at least $1-2^{O(k)}\cdot r\cdot(\varepsilon+2^{-n})^{1/2}\cdot\delta^{-1}$ over $i$ , it holds that

\left\lVert\rho_{A}-\frac{1}{2^{k}}\mathbb{I}_{k}\right\rVert_{1}\leq\delta.

Combining the above corollaries together, we obtain the desired pseudorandomness against geometrically local $\mathsf{QNC}^{0}$ circuits.

Theorem 35.

Let $\{U_{i}\}$ be an $\varepsilon$ -approximate unitary $2$ -design on $n$ qubits for $\varepsilon=2^{-\Omega(n)}$ . Then $\{U_{i}\}$ is non-adaptive secure PRU against $1$ -dimensional geometrically local $\mathsf{QNC}$ circuits of depth $d=\log n-\omega(1)$ . Moreover, the pre-processing part of the $\mathsf{QNC}$ circuit (before applying $U_{i}$ ) could have depth up to $o(n)$ .

Proof.

The proof follows from that of Theorem 20. Since the output of the $\mathsf{QNC}$ circuit depends on only $k=2^{d}=o(n)$ of the output qubits of $U^{\otimes t}$ , by Corollaries 33 and 34 we know that the outputs have $\operatorname{negl}(n)$ trace distance between the Haar random $U$ and unitary design $\{U_{i}\}$ , with probability $1-\operatorname{negl}(n)$ over the choice of the unitaries. This is because

2^{O(k)}\cdot r\cdot(\varepsilon+2^{-n})^{1/2}\leq\operatorname{negl}(n)

when $k=o(n)$ and $\varepsilon=2^{-\Omega(n)}$ , and $r\leq 2^{d}$ from Lemma 31. In addition, the circuit depth $d$ used to bound the Schmidt rank $r$ only concerns the depth of the pre-processing part of the circuit, which can be raised up to $o(n)$ . $\hfill\blacktriangleleft$

Although Corollary 33 and Corollary 34 have virtually the same form as Corollary 18 and Corollary 19, we cannot use the techniques in Section 3.2 to directly obtain the similar security of PRU against $\mathsf{QNC}^{0}$ circuits with $\mathsf{AC}^{0}$ post-processing. The reason is that in Section 3.2 we have to limit the number of ancillae, and here they correspond to the qubits that $U$ is not applied to, which we cannot put any natural restrictions on. However, in the artificial scenario where we force the the unitary to be applied in parallel on all qubits (and therefore allow no ancillae for the post-processing $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuit), we can obtain the following statement in analogy to Theorem 25:

Theorem 36.

Let $\{U_{i}\}$ be an $\varepsilon$ -approximate unitary $2$ -design on $n$ qubits for $\varepsilon=2^{-\log^{\omega(1)}n}$ . Then $\{U_{i}\}$ is PRU against a subclass of $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ circuits on a multiple of $n$ qubits, where $U_{i}$ is applied non-adaptively over all the qubits used by the circuit, and the pre-processing $\mathsf{QNC}^{0}$ circuit before applying $U_{i}$ is $1$ -dimensional geometrically local.

5 Discussion and outlook

Our work initiates the study of unconditionally fooling shallow quantum circuits. In general, statistical and computational notions of quantum pseudorandomness – such as $t$ -designs and PRS – are incomparable. Our work shows that in the low-complexity regime, the two notions can in fact overlap and illustrate rich connections to computational complexity theory, reminiscent of the intimate relation between hardness and randomness in classical computation. Our work leaves a number of interesting questions regarding the connections between hardness and quantum pseudorandomness. We discuss a few of these below.

Fooling stronger circuits

What are the strongest class of quantum circuits that $t$ -designs, or in particular $2$ -designs, can fool? We conjecture that $2$ -designs are computationally secure against $\mathsf{QAC}^{0}$ circuits as well. To prove this, it suffices to show a $\mathsf{QAC}$ analogy of Braverman’s result on almost $k$ -wise maximally mixed input states. These states have the property that every subsystem on $k$ qubits is close to being maximally mixed, and we conjecture that they cannot be distinguished from the true maximally mixed state by $\mathsf{QAC}$ circuits of small depths.

A more immediate improvement on our results would be the removal of the constraints on ancillae in Theorem 27 and Corollary 28. The reason we require a bounded number of ancillae is purely technical: we need this to argue that the output distribution has high min-entropy, as otherwise the $k$ -wise indistinguishability would not guarantee that we can fool $\mathsf{AC}^{0}$ circuits. We note that a similar techinical issue occured in the $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ lower bound lower bound result of [55].

Stronger security for PRU

The unconditional security we proved for PRU is quite limited. Specifically, in Theorem 35 we could only show security when the unitaries are queried non-adaptively, while the adversaries are 1-dimensional geometrically local $\mathsf{QNC}$ circuits. Can we lift the requirement of non-adaptivity or geometric locality?

We conjecture that new constructions are necessary in order to achieve security against adaptive queries. In other words, there exist (approximate) $t$ -designs that are not PRU against $\mathsf{QNC}^{0}$ circuits with adaptive queries. Such an example that works for arbitrary $t\leq\operatorname{poly}(n)$ would also give a separation between non-adaptive and adaptive PRU.

Optimal pseudoentanglement

It is known that the optimal entanglement entropy gap for pseudoentanglement is $\omega(\log n)$ versus $O(n)$ , which is achievable across every cut when assuming the existence of post-quantum one way functions [1]. In Corollary 29 we showed explicit examples of unconditional pseudoentanglement, which is optimal across every cut against $\mathsf{QNC}^{0}$ distinguishers, but only $\log^{\omega(1)}n$ versus $O(n)$ against an $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ adversary. Can we also construct unconditional optimal pseudoentanglement against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$ , or even stronger circuits?

PRG against shallow circuits

In this work we did not consider classical pseudorandom primitives, such as PRGs. One of the reasons is that we need to be careful about the definition when the adversaries are shallow quantum circuits, since it makes a difference whether or not we allow access to multiple copies of the PRG output. In fact, if the adversary could only access a single copy, then the classical Nisan-Wigderson generator [49, 50] instantiated by the parity function would directly give an unconditional PRG with $\operatorname{polylog}(n)$ seed length against $\mathsf{QAC}^{0}$ circuits with bounded number of ancillae, using recent results on the hardness of parity against $\mathsf{QAC}^{0}$ [45, 5]. However, the hardness proofs in these works, which examine the Pauli spectrum of the $\mathsf{QAC}^{0}$ circuit, break down when allowing multi-copy access to the input, as even a single classical fan-out gate could significantly increase the Pauli weight of the overall circuit.

As a result, designing unconditional multi-copy secure PRG against $\mathsf{QAC}^{0}$ circuits remains to be an intriguing open problem. A follow-up direction is to use such PRG to construct other pseudorandom primitives such as pseudorandom functions or even PRS and PRU. Notice that we have recipes for these constructions against polynomial-sized adversaries, but in order to work against bounded adversaries, the construction needs to be super-efficient and such constructions are largely unknown.

Fooling other models

Finally, an open-ended question is to find unconditional pseudorandom objects against other restricted models of quantum computation, with or without our constructions and techniques. It was shown in [23] that the INW generator [33] is secure against space-bounded quantum computation. To study PRS or PRU against such models, the first challenge lies in finding the most relevant and useful definition, which we leave for future work.

References

[1] Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Quantum Pseudoentanglement. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:21, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2024.2.
[2] Chris Akers, Adam Bouland, Lijie Chen, Tamara Kohler, Tony Metger, and Umesh Vazirani. Holographic pseudoentanglement and the complexity of the ads/cft dictionary, 2024. arXiv:2411.04978.
[3] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. Pseudorandom (function-like) quantum state generators: New definitions and applications, 2023. doi:10.48550/arXiv.2211.01444.
[4] Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states, 2022. arXiv:2112.10020.
[5] Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao. On the computational power of qac0 with barely superlinear ancillae, 2024. arXiv:2410.06499.
[6] Srinivasan Arunachalam and Arkopal Dutt. Polynomial-time tolerant testing stabilizer states. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 1234–1241. ACM, June 2025. doi:10.1145/3717823.3718277.
[7] Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded indistinguishability and the complexity of recovering secrets. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, volume 9816 of Lecture Notes in Computer Science, pages 593–618. Springer, 2016. doi:10.1007/978-3-662-53015-3_21.
[8] Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464–2486, 2010. doi:10.1137/070712109.
[9] John Bostanci, Boyang Chen, and Barak Nehoran. Oracle separation between quantum commitments and quantum one-wayness. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, volume 15607 of Lecture Notes in Computer Science, pages 3–22. Springer, 2025. doi:10.1007/978-3-031-91098-2_1.
[10] Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Public-key pseudoentanglement and the hardness of learning ground state entanglement structure, 2023. doi:10.48550/arXiv.2311.12017.
[11] Adam Bouland, Chenyi Zhang, and Zixin Zhou. On the hardness of learning ground state entanglement of geometrically local hamiltonians, 2024. doi:10.48550/arXiv.2411.04353.
[12] Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics, 346(2):397–434, August 2016. doi:10.1007/s00220-016-2706-8.
[13] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki. Efficient quantum pseudorandomness. Physical Review Letters, 116(17), April 2016. doi:10.1103/physrevlett.116.170502.
[14] Mark Braverman. Polylogarithmic independence fools $\mathsf{AC}^{0}$ circuits. J. ACM, 57(5), 2008. doi:10.1145/1754399.1754401.
[15] Shantanav Chakraborty, Soonwon Choi, Soumik Ghosh, and Tudor Giurgică-Tiron. Fast computational deep thermalization, 2025. doi:10.48550/arXiv.2507.13670.
[16] Laura Cui, Thomas Schuster, Fernando Brandao, and Hsin-Yuan Huang. Unitary designs in nearly optimal depth, 2025. doi:10.48550/arXiv.2507.06216.
[17] Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brandão. Random quantum circuits anticoncentrate in log depth. PRX Quantum, 3(1):010333, 2022.
[18] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A, 80(1), July 2009. doi:10.1103/physreva.80.012304.
[19] Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2010, volume 6302 of Lecture Notes in Computer Science, pages 504–517. Springer, 2010. doi:10.1007/978-3-642-15369-3_38.
[20] Xiaozhou Feng and Matteo Ippoliti. Dynamics of pseudoentanglement, 2024. arXiv:2403.09619.
[21] Xiaozhou Feng and Matteo Ippoliti. Dynamics of pseudoentanglement. Journal of High Energy Physics, 2025(2), February 2025. doi:10.1007/jhep02(2025)128.
[22] Sevag Gharibian and Julia Kempe. Approximation algorithms for QMA-complete problems. SIAM J. Comput., 41(4):1028–1050, 2012. doi:10.1137/110842272.
[23] Uma Girish and Ran Raz. Eliminating intermediate measurements using pseudorandom generators. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPIcs, pages 76:1–76:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ITCS.2022.76.
[24] Tudor Giurgica-Tiron and Adam Bouland. Pseudorandomness from subset states, 2023. doi:10.48550/arXiv.2312.09206.
[25] Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 120–129. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.77.
[26] Manuel Goulão and David Elkouss. Pseudo-entanglement is necessary for efi pairs, 2024. doi:10.48550/arXiv.2406.06881.
[27] David Gross, Sepehr Nezami, and Michael Walter. Schur–weyl duality for the clifford group with applications: Property testing, a robust hudson theorem, and de finetti representations. Communications in Mathematical Physics, 385(3):1325–1393, June 2021. doi:10.1007/s00220-021-04118-7.
[28] Andi Gu, Lorenzo Leone, Soumik Ghosh, Jens Eisert, Susanne F. Yelin, and Yihui Quek. Pseudomagic quantum states. Physical Review Letters, 132(21), May 2024. doi:10.1103/physrevlett.132.210602.
[29] Prahladh Harsha and Srikanth Srinivasan. On polynomial approximations to $\mathsf{AC}^{0}$ . Random Struct. Algorithms, 54(2):289–303, 2019. doi:10.1002/RSA.20786.
[30] Pooya Hatami and William Hoza. Paradigms for unconditional pseudorandom generators. Found. Trends Theor. Comput. Sci., 16(1-2):1–210, 2024. doi:10.1561/0400000109.
[31] Alexander Healy, Salil P. Vadhan, and Emanuele Viola. Using nondeterminism to amplify hardness. SIAM J. Comput., 35(4):903–931, 2006. doi:10.1137/S0097539705447281.
[32] William M. Hoza. Better pseudodistributions and derandomization for space-bounded computation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, volume 207 of LIPIcs, pages 28:1–28:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.28.
[33] Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 356–364. ACM, 1994. doi:10.1145/195058.195190.
[34] Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu. Pseudorandom and pseudoentangled states from subset states, 2024. arXiv:2312.15285.
[35] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom Quantum States, pages 126–152. Springer International Publishing, 2018. doi:10.1007/978-3-319-96878-0_5.
[36] Iordanis Kerenidis and Anupam Prakash. Quantum machine learning with subspace states, 2022. arXiv:2202.00054.
[37] William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.TQC.2021.2.
[38] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1589–1602. ACM, 2023. doi:10.1145/3564246.3585225.
[39] William Kretschmer, Luowen Qian, and Avishay Tal. Quantum-computable one-way functions without one-way functions. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, pages 189–200. ACM, 2025. doi:10.1145/3717823.3718144.
[40] Zi-Wen Liu, Seth Lloyd, Elton Zhu, and Huangjun Zhu. Entanglement, quantum randomness, and complexity beyond scrambling. Journal of High Energy Physics, 2018(7):1–62, 2018.
[41] Elihu Lubkin. Entropy of an $n$ -system from its correlation with a $k$ -reservoir. Journal of Mathematical Physics, 19(5):1028–1031, 1978.
[42] Michael George Luby. Pseudorandomness and Cryptographic Applications. Princeton University Press, USA, 1994.
[43] Antonio Anna Mele. Introduction to haar measure tools in quantum information: A beginner’s tutorial. Quantum, 8:1340, 2024. doi:10.22331/Q-2024-05-08-1340.
[44] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Pseudorandom unitaries with non-adaptive security, 2024. doi:10.48550/arXiv.2402.14803.
[45] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. On the Pauli spectrum of QAC0. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1498–1506, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649662.
[46] Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. doi:10.1137/0222053.
[47] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010.
[48] Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, March 1991. doi:10.1007/bf01375474.
[49] Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. doi:10.1007/BF01305237.
[50] Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149–167, 1994. doi:10.1016/S0022-0000(05)80043-1.
[51] Noam Nisan and David Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci., 52(1):43–52, 1996. doi:10.1006/JCSS.1996.0004.
[52] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography, 2024. doi:10.48550/arXiv.2401.03703.
[53] Michael E. Saks and Shiyu Zhou. $\mathsf{BP_{H}SPACE}(s)\subseteq\mathsf{DSPACE}(s^{3/2})$ . J. Comput. Syst. Sci., 58(2):376–403, 1999. doi:10.1006/JCSS.1998.1616.
[54] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth. Science, 389(6755):92–96, July 2025. doi:10.1126/science.adv8590.
[55] Joseph Slote. Parity vs. AC0 with simple quantum preprocessing. In 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, volume 287 of LIPIcs, pages 92:1–92:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ITCS.2024.92.
[56] Avishay Tal. Tight bounds on the fourier spectrum of $\mathsf{AC}^{0}$ . In 32nd Computational Complexity Conference, CCC 2017, volume 79 of LIPIcs, pages 15:1–15:31. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.15.
[57] Salil P Vadhan. Pseudorandomness. Foundations and Trends^® in Theoretical Computer Science, 7(1–3):1–336, 2012. doi:10.1561/0400000010.
[58] Emanuele Viola. The sum of $d$ small-bias generators fools polynomials of degree $d$ . Comput. Complex., 18(2):209–217, 2009. doi:10.1007/S00037-009-0273-5.
[59] Lisa Yang and Netta Engelhardt. The complexity of learning (pseudo)random dynamics of black holes and other chaotic systems, 2023. arXiv:2302.11013.
[60] Mark Zhandry. How to construct quantum random functions. J. ACM, 68(5), August 2021. doi:10.1145/3450745.

Appendix A Design properties of random phased subspace states

Here we show that the random phased subspace states $|\psi_{S,f}\rangle$ , defined in Definition 22, form an approximate design. Fixing the subspace $S$ and taking the average over the random function $f:S\rightarrow\{0,1\}$ , we have

\operatorname*{\mathbb{E}}_{{f}}\left[|\psi_{S,f}\rangle\langle\psi_{S,f}|^{% \otimes t}\right]=\frac{1}{2^{dt}}\sum_{\begin{subarray}{c}x_{1},\ldots,x_{t}% \in S\\ y_{1},\ldots,y_{t}\in S\end{subarray}}\operatorname*{\mathbb{E}}_{{f}}\left[(-% 1)^{f(x_{1})+\ldots+f(x_{t})+f(y_{1})+\ldots+f(y_{t})}\right]|x_{1}\cdots x_{t% }\rangle\langle y_{1}\cdots y_{t}|,

(9)

where the term $|x_{1}\cdots x_{t}\rangle\langle y_{1}\cdots y_{t}|$ has non-zero coefficient only when each element of $S$ appears an even number of times in $(x_{1},\ldots,x_{t},y_{1},\ldots,y_{t})$ . Among those let us consider the ones such that $x_{1},\ldots,x_{t}$ are all distinct (so that $y_{1},\ldots,y_{t}$ is a permutation of $x_{1},\ldots,x_{t}$ ); the partial summation over these terms is

		$\displaystyle\ \frac{1}{2^{dt}}\sum_{\begin{subarray}{c}x_{1},\ldots,x_{t}\in S% \\ x_{i}\neq x_{j},\forall i<j\\ \pi\in\mathcal{S}_{t}\end{subarray}}\|x_{1}\cdots x_{t}\rangle\langle x_{\pi(1)% }\cdots x_{\pi(t)}\|$
	$\displaystyle=$	$\displaystyle\ \frac{1}{2^{dt}}\sum_{\{x_{1},\ldots,x_{t}\}\subset S}\left(% \sum_{\pi\in\mathcal{S}_{t}}\|x_{\pi(1)}\cdots x_{\pi(t)}\rangle\right)\left(% \sum_{\pi\in\mathcal{S}_{t}}\langle x_{\pi(1)}\cdots x_{\pi(t)}\|\right)$
	$\displaystyle=$	$\displaystyle\ \frac{t!}{2^{dt}}\sum_{X\subset S,\|X\|=t}\|\mathsf{Sym_{X}}% \rangle\langle\mathsf{Sym}_{X}\|.$

Here $\mathcal{S}_{t}$ is the symmetric group on $[t]$ , and $|\mathsf{Sym_{X}}\rangle=\frac{1}{\sqrt{t!}}\sum_{\pi\in\mathcal{S}_{t}}|x_{% \pi(1)}\cdots x_{\pi(t)}\rangle$ for $X=\{x_{1},\ldots,x_{t}\}$ . As a result, the above partial sum has trace

\frac{t!}{2^{dt}}\cdot\binom{2^{d}}{t}=\frac{2^{d}\cdot(2^{d}-1)\cdot\cdots% \cdot(2^{d}-t+1)}{2^{dt}}\geq 1-\frac{t^{2}}{2^{d}}.

Also notice that the partial sum can be thought as the projection of $\operatorname*{\mathbb{E}}_{{f}}\left[|\psi_{S,f}\rangle\langle\psi_{S,f}|^{% \otimes t}\right]$ onto the subspace spanned by $\{|\mathsf{Sym}_{X}\rangle\}_{X\subset S,|X|=t}$ , implying that the remaining part is still positive-definite. This allows us to bound the trace distance:

		$\displaystyle\ \left\lVert\operatorname*{\mathbb{E}}_{{f}}\left[\|\psi_{S,f}% \rangle\langle\psi_{S,f}\|^{\otimes t}\right]-\binom{2^{d}}{t}^{-1}\sum_{X% \subset S,\|X\|=t}\|\mathsf{Sym_{X}}\rangle\langle\mathsf{Sym}_{X}\|\right\rVert_{1}$
	$\displaystyle\leq$	$\displaystyle\ \left\lVert\operatorname*{\mathbb{E}}_{{f}}\left[\|\psi_{S,f}% \rangle\langle\psi_{S,f}\|^{\otimes t}\right]-\frac{t!}{2^{dt}}\sum_{X\subset S% ,\|X\|=t}\|\mathsf{Sym_{X}}\rangle\langle\mathsf{Sym}_{X}\|\right\rVert_{1}+\left% \lvert\frac{t!}{2^{dt}}\cdot\binom{2^{d}}{t}-1\right\rvert\leq\frac{2t^{2}}{2^% {d}}.$

Now we think of $S$ as a uniformly random $d$ -dimensional subspace of $\{0,1\}^{n}$ . For a uniformly random $X\subset S$ with $|X|=t$ , the elements in $X$ are linearly dependent with probability at most

\frac{1}{2^{d}}+\frac{1}{2^{d-1}}+\cdots+\frac{1}{2^{d-t+1}}<\frac{1}{2^{d-t}}.

Similarly, when $X$ is a uniformly random size- $t$ subset of $\{0,1\}^{n}$ , the elements in $X$ are linearly dependent with probability at most $2^{t-n}$ . When conditioned on linear independence, the distributions of $X$ in both cases are the same, and thus
$\left\lVert\operatorname*{\mathbb{E}}_{{S}}\left[\binom{2^{d}}{t}^{-1}\sum_{X% \subset S,|X|=t}|\mathsf{Sym_{X}}\rangle\langle\mathsf{Sym}_{X}|\right]-\binom% {2^{n}}{t}^{-1}\sum_{X\subset\{0,1\}^{n},|X|=t}|\mathsf{Sym_{X}}\rangle\langle% \mathsf{Sym}_{X}|\right\rVert_{1}\leq 2^{t-d}+2^{t-n}.$

Hence we conclude that
$\left\lVert\operatorname*{\mathbb{E}}_{{S,f}}\left[|\psi_{S,f}\rangle\langle% \psi_{S,f}|^{\otimes t}\right]-\binom{2^{n}}{t}^{-1}\sum_{X\subset\{0,1\}^{n},% |X|=t}|\mathsf{Sym_{X}}\rangle\langle\mathsf{Sym}_{X}|\right\rVert_{1}\leq% \frac{2t^{2}}{2^{d}}+2^{t-d}+2^{t-n}=O(2^{t-d}).$

On the other hand, for the Haar random state $|\psi_{\mathsf{Haar}}\rangle$ , it is well known that (see e.g. [43])

\operatorname*{\mathbb{E}}\left[|\psi_{\mathsf{Haar}}\rangle\langle\psi_{% \mathsf{Haar}}|^{\otimes t}\right]=\binom{2^{n}+t-1}{t}^{-1}\Pi_{\mathsf{sym}}% ^{(t,2^{n})},

where $\Pi_{\mathsf{sym}}^{(t,2^{n})}$ is the projection onto the symmetric subspace of $(\mathbb{C}^{2^{n}})^{\otimes t}$ . Since all the $|\mathsf{Sym}_{X}\rangle$ take up $\binom{2^{n}}{t}$ dimensions in the subspace, their weight in $\Pi_{\mathsf{sym}}^{(t,2^{n})}$ is at least

\binom{2^{n}}{t}\Big/\binom{2^{n}+t-1}{t}=\frac{2^{n}\cdot(2^{n}-1)\cdot\cdots% \cdot(2^{n}-t+1)}{2^{n}\cdot(2^{n}+1)\cdot\cdots\cdot(2^{n}+t-1)}\geq 1-\frac{% t^{2}}{2^{n}}.

This means that

\left\lVert\operatorname*{\mathbb{E}}\left[|\psi_{\mathsf{Haar}}\rangle\langle% \psi_{\mathsf{Haar}}|^{\otimes t}\right]-\binom{2^{n}}{t}^{-1}\sum_{X\subset\{% 0,1\}^{n},|X|=t}|\mathsf{Sym_{X}}\rangle\langle\mathsf{Sym}_{X}|\right\rVert_{% 1}\leq\frac{2t^{2}}{2^{n}},

and we can finally obtain that

\left\lVert\operatorname*{\mathbb{E}}_{{S,f}}\left[|\psi_{S,f}\rangle\langle% \psi_{S,f}|^{\otimes t}\right]-\operatorname*{\mathbb{E}}\left[|\psi_{\mathsf{% Haar}}\rangle\langle\psi_{\mathsf{Haar}}|^{\otimes t}\right]\right\rVert_{1}% \leq\frac{2t^{2}}{2^{n}}+O(2^{t-d})\leq O(2^{t-d}).

[bib.bib1] [1] Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Quantum Pseudoentanglement. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:21, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2024.2.

[bib.bib2] [2] Chris Akers, Adam Bouland, Lijie Chen, Tamara Kohler, Tony Metger, and Umesh Vazirani. Holographic pseudoentanglement and the complexity of the ads/cft dictionary, 2024. arXiv:2411.04978.

[bib.bib3] [3] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. Pseudorandom (function-like) quantum state generators: New definitions and applications, 2023. doi:10.48550/arXiv.2211.01444.

[bib.bib4] [4] Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states, 2022. arXiv:2112.10020.

[bib.bib5] [5] Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao. On the computational power of qac0 with barely superlinear ancillae, 2024. arXiv:2410.06499.

[bib.bib6] [6] Srinivasan Arunachalam and Arkopal Dutt. Polynomial-time tolerant testing stabilizer states. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 1234–1241. ACM, June 2025. doi:10.1145/3717823.3718277.

[bib.bib7] [7] Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded indistinguishability and the complexity of recovering secrets. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, volume 9816 of Lecture Notes in Computer Science, pages 593–618. Springer, 2016. doi:10.1007/978-3-662-53015-3_21.

[bib.bib8] [8] Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464–2486, 2010. doi:10.1137/070712109.

[bib.bib9] [9] John Bostanci, Boyang Chen, and Barak Nehoran. Oracle separation between quantum commitments and quantum one-wayness. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, volume 15607 of Lecture Notes in Computer Science, pages 3–22. Springer, 2025. doi:10.1007/978-3-031-91098-2_1.

[bib.bib10] [10] Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Public-key pseudoentanglement and the hardness of learning ground state entanglement structure, 2023. doi:10.48550/arXiv.2311.12017.

[bib.bib11] [11] Adam Bouland, Chenyi Zhang, and Zixin Zhou. On the hardness of learning ground state entanglement of geometrically local hamiltonians, 2024. doi:10.48550/arXiv.2411.04353.

[bib.bib12] [12] Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics, 346(2):397–434, August 2016. doi:10.1007/s00220-016-2706-8.

[bib.bib13] [13] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki. Efficient quantum pseudorandomness. Physical Review Letters, 116(17), April 2016. doi:10.1103/physrevlett.116.170502.

[bib.bib14] [14] Mark Braverman. Polylogarithmic independence fools $\mathsf{AC}^{0}$ circuits. J. ACM, 57(5), 2008. doi:10.1145/1754399.1754401.

[bib.bib15] [15] Shantanav Chakraborty, Soonwon Choi, Soumik Ghosh, and Tudor Giurgică-Tiron. Fast computational deep thermalization, 2025. doi:10.48550/arXiv.2507.13670.

[bib.bib16] [16] Laura Cui, Thomas Schuster, Fernando Brandao, and Hsin-Yuan Huang. Unitary designs in nearly optimal depth, 2025. doi:10.48550/arXiv.2507.06216.

[bib.bib17] [17] Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brandão. Random quantum circuits anticoncentrate in log depth. PRX Quantum, 3(1):010333, 2022.

[bib.bib18] [18] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A, 80(1), July 2009. doi:10.1103/physreva.80.012304.

[bib.bib19] [19] Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2010, volume 6302 of Lecture Notes in Computer Science, pages 504–517. Springer, 2010. doi:10.1007/978-3-642-15369-3_38.

[bib.bib20] [20] Xiaozhou Feng and Matteo Ippoliti. Dynamics of pseudoentanglement, 2024. arXiv:2403.09619.

[bib.bib21] [21] Xiaozhou Feng and Matteo Ippoliti. Dynamics of pseudoentanglement. Journal of High Energy Physics, 2025(2), February 2025. doi:10.1007/jhep02(2025)128.

[bib.bib22] [22] Sevag Gharibian and Julia Kempe. Approximation algorithms for QMA-complete problems. SIAM J. Comput., 41(4):1028–1050, 2012. doi:10.1137/110842272.

[bib.bib23] [23] Uma Girish and Ran Raz. Eliminating intermediate measurements using pseudorandom generators. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, volume 215 of LIPIcs, pages 76:1–76:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ITCS.2022.76.

[bib.bib24] [24] Tudor Giurgica-Tiron and Adam Bouland. Pseudorandomness from subset states, 2023. doi:10.48550/arXiv.2312.09206.

[bib.bib25] [25] Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 120–129. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.77.

[bib.bib26] [26] Manuel Goulão and David Elkouss. Pseudo-entanglement is necessary for efi pairs, 2024. doi:10.48550/arXiv.2406.06881.

[bib.bib27] [27] David Gross, Sepehr Nezami, and Michael Walter. Schur–weyl duality for the clifford group with applications: Property testing, a robust hudson theorem, and de finetti representations. Communications in Mathematical Physics, 385(3):1325–1393, June 2021. doi:10.1007/s00220-021-04118-7.

[bib.bib28] [28] Andi Gu, Lorenzo Leone, Soumik Ghosh, Jens Eisert, Susanne F. Yelin, and Yihui Quek. Pseudomagic quantum states. Physical Review Letters, 132(21), May 2024. doi:10.1103/physrevlett.132.210602.

[bib.bib29] [29] Prahladh Harsha and Srikanth Srinivasan. On polynomial approximations to $\mathsf{AC}^{0}$ . Random Struct. Algorithms, 54(2):289–303, 2019. doi:10.1002/RSA.20786.

[bib.bib30] [30] Pooya Hatami and William Hoza. Paradigms for unconditional pseudorandom generators. Found. Trends Theor. Comput. Sci., 16(1-2):1–210, 2024. doi:10.1561/0400000109.

[bib.bib31] [31] Alexander Healy, Salil P. Vadhan, and Emanuele Viola. Using nondeterminism to amplify hardness. SIAM J. Comput., 35(4):903–931, 2006. doi:10.1137/S0097539705447281.

[bib.bib32] [32] William M. Hoza. Better pseudodistributions and derandomization for space-bounded computation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, volume 207 of LIPIcs, pages 28:1–28:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.28.

[bib.bib33] [33] Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 356–364. ACM, 1994. doi:10.1145/195058.195190.

[bib.bib34] [34] Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu. Pseudorandom and pseudoentangled states from subset states, 2024. arXiv:2312.15285.

[bib.bib35] [35] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom Quantum States, pages 126–152. Springer International Publishing, 2018. doi:10.1007/978-3-319-96878-0_5.

[bib.bib36] [36] Iordanis Kerenidis and Anupam Prakash. Quantum machine learning with subspace states, 2022. arXiv:2202.00054.

[bib.bib37] [37] William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.TQC.2021.2.

[bib.bib38] [38] William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum cryptography in algorithmica. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1589–1602. ACM, 2023. doi:10.1145/3564246.3585225.

[bib.bib39] [39] William Kretschmer, Luowen Qian, and Avishay Tal. Quantum-computable one-way functions without one-way functions. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, pages 189–200. ACM, 2025. doi:10.1145/3717823.3718144.

[bib.bib40] [40] Zi-Wen Liu, Seth Lloyd, Elton Zhu, and Huangjun Zhu. Entanglement, quantum randomness, and complexity beyond scrambling. Journal of High Energy Physics, 2018(7):1–62, 2018.

[bib.bib41] [41] Elihu Lubkin. Entropy of an $n$ -system from its correlation with a $k$ -reservoir. Journal of Mathematical Physics, 19(5):1028–1031, 1978.

[bib.bib42] [42] Michael George Luby. Pseudorandomness and Cryptographic Applications. Princeton University Press, USA, 1994.

[bib.bib43] [43] Antonio Anna Mele. Introduction to haar measure tools in quantum information: A beginner’s tutorial. Quantum, 8:1340, 2024. doi:10.22331/Q-2024-05-08-1340.

[bib.bib44] [44] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Pseudorandom unitaries with non-adaptive security, 2024. doi:10.48550/arXiv.2402.14803.

[bib.bib45] [45] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. On the Pauli spectrum of QAC0. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1498–1506, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3618260.3649662.

[bib.bib46] [46] Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. doi:10.1137/0222053.

[bib.bib47] [47] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010.

[bib.bib48] [48] Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, March 1991. doi:10.1007/bf01375474.

[bib.bib49] [49] Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. doi:10.1007/BF01305237.

[bib.bib50] [50] Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149–167, 1994. doi:10.1016/S0022-0000(05)80043-1.

[bib.bib51] [51] Noam Nisan and David Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci., 52(1):43–52, 1996. doi:10.1006/JCSS.1996.0004.

[bib.bib52] [52] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography, 2024. doi:10.48550/arXiv.2401.03703.

[bib.bib53] [53] Michael E. Saks and Shiyu Zhou. $\mathsf{BP_{H}SPACE}(s)\subseteq\mathsf{DSPACE}(s^{3/2})$ . J. Comput. Syst. Sci., 58(2):376–403, 1999. doi:10.1006/JCSS.1998.1616.

[bib.bib54] [54] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth. Science, 389(6755):92–96, July 2025. doi:10.1126/science.adv8590.

[bib.bib55] [55] Joseph Slote. Parity vs. AC0 with simple quantum preprocessing. In 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, volume 287 of LIPIcs, pages 92:1–92:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ITCS.2024.92.

[bib.bib56] [56] Avishay Tal. Tight bounds on the fourier spectrum of $\mathsf{AC}^{0}$ . In 32nd Computational Complexity Conference, CCC 2017, volume 79 of LIPIcs, pages 15:1–15:31. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.CCC.2017.15.

[bib.bib57] [57] Salil P Vadhan. Pseudorandomness. Foundations and Trends^® in Theoretical Computer Science, 7(1–3):1–336, 2012. doi:10.1561/0400000010.

[bib.bib58] [58] Emanuele Viola. The sum of $d$ small-bias generators fools polynomials of degree $d$ . Comput. Complex., 18(2):209–217, 2009. doi:10.1007/S00037-009-0273-5.

[bib.bib59] [59] Lisa Yang and Netta Engelhardt. The complexity of learning (pseudo)random dynamics of black holes and other chaotic systems, 2023. arXiv:2302.11013.

[bib.bib60] [60] Mark Zhandry. How to construct quantum random functions. J. ACM, 68(5), August 2021. doi:10.1145/3450745.

		$\displaystyle\ \operatorname{\mathbb{E}}_{{i}}\left[\left\lVert\operatorname{% Tr}_{B}[\|\psi_{i}\rangle\langle\psi_{i}\|]\right\rVert_{2}^{2}\right]-% \operatorname{\mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B}[\|\psi_{% \mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}\|]\right\rVert_{2}^{2}\right]$
	$\displaystyle=$	$\displaystyle\ \operatorname{Tr}\left[\left(\operatorname{\mathbb{E}}_{{i}}% \left[\|\psi_{i}\rangle\langle\psi_{i}\|^{\otimes 2}\right]-\operatorname{% \mathbb{E}}\left[\|\psi_{\mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}\|^{% \otimes 2}\right]\right)\cdot R\right]$
	$\displaystyle\leq$	$\displaystyle\ \left\lVert\operatorname{\mathbb{E}}_{{i}}\left[\|\psi_{i}% \rangle\langle\psi_{i}\|^{\otimes 2}\right]-\operatorname{\mathbb{E}}\left[\|% \psi_{\mathsf{Haar}}\rangle\langle\psi_{\mathsf{Haar}}\|^{\otimes 2}\right]% \right\rVert_{1}\cdot\left\lVert R\right\rVert_{\infty}\leq\varepsilon.\$

		$\displaystyle\ \operatorname{\mathbb{E}}_{{i}}\left[\left\lVert\operatorname{% Tr}_{B}[U_{i}\|v\rangle\langle w\|U_{i}^{\dagger}]\right\rVert_{2}^{2}\right]-% \operatorname{\mathbb{E}}\left[\left\lVert\operatorname{Tr}_{B}[U_{\mathsf{% Haar}}\|v\rangle\langle w\|U_{\mathsf{Haar}}^{\dagger}]\right\rVert_{2}^{2}\right]$
	$\displaystyle=$	$\displaystyle\ \operatorname{Tr}\left[\left(\Phi_{\mathcal{D}}^{(t)}(\|v\rangle% \langle w\|^{\otimes 2})-\Phi_{\mathsf{Haar}}^{(t)}(\|v\rangle\langle w\|^{% \otimes 2})\right)\cdot R\right]$
	$\displaystyle=$	$\displaystyle\ \left\lVert\Phi_{\mathcal{D}}^{(t)}(\|v\rangle\langle w\|^{% \otimes 2})-\Phi_{\mathsf{Haar}}^{(t)}(\|v\rangle\langle w\|^{\otimes 2})\right% \rVert_{1}\cdot\left\lVert R\right\rVert_{\infty}\leq\varepsilon.\$

	$\displaystyle\left\lVert\operatorname{Tr}_{B}[U\|v\rangle\langle w\|U^{\dagger}]% \right\rVert_{2}^{2}$	$\displaystyle=\operatorname{Tr}\left[(\mathbb{I}_{A}\otimes\|0^{n-k}\rangle% \langle 0^{n-k}\|_{B})\|u\rangle\langle 0^{n}\|0^{n}\rangle\langle u\|(\mathbb{I}_% {A}\otimes\|0^{n-k}\rangle\langle 0^{n-k}\|_{B})\right]$
		$\displaystyle=\operatorname{Tr}\left[(\mathbb{I}_{A}\otimes\|0^{n-k}\rangle% \langle 0^{n-k}\|_{B})\|u\rangle\langle u\|\right]$
		$\displaystyle=\sum_{x\in\{0,1\}^{k}}\left\lvert\langle x_{A}0^{n-k}_{B}\|u% \rangle\right\rvert^{2}.$

		$\displaystyle\ \frac{1}{2^{dt}}\sum_{\begin{subarray}{c}x_{1},\ldots,x_{t}\in S% \\ x_{i}\neq x_{j},\forall i<j\\ \pi\in\mathcal{S}_{t}\end{subarray}}\|x_{1}\cdots x_{t}\rangle\langle x_{\pi(1)% }\cdots x_{\pi(t)}\|$
	$\displaystyle=$	$\displaystyle\ \frac{1}{2^{dt}}\sum_{\{x_{1},\ldots,x_{t}\}\subset S}\left(% \sum_{\pi\in\mathcal{S}_{t}}\|x_{\pi(1)}\cdots x_{\pi(t)}\rangle\right)\left(% \sum_{\pi\in\mathcal{S}_{t}}\langle x_{\pi(1)}\cdots x_{\pi(t)}\|\right)$
	$\displaystyle=$	$\displaystyle\ \frac{t!}{2^{dt}}\sum_{X\subset S,\|X\|=t}\|\mathsf{Sym_{X}}% \rangle\langle\mathsf{Sym}_{X}\|.$

Unconditional Pseudorandomness Against Shallow Quantum Circuits

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Our contributions.

1.1 Main results

1.2 PRS from state designs

Theorem 1 (Informal; See Corollary 21).

Theorem 2 (Informal; See Corollary 28).

Theorem 3 (Informal; See Corollary 29).

1.3 PRU from unitary designs

Theorem 4 (Informal; See Theorem 35).

Theorem 5 (Informal; See Theorem 36).

1.4 Proof techniques

1.5 Related work

2 Preliminaries

Definition 6.

Quantum Pseudorandom Primitives

Definition 7.

Definition 8.

Definition 9.

Definition 10.

State and Unitary Designs

Definition 11 (State t-design).

Lemma 12.

Proof.

Definition 13 (Unitary t-design).

Lemma 14.

Proof.

Schmidt Decomposition

Definition 15.

Lemma 16.

3 Unconditional pseudorandomness from 2-designs

Lemma 17 ([41, 40]).

Corollary 18.

Proof.

Corollary 19.

Proof.

3.1 Pseudorandomness against 𝗤𝗡𝗖𝟎

Theorem 20.

Proof.

Corollary 21.

Proof.

3.2 Pseudorandomness against 𝗔𝗖𝟎∘𝗤𝗡𝗖𝟎

Definition 22 (Random phased subspace states).

Theorem 23.

Proof.

Lemma 24.

Theorem 25.

Proof.

Lemma 26.

Proof.

Theorem 27.

Proof.

Corollary 28.

Proof.

3.3 Pseudoentanglement against 𝗔𝗖𝟎∘𝗤𝗡𝗖𝟎

Corollary 29.

Proof.

Preparing phased subspace states.

4 Parallel-query secure PRU against local 𝗤𝗡𝗖𝟎

Lemma 30.

Proof.

Lemma 31 (Recursive Schmidt Decomposition).

Proof.

Lemma 32.

Proof.

Corollary 33.

Proof.

Corollary 34.

Theorem 35.

Definition 11 (State $t$ -design).

Definition 13 (Unitary $t$ -design).

3.1 Pseudorandomness against $\mathsf{QNC}^{0}$

3.2 Pseudorandomness against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$

3.3 Pseudoentanglement against $\mathsf{AC}^{0}\circ\mathsf{QNC}^{0}$

4 Parallel-query secure PRU against local $\mathsf{QNC}^{0}$