Learning quantum states and unitaries of bounded gate complexity

$\star$These authors contributed equally to this work.footnote

Haimeng Zhao^⋆
Institute for Quantum Information and Matter, Caltech, Pasadena, CA, USA
Tsinghua University, Beijing, China

Laura Lewis^⋆
Institute for Quantum Information and Matter, Caltech, Pasadena, CA, USA
Google Quantum AI, Venice, CA, USA

Ishaan Kannan^⋆
Institute for Quantum Information and Matter, Caltech, Pasadena, CA, USA

Yihui Quek
Harvard University, 17 Oxford Street, Cambridge, MA, USA
Massachusetts Institute of Technology, Cambridge, MA, USA

Hsin-Yuan Huang
Institute for Quantum Information and Matter, Caltech, Pasadena, CA, USA
Google Quantum AI, Venice, CA, USA
Massachusetts Institute of Technology, Cambridge, MA, USA

Matthias C. Caro
Institute for Quantum Information and Matter, Caltech, Pasadena, CA, USA
Freie Universität Berlin, Berlin, Germany

While quantum state tomography is notoriously hard, most states hold little interest to practically-minded tomographers. Given that states and unitaries appearing in Nature are of bounded gate complexity, it is natural to ask if efficient learning becomes possible.
In this work, we prove that to learn a state generated by a quantum circuit with $G$ two-qubit gates to a small trace distance, a sample complexity scaling linearly in $G$ is necessary and sufficient. We also prove that the optimal query complexity to learn a unitary generated by $G$ gates to a small average-case error scales linearly in $G$.
While sample-efficient learning can be achieved, we show that under reasonable cryptographic conjectures, the computational complexity for learning states and unitaries of gate complexity $G$ must scale exponentially in $G$.
We illustrate how these results establish fundamental limitations on the expressivity of quantum machine learning models and provide new perspectives on no-free-lunch theorems in unitary learning.
Together, our results answer how the complexity of learning quantum states and unitaries relate to the complexity of creating these states and unitaries.

§ INTRODUCTION

A central problem in quantum physics is to characterize a quantum system by constructing a full classical description of its state or its evolution based on data from experiments. These two tasks, named quantum state tomography [1, 2, 3, 4] and quantum process tomography [5, 6, 7, 8, 9], are (in)famous for being ubiquitous yet highly expensive. The applications of tomography include quantum metrology [10, 11], verification [12, 13], benchmarking [5, 6, 7, 8, 14, 15, 16, 17], and error mitigation [18]. Yet tomography provably requires exponentially many (in the system size) copies of the unknown state [19, 20] or runs of the unknown process [21]. This intuitively arises from the exponential scaling of the number of parameters needed to describe an arbitrary quantum system.

But the situation is less dire than it theoretically appears. In practice, tools for analyzing many-body systems often exploit known structures cleverly to predict their phenomenology or classically simulate them.
Notable examples include the BCS theory for superconductivity [22], tensor networks [23, 24], and neural network [25, 26, 27] Ansätze.
Indeed, while most of the states or unitaries may have exponential gate complexity [28], such objects are also unphysical: an exponentially-complex state or unitary cannot be produced in Nature with limited time [29].

In this work, we study if tomography, too, can benefit from the observation that Nature can only produce states and unitaries with bounded complexity. This gives rise to the following main question.

Can we efficiently learn states/unitaries of bounded gate complexity?

In particular, we consider the following two tasks:

* Given copies (samples) of a pure quantum state $\ket{\psi}$ generated by $G$ two-qubit gates, learn $\ket{\psi}$ to within $\epsilon$ trace distance; see <Ref>(a).

* Given uses (queries) of a unitary $U$ composed of $G$ two-qubit gates, learn $U$ to within $\epsilon$ root mean squared trace distance between output states (average-case learning); see <Ref>(b).

Note that the $G$ quantum gates can act on arbitrary pairs of qubits without any geometric locality constraint.
We present algorithms for both of these tasks that use a number of samples/queries linear in the circuit complexity $G$ up to logarithmic factors.
Thus, for $G$ scaling polynomially with the number of qubits, our learning procedures have significantly lower sample/query complexities than required for general tomography, answering our central question affirmatively.
We also prove matching lower bounds (up to logarithmic factors), showing that our algorithms are effectively optimal.
Moreover, we show that the focus on average-case learning is crucial in the case of unitaries: unitary tomography up to error $\epsilon$ in diamond distance (a worst-case metric over input states) requires a number of queries scaling exponentially in $G$, establishing an exponential separation between average and worst case.

(a)-(c) Schematic overview of the learning models in this work. (a) Learning quantum states with bounded circuit complexity $G$. (b) Learning unitaries with bounded circuit complexity $G$. (c) Learning classical functions from quantum experiments with bounded circuit complexity $G$. (d) Sample complexity of learning states in trace distance and unitaries in average-case distance scales linearly with circuit complexity, while that of learning unitaries in worst-case distance scales exponentially.

While our learning algorithms for bounded-complexity states and unitaries are efficient in terms of sample/query complexity, they are not computationally efficient. We prove that this is unavoidable. Assuming the quantum subexponential hardness of Ring Learning with Errors () [30, 31, 32, 33, 34, 35], any quantum algorithm that learns arbitrary states/unitaries with $\tilde{\bigo}(G)$ gates requires computational time scaling exponentially in $G$.
This result highlights a significant computational complexity limitation on learning even comparatively simple states and unitaries. This result also answers an open question in [36].
Meanwhile, we show that $\mathrm{poly}(n)$-time algorithms are possible for $G=\mathcal{O}(\log n)$.
Together, this establishes a “phase transition” in computational hardness at $G \sim \log n$, kicking in far before the sample complexity becomes exponential (at $G = \exp(n)$).
This means that relatively few samples/queries already contain enough information for the learning task, but it is hard to retrieve the information.

Finally, we study two variations of unitary learning which deepen our insights about the problem. The first variation utilizes classical (not quantum) descriptions of input and output pairs, and explains why both learning states and unitaries display a linear-in-$G$ sample complexity: The underlying source of complexity in learning unitaries is, in fact, the readout of input and output quantum states, rather than learning the mapping. We generalize recent quantum no-free lunch theorems [37, 38] to reach this conclusion.
For the second variation we study quantum machine learning (QML) models. We focus on learning classical functions that map variables controlling the input states and the evolution to some experimentally observed property of the outputs (<Ref>(c)). Surprisingly, we find that certain well-behaved many-variable functions can in fact not (even approximately) be implemented by quantum experiments with bounded complexity. This highlights a fundamental limitation on the functional expressivity of both Nature and practical QML models.

§ LEARNING QUANTUM STATES AND UNITARIES

In this section, we discuss our rigorous guarantees for learning quantum states and unitaries with circuit complexity $G$. Our sample complexity results are summarized in <Ref> and <Ref>(d).

Sample complexity
Unitary (average-case)
Unitary (worst-case)

Upper bound
$\tilde{\mathcal{O}}\left(G\min\left\{1/\epsilon^2, \sqrt{2^n}/\epsilon\right\}\right)$
$\tilde{\mathcal{O}}\left(2^n G/\epsilon\right)$

Lower bound
$\Omega\left(2^{\min\{G/(2C), n/2\}}/{\epsilon}\right)$

Sample complexity of learning $n$-qubit states and unitaries with circuit complexity $G$. The learning accuracy $\epsilon$ is measured in trace distance for states, root mean squared trace distance for average case unitary learning, and diamond distance for worst case. Here, $C>0$ is some universal constant. Throughout the manuscript, $\tilde{\mathcal{O}}, \tilde{\Theta}$ and $\tilde{\Omega}$ denote that we are suppressing non-leading logarithmic factors.

We also present computational complexity results, where we establish the exponential-in-$G$ growth of computational complexity, implying that $\log n$ gate complexity is a transition point at which learning becomes computationally inefficient.
In particular, we prove that for circuit complexity $\tilde{\bigo}(G)$, any quantum algorithm for learning states in trace distance or unitaries in average-case distance must use time exponential in $G$, under the conjecture that  cannot be solved by a quantum computer in sub-exponential time.
Hence, for a number $G$ of gates that scales slightly higher than $\log n$, the learning tasks cannot be solved by any polynomial-time quantum algorithm under the same conjecture.
Meanwhile, for $G=\mathcal{O}(\log n)$, both learning tasks can be solved efficiently in polynomial time.

§.§ Learning quantum states

We consider the task of learning quantum states of bounded circuit complexity.
Let $\ket{\psi} = U\ket{0}^{\otimes n}$ be an $n$-qubit pure state generated by a unitary $U$ consisting of $G$ two-qubit gates acting on the zero state.
Throughout this section, we denote $\rho \triangleq \ketbra{\psi}$.
Given $N$ identically prepared copies of $ρ$, the goal is to learn a classical circuit description of a quantum state $ρ̂$ that is $ϵ$-close to $ρ$ in trace distance: $(ρ̂, ρ) = ρ̂ - ρ_1 /2 < ϵ$.
We establish the following theorem, which states that linear-in-$G$ many samples (up to logarithmic factors) are both necessary and sufficient to learn the unknown quantum state $|ψ⟩$ within a small trace distance.

\vspace*{1mm}
\begin{theorem}[State learning]
\label{thm:state-learning}
Suppose we are given $N$ copies of an $n$-qubit pure state $\rho = \ketbra{\psi}$, where $\ket{\psi} = U\ket{0}^{\otimes n}$ is generated by a unitary $U$ consisting of $G$ two-qubit gates. Then, $N = \tilde{\Theta}\left(G/\epsilon^2\right)$ copies are necessary and sufficient to learn the state within $\epsilon$-trace distance $\dtr$ with high probability.
\end{theorem}

This result resolves an open question from~[39].
We prove the upper bound in \Cref{app:states-upper}, utilizing covering nets~[40] and quantum hypothesis selection~[41].
Our proposed algorithm first creates a covering net over the space of all unitaries consisting of $G$ two-qubit gates.
This can easily be transformed into a covering net over the space of all quantum states generated by $G$ two-qubit gates by applying each element of the unitary covering net to the zero state.
Thus, any quantum state generated by $G$ two-qubit gates is close (in trace distance) to some element of the covering net.
We can then apply quantum hypothesis selection~[41] to the covering net, which allows us to identify the element in the covering net that is close to the unknown target state $\ket{\psi}$.
We also note that our algorithm for learning quantum states does not require knowledge of or access to the unitary $U$ which generates the unknown state $\ket{\psi}$.
Only the condition that some unitary $U$ consisting of $G$ gates generates $\ket{\psi}$ is needed.
In the regime where $G\log G < 2^n$, the sample complexity of our proposed algorithm improves substantially over the sample complexity $N = \mathcal{O}(2^n)$ of the sample-optimal result for arbitrary pure quantum states~[19, 20].
The lower bound is proven in \Cref{app:states-lower} by using an information-theoretic argument via reduction to distinguishing a packing net over $G$-gate states~[19].

Our algorithm to learn the unknown quantum state $\ket{\psi}$ is computationally inefficient, as it requires a search over a covering net whose cardinality is exponential in $G$.
We show that for circuits of size $\tilde{\mathcal{O}}(G)$, any quantum algorithm that can learn $\ket{\psi}$ given access to copies of this state must use time exponential in $G$, under commonly-believed cryptographic assumptions [30, 31, 32, 33, 34, 35].
Meanwhile, the learning task is computationally-efficiently solvable for $G=\mathcal{O}(\log n)$ via junta learning [42] and standard tomography methods.
This implies a transition point of computational efficiency at $\log n$ circuit complexity.

\begin{theorem}[State learning computational complexity]
\label{thm:state-comp-complex}
Suppose we are given $N$ copies of an unknown $n$-qubit pure state $\ket{\psi} = U\ket{0}^{\otimes n}$ generated by an arbitrary unknown unitary $U$ consisting of $\tilde{\mathcal{O}}(G)$ two-qubit gates.
Suppose that \textsf{RingLWE} cannot be solved by a quantum computer in sub-exponential time.
Then, any quantum algorithm that learns the state to within $\epsilon$ trace distance $\dtr$ must use $\exp(\Omega(\min\{G, n\}))$ time.
Meanwhile, for $G=\mathcal{O}(\log n)$, the learning task can be solved in polynomial time.
\end{theorem}

\subsection{Learning quantum unitaries}}
For learning unitaries, a natural distance metric analogous to the trace distance for states is the diamond distance $\dworst(U, V) = \max_{\rho} \|(U\otimes I)\rho(U\otimes I)^\dagger - (V\otimes I)\rho(V\otimes I)^\dagger\|_1$.
It characterizes the optimal success probability for discriminating between two unitary channels.
Moreover, it can be reinterpreted in terms of the largest distance between $U\ket{\psi}$ and $V\ket{\psi}$ over all input states $\ket{\psi}$, and thus represents the error we make in the worst case over input states.
We find that in this worst-case learning task, a number of queries exponential in $G$ is necessary to learn the unitary.

\vspace*{1mm}
\begin{theorem}[Worst-case unitary learning]
To learn an $n$-qubit unitary composed of $G$ two-qubit gates to accuracy $\epsilon$ in diamond distance $\dworst$ with high probability, any quantum algorithm must use at least $\Omega\left(\nicefrac{2^{\min\{G/(2C), n/2\}}}{\epsilon}\right)$ queries to the unknown unitary, where $C>0$ is a universal constant.
Meanwhile, there exists such an algorithm using $\tilde{\mathcal{O}}(\nicefrac{2^nG}{\epsilon})$ queries.
\label{thm:worst-case-unitary}
\end{theorem}

The complete proof is given in \Cref{app:worst-case-unitary} and relies on the adversary method~[43, 44, 45, 46].
We construct a set of unitaries that a worst-case learning algorithm can successfully distinguish, but that only make minor differences when acting on states so that a minimal number of queries have to be made in order to distinguish them.
The upper bound is achieved by the average-case learning algorithm in \Cref{thm:avg-case-unitary} below when applied in the regime of exponentially small error.

Having established this no-go theorem for worst-case learning, we turn to a more realistic average-case learning alternative. Here, the accuracy is measured using the root mean squared trace distance between output states over Haar-random inputs, $\davg(U, V) = \sqrt{\mathbb{E}_{\ket{\psi}}[\dtr(U\ket{\psi}, V\ket{\psi})^2]}$.
This metric characterizes the average error when testing the learned unitary on randomly chosen input states.

We find that, similarly to the state learning task, linear-in-$G$ many queries are both necessary and sufficient to learn a unitary in the average case.

\begin{theorem}[Average-case unitary learning]
There exists an algorithm that learns an $n$-qubit unitary composed of $G$ two-qubit gates to accuracy $\epsilon$ in root mean squared trace distance $\davg$ with high probability using $\tilde{\mathcal{O}}\left(G\min\{\nicefrac{1}{\epsilon^2}, \nicefrac{\sqrt{2^n}}{\epsilon}\}\right)$ queries to the unknown unitary.
Meanwhile, $\Omega\left(\nicefrac{G}{\epsilon}\right)$ queries to the unitary or its inverse or the controlled versions are necessary for any such algorithm.
\label{thm:avg-case-unitary}
\end{theorem}

We show the upper bound in \Cref{app:avg-case-unitary-up} by combining a covering net with quantum hypothesis selection similarly to the upper bound in \Cref{thm:state-learning}.
Our algorithm achieving the query complexity $\tilde{\bigo}(\nicefrac{G}{\epsilon^2})$ uses maximally entangled states and the Choi–Jamio{\l}kowski duality~[47, 48, 49].
With a bootstrap method similar to quantum phase estimation [21], we improve the $\epsilon$-dependence to the Heisenberg scaling $\tilde{\bigo}(\nicefrac{1}{\epsilon})$, albeit at the cost of a dimensional factor.
Without auxiliary systems, we prove a query complexity bound of $\tilde{\bigo}(G\min\{\nicefrac{1}{\epsilon^4}, \nicefrac{\left(\sqrt{2^n}\right)^3}{\epsilon}\})$.
The lower bound is proven in \Cref{app:avg-case-unitary-lo} by mapping to a fractional query problem [21, 50, 51] and making use of a recent upper bound on the success probability in unitary distinguishing tasks [52].
In the case of learning generic unitaries, our result yields a $\Omega(4^n/\epsilon)$ lower bound, improving upon the $\Omega(4^n/n^2)$ bound from the recent work [53],  which studies the hardness of learning Haar-(pseudo)random unitaries.

As Haar-random states are hard to generate in practice, we also discuss other input state ensembles of physical interest.
Relying on the equivalence of root mean squared trace distances over different locally scrambled ensembles [54, 55], recently established in [56], our algorithm achieves the same average-case guarantee over any such ensemble.
Notable examples of locally scrambled ensembles include products of Haar-random single-qubit states or of random single-qubit stabilizer states, $2$-designs on $n$-qubit states, and output states of random local quantum circuits with any fixed architecture.

The similar linear-in-$G$ sample/query complexity scaling in \Cref{thm:state-learning,thm:avg-case-unitary} hints at a common underlying source of complexity.
However, in contrast to state learning, unitary learning comes with two natural such sources: (1) to readout input and output states, and (2) to learn the mapping from inputs to outputs.
The similarity between learning states and unitaries in terms of complexities suggests that the former may encapsulate the central difficulty in unitary learning whereas the latter may be easy.
This seemingly contradicts recent quantum no-free-lunch theorems~[37, 38], which state $\Omega(2^n)$ samples are required to learn a generic unitary even from classical descriptions of input-output state pairs, highlighting the difficulty of (2).

To resolve this apparent contradiction, we reformulate the quantum no-free-lunch theorem from a unifying information-theoretic perspective in \Cref{app:classical-description}.
We highlight that enlarging the space for the classically described data allows to systematically reduce the sample complexity until a single sample suffices to learn a general unitary.
Therefore, the difficulty of learning the mapping, as indicated by quantum no-free-lunch theorems, vanishes when we allow auxiliary systems and query access to the unitary.
Inspired by this observation, we give two ways of enlarging the representation space with auxiliary systems. The first is fundamentally quantum, making use of entangled input states~[38]. The other is purely classical, relying on mixed state inputs~[57].

\begin{theorem}[Learning with classical descriptions]
There exists an algorithm that learns a generic $n$-qubit unitary with any non-trivial accuracy and with high success probability using $\bigo(2^n/r)$ classically described input-output pairs with mixed (entangled) input states of (Schmidt) rank $r$.
Moreover, any such algorithm that is robust to noise needs at least $\Omega(2^n/r)$ samples.
\label{thm:classical-description}
\end{theorem}

Similarly to the case for state learning, our average-case unitary learning algorithm is not computationally efficient.
We show that this cannot be avoided. Under commonly-believed cryptographic assumptions [30, 31, 32, 33, 34, 35], any quantum algorithm that can learn unknown unitaries with circuit size $\tilde{\bigo}(G)$ to a small error in average-case distance from queries must have a computational time exponential in $G$.
This implies the same computational hardness for worst-case unitary learning, and a $\log n$ transition point of computational efficiency.
Note that the hard instances we construct are implementable with a similar number of Clifford and T gates [58]. Therefore, together with \Cref{thm:state-comp-complex}, this implies that there is no polynomial time quantum algorithms for learning Clifford+T circuits with $\tilde{\omega}(\log n)$ T gates, answering an open question (the fifth question) in the survey [36] negatively.

\begin{theorem}[Unitary learning computational complexity]
\label{thm:unitary-comp-complex}
Suppose we are given $N$ queries to an arbitrary unknown $n$-qubit unitary $U$ consisting of $\tilde{\bigo}(G)$ two-qubit gates.
Assume that \textsf{RingLWE} cannot be solved by a quantum computer in sub-exponential time.
Then, any quantum algorithm that learns the unitary to within $\epsilon$ average-case distance $\davg$ must use $\exp(\Omega(\min\{G, n\}))$ time.
Meanwhile, for $G=\mathcal{O}(\log n)$, the learning task can be solved in polynomial time.
\end{theorem}

\subsection{Learning physical functions}}

An alternative way of learning about Nature is to focus on \textit{physical functions}, which we define in \Cref{app:learning-function} as functions $f(x, \{U_i\}_{i=1}^G, a)$ mapping $x\in[0, 1]^\nu$ to $\mathbb{R}$ resulting from a physical experiment consisting of three steps: (1) a fixed state preparation procedure that can depend on $x$; (2) a unitary evolution consisting of $G$ tunable two-qubit gates $\{U_i\}_{i=1}^G$ and arbitrary fixed unitaries that can depend on $x$, arranged in a circuit architecture $a$; (3) the measurement of a fixed observable, whose expectation is the function output.
By tuning the local gates $\{U_i\}_{i=1}^G$ and potentially changing architecture $a$, we obtain a resulting class of functions that can be implemented in this general experimental setting.
Despite the generality of this setup, we find that certain well-behaved functions are actually not physical in this sense: they cannot be efficiently approximated or learned via physical functions.

\vspace*{1mm}
\begin{theorem}[Approximating and learning with physical functions]
To approximate and learn arbitrary $1$-bounded and $1$-Lipschitz $\mathbb{R}$-valued functions on $[0, 1]^\nu$ to accuracy $\epsilon$ in $\|\cdot\|_\infty$ with high probability, using physical functions with $G$ gates and variable circuit structures, we must use $G\geq \tilde{\Omega}(\nicefrac{1}{\epsilon^{\nu/2}})$ gates and collect at least $\Omega(\nicefrac{1}{\epsilon^{\nu}})$ samples.
\label{thm:approx-functions}
\end{theorem}

We prove this in \Cref{app:learning-function} by noting that to approximate arbitrary $1$-bounded and $1$-Lipschitz functions well, the complexity of experimentally implementable functions cannot be too small, as measured by pseudo-dimension [59] or fat-shattering dimension [60].
Then the gate complexity lower bound follows because the function class complexity is limited by the circuit complexity [61], and we can appeal to results in classical learning theory [62] to obtain our sample complexity lower bound.

It has been established that a classical neural network can learn to approximate any $1$-bounded and $1$-Lipschitz functions to accuracy $\epsilon$ in $\|\cdot\|_\infty$ with $\tilde{\Theta}(1/\epsilon^\nu)$ parameters, exponential in the number of variables $\nu$, known as the curse of dimensionality~[63].
Our results show that quantum neural networks can do no better.
This result not only is relevant to the practical implementation of quantum machine learning, complementing existing results on the universal approximation of quantum neural networks~[64, 65, 66, 67], but also has deep implications to the physicality of the function class at consideration.
It means that there are some many-variable $1$-bounded and $1$-Lipschitz functions that cannot be implemented in Nature efficiently.
On the other hand, certain more restricted function classes can be approximated using only $\mathcal{O}(1/\epsilon^2)$ parameters with both classical~[63] and quantum neural networks~[64], independent of the number of variables.
This reveals a fundamental limitation on the functional expressivity of both Nature and practical quantum machine learning models.

\section{Proof ideas}}

In this section, we discuss the main ideas behind the proof of our results on the sample complexity of learning states (\Cref{thm:state-learning}) and unitaries (\Cref{thm:avg-case-unitary}), along with the computational complexity (\Cref{thm:state-comp-complex,thm:unitary-comp-complex}).

\vspace{1.0em}
\subsection{Sample complexity upper bounds}}

We prove the upper bounds in \Cref{thm:state-learning,thm:avg-case-unitary} using a hypothesis selection protocol similar to [41], but now based on classical shadow tomography [68] that enables a linear-in-$G$ scaling.

\paragraph{State learning}
For state learning, we first take a minimal covering net $\mathcal{N}$ over the set of states with bounded circuit complexity $G$ such that for any such state $\ket{\psi}$, there exists a state in the covering net that is $\epsilon$-close to $\ket{\psi}$ in trace distance.
This net then serves as a set of candidate states from which the learning algorithm will select one.
Importantly, we prove that the cardinality of $\mathcal{N}$ can be upper bounded by $|\mathcal{N}| \leq e^{\tilde{\bigo}(G)}$.

Next, we use classical shadows created via random Clifford measurements~[68] to estimate the trace distance between the unknown state and each of the candidates in $\mathcal{N}$.
This is achieved by estimating the expectation value of the Helstrom measurement [69], which is closely related to the trace distance between two states.
As the rank of Helstrom measurements between pure states is at most $2$, Clifford classical shadows can efficiently estimate all $\binom{|\mathcal{N}|}{2}$ of them simultaneously to $\epsilon$ error using $\bigo(\log|\mathcal{N}|/\epsilon^2)\leq \tilde{\bigo}(G/\epsilon^2)$ copies of $\ket{\psi}$.
Then we select the candidate that has the smallest trace distance from $\ket{\psi}$ as the output.

The above strategy leads to a sample complexity upper bound that depends logarithmically on the number of qubits $n$.
This is undesirable when the circuit complexity $G$ is smaller than $n/2$ (i.e., when some of the qubits are in fact never influenced by the circuit).
We improve our algorithm in this small-size regime by first performing a junta learning step [42] to identify which of the qubits are acted on non-trivially.
After that, we enhance our protocol with a measure-and-postselect step.
This allows us to construct a covering net only over the qubits acted upon non-trivially whose cardinality no longer depends on $n$.
We then perform the hypothesis selection as before.

\paragraph{Unitary learning}
The algorithm for unitary learning is similar to the state learning protocol.
When allowing the use of an auxiliary system, we utilize the fact that the average-case distance between unitaries is equivalent to the trace distance between their Choi states. This way, we can reduce the problem to state learning of the Choi states and achieve the $\tilde{\bigo}(G/\epsilon^2)$ sample complexity.
Without auxiliary systems, we can sample random input states and perform one-shot Clifford shadows on the outputs to estimate the squared average-case distance, resulting in an $\tilde{\bigo}(G/\epsilon^4)$ sample complexity with a sub-optimal $\epsilon$-dependence.

Furthermore, we improve the $\epsilon$ dependence in unitary learning to the Heisenberg scaling $\tilde{\bigo}(1/\epsilon)$ via a bootstrap method similar to [21], using the above learning algorithm as a sub-routine.
Specifically, we iteratively refine our learning outcome $\hat{U}$ by performing hypothesis selection over a covering net of $(U\hat{U}^\dagger)^{p}$, with $p$ increasing exponentially as the iteration proceeds.
Although the circuit complexity of $(U\hat{U}^\dagger)^{p}$ grows with $p$, a covering net with $p$-independent cardinality can be constructed based on the one-to-one correspondence to $U$.
However, unlike the diamond distance learner considered in [21], which has fine control over every eigenvalue of the unitaries, our average-case learner only has control over the average of the eigenvalues.
Thus for the bootstrap to work (i.e., for the learning error to decrease with increasing $p$), the average-case learner has to work in an exponentially small error regime, which results in a dimensional factor in the final sample complexity $\tilde{\bigo}(\sqrt{2^n}G/\epsilon)$.

\subsection{Sample complexity lower bounds}}

We prove the sample complexity lower bounds in \Cref{thm:state-learning,thm:avg-case-unitary} by reduction to distinguishing tasks.
Specifically, if we can learn the state/unitary to within $\epsilon$ error, then we can use this learning algorithm to distinguish a set of states/unitaries that are $3\epsilon$ far apart from each other.
Hence a lower bound on the sample complexity of distinguishing states/unitaries from a packing net implies a lower bound for the learning task.

\paragraph{State learning}
For state learning, we construct a packing net $\mathcal{M}$ of the set of $(\log_2 G)$-qubit states, which we later tensor product with zero states on the remaining qubits.
These states have circuit complexity $\sim G$ because $\mathcal{O}(2^k)$ two-qubit gates can implement any pure $k$-qubit states [70].
We prove that the cardinality of $\mathcal{M}$ can be lower bounded by $e^{\Omega(G)}$.
This means that to distinguish the states in $\mathcal{M}$, one has to gather $\Omega(\log|\mathcal{M}|)\geq \Omega(G)$ bits of information.
Meanwhile, Holevo's theorem [71] asserts that the amount of information carried by each sample is upper bounded by $\tilde{\mathcal{O}}(\epsilon^2)$ [72].
Hence, we need at least $\tilde{\Omega}(G/\epsilon^2)$ copies of the unknown state.

\paragraph{Unitary learning}
Similarly, for unitary learning, we construct a packing net by stacking all the gates into $\log_4 G$ qubits, using the fact that $\bigo(4^k)$ two-qubit gates suffice to implement any $k$-qubit unitaries~[73].
Lacking an analogue of Holevo's theorem for unitary queries, we turn to a recently established bound on the success probability of unitary discrimination [52] and obtain an $\Omega(G)$ sample complexity lower bound for constant $\epsilon$.
To incorporate the $\epsilon$ dependence, we follow [21] and map the problem into a fractional query problem.
We show that with $N$ queries, we can use the learning algorithm to simulate [50, 51] an $\bigo(\epsilon N)$ query algorithm that solves the above constant-accuracy distinguishing problem.
This gives us the desired $N\geq \Omega(G/\epsilon)$ lower bound.

\subsection{Computational hardness}}

We prove the computational complexity lower bounds in \Cref{thm:state-comp-complex,thm:unitary-comp-complex} again by reduction to distinguishing tasks, whose hardness relies on cryptographic primitives in this case.
In particular, we show that if we can learn the state/unitary in polynomial time, then we can use this learning algorithm to efficiently distinguish between pseudorandom states/functions~[74, 75] and truly random states/functions.

Both cases rely on the construction of quantum-secure pseudorandom functions (PRFs) that can be implemented using $\mathsf{TC}^0$ circuits, subject to the assumption that Ring Learning with Errors (\textsf{RingLWE}) cannot be solved by a quantum computer in sub-exponential time~[32].
We show that the circuit construction of ~[32] can be implemented quantumly using $G = \mathcal{O}(n\polylog(n))$ gates by converting this $\mathsf{TC}^0$ circuit into a quantum circuit that computes the same function.
With this construction, we can prove the computational hardness of learning when $G = \mathcal{O}(n\polylog(n))$ as follows.

\paragraph{State learning}
For state learning, we utilize these quantum-secure PRFs to construct pseudorandom quantum states (PRS)~[74, 76] with $G = \mathcal{O}(n\polylog(n))$ gates.
Given copies of some unknown quantum state that is promised to either be a PRS or a Haar-random state, we design a procedure that can distinguish these two cases.
The distinguisher uses our algorithm for learning states along with the SWAP test applied to the learned state and the given state~[77, 78].
Thus, we show that if our learning algorithm was able to computationally efficiently learn PRS, then we would have an efficient distinguisher between PRS and Haar-random states, contradicting the definition of a PRS~[74].

\paragraph{Unitary learning}
The proof idea in the unitary setting is similar.
In this case, we consider PRFs directly rather than the PRS construction.
Given query access to some unknown unitary that is promised to be the unitary oracle of either a PRF or a uniformly random Boolean function, we design a procedure that can distinguish these two cases.
The distinguisher uses our algorithm for learning unitaries along with the SWAP test~[77, 78].
Here, we query the given/learned unitaries on a random tensor product of single-qubit stabilizer states and conduct the SWAP test between the output states.
This way, we show that if our learning algorithm was able to computationally efficiently learn a unitary implementing a PRF, then we would have an efficient distinguisher between PRFs and uniformly random functions, which contradicts the definition of a PRF~[75].

We then go one step further and show computational hardness for circuit size $\tilde{\mathcal{O}}(G)$. To do this we rely critically on the assumption that $\mathsf{RingLWE}$ is hard not just to polynomial-time quantum algorithms, but even to quantum algorithms that run for longer (sub-exponential) time. This allows us to take a much smaller input size to the PRS/PRF in our previous constructions (i.e., over $\mathcal{O}(G)$ qubits which can be implemented with $\tilde{\bigo}(G)$ gates).
The sub-exponential computational hardness of $\mathsf{RingLWE}$ then implies that solving the learning tasks requires time exponential in $G$.

Meanwhile, for $G=\mathcal{O}(\log n)$, the learning tasks can be solved efficiently by junta learning and standard tomography methods.
This establishes $\log n$ circuit complexity as a transition point of computational efficiency.
This also implies that the circuit complexity of the PRS/PRF constructions in [32, 76] is optimal up to logarithmic factors, otherwise it would contradict efficient tomography of $\bigo(\log n)$-complexity states/unitaries.
Finally, we note that the PRS/PRF we consider can be implemented with a similar number of Clifford and T gates, extending our results to Clifford+T circuits.

\section{Outlook}}
Our work provides a new, more fine-grained perspective on the fundamental problems of state and process tomography by analyzing them for the broad and physically realistic class of bounded-complexity states and unitaries.
It complements existing literature on learning restricted classes of states/unitaries or their properties.
Examples include stabilizer circuits and states~[79, 80, 81, 82], Clifford circuits with few non-Clifford T gates and their output states~[58, 83, 84, 85], matrix product operators~[24] and states~[86, 87], phase states~[88, 80, 89, 90], outputs of shallow quantum circuits [91], PAC learning quantum states [92], shadow tomography~[93], classical shadow formalism~[68, 14, 94, 95], and property prediction of the outputs of quantum processes~[96, 97, 98].
It also raises many interesting questions for future research.

Firstly, given our results for learning pure states and unitaries of bounded complexity, it becomes natural to ask the analogous question about mixed states and channels. As our learning algorithms based on hypothesis selection and classical shadows rely on the purity/unitarity of the unknown state/process, it seems that different algorithmic approaches would be needed to go beyond states of constant rank.
Moreover, while our results show that learners using only single-copy measurements and no coherent quantum processing can achieve  optimal sample/query complexity (in $G$) for pure state/unitary learning (in line with the state tomography protocol in [20], which uses at most $\mathrm{rank}(\rho)$ copies at a time for the tomography of general state $\rho$), quantum-enhanced learners, using multi-copy measurements and coherent processing, may have an advantage in the case of mixed states and channels. Such a quantum advantage is known for general mixed state tomography [99, 100] and in certain channel learning scenarios [101, 96, 98, 102, 103, 104, 105], however, to our knowledge not yet under assumptions of bounded complexity.

Secondly, there are two regimes of interest in which our results may be further extended. On the one hand, while we establish computational efficiency transition for state and unitary learning at logarithmic circuit complexity, we leave open the question of computationally efficient learning with constraints beyond circuit complexity (e.g., constant-depth circuits where the gates are spread out).
On the other hand, our adaptation of the bootstrap strategy from [21] to average-case unitary learning achieves Heisenberg scaling only at the cost of a dimension-dependent factor.
Given recent work in state shadow tomography [106, 107, 108], it may not be possible to find a learner free from this dimensional factor while achieving the $\epsilon^{-1}$ scaling.
Finding such a learner or disproving its existence could serve as an important contribution to recent progress on Heisenberg-limited learning in different scenarios [109, 110, 111].

Thirdly, can we make learning even more efficient if the circuit structure is fixed and known in advance? Our upper bound already implies an algorithm with $\tilde{\bigo}(G)$ sample complexity for fixed circuit structure, but the lower bound proof crucially relies on the ability to place gates freely in the construction of the packing net.
A particular fixed circuit structure of physical relevance is the brickwork circuit [112]. In \Cref{app:brickwork}, we give preliminary results showing that if an $n$-qubit $G$-gate brickwork circuit suffices to implement an approximate unitary $t$-design [113], then the metric entropy of this unitary class with respect to $\davg$ is lower bounded by $\Omega(tn)$.
Considering the known lower bound of $G\geq \tilde{\Omega}(tn)$ on the size of brickwork circuits implementing $t$-designs [113], whose tightness is still an open problem [114], this may hint at a similar $\tilde{\Theta}(G)$ sample complexity of learning brickwork circuits.

Lastly, we outline a potential connection to the Brown-Susskind conjecture [115, 116] originating from the wormhole-growth paradox in holographic duality [117, 118, 119, 120]. Informally, the conjecture states that the complexity of a generic local quantum circuit grows linearly with the number of $2$-qubit gates for an exponentially long time, dual to the steady growth of a wormhole's volume in the bulk theory.
With ``complexity'' understood as ``circuit complexity'' [119], this conjecture has recently been confirmed [121, 122, 123].
Our work suggests an alternative approach to the Brown-Susskind conjecture. Namely, we have demonstrated that the complexity of learning quantum circuits grows linearly with the number of local gates in the worst case. If our bounds were extended to hold with high probability over random circuits with $G$ gates, this would yield a sample complexity version of the Brown-Susskind conjecture, suggesting the complexity of learning as a dual of the wormhole volume.

Via these open questions, tomography problems dating back to the early days of quantum computation and information connect closely to different avenues of current research in the field. Consequently, answering these questions will shed new light on fundamental quantum physics as well as on the frontiers of quantum complexity and quantum learning.

\vspace{2em}
\section*{Acknowledgments}}
The authors thank John Preskill for valuable feedback and continuous support throughout this project.
The authors also thank Ryan Babbush, Yiyi Cai, Charles Cao, Alexandru Gheorghiu, András Gilyén, Alex B. Grilo, Jerry Huang, Nadine Meister, Chris Pattison, Alexander Poremba, Xiao-Liang Qi, Ruohan Shen, Mehdi Soleimanifar, Yu Tong, Tzu-Chieh Wei, Tai-Hsuan Yang, Nengkun Yu for fruitful discussions.
HZ was supported by a Caltech Summer Undergraduate Research Fellowship (SURF).
LL was supported by a Mellon Mays Undergraduate Fellowship.
HH was supported by a Google PhD fellowship and a MediaTek Research Young Scholarship.
HH acknowledges the visiting associate position at the Massachusetts Institute of Technology.
MCC was supported by a DAAD PRIME fellowship.
This work was done (in part) while a subset of the authors were visiting the Simons Institute for the Theory of Computing.
The Institute for Quantum Information and Matter is an NSF Physics Frontiers Center.

\newpage
\bibliographystyle{unsrt}
\let\oldaddcontentsline\addcontentsline% Store \addcontentsline
\renewcommand{\addcontentsline}[3]{}% Make \addcontentsline a no-op
\begin{thebibliography}{100}

[1]
Konrad Banaszek, Marcus Cramer, and David Gross.
\newblock Focus on quantum tomography.
\newblock {\em New Journal of Physics}, 15(12):125020, 2013.

[2]
Robin Blume-Kohout.
\newblock Optimal, reliable estimation of quantum states.
\newblock {\em New Journal of Physics}, 12(4):043034, 2010.

[3]
David Gross, Yi-Kai Liu, Steven~T Flammia, Stephen Becker, and Jens Eisert.
\newblock Quantum state tomography via compressed sensing.
\newblock {\em Physical review letters}, 105(15):150401, 2010.

[4]
Zdenek Hradil.
\newblock Quantum-state estimation.
\newblock {\em Physical Review A}, 55(3):R1561, 1997.

[5]
Masoud Mohseni, Ali~T Rezakhani, and Daniel~A Lidar.
\newblock Quantum-process tomography: Resource analysis of different
\newblock {\em Physical Review A}, 77(3):032322, 2008.

[6]
Jeremy~L O'Brien, Geoff~J Pryde, Alexei Gilchrist, Daniel~FV James, Nathan~K
Langford, Timothy~C Ralph, and Andrew~G White.
\newblock Quantum process tomography of a controlled-not gate.
\newblock {\em Physical review letters}, 93(8):080502, 2004.

[7]
Andrew~James Scott.
\newblock Optimizing quantum process tomography with unitary 2-designs.
\newblock {\em Journal of Physics A: Mathematical and Theoretical},
41(5):055308, 2008.

[8]
Isaac~L Chuang and Michael~A Nielsen.
\newblock Prescription for experimental determination of the dynamics of a
quantum black box.
\newblock {\em Journal of Modern Optics}, 44(11-12):2455--2467, 1997.

[9]
GM~D'Ariano and P~Lo Presti.
\newblock Quantum tomography for measuring experimentally the matrix elements
of an arbitrary quantum operation.
\newblock {\em Physical review letters}, 86(19):4195, 2001.

[10]
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.
\newblock Quantum metrology.
\newblock {\em Physical review letters}, 96(1):010401, 2006.

[11]
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.
\newblock Advances in quantum metrology.
\newblock {\em Nature photonics}, 5(4):222--229, 2011.

[12]
Christian Kokail, Rick van Bijnen, Andreas Elben, Beno{\^\i}t Vermersch, and
Peter Zoller.
\newblock Entanglement {Hamiltonian} tomography in quantum simulation.
\newblock {\em Nature Physics}, 17(8):936--942, 2021.

[13]
Jose Carrasco, Andreas Elben, Christian Kokail, Barbara Kraus, and Peter
\newblock Theoretical and experimental perspectives of quantum verification.
\newblock {\em PRX Quantum}, 2(1):010102, 2021.

[14]
Ryan Levy, Di~Luo, and Bryan~K Clark.
\newblock Classical shadows for quantum process tomography on near-term quantum
\newblock {\em arXiv preprint arXiv:2110.02965}, 2021.

[15]
Seth~T Merkel, Jay~M Gambetta, John~A Smolin, Stefano Poletto, Antonio~D
C{\'o}rcoles, Blake~R Johnson, Colm~A Ryan, and Matthias Steffen.
\newblock Self-consistent quantum process tomography.
\newblock {\em Physical Review A}, 87(6):062119, 2013.

[16]
Robin Blume-Kohout, John~King Gamble, Erik Nielsen, Kenneth Rudinger, Jonathan
Mizrahi, Kevin Fortier, and Peter Maunz.
\newblock Demonstration of qubit operations below a rigorous fault tolerance
threshold with gate set tomography.
\newblock {\em Nature communications}, 8(1):14485, 2017.

[17]
Hsin-Yuan Huang, Steven~T Flammia, and John Preskill.
\newblock Foundations for learning from noisy quantum experiments.
\newblock {\em arXiv preprint arXiv:2204.13691}, 2022.

[18]
Zhenyu Cai, Ryan Babbush, Simon~C Benjamin, Suguru Endo, William~J Huggins,
Ying Li, Jarrod~R McClean, and Thomas~E O'Brien.
\newblock Quantum error mitigation.
\newblock {\em arXiv preprint arXiv:2210.00921}, 2022.

[19]
Jeongwan Haah, Aram~W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu.
\newblock Sample-optimal tomography of quantum states.
\newblock {\em IEEE Transactions on Information Theory}, 63(9):5628--5641,

[20]
Ryan O'Donnell and John Wright.
\newblock Efficient quantum tomography.
\newblock In {\em Proceedings of the forty-eighth annual ACM symposium on
Theory of Computing}, pages 899--912, 2016.

[21]
Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang.
\newblock Query-optimal estimation of unitary channels in diamond distance.
\newblock {\em arXiv preprint arXiv:2302.14066}, 2023.

[22]
John Bardeen, Leon~N Cooper, and John~Robert Schrieffer.
\newblock Theory of superconductivity.
\newblock {\em Physical review}, 108(5):1175, 1957.

[23]
Rom{\'a}n Or{\'u}s.
\newblock A practical introduction to tensor networks: Matrix product states
and projected entangled pair states.
\newblock {\em Annals of physics}, 349:117--158, 2014.

[24]
Giacomo Torlai, Christopher~J Wood, Atithi Acharya, Giuseppe Carleo, Juan
Carrasquilla, and Leandro Aolita.
\newblock Quantum process tomography with unsupervised learning and tensor
\newblock {\em Nature Communications}, 14(1):2858, 2023.

[25]
Giuseppe Carleo and Matthias Troyer.
\newblock Solving the quantum many-body problem with artificial neural
\newblock {\em Science}, 355(6325):602--606, 2017.

[26]
Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger
Melko, and Giuseppe Carleo.
\newblock Neural-network quantum state tomography.
\newblock {\em Nat. Phys.}, 14(5):447, 2018.

[27]
Haimeng Zhao, Giuseppe Carleo, and Filippo Vicentini.
\newblock Empirical sample complexity of neural network mixed state
\newblock {\em arXiv preprint arXiv:2307.01840}, 2023.

[28]
Fernando~GSL Brand{\~a}o, Wissam Chemissany, Nicholas Hunter-Jones, Richard
Kueng, and John Preskill.
\newblock Models of quantum complexity growth.
\newblock {\em PRX Quantum}, 2(3):030316, 2021.

[29]
David Poulin, Angie Qarry, Rolando Somma, and Frank Verstraete.
\newblock Quantum simulation of time-dependent {Hamiltonians} and the
convenient illusion of {Hilbert} space.
\newblock {\em Physical review letters}, 106(17):170501, 2011.

[30]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev.
\newblock On ideal lattices and learning with errors over rings.
\newblock In {\em Advances in Cryptology--EUROCRYPT 2010: 29th Annual
International Conference on the Theory and Applications of Cryptographic
Techniques, French Riviera, May 30--June 3, 2010. Proceedings 29}, pages
1--23. Springer, 2010.

[31]
Oded Regev.
\newblock On lattices, learning with errors, random linear codes, and
\newblock {\em Journal of the ACM (JACM)}, 56(6):1--40, 2009.

[32]
Srinivasan Arunachalam, Alex~Bredariol Grilo, and Aarthi Sundaram.
\newblock Quantum hardness of learning shallow classical circuits.
\newblock {\em SIAM Journal on Computing}, 50(3):972--1013, 2021.

[33]
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, and Lisheng Ren.
\newblock Cryptographic hardness of learning halfspaces with massart noise.
\newblock {\em Advances in Neural Information Processing Systems},
35:3624--3636, 2022.

[34]
Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra
Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, and Vinod
\newblock Lattice problems beyond polynomial time.
\newblock In {\em Proceedings of the 55th Annual ACM Symposium on Theory of
Computing}, pages 1516--1526, 2023.

[35]
Prabhanjan Ananth, Alexander Poremba, and Vinod Vaikuntanathan.
\newblock Revocable cryptography from learning with errors.
\newblock {\em arXiv preprint arXiv:2302.14860}, 2023.

[36]
Anurag Anshu and Srinivasan Arunachalam.
\newblock A survey on the complexity of learning quantum states.
\newblock {\em arXiv preprint arXiv:2305.20069}, 2023.

[37]
Kyle Poland, Kerstin Beer, and Tobias~J Osborne.
\newblock No free lunch for quantum machine learning.
\newblock {\em arXiv preprint arXiv:2003.14103}, 2020.

[38]
Kunal Sharma, Marco Cerezo, Zo{\"e} Holmes, Lukasz Cincio, Andrew Sornborger,
and Patrick~J Coles.
\newblock Reformulation of the no-free-lunch theorem for entangled datasets.
\newblock {\em Physical Review Letters}, 128(7):070501, 2022.

[39]
Nengkun Yu and Tzu-Chieh Wei.
\newblock Learning marginals suffices!
\newblock {\em arXiv preprint arXiv:2303.08938}, 2023.

[40]
Roman Vershynin.
\newblock {\em High-dimensional probability}, volume~47 of {\em Cambridge
Series in Statistical and Probabilistic Mathematics}.
\newblock Cambridge University Press, Cambridge, 2018.

[41]
Costin B{\u{a}}descu and Ryan O'Donnell.
\newblock Improved quantum data analysis.
\newblock In {\em Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory
of Computing}, pages 1398--1411, 2021.

[42]
Thomas Chen, Shivam Nadimpalli, and Henry Yuen.
\newblock Testing and learning quantum juntas nearly optimally.
\newblock In {\em Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA)}, pages 1163--1185. SIAM, 2023.

[43]
Joran van Apeldoorn.
\newblock {\em A quantum view on convex optimization}.
\newblock PhD thesis, University of Amsterdam, 2019.

[44]
Andris Ambainis.
\newblock Quantum lower bounds by quantum arguments.
\newblock In {\em Proceedings of the thirty-second annual ACM symposium on
Theory of computing}, pages 636--643, 2000.

[45]
Aleksandrs Belovs.
\newblock Variations on quantum adversary.
\newblock {\em arXiv preprint arXiv:1504.06943}, 2015.

[46]
Peter Hoyer, Troy Lee, and Robert Spalek.
\newblock Negative weights make adversaries stronger.
\newblock In {\em Proceedings of the thirty-ninth annual ACM symposium on
Theory of computing}, pages 526--535, 2007.

[47]
Man-Duen Choi.
\newblock Completely positive linear maps on complex matrices.
\newblock {\em Linear algebra and its applications}, 10(3):285--290, 1975.

[48]
Andrzej Jamio{\l}kowski.
\newblock Linear transformations which preserve trace and positive
semidefiniteness of operators.
\newblock {\em Reports on Mathematical Physics}, 3(4):275--278, 1972.

[49]
Min Jiang, Shunlong Luo, and Shuangshuang Fu.
\newblock Channel-state duality.
\newblock {\em Physical Review A}, 87(2):022310, 2013.

[50]
Dominic~W Berry, Andrew~M Childs, and Robin Kothari.
\newblock Hamiltonian simulation with nearly optimal dependence on all
\newblock In {\em 2015 IEEE 56th Annual Symposium on Foundations of Computer
Science}, pages 792--809. IEEE, 2015.

[51]
Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando~D Somma, and David
\newblock Efficient discrete-time simulations of continuous-time quantum query
\newblock In {\em Proceedings of the forty-first annual ACM symposium on Theory
of computing}, pages 409--416, 2009.

[52]
Jessica Bavaresco, Mio Murao, and Marco~T{\'u}lio Quintino.
\newblock Unitary channel discrimination beyond group structures: Advantages of
sequential and indefinite-causal-order strategies.
\newblock {\em Journal of Mathematical Physics}, 63(4), 2022.

[53]
Lisa Yang and Netta Engelhardt.
\newblock The complexity of learning (pseudo) random dynamics of black holes
and other chaotic systems.
\newblock {\em arXiv preprint arXiv:2302.11013}, 2023.

[54]
Wei-Ting Kuo, AA~Akhtar, Daniel~P Arovas, and Yi-Zhuang You.
\newblock Markovian entanglement dynamics under locally scrambled quantum
\newblock {\em Physical Review B}, 101(22):224202, 2020.

[55]
Hong-Ye Hu, Soonwon Choi, and Yi-Zhuang You.
\newblock Classical shadow tomography with locally scrambled quantum dynamics.
\newblock {\em Physical Review Research}, 5(2):023027, 2023.

[56]
Matthias~C. Caro, Hsin-Yuan Huang, Nicholas Ezzell, Joe Gibbs, Andrew~T.
Sornborger, Lukasz Cincio, Patrick~J. Coles, and Zoë Holmes.
\newblock Out-of-distribution generalization for learning quantum dynamics.
\newblock {\em Nature Communications}, 14, 2023.

[57]
Zhan Yu, Xuanqiang Zhao, Benchi Zhao, and Xin Wang.
\newblock Optimal quantum dataset for learning a unitary transformation.
\newblock {\em Physical Review Applied}, 19(3):034017, 2023.

[58]
Ching-Yi Lai and Hao-Chung Cheng.
\newblock Learning quantum circuits of some t gates.
\newblock {\em IEEE Transactions on Information Theory}, 68(6):3951--3964,

[59]
David Pollard.
\newblock Convergence of stochastic processes.
\newblock {\em Springer Series in Statistics}, 1984.

[60]
Michael~J Kearns and Robert~E Schapire.
\newblock Efficient distribution-free learning of probabilistic concepts.
\newblock {\em Journal of Computer and System Sciences}, 48(3):464--497, 1994.

[61]
Matthias~C Caro and Ishaun Datta.
\newblock Pseudo-dimension of quantum circuits.
\newblock {\em Quantum Machine Intelligence}, 2(2):14, 2020.

[62]
Martin Anthony, Peter~L Bartlett, Peter~L Bartlett, et~al.
\newblock {\em Neural network learning: Theoretical foundations}.
\newblock Cambridge University Press, 1999.

[63]
Philipp Grohs and Gitta Kutyniok.
\newblock {\em Mathematical aspects of deep learning}.
\newblock Cambridge University Press, 2022.

[64]
Lukas Gonon and Antoine Jacquier.
\newblock Universal approximation theorem and error bounds for quantum neural
networks and quantum reservoirs.
\newblock {\em arXiv preprint arXiv:2307.12904}, 2023.

[65]
Adri{\'a}n P{\'e}rez-Salinas, David L{\'o}pez-N{\'u}{\~n}ez, Artur
Garc{\'\i}a-S{\'a}ez, Pol Forn-D{\'\i}az, and Jos{\'e}~I Latorre.
\newblock One qubit as a universal approximant.
\newblock {\em Physical Review A}, 104(1):012405, 2021.

[66]
Maria Schuld, Ryan Sweke, and Johannes~Jakob Meyer.
\newblock Effect of data encoding on the expressive power of variational
quantum-machine-learning models.
\newblock {\em Physical Review A}, 103(3):032430, 2021.

[67]
Alberto Manzano, David Dechant, Jordi Tura, and Vedran Dunjko.
\newblock Parametrized quantum circuits and their approximation capacities in
the context of quantum machine learning.
\newblock {\em arXiv preprint arXiv:2307.14792}, 2023.

[68]
Hsin-Yuan Huang, Richard Kueng, and John Preskill.
\newblock Predicting many properties of a quantum system from very few
\newblock {\em Nature Physics}, 16(10):1050--1057, 2020.

[69]
Carl~W. Helstrom.
\newblock Quantum detection and estimation theory.
\newblock {\em J. Statist. Phys.}, 1:231--252, 1969.

[70]
Vivek~V Shende, Stephen~S Bullock, and Igor~L Markov.
\newblock Synthesis of quantum logic circuits.
\newblock In {\em Proceedings of the 2005 Asia and South Pacific Design
Automation Conference}, pages 272--275, 2005.

[71]
A.~S. Holevo.
\newblock {Some estimates of the information transmitted by quantum
communication channels}.
\newblock {\em Probl. Inf. Transm.}, 9(3):177--183, 1973.

[72]
Jeongwan Haah, Aram~W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu.
\newblock Sample-optimal tomography of quantum states.
\newblock In {\em Proceedings of the forty-eighth annual ACM symposium on
Theory of Computing}, pages 913--925, 2016.

[73]
Juha~J Vartiainen, Mikko M{\"o}tt{\"o}nen, and Martti~M Salomaa.
\newblock Efficient decomposition of quantum gates.
\newblock {\em Physical review letters}, 92(17):177902, 2004.

[74]
Zhengfeng Ji, Yi-Kai Liu, and Fang Song.
\newblock Pseudorandom quantum states.
\newblock In {\em Advances in Cryptology--CRYPTO 2018: 38th Annual
International Cryptology Conference, Santa Barbara, CA, USA, August 19--23,
2018, Proceedings, Part III 38}, pages 126--152. Springer, 2018.

[75]
Oded Goldreich, Shafi Goldwasser, and Silvio Micali.
\newblock How to construct random functions.
\newblock {\em Journal of the ACM (JACM)}, 33(4):792--807, 1986.

[76]
Zvika Brakerski and Omri Shmueli.
\newblock (pseudo) random quantum states with binary phase.
\newblock In {\em Theory of Cryptography Conference}, pages 229--250. Springer,

[77]
Adriano Barenco, Andre Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa,
and Chiara Macchiavello.
\newblock Stabilization of quantum computations by symmetrization.
\newblock {\em SIAM Journal on Computing}, 26(5):1541--1557, 1997.

[78]
Harry Buhrman, Richard Cleve, John Watrous, and Ronald De~Wolf.
\newblock Quantum fingerprinting.
\newblock {\em Physical Review Letters}, 87(16):167902, 2001.

[79]
Scott Aaronson and Daniel Gottesman.
\newblock Improved simulation of stabilizer circuits.
\newblock {\em Phys. Rev. A}, 70(5):052328, 2004.

[80]
Ashley Montanaro.
\newblock Learning stabilizer states by bell sampling.
\newblock {\em arXiv preprint arXiv:1707.04012}, 2017.

[81]
Richard~A Low.
\newblock Learning and testing algorithms for the clifford group.
\newblock {\em Physical Review A}, 80(5):052314, 2009.

[82]
Andrea Rocchetto.
\newblock Stabiliser states are efficiently pac-learnable.
\newblock {\em Quantum Info. Comput.}, 18(7–8):541–552, June 2018.

[83]
Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.
\newblock Efficient learning of quantum states prepared with few non-clifford
\newblock {\em arXiv preprint arXiv:2305.13409}, 2023.

[84]
Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang.
\newblock Efficient learning of quantum states prepared with few non-clifford
gates ii: Single-copy measurements.
\newblock {\em arXiv preprint arXiv:2308.07175}, 2023.

[85]
Dominik Hangleiter and Michael~J Gullans.
\newblock Bell sampling from quantum circuits.
\newblock {\em arXiv preprint arXiv:2306.00083}, 2023.

[86]
Marcus Cramer, Martin~B Plenio, Steven~T Flammia, Rolando Somma, David Gross,
Stephen~D Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu.
\newblock Efficient quantum state tomography.
\newblock {\em Nature communications}, 1(1):149, 2010.

[87]
Olivier Landon-Cardinal, Yi-Kai Liu, and David Poulin.
\newblock Efficient direct tomography for matrix product states.
\newblock {\em arXiv preprint arXiv:1002.4632}, 2010.

[88]
Ethan Bernstein and Umesh Vazirani.
\newblock Quantum complexity theory.
\newblock In {\em Proceedings of the twenty-fifth annual ACM symposium on
Theory of computing}, pages 11--20, 1993.

[89]
Martin R{\"o}tteler.
\newblock Quantum algorithms to solve the hidden shift problem for quadratics
and for functions of large gowers norm.
\newblock In {\em International Symposium on Mathematical Foundations of
Computer Science}, pages 663--674. Springer, 2009.

[90]
Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore~J. Yoder.
\newblock {Optimal Algorithms for Learning Quantum Phase States}.
\newblock In Omar Fawzi and Michael Walter, editors, {\em 18th Conference on
the Theory of Quantum Computation, Communication and Cryptography (TQC
2023)}, volume 266 of {\em Leibniz International Proceedings in Informatics
(LIPIcs)}, pages 3:1--3:24, Dagstuhl, Germany, 2023. Schloss Dagstuhl --
Leibniz-Zentrum f{\"u}r Informatik.

[91]
Cambyse Rouz{\'e} and Daniel~Stilck Fran{\c{c}}a.
\newblock Learning quantum many-body systems from a few copies.
\newblock {\em arXiv preprint arXiv:2107.03333}, 2021.

[92]
Scott Aaronson.
\newblock The learnability of quantum states.
\newblock {\em Proceedings of the Royal Society A: Mathematical, Physical and
Engineering Sciences}, 463(2088):3089--3114, 2007.

[93]
Scott Aaronson.
\newblock Shadow tomography of quantum states.
\newblock In {\em STOC}, pages 325--338, 2018.

[94]
Andreas Elben, Steven~T Flammia, Hsin-Yuan Huang, Richard Kueng, John Preskill,
Beno{\^\i}t Vermersch, and Peter Zoller.
\newblock The randomized measurement toolbox.
\newblock {\em Nature Review Physics}, 2022.

[95]
Jonathan Kunjummen, Minh~C Tran, Daniel Carney, and Jacob~M Taylor.
\newblock Shadow process tomography of quantum channels.
\newblock {\em Physical Review A}, 107(4):042403, 2023.

[96]
Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud
Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et~al.
\newblock Quantum advantage in learning from experiments.
\newblock {\em Science}, 376(6598):1182--1186, 2022.

[97]
Hsin-Yuan Huang, Sitan Chen, and John Preskill.
\newblock Learning to predict arbitrary quantum processes.
\newblock {\em arXiv preprint arXiv:2210.14894}, 2022.

[98]
Matthias~C Caro.
\newblock Learning quantum processes and hamiltonians via the pauli transfer
\newblock {\em arXiv preprint arXiv:2212.04471}, 2022.

[99]
Sitan Chen, Jerry Li, Brice Huang, and Allen Liu.
\newblock Tight bounds for quantum state certification with incoherent
\newblock In {\em 2022 IEEE 63rd Annual Symposium on Foundations of Computer
Science (FOCS)}, pages 1205--1213. IEEE, 2022.

[100]
Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke.
\newblock When does adaptivity help for quantum state learning?, 2023.

[101]
Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li.
\newblock Exponential separations between learning with and without quantum
\newblock In {\em 2021 IEEE 62nd Annual Symposium on Foundations of Computer
Science (FOCS)}, pages 574--585. IEEE, 2022.

[102]
Kean Chen, Qisheng Wang, Peixun Long, and Mingsheng Ying.
\newblock Unitarity estimation for quantum channels.
\newblock {\em IEEE Transactions on Information Theory}, 69(8):5116--5134,

[103]
Omar Fawzi, Aadil Oufkir, and Daniel~Stilck Fran{\c{c}}a.
\newblock Lower bounds on learning pauli channels.
\newblock {\em arXiv preprint arXiv:2301.09192}, 2023.

[104]
Omar Fawzi, Nicolas Flammarion, Aur{\'e}lien Garivier, and Aadil Oufkir.
\newblock Quantum channel certification with incoherent measurements.
\newblock In Gergely Neu and Lorenzo Rosasco, editors, {\em Proceedings of
Thirty Sixth Conference on Learning Theory}, volume 195 of {\em Proceedings
of Machine Learning Research}, pages 1822--1884. PMLR, 12--15 Jul 2023.

[105]
Aadil Oufkir.
\newblock Sample-optimal quantum process tomography with non-adaptive
incoherent measurements.
\newblock {\em arXiv preprint arXiv:2301.12925}, 2023.

[106]
Joran van Apeldoorn.
\newblock Quantum probability oracles \& multidimensional amplitude estimation.
\newblock In {\em 16th Conference on the Theory of Quantum Computation,
Communication and Cryptography (TQC 2021)}. Schloss Dagstuhl-Leibniz-Zentrum
f{\"u}r Informatik, 2021.

[107]
William~J Huggins, Kianna Wan, Jarrod McClean, Thomas~E O’Brien, Nathan
Wiebe, and Ryan Babbush.
\newblock Nearly optimal quantum algorithm for estimating multiple expectation
\newblock {\em Physical Review Letters}, 129(24):240501, 2022.

[108]
Joran van Apeldoorn, Arjan Cornelissen, Andr{\'a}s Gily{\'e}n, and Giacomo
\newblock Quantum tomography using state-preparation unitaries.
\newblock In {\em Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA)}, pages 1265--1318. SIAM, 2023.

[109]
Hsin-Yuan Huang, Yu~Tong, Di~Fang, and Yuan Su.
\newblock Learning many-body hamiltonians with heisenberg-limited scaling.
\newblock {\em Physical Review Letters}, 130(20):200403, 2023.

[110]
Alicja Dutkiewicz, Thomas~E O'Brien, and Thomas Schuster.
\newblock The advantage of quantum control in many-body {Hamiltonian} learning.
\newblock {\em arXiv preprint arXiv:2304.07172}, 2023.

[111]
Haoya Li, Yu~Tong, Hongkang Ni, Tuvia Gefen, and Lexing Ying.
\newblock Heisenberg-limited {Hamiltonian} learning for interacting bosons.
\newblock {\em arXiv preprint arXiv:2307.04690}, 2023.

[112]
Matthew~PA Fisher, Vedika Khemani, Adam Nahum, and Sagar Vijay.
\newblock Random quantum circuits.
\newblock {\em Annual Review of Condensed Matter Physics}, 14:335--379, 2023.

[113]
Fernando~GSL Brandao, Aram~W Harrow, and Micha{\l} Horodecki.
\newblock Local random quantum circuits are approximate polynomial-designs.
\newblock {\em Communications in Mathematical Physics}, 346:397--434, 2016.

[114]
Jonas Haferkamp.
\newblock Random quantum circuits are approximate unitary $ t $-designs in
depth {$O\left( n t^{5+ o (1)}\right)$}.
\newblock {\em Quantum}, 6:795, 2022.

[115]
Adam~R Brown and Leonard Susskind.
\newblock Second law of quantum complexity.
\newblock {\em Physical Review D}, 97(8):086015, 2018.

[116]
Leonard Susskind.
\newblock Black holes and complexity classes.
\newblock {\em arXiv preprint arXiv:1802.02175}, 2018.

[117]
Leonard Susskind.
\newblock Computational complexity and black hole horizons.
\newblock {\em Fortschritte der Physik}, 64(1):24--43, 2016.

[118]
Adam Bouland, Bill Fefferman, and Umesh Vazirani.
\newblock Computational pseudorandomness, the wormhole growth paradox, and
constraints on the ads/cft duality.
\newblock {\em arXiv preprint arXiv:1910.14646}, 2019.

[119]
Douglas Stanford and Leonard Susskind.
\newblock Complexity and shock wave geometries.
\newblock {\em Physical Review D}, 90(12):126007, 2014.

[120]
Adam~R Brown, Daniel~A Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao.
\newblock Complexity, action, and black holes.
\newblock {\em Physical Review D}, 93(8):086006, 2016.

[121]
Jonas Haferkamp, Philippe Faist, Naga~BT Kothakonda, Jens Eisert, and Nicole
\newblock Linear growth of quantum circuit complexity.
\newblock {\em Nature Physics}, 18(5):528--532, 2022.

[122]
Zhi Li.
\newblock Short proofs of linear growth of quantum circuit complexity.
\newblock {\em arXiv preprint arXiv:2205.05668}, 2022.

[123]
Jonas Haferkamp.
\newblock On the moments of random quantum circuits and robust quantum
\newblock {\em arXiv preprint arXiv:2303.16944}, 2023.

[124]
Matthias~C Caro, Hsin-Yuan Huang, Marco Cerezo, Kunal Sharma, Andrew
Sornborger, Lukasz Cincio, and Patrick~J Coles.
\newblock Generalization in quantum machine learning from few training data.
\newblock {\em Nature {C}ommunications}, 13, 2022.

[125]
Mark~M. Wilde.
\newblock {\em {Quantum Information Theory}}.
\newblock Cambridge University Press, Cambridge, 2nd edition, 2013.

[126]
John Watrous.
\newblock {\em The Theory of Quantum Information}.
\newblock Cambridge University Press, 2018.

[127]
Antonio~Anna Mele.
\newblock Introduction to haar measure tools in quantum information: A
beginner's tutorial.
\newblock {\em arXiv preprint arXiv:2307.08956}, 2023.

[128]
Thomas Barthel and Jianfeng Lu.
\newblock Fundamental limitations for measurements in quantum many-body
\newblock {\em Physical Review Letters}, 121(8):080406, 2018.

[129]
Stanislaw~J Szarek.
\newblock Nets of {Grassmann} manifold and orthogonal group.
\newblock In {\em Proceedings of research workshop on Banach space theory (Iowa
City, Iowa, 1981)}, page 169. University of Iowa Iowa City, IA, 1982.

[130]
Costin Bădescu and Ryan O'Donnell.
\newblock Improved quantum data analysis.
\newblock {\em arXiv preprint arXiv:2011.10908}, 2020.

[131]
VN~Vapnik and A~Ya Chervonenkis.
\newblock On the uniform convergence of relative frequencies of events to their
\newblock {\em Theory of Probability and its Applications}, 16(2):264, 1971.

[132]
Abhishek Banerjee, Chris Peikert, and Alon Rosen.
\newblock Pseudorandom functions and lattices.
\newblock In {\em Annual International Conference on the Theory and
Applications of Cryptographic Techniques}, pages 719--737. Springer, 2012.

[133]
Moni Naor and Omer Reingold.
\newblock Synthesizers and their application to the parallel construction of
pseudo-random functions.
\newblock {\em Journal of Computer and System Sciences}, 58(2):336--375, 1999.

[134]
Yasuhiro Takahashi, Seiichiro Tani, and Noboru Kunihiro.
\newblock Quantum addition circuits and unbounded fan-out.
\newblock {\em Quantum Info. Comput.}, 10(9):872–890, sep 2010.

[135]
Nengkun Yu, Runyao Duan, and Mingsheng Ying.
\newblock Five two-qubit gates are necessary for implementing the toffoli gate.
\newblock {\em Physical Review A}, 88(1):010304, 2013.

[136]
Paul~W Beame, Stephen~A Cook, and H~James Hoover.
\newblock Log depth circuits for division and related problems.
\newblock {\em SIAM Journal on Computing}, 15(4):994--1003, 1986.

[137]
Prabhanjan Ananth, Luowen Qian, and Henry Yuen.
\newblock Cryptography from pseudorandom quantum states.
\newblock In {\em Annual International Cryptology Conference}, pages 208--236.
Springer, 2022.

[138]
William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal.
\newblock Quantum cryptography in algorithmica.
\newblock In {\em Proceedings of the 55th Annual ACM Symposium on Theory of
Computing}, pages 1589--1602, 2023.

[139]
Tomoyuki Morimae and Takashi Yamakawa.
\newblock Quantum commitments and signatures without one-way functions.
\newblock In {\em Annual International Cryptology Conference}, pages 269--295.
Springer, 2022.

[140]
William Kretschmer.
\newblock {Quantum Pseudorandomness and Classical Complexity}.
\newblock In Min-Hsiu Hsieh, editor, {\em 16th Conference on the Theory of
Quantum Computation, Communication and Cryptography (TQC 2021)}, volume 197
of {\em Leibniz International Proceedings in Informatics (LIPIcs)}, pages
2:1--2:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl -- Leibniz-Zentrum
f{\"u}r Informatik.

[141]
Srinivasan Arunachalam and Ronald de~Wolf.
\newblock Optimal quantum sample complexity of learning algorithms.
\newblock {\em arXiv preprint arXiv:1607.00932}, 2016.

[142]
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert~E. Schapire,
and Linda Sellie.
\newblock On the learnability of discrete distributions.
\newblock In {\em Proceedings of the Twenty-Sixth Annual ACM Symposium on
Theory of Computing}, STOC '94, page 273–282, New York, NY, USA, 1994.
Association for Computing Machinery.

[143]
Michael Foss-Feig, David Hayes, Joan~M Dreiling, Caroline Figgatt, John~P
Gaebler, Steven~A Moses, Juan~M Pino, and Andrew~C Potter.
\newblock Holographic quantum algorithms for simulating correlated spin
\newblock {\em Physical Review Research}, 3(3):033002, 2021.

[144]
Christian Sch{\"o}n, Enrique Solano, Frank Verstraete, J~Ignacio Cirac, and
Michael~M Wolf.
\newblock Sequential generation of entangled multiqubit states.
\newblock {\em Physical review letters}, 95(11):110503, 2005.

[145]
A.~S. Holevo.
\newblock Statistical decision theory for quantum systems.
\newblock {\em J. Multivariate Anal.}, 3:337--394, 1973.

[146]
Michel Boyer, Gilles Brassard, Peter H{\o}yer, and Alain Tapp.
\newblock Tight bounds on quantum searching.
\newblock {\em Fortschritte der Physik: Progress of Physics}, 46(4-5):493--505,

[147]
Craig Gidney.
\newblock Constructing large controlled nots, 2015.
\newblock
\url{https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots.html}.
Accessed: 2023-08-20.

[148]
Mark~M Wilde.
\newblock {\em Quantum information theory}.
\newblock Cambridge university press, 2013.

[149]
Michael~M. Wolf.
\newblock Quantum channels and operations - guided tour, 7 2012.

[150]
John Wright.
\newblock {\em How to learn a quantum state}.
\newblock PhD thesis, Carnegie Mellon University, 2016.

[151]
Hsin-Yuan Huang, Richard Kueng, and John Preskill.
\newblock Information-theoretic bounds on quantum advantage in machine
\newblock {\em Physical Review Letters}, 126(19):190505, 2021.

[152]
\newblock {On Spaces of Linear Transformations with Bounded Rank}.
\newblock {\em Journal of the London Mathematical Society}, s1-37(1):10--16, 01

[153]
Alexandros Eskenazis, Paata Ivanisvili, and Lauritz Streck.
\newblock Low-degree learning and the metric entropy of polynomials.
\newblock {\em arXiv preprint arXiv:2203.09659}, 2022.

[154]
Gyora~M Benedek and Alon Itai.
\newblock Learnability with respect to fixed distributions.
\newblock {\em Theoretical Computer Science}, 86(2):377--389, 1991.

[155]
Thomas~M Cover and Joy~A. Thomas.
\newblock {\em Elements of information theory}.
\newblock John Wiley \& Sons, 1999.

[156]
Peter~L Bartlett, Philip~M Long, and Robert~C Williamson.
\newblock Fat-shattering and the learnability of real-valued functions.
\newblock In {\em Proceedings of the seventh annual conference on Computational
learning theory}, pages 299--310, 1994.

[157]
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.
\newblock Quantum random access memory.
\newblock {\em Physical review letters}, 100(16):160501, 2008.

[158]
Adri{\'a}n P{\'e}rez-Salinas, Alba Cervera-Lierta, Elies Gil-Fuster, and
Jos{\'e}~I Latorre.
\newblock Data re-uploading for a universal quantum classifier.
\newblock {\em Quantum}, 4:226, 2020.

[159]
Matthias~C. Caro, Elies Gil-Fuster, Johannes~Jakob Meyer, Jens Eisert, and Ryan
\newblock Encoding-dependent generalization bounds for parametrized quantum
\newblock {\em {Quantum}}, 5, 2021.

[160]
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.
\newblock {\em Foundations of machine learning}.
\newblock The MIT Press, 2018.

[161]
Michael~M Wolf.
\newblock Mathematical foundations of machine learning, 2018.

[162]
Paul~W Goldberg and Mark~R Jerrum.
\newblock Bounding the {Vapnik-Chervonenkis} dimension of concept classes
parameterized by real numbers.
\newblock {\em Machine Learning}, 18(2-3):131--148, 1995.

[163]
Hugh~E. Warren.
\newblock Lower bounds for approximation by nonlinear manifolds.
\newblock {\em Transactions of the American Mathematical Society},
133(1):167--178, 1968.

[164]
Dmitry Yarotsky.
\newblock Error bounds for approximations with deep relu networks.
\newblock {\em Neural Networks}, 94:103--114, 2017.

\end{thebibliography}

\let\addcontentsline\oldaddcontentsline% Restore \addcontentsline

\newpage
\appendix
\appendixpage

\tableofcontents

\section{Preliminaries}

Throughout the appendices, we use $d=2^n$ to denote the dimension of the $n$-qubit Hilbert space unless otherwise stated.

\subsection{Distance metrics}

Here we review some distance metrics and their properties used throughout our proofs.
In the main text we have already introduced the trace distance
\begin{equation}
\dtr(\ket{\psi}, \ket{\phi})
=\frac{1}{2} \|\ketbra{\psi} - \ketbra{\phi}\|_1 \, ,
\end{equation}
which is analogously defined for density matrices as $\dtr(\rho, \sigma) = \norm{\rho - \sigma}_1/2$, the diamond distance
\begin{equation}
\dworst(U, V) = \max_{\rho} \|(U\otimes I)\rho(U\otimes I)^\dagger - (V\otimes I)\rho(V\otimes I)^\dagger\|_1\, ,
\end{equation}
and the root mean squared trace distance
\begin{equation}
\davg(U, V) = \sqrt{\E_{\ket{\psi}}[\dtr(U\ket{\psi}, V\ket{\psi})^2]}
\end{equation}
where the expectation is taken over Haar measure\footnote{Due to the concentration of Lipschitz functions on inputs drawn from the Haar measure, controlling this root mean squared distance also leads to error bounds that hold with high probability over random input states.}.

Apart from these, we also use the following auxiliary distance metrics.
We define the quotient spectral distance
\begin{equation}
d_2'(U, V)
= \min_{e^{i\phi}\in U(1)}\|U-e^{i\phi}V\|
\end{equation}
to be the spectral distance $d_2(U, V) = \|U-V\|$ up to a global phase.
Similarly, we define the quotient normalized Frobenius distance
\begin{equation}
d_F'(U, V) = \min_{e^{i\phi}\in U(1)}\frac{1}{\sqrt{d}}\|U-e^{i\phi}V\|_F
\end{equation}
as the normalized Frobenius norm distance $d_F(U, V) = \tfrac{1}{\sqrt{d}}\|U-V\|_F$ up to a global phase.

The following lemma shows that (quotient) spectral distance and diamond distance are equivalent.
\begin{lemma}[Spectral and diamond distance of unitaries, variant of {\cite[Lemma B.5]{caro2022generalization}}]
For any two $d$-dimensional unitaries $U$ and $V$, we have
\begin{equation}
\frac{1}{\sqrt{2}}d_2'(U, V)\leq \frac{1}{2}\dworst(U, V)\leq d_2'(U, V)\leq \|U-V\|.
\end{equation}
\label{lem:dist-spectral-diamond}
\end{lemma}
\begin{proof}
Since stabilization is not necessary for computing the diamond distance of two unitary channels~[125], we have
\begin{equation}
\begin{split}
&\frac{1}{2}\dworst(U, V) = \max_{\ket{\psi}} \frac{1}{2}\|U\ketbra{\psi}U^\dagger - V\ketbra{\psi}V^\dagger\|_1
= \max_{\ket{\psi}} \sqrt{1-|\braket{\psi}{U^\dagger V|\psi}|^2} \\
&=\max_{\ket{\psi}} \sqrt{(1+|\braket{\psi}{U^\dagger V|\psi}|)(1-|\braket{\psi}{U^\dagger V|\psi}|)}
\geq \max_{\ket{\psi}}\frac{1}{\sqrt{2}} \sqrt{2(1-|\braket{\psi}{U^\dagger V|\psi}|)} \\
&=\frac{1}{\sqrt{2}}\min_{e^{i\phi}\in U(1)} \max_{\ket{\psi}} \|U\ket{\psi} - e^{i\phi}V\ket{\psi}\|_2
= \frac{1}{\sqrt{2}}\min_{e^{i\phi}\in U(1)}\|U-e^{i\phi}V\|
= \frac{1}{\sqrt{2}}d_2'(U, V),
\end{split}
\end{equation}
where we have used $\left|\braket{\psi}{U^\dagger V|\psi}\right|\geq 0$ and the standard conversion between trace distance and fidelity.
This proves the first inequality.
Similarly, we have
\begin{equation}
\begin{split}
&\frac{1}{2}\dworst(U, V) = \max_{\ket{\psi}} \frac{1}{2}\|U\ketbra{\psi}U^\dagger - V\ketbra{\psi}V^\dagger\|_1
= \max_{\ket{\psi}} \sqrt{1-|\braket{\psi}{U^\dagger V|\psi}|^2} \\
&=\max_{\ket{\psi}} \sqrt{(1+|\braket{\psi}{U^\dagger V|\psi}|)(1-|\braket{\psi}{U^\dagger V|\psi}|)}
\leq \max_{\ket{\psi}} \sqrt{2(1-|\braket{\psi}{U^\dagger V|\psi}|)} \\
&=\min_{e^{i\phi}\in U(1)} \max_{\ket{\psi}} \|U\ket{\psi} - e^{i\phi}V\ket{\psi}\|_2
= \min_{e^{i\phi}\in U(1)}\|U-e^{i\phi}V\|
= d_2'(U, V),
\end{split}
\end{equation}
where we have used $\left|\braket{\psi}{U^\dagger V|\psi}\right|\leq 1$, proving the second inequality.
The third inequality follows immediately from $d_2'(U, V)=\min_{e^{i\phi}\in U(1)}\|U-e^{i\phi}V\|\leq \|U-V\|$.
\end{proof}

We will also utilize the subadditivity of the diamond distance.

\begin{lemma}[Subadditivity of diamond distance {\cite[Prop.~3.48]{watrous2018book}}]
\label{lem:subadd-diamond}
For any $d$-dimensional unitaries $U_1, U_2, V_1, V_2$, we have the following inequality:
\begin{equation}
\dworst(U_2U_1, V_2V_1) \leq \dworst(U_2, V_2) + \dworst(U_1, V_1).
\end{equation}
\end{lemma}

From the standard relationship between different $p$-norms, we have the following relation between $d_2'$ and $d_F'$.

\begin{lemma}[Norm conversion between quotient spectral and normalized Frobenius distance]
For any two $d$-dimensional unitaries $U$ and $V$, we have
\begin{equation}
\frac{1}{\sqrt{d}}d_2'(U, V)\leq d_F'(U, V)\leq d_2'(U, V).
\end{equation}
\label{lem:dist-norm-conversion}
\end{lemma}
\begin{proof}
For any $e^{i\phi}\in U(1)$, the standard relation between matrix norms gives us
\begin{equation}
\|U-Ve^{i\phi}\| \leq \|U-Ve^{i\phi}\|_F \leq \sqrt{d}\|U-Ve^{i\phi}\|.
\end{equation}
Taking the minimum of $\|U-Ve^{i\phi}\|_F$ over $e^{i\phi}$ in the first inequality and dividing by $\sqrt{d}$, we obtain
\begin{equation}
\frac{1}{\sqrt{d}}d_2'(U, V)\leq \frac{1}{\sqrt{d}}\|U-Ve^{i\phi}\| \leq d_F'(U, V).
\end{equation}
Similarly, taking the minimum of $\|U-Ve^{i\phi}\|$ over $e^{i\phi}$ in the second inequality and dividing by $\sqrt{d}$ yields \begin{equation}
d_F'(U, V)\leq \frac{1}{\sqrt{d}}\|U-Ve^{i\phi}\|_F \leq d_2'(U, V).
\end{equation}
Thus we have the desired results.
\end{proof}

The following lemma collects some useful properties of $d_F'$ and in particular shows that $d_F'$ and $\davg$ are equivalent.

\begin{lemma}[Properties of quotient normalized Frobenius distance]
For any two $d$-dimensional unitaries $U$ and $V$, we have:
\begin{enumerate}
\item $\frac{1}{2} d_F'(U, V)\leq \davg(U, V) \leq d_F'(U, V)$.
\item For any integer $p\geq 1$, $d_F'(U^p, V^p)\leq p d_F'(U, V)$.
\item For any integer $p\geq 1$, if $d_F'(U, I), d_F'(V, I) \leq \frac{4/(25\pi)}{\sqrt{d}}$, then $d_F'(U^{1/p}, V^{1/p})\leq \frac{2}{p} d_F'(U, V)$.
\end{enumerate}
\label{lem:dist-df'}
\end{lemma}

Item 3 can be viewed as a version of \cite[Lemma 3.1]{haah2023query}.

\begin{proof}
Item 1: From properties of the Haar integral (see e.g., \cite[Example 50]{mele2023introduction}), we have
\begin{equation}
\label{eq:davg}
\davg(U, V)^2 = 1 - \frac{d+|\tr(U^\dagger V)|^2}{d(d+1)}.
\end{equation}
On the other hand, we have
\begin{equation}
d_F'^2(U, V)
= \min_{e^{i\phi}\in U(1)}\frac{1}{d}\|U-V e^{i\phi}\|_F^2
= \min_{e^{i\phi}\in U(1)}2 - \frac{2}{d}\mathrm{Re}[\tr(U^\dagger V e^{i\phi})]
= 2 - \frac{2}{d}|\tr(U^\dagger V)|.
\end{equation}
Combining them, we get
\begin{equation}
\davg(U, V)^2 = \frac{d}{d+1}d_F'^2(U, V)\left(1-\frac{d_F'^2(U, V)}{4}\right)\in \left[\frac{1}{4}d_F'^2(U, V), d_F'^2(U, V)\right],
\end{equation}
because $d_F'^2(U, V) \in [0, 2]$. Thus we have established Item 1.

Item 2:
From triangle inequality, we have
\begin{equation}
d_F'(U^p, V^p) \leq \sum_{k=1}^p d_F'(U^{p+1-k}V^{k-1}, U^{p-k}V^{k}) = \sum_{k=1}^p d_F'(U, V) = p d_F'(U, V)\, ,
\end{equation}
where we have used the unitary invariance of $d_F'$. This proves Item 2.

Item 3:
We first prove the following modified version without the global phase: ``If $d_F(U, I), d_F(V, I)\leq \frac{4/(5\pi)}{\sqrt{d}}$, then $d_F(U^{1/p}, V^{1/p})\leq \frac{2}{p}d_F(U, V)$.''
Let $U=e^X, V=e^Y$ with $\|X\|, \|Y\|\leq \pi$. We can refine the bound on $\|X\|, \|Y\|$ by noting the following
\begin{equation}
\|X\|\leq \frac{\pi}{2}\|e^X-I\|\leq \frac{\pi}{2}\|U-I\|_F
=\frac{\pi \sqrt{d}}{2}d_F(U, I)\leq \frac{2}{5},
\end{equation}
where the first inequality can be seen from eigenvalue analysis as follows:
Let $i\theta_k$ be the eigenvalues of $X$ with $|\theta_k|\leq \pi$. Then we have
\begin{equation}
\|X\|=\max_k |\theta_k| \leq \pi \max_k \left|\sin\frac{\theta_k}{2}\right| = \frac{\pi}{2} \max_k \left|e^{i\theta_k}-1\right| = \frac{\pi}{2}\|e^X-I\|.
\end{equation}
Similarly, we have $\|Y\|\leq 2/5$.

Next, we prove the following inequality when $\|X\|, \|Y\|\leq 2/5$ (similar to~\cite[Appendix D]{barthel2018fundamental}):
\begin{equation}\label{eq:frobenius-norm-generator-exponential-1}
\frac{1}{2}\|X-Y\|_F \leq \|e^X-e^Y\|_F \leq \|X-Y\|_F.
\end{equation}
For the upper bound, we use the triangle inequality and a telescoping sum representation: For any $m\in\mathbb{N}$,
\begin{equation}
\|e^X-e^Y\|_F \leq \sum_{k=1}^m \|e^{(k-1)X/m}(e^{X/m}-e^{Y/m})e^{(m-k)Y/m}\|_F = m \|e^{X/m}-e^{Y/m}\|_F\, ,
\end{equation}
and by taking $m\to\infty$ we arrive at the upper bound.
For the lower bound, note that by triangle inequality, we have
\begin{equation}
\|e^X-e^Y\|_F = \left\|\sum_{k=1}^{\infty} \frac{1}{k!}(X^k-Y^k)\right\|_F \geq \|X-Y\|_F - \left\|\sum_{k=2}^{\infty} \frac{1}{k!}(X^k-Y^k)\right\|_F.
\end{equation}
The second term can be upper bounded by
\begin{equation}
\begin{split}
\left\|\sum_{k=2}^{\infty} \frac{1}{k!}(X^k-Y^k)\right\|_F &= \left\|\sum_{k=2}^{\infty} \sum_{l=1}^k \frac{1}{k!}X^{l-1}(X-Y)Y^{k-l}\right\|_F \\
&\leq \sum_{k=2}^{\infty}\frac{k}{k!}\left(\frac{2}{5}\right)^k\|X-Y\|_F \\
&= (e^{2/5}-1)\|X-Y\|_F\, ,
\end{split}
\end{equation}
where we have used $\|AB\|_F\leq \|A\|\cdot \|B\|_F$ and $\|X\|, \|Y\|\leq 2/5$.
Plugging this bound back in, we arrive at the lower bound
\begin{equation}\label{eq:frobenius-norm-generator-exponential-2}
\|e^X-e^Y\|_F \geq (2-e^{2/5})\|X-Y\|_F\geq \frac{1}{2}\|X-Y\|_F.
\end{equation}\Cref{eq:frobenius-norm-generator-exponential-1} in particular implies
\begin{equation}
d_F(U^{1/p}, V^{1/p})
\leq\frac{1}{p\sqrt{d}}\|X-Y\|_F
\leq\frac{2}{p}d_F(U, V)\, ,
\end{equation}
and thus the modified version of our claim.

Finally, we deal with the global phase and prove the $d_F'$ version, where we assume $d_F'(U, I), d_F'(V, I)\leq\frac{4/(25\pi)}{\sqrt{d}}$.
Let $e^{i\phi_U}, e^{i\phi_V}, e^{i\phi}\in U(1)$ denote the global phases that minimize $d_F(U, Ie^{i\phi_U}), d_F(V, Ie^{i\phi_V})$ and $d_F(Ue^{-i\phi_U}, Ve^{-i\phi_V} e^{i\phi})$, respectively.
Then $d_F(U, Ie^{i\phi_U}), d_F(V, Ie^{i\phi_V})\leq \frac{4/(25\pi)}{\sqrt{d}}$ by assumption, and $d_F(Ue^{-i\phi_U}, Ve^{-i\phi_V})\leq d_F(U, Ie^{i\phi_U}) + d_F(V, Ie^{i\phi_V}) \leq \frac{8/(25\pi)}{\sqrt{d}}$.
\begin{equation}
\begin{split}
d_F(e^{i\phi}, I)
&\leq d_F(e^{i\phi}, (Ve^{-i\phi_V})^\dagger (Ue^{-i\phi_U})) + d_F((Ve^{-i\phi_V})^\dagger (Ue^{-i\phi_U}), I) \\
&= d_F(Ue^{-i\phi_U}, Ve^{-i\phi_V}e^{i\phi}) + d_F(Ue^{-i\phi_U}, Ve^{-i\phi_V})
\\
&\leq 2d_F(Ue^{-i\phi_U}, Ve^{-i\phi_V})
\\
&\leq \frac{16/(25\pi)}{\sqrt{d}}\, .
\end{split}
\end{equation}
This means that $d_F(Ue^{-i\phi_U} e^{-i\phi}, I)\leq d_F(U, Ie^{i\phi_U}) + d_F(e^{i\phi}, I) \leq \frac{(4+16)/(25\pi)}{\sqrt{d}}=\frac{4/(5\pi)}{\sqrt{d}}.$
We also know that $d_F(Ve^{-i\phi_V}, I)\leq \frac{4/(25\pi)}{\sqrt{d}}\leq \frac{4/(5\pi)}{\sqrt{d}}$.
Thus the two matrices $Ue^{-i\phi_U}e^{-i\phi}$ and $Ve^{-i\phi_V}$ satisfy the condition of the modified version without global phase, and we thus have
\begin{equation}
\begin{split}
d_F'(U^{1/p}, V^{1/p})
&\leq d_F'(U^{1/p}, V^{1/p}(e^{-i\phi_V})^{1/p}(e^{i\phi_U})^{1/p} (e^{i\phi})^{1/p})\\
&=d_F((Ue^{-i\phi_U} e^{-i\phi})^{1/p}, (Ve^{-i\phi_V})^{1/p})
\\
&\leq\frac{2}{p}d_F(Ue^{-i\phi_U} e^{-i\phi}, Ve^{-i\phi_V})
=d_F'(U, V).
\end{split}
\end{equation}
This concludes the proof of Item 3.
\end{proof}

Haar-random states are in general hard to generate.
One may want to use other ensembles of input states and the associated distance metric for average-case learning.
A class of ensembles of physical interest is that of locally scrambled ensembles [54, 55] defined as follows:

\begin{definition}[Locally scrambled ensembles up to the second moment]
\label{def:local-scram-ensem}
An ensemble $\mathcal{S}$ of (i.e., a distribution over) $n$-qubit states is called a locally scrambled ensemble up to the second moment if it is of the form $\mathcal{S}=\mathcal{U}\ket{0}^{\otimes n}$, where $\mathcal{U}$ is an ensemble of unitaries that is locally scrambled up to the second moment.
That is, there exists another unitary ensemble $\mathcal{U}'$, such that: (1) for any $U'$ randomly sampled from $\mathcal{U}'$ and for any tensor product of single-qubit unitaries $\otimes_{i=1}^n U_i$, $U'\otimes_{i=1}^n U_i$ follows the same distribution of $\mathcal{U}'$; and (2) for any $2n$-qubit density matrices $\rho$, we have $\mathbb{E}_{U\sim \mathcal{U}}[U^{\otimes 2}\rho (U^\dagger)^{\otimes 2}] = \mathbb{E}_{U'\sim \mathcal{U}'}[U'^{\otimes 2}\rho (U'^\dagger)^{\otimes 2}]$.
We use $\mathbb{S}_\mathrm{LS}^{(2)}$ to denote the set of all such state ensembles.
\end{definition}

Notable examples of these ensembles include $n$-qubit Haar-random states, products of Haar-random single-qubit states, products of random single-qubit stabilizer states, $2$-designs on $n$-qubit states, and output states of random local quantum circuits with any fixed architecture.
The following lemma from the study of out-of-distribution generalization [56] shows that these ensembles lead to mutually equivalent average-case distance metrics.

\begin{lemma}[Equivalence of locally scrambled average-case distances {\cite[Theorem 1]{caro2022out}}]
We denote by $d_P (U,V) = \sqrt{\E_{\ket{\psi}\sim P}[\dtr(U\ket{\psi}, V\ket{\psi})^2]}$ the root mean squared trace distance with respect to an ensemble $P$. For any $P, Q\in \mathbb{S}_\mathrm{LS}^{(2)}$ and for any unitaries $U, V$, we have
\begin{equation}
\frac{1}{\sqrt{2}}d_Q(U, V)\leq d_P(U, V) \leq \sqrt{2}d_Q(U, V).
\end{equation}
\label{lem:equi_local_scram}
\end{lemma}

The following lemma shows that the triangle inequality holds for $d_P$ (and in particular, $\davg$).

\begin{lemma}[Triangle inequality for average-case distance]
\label{lem:tri-ineq-avg}
Let $d_P (U,V) = \sqrt{\E_{\ket{\psi}\sim P}[\dtr(U\ket{\psi}, V\ket{\psi})^2]}$ be the root mean squared trace distance with respect to an ensemble $P$.
For any three unitaries $U, V$ and $W$, we have the triangle inequality
\begin{equation}
d_P(U, V)\leq d_P(U, W) + d_P(W, V).
\end{equation}
\end{lemma}
\begin{proof}
Note that
\begin{equation}
\begin{split}
&d_{P}^2(U, V)
= \mathbb{E}_{\ket{\psi}\sim P}[\dtr(U\ket{\psi}, V\ket{\psi})^2]
\leq \mathbb{E}_{\ket{\psi}\sim P}[\left(\dtr(U\ket{\psi}, W\ket{\psi}) + \dtr(W\ket{\psi}, V\ket{\psi})\right)^2] \\
&= d_P^2(U, W) +  d_P^2(W, V) + 2 \mathbb{E}_{\ket{\psi}\sim P}[\dtr(U\ket{\psi}, W\ket{\psi}) \dtr(W\ket{\psi}, V\ket{\psi}) ] \\
&\leq d_P^2(U, W) +  d_P^2(W, V) + 2 \sqrt{\mathbb{E}_{\ket{\psi}\sim P}[\dtr(U\ket{\psi}, W\ket{\psi})^2]}\cdot \sqrt{\mathbb{E}_{\ket{\psi}\sim P}[\dtr(W\ket{\psi}, V\ket{\psi})^2]} \\
&= \left( d_{P}(U, W) + d_{P}(W, V)\right)^2,
\end{split}
\end{equation}
where we have used the triangle inequality for $\dtr$ and the Cauchy-Schwartz inequality.
Taking the square root gives us the desired result.
\end{proof}

\subsection{Covering and packing nets}
Our results in state and unitary learning utilize a tool from high-dimensional probability theory, namely covering and packing nets.
We employ covering nets in our proofs of the sample complexity upper bounds and packing nets in our proofs of sample complexity lower bounds.
Intuitively, covering and packing nets characterize the complexity of a space by discretizing it with small balls of a given resolution.
We formally define these concepts below.

\begin{definition}[Covering net/number and metric entropy]
Let $(X,d)$ be a metric space. Let $K \subseteq X$ be a subset and $\epsilon > 0$. Then, define the following.
\begin{itemize}
\item $N \subseteq K$ is an \emph{$\epsilon$-covering net} of $K$ if for any $x \in K$, there exists a $y \in N$ such that $d(x,y) \leq \epsilon$.
\item The \emph{covering number} $\mathcal{N}(K, d, \epsilon)$ of $K$ is the smallest possible cardinality of an $\epsilon$-covering net of $K$.
\item The \emph{metric entropy} is $\log \mathcal{N}(K,d,\epsilon)$.
\end{itemize}
\end{definition}

We can similarly define a packing net.

\begin{definition}[Packing net/number]
Let $(X,d)$ be a metric space. Let $K \subseteq X$ be a subset and $\epsilon > 0$. Then, define the following.
\begin{itemize}
\item $N \subseteq K$ is an \emph{$\epsilon$-packing net} of $K$ if for any $x,y \in N$, $d(x,y) > \epsilon$.
\item The \emph{packing number} $\mathcal{M}(K, d, \epsilon)$ of $K$ is the largest possible cardinality of an $\epsilon$-packing net of $K$.
\end{itemize}
\end{definition}

The following equivalence between covering and packing numbers is often useful.

\begin{lemma}[Covering and packing are equivalent, {\cite[Section 4.2]{vershynin2018high}}]
\label{lem:equi-cov-pack}
Let $(X, d)$ be a metric space. Let $K\subseteq X$ and $\epsilon>0$. We have
\begin{equation}
\mathcal{N}(K, d, \epsilon/2) \geq \mathcal{M}(K, d, \epsilon) \geq \mathcal{N}(K, d, \epsilon).
\end{equation}
\end{lemma}

Covering numbers also have the following monotonicity property.

\begin{lemma}[Monotonicity of covering number, {\cite[Section 4.2]{vershynin2018high}}]
Let $(K, d)$ be a metric space. If $L\subseteq K$, then $\mathcal{N}(L, d, \epsilon) \leq \mathcal{N}(K, d, \epsilon/2)$.
\end{lemma}

For our purposes, we need the following upper and lower bounds on the covering number of the unitary group.
Since the states that we consider can be generated by unitaries applied to a fixed input state, a covering number upper bound for unitaries with respect to the diamond distance implies a corresponding covering number upper bound for states with respect to the trace distance.

\begin{lemma}[Covering number of the unitary group, {\cite[Proposition 7]{szarek1982nets}}, {\cite[Lemma 1]{barthel2018fundamental}} and {\cite[Lemma C.1]{caro2022generalization}}]
\label{lem:2q-unitaries}
Let $\norm{\cdot}'$ be any unitarily invariant norm. there exist universal constants $c_1, c_2>0$ such that for any $\epsilon\in(0, 2]$, the covering number of the $d$-dimensional unitary group $U(d)$ with respect to the norm $\norm{\cdot}'$ satisfies:
\begin{equation}
\left(\frac{c_1}{\epsilon}\right)^{d^2}
\leq
\mathcal{N}(U(d), \norm{\cdot}', \norm{I}'\epsilon)
\leq
\left(\frac{c_2}{\epsilon}\right)^{d^2}.
\end{equation}
In particular, for the spectral norm $\norm{\cdot}$, we have the upper bound $\mathcal{N}(U(d), \norm{\cdot}, \epsilon) \leq \left(6/\epsilon\right)^{2d^2}$.
For the Frobenius norm $\norm{\cdot}_F$, we have $\left(c_1/\epsilon\right)^{d^2} \leq \mathcal{N}(U(d), \norm{\cdot}_F, \sqrt{d}\epsilon) \leq \left(c_2/\epsilon\right)^{d^2}$.
\end{lemma}

We can use this result to bound the covering number for $n$-qubit unitaries consisting of $G$ two-qubit gates.

\begin{theorem}[Covering number of $G$-gate unitaries]
\label{thm:covering}
Let $U^G \subseteq U(2^n)$ be the set of $n$-qubit unitaries that can be implemented by $G$ two-qubit gates.
Then for any $\epsilon \in (0, 1]$, there exist universal constants $c_1, c_2, C>0$ such that for $1\leq G/C\leq 4^{n+1}$, the metric entropy of $U^G$ with respect to the normalized Frobenius distance $d_F$ can be bounded as
\begin{equation}
\frac{G}{4C}\log(\frac{c_1}{\epsilon})\leq \log\mathcal{N}(U^G, d_F, \epsilon) \leq 16G\log(\frac{c_2G}{\epsilon}) + 2G\log n.
\end{equation}
Moreover, the metric entropy with respect to diamond distance $\dworst$ can be explicitly upper bounded by
\begin{equation}
\log\mathcal{N}(U^G, \dworst, \epsilon) \leq 32G\log(\frac{12G}{\epsilon}) + 2G\log n.
\end{equation}
\end{theorem}
\begin{proof}
The proof of the upper bounds is similar to the proof of Theorem C.1 in [124].
We first prove the upper bound for diamond distance.

Let $\epsilon\in (0, 1]$, and define $\epsilon' = \epsilon/2G$.
Then by Lemma~\ref{lem:2q-unitaries}, there exists an $\epsilon'$-covering net $\tilde{\mathcal{N}}_{\epsilon'}$ of the set of two-qubit unitaries $U(2^2)$ with respect to the spectral norm $\norm{\cdot}$ of size
\begin{equation}
|\tilde{\mathcal{N}}_{\epsilon'}| \leq \left(\frac{6}{\epsilon'}\right)^{32} = \left(\frac{12G}{\epsilon}\right)^{32}.
\end{equation}
This bound applies when the two-qubit unitary acts on a fixed set of two qubits.
We can consider two-qubit unitaries that act on any of the $n$ qubits.
Let $U^{2q} \subset U(2^n)$ denote this set of two-qubit unitaries that can act on any pair of the $n$ qubits of the system.
Because there are $\binom{n}{2}$ pairs of qubits that the unitary could act on, the size of the covering net $\tilde{\mathcal{N}}_{\epsilon',n}$ of $U^{2q}$ is bounded by
\begin{equation}
|\tilde{\mathcal{N}}_{\epsilon',n}| \leq \binom{n}{2}\left(\frac{12G}{\epsilon}\right)^{32}.
\end{equation}

Recall that we want to find a covering net for the set $U^G$ of $n$-qubit unitaries consisting of $G$ two-qubit gates.
Any unitary $U \in U^G$ can be written as $U_GU_{G-1}...U_1$ for $U_i \in U^{2q}$, where we suppress the tensor product with identity for readability.
We consider the set of unitaries obtained by multiplying elements of the covering net $\tilde{\mathcal{N}}_{\epsilon',n}$ of $U^{2q}$. Namely, we define
\begin{equation}
\mathcal{N}_{\epsilon} \triangleq \{U_GU_{G-1}...U_1|U_i \in \tilde{\mathcal{N}}_{\epsilon',n}, 1\leq i \leq G\}\, .
\end{equation}
Let $U \in U^G$ be any arbitrary unitary that can be implemented by $G$ two-qubit gates, i.e., it can be written as $U = U_GU_{G-1}...U_1$ for $U_i \in U^{2q}$.
As $\tilde{\mathcal{N}}_{\epsilon',n}$ is an $\epsilon'$-covering net of the set $U^{2q}$ of two-qubit unitaries, for each $U_i$ comprising the circuit $U$, we can find a $\Tilde{U}_i\in \Tilde{\mathcal{N}}_{\epsilon',n}$ such that $\lVert U_i - \Tilde{U}_i \rVert \leq \epsilon'$ for all $1 \leq i \leq G$, where $\norm{\cdot}$ denotes the spectral norm. Then, the unitary $\Tilde{U} \triangleq \Tilde{U}_G\Tilde{U}_{G-1}...\Tilde{U}_1 \in \mathcal{N}_{\epsilon_1}$ satisfies
\begin{equation}
\dworst(U, \tilde{U}) \leq \sum_{i=1}^G \dworst(U_i, \tilde{U}_i) \leq 2\sum_{i=1}^G \norm{U_i - \tilde{U}_i} \leq 2G \epsilon'=\epsilon,
\end{equation}
where we have employed the subadditivity of the diamond distance (Lemma~\ref{lem:subadd-diamond}) in the first inequality and then used the relationship between the diamond norm and spectral norm in the second inequality (Lemma~\ref{lem:dist-spectral-diamond}). In the last inequality, we used that $\norm{U_i - \tilde{U}_i} \leq \epsilon'$ and $\epsilon' = \nicefrac{\epsilon}{2G}$.

Thus, $\mathcal{N}_{\epsilon}$ is an $\epsilon$-covering net of the set $U^G$ of $n$-qubit unitaries that can be implemented by $G$ two-qubit gates with respect to the diamond distance.
By definition of $\mathcal{N}_{\epsilon}$, we have $|\mathcal{N}_{\epsilon}| = |\Tilde{\mathcal{N}}_{\epsilon',n}|^G$, since each unitary in the length $G$ strings of unitaries comprising elements of $\mathcal{N}_{\epsilon}$ are chosen from $\Tilde{\mathcal{N}}_{\epsilon',n}$. Then
\begin{equation}
|\mathcal{N}_{\epsilon}|\leq \binom{n}{2}^G\left(\frac{12G}{\epsilon}\right)^{32G} \leq n^{2G}\left(\frac{12G}{\epsilon}\right)^{32G}.
\end{equation}
Taking the logarithm gives the desired result for diamond distance.

We can argue similarly for the normalized Frobenius distance $d_F$.
Specifically, we make use of the subadditivity of $\|\cdot\|_F$: $\forall U_1, V_1, U_2, V_2\in U(2^n)$, we have
\begin{equation}
\|U_2U_1 - V_2V_1\|_F \leq \|U_2U_1 - U_2V_1\|_F + \|U_2V_1 - V_2V_1\|_F = \|U_1 - V_1\|_F + \|U_2 - V_2\|_F,
\end{equation}
where we have used triangle inequality and $\|\cdot\|_F$ being unitary invariant.

Consider any $U\in U^G, U = U_G\cdots U_1$, where $U_i, 1\leq i\leq T$ are 2-qubit unitaries acting on some pair of qubits.
Take $\epsilon'=\epsilon/G$ and let $\mathcal{N}_{\epsilon'}$ be an $\epsilon'$-covering net of $U(2^2)$ with respect to $\|\cdot\|_F$. Then there exist $V_i\in \mathcal{N}, 1\leq i\leq G$, such that $\|U_i - V_i\|\leq \epsilon/G$ when the $V_i$ are placed on the corresponding qubits. Let $V=V_G\cdots V_1$. By sub-additivity, we have
\begin{equation}
\|U-V\|_F \leq \sum_{i=1}^G \sqrt{2^{n-2}}\|U_i - V_i\|_F \leq \sqrt{2^{n-2}}G\epsilon' = \sqrt{2^{n-2}}\epsilon,
\end{equation}
where we have used the facts that the Frobenius norm is multiplicative w.r.t.~tensor products and that an ($n-2$)-qubit identity has Frobenius norm equal to $\sqrt{2^{n-2}}$.
Therefore, the set of $V=V_G\cdots V_1$, where $V_i\in U(2^2)$ and acting on all possible pair of qubits is a $(2^{n-2}\epsilon)$-covering net of $U^G$. Since the number of choices for qubits to act on is $\binom{n}{2}$ for each $V_i$, we have
\begin{equation}
\mathcal{N}(U^G, \|\cdot\|_F, \sqrt{2^{n-2}}\epsilon) \leq \left[\binom{n}{2} \mathcal{N}(U(2^2), \|\cdot\|_F, \epsilon/G)\right]^G \leq n^{2G}\left(\frac{c_2 G \sqrt{2^2}}{\epsilon}\right)^{16G},
\end{equation}
where we have used \Cref{lem:2q-unitaries}. Redefining $\epsilon$ to be $\epsilon/\sqrt{2^2}$ and switching to the normalized $d_F$, we obtain
\begin{equation}
\log\mathcal{N}(U^G, d_F, \epsilon) \leq 16G\log \left(\frac{c_2G}{\epsilon}\right) + 2G\log n.
\end{equation}

Finally, we prove the lower bound.
For this, we consider a particular set of circuit structures where all the $G$ gates are placed on the first $k\leq n$ qubits.
The set of unitaries that can be implemented by such circuits is denoted by $U^{\leq k}_G \subseteq U^G$. From the theory of universal quantum gates (see [73]), we know that to implement an arbitrary $k$-qubit unitary, we only need $G_k=\bigo(4^k)$ two-qubit gates that can implement single-qubit gates and CNOT.
That is, there exists a universal constant $C>0$, such that $C4^k\geq G_k$.
Therefore, for any integer $k\leq n$ satisfying $C4^k \leq G$, we have $G \geq G_k$.
Then all possible $k$-qubit unitaries can be implemented with these $G$ gates: $U^n(2^k)=\{U\otimes I_{2^{n-k}}: U\in U(2^k)\} \subseteq U^{\leq k}_G \subseteq U^G$, where $U^n(2^k)$ denotes the set obtained by embedding the $k$-qubit unitaries into the $n$-qubit unitaries via tensor-multiplication with the identity.
Thus $\mathcal{N}(U^G, \|\cdot\|_F, \epsilon) \geq \mathcal{N}(U^n(2^k), \|\cdot\|_F, 2\epsilon)$ by monotonicity.

Next, we prove that $\mathcal{N}(U^n(2^k), \|\cdot\|_F, 2\epsilon)\geq \mathcal{N}(U(2^k), \|\cdot\|_F, 2\epsilon/\sqrt{2^{n-k})}$.
To do this, we take a minimal $2\epsilon$-covering net $\mathcal{N}$ of $U^n(2^k)$ with $|\mathcal{N}|=\mathcal{N}(U^n(2^k), \|\cdot\|_F, 2\epsilon)$.
Hence $\forall U\in U(2^k)$, $U\otimes I_{2^{n-k}}\in U^n(2^k), \exists V\otimes I_{2^{n-k}} \in \mathcal{N}$, such that $\|U-V\|_F =  \|U\otimes I_{2^{n-k}}-V\otimes I_{2^{n-k}}\|_F /\sqrt{2^{n-k}} \leq {2\epsilon}/\sqrt{2^{n-k}}$.
Therefore, $\{V: V\otimes I_{2^{n-k}}\in \mathcal{N}\}$ forms a $2\epsilon/\sqrt{2^{n-k}}$-covering net of $U(2^k)$, and we have $\mathcal{N}(U^n(2^k), \|\cdot\|_F, 2\epsilon)\geq\mathcal{N}(U(2^k), \|\cdot\|_F, 2\epsilon/\sqrt{2^{n-k}})$.

Combining the above inequalities, we have
\begin{equation}
\log\mathcal{N}(U^G, \|\cdot\|_F, \epsilon) \geq \log\mathcal{N}(U^n(2^k), \|\cdot\|_F, 2\epsilon) \geq \log\mathcal{N}(U(2^k), \|\cdot\|_F, 2\epsilon/\sqrt{2^{n-k}}) \geq 2^{2k}\log\frac{c_1 \sqrt{2^{n}}}{2\epsilon},
\end{equation}
where the last inequalities follow from \Cref{lem:2q-unitaries}.
The largest possible $k$ is given by $k=\floor{\log_4(G/C)}\geq \log_4{G/(4C)}$. Thus, by redefining $\epsilon$ to be $\epsilon/\sqrt{2^n}$ and switching to $d_F$, we arrive at
\begin{equation}
\log\mathcal{N}(U^G, d_F, \epsilon) \geq \frac{G}{4C}\log\frac{c_1}{2\epsilon}.
\end{equation}
This completes the proof of \Cref{thm:covering}.
\end{proof}

The $d_F$ covering number bounds in \Cref{thm:covering} do not yet properly take into account the global $U(1)$ phase.
To obtain covering number for the average-case distance $\davg$, which is equivalent to the quotient normalized Frobenius distance $d_F'$ (\Cref{lem:dist-df'} Item 1), we need to quotient out the global phase.
This is formalized in the following lemma.

\begin{lemma}[Packing number of quotient distance metric, variant of {\cite[Lemma 4]{barthel2018fundamental}}]
\label{lem:quotient-packing}
For any $d$-dimensional unitaries $U$ and $V$, let $d_F(U, V)=\norm{U-V}_F/\sqrt{d}$ be the normalized Frobenius distance, and $d_F'(U, V) = \min_{W\in U(1)}d_F(U, VW)$ be the corresponding quotient distance. Then there exists a universal constant $c_2>0$ such that the packing number of any set $\mathcal{U}\subseteq U(d)$ with respect to $d_F$ and $d_F'$ satisfies
\begin{equation}
\log\mathcal{M}(\mathcal{U}, d_F, 4\epsilon) - \log(c_2/\epsilon)
\leq
\log\mathcal{M}(\mathcal{U}, d_F', \epsilon)
\leq
\log\mathcal{M}(\mathcal{U}, d_F, \epsilon).
\end{equation}
\end{lemma}
\begin{proof}
We focus on the lower bound first.
Take a minimal $\epsilon$-covering $\mathcal{N}_1$ of $\mathcal{U}$ with respect to $d_F'$ and a minimal $\epsilon$-covering $\mathcal{N}_2$ of $U(1)$ with respect to the absolute value distance $d_A(e^{i\phi}, e^{-i\phi'})=|e^{i\phi}-e^{-i\phi'}|$. Then, for any $U\in\mathcal{U}$, there exists $V\in \mathcal{N}_1$ such that $d_F'(U, V)\leq \epsilon$. Let $e^{i\phi^\star} = \argmin_{e^{i\phi}} d_F(U, Ve^{i\phi})$. Then $d_F(U, Ve^{i\phi^\star})\leq \epsilon$, and there exists $e^{i\phi'} \in \mathcal{N}_2$ such that $d_A(e^{i\phi^\star}, e^{i\phi'})\leq \epsilon$. Therefore,
\begin{equation}
d_F(U, V e^{i\phi'}) \leq d_F(U, Ve^{i\phi^\star}) + d_F(Ve^{i\phi^\star}, Ve^{i\phi'}) = d_F(U, Ve^{i\phi^\star}) + d_F(Ie^{i\phi^\star}, Ie^{i\phi'}) \leq 2\epsilon,
\end{equation}
where we have used the triangle inequality, $d_F$ being unitary invariant, and $d_F(Ie^{i\phi^\star}, Ie^{i\phi'}) = \frac{1}{\sqrt{d}}\|Ie^{i\phi^\star}-Ie^{i\phi'}\|_F=\frac{\|I\|_F}{\sqrt{d}}|e^{i\phi^\star}-e^{i\phi'}|=d_A(e^{i\phi^\star}, e^{i\phi'})\leq \epsilon$.
Hence, the set $\{Ve^{i\phi'}: V\in \mathcal{N}_1, e^{i\phi'}\in \mathcal{N}_2\}$ is a $(2\epsilon)$-covering of $\mathcal{U}$ with respect to $d_F$. Then
\begin{equation}
\mathcal{N}(\mathcal{U}, d_F, 2\epsilon) \leq \mathcal{N}(\mathcal{U}, d_F', \epsilon)\mathcal{N}(U(1), d_A, \epsilon).
\end{equation}
Therefore, using the equivalence of covering and packing (\Cref{lem:equi-cov-pack}) and the covering number bound for $U(1)$ (\Cref{lem:2q-unitaries}), we arrive at
\begin{equation}
\log \mathcal{M}(\mathcal{U}, d_F', \epsilon) \geq \log \mathcal{M}(\mathcal{U}, d_F', 4\epsilon) - \log(c_2/\epsilon).
\end{equation}

For the upper bound, note that $\forall U, V \in \mathcal{U}$, we have
\begin{equation}
d_F'(U, V) = \min_{e^{i\phi}\in U(1)}d_F(U, Ve^{i\phi}) \leq d_F(U, V).
\end{equation}
Therefore, a maximal $\epsilon$-packing net with respect to $d_F'$ is an $\epsilon$-packing net with respect to $d_F$. Therefore,
\begin{equation}
\mathcal{M}(\mathcal{U}, d_F', \epsilon) \leq \mathcal{M}(\mathcal{U}, d_F, \epsilon).
\end{equation}
This concludes the proof of \Cref{lem:quotient-packing}.
\end{proof}

With \Cref{lem:quotient-packing}, we can obtain the covering number of $G$-gate unitaries with respect to the average-case distance.

\begin{corollary}[Covering number with average-case distance]
\label{cor:covering-avg}
Let $U^G \subseteq U(2^n)$ be the set of $n$-qubit unitaries that can be implemented by $G$ two-qubit gates.
Then for any $\epsilon \in (0, 1]$, there exist universal constants $c_1, c_2, C>0$ such that for $1\leq G/C\leq 4^{n+1}$, the metric entropy of $U^G$ with respect to the average-case distance $\davg(U, V) = \sqrt{\E_{\ket{\psi}}[\dtr(U\ket{\psi}, V\ket{\psi})^2]}$, where the expectation value is over Haar measure, can be bounded as
\begin{equation}
\frac{G}{4C}\log(\frac{c_1}{8\epsilon}) - \log(\frac{c_2}{2\epsilon})\leq \log\mathcal{N}(U^G, \davg, \epsilon) \leq 16G\log(\frac{c_2G}{\epsilon}) + 2G\log n.
\end{equation}
\end{corollary}
\begin{proof}
The corollary follows directly from \Cref{thm:covering}, \Cref{lem:quotient-packing}, and the equivalence of $d_F'$ and $\davg$ (\Cref{lem:dist-df'} Item 1).
\end{proof}

\subsection{Classical shadows and hypothesis selection}
\label{app:hypothesis}

Our proofs of the sample complexity upper bounds crucially rely on a known algorithm for quantum hypothesis selection~[130].
The high-level idea is to find a covering net over all unitaries consisting of only $G$ two-qubit gates and to then use quantum hypothesis selection to identify a candidate in the covering net close to the unknown target state/unitary.
A similar idea has previously appeared in~[96].
In this section, we discuss the quantum hypothesis selection algorithm from~[130] and prove a performance guarantee when basing it on classical shadow tomography~[68].

The quantum hypothesis selection algorithm takes as input (classical descriptions of) a set of hypothesis states $\sigma_1,\dots,\sigma_m$ and quantum copies of an unknown state $\rho$.
Using these copies, the algorithm identifies a hypothesis state $\sigma_k$ that is close to the unknown state $\rho$ in trace distance.
Importantly, quantum hypothesis selection black-box reduces to shadow tomography~[93], i.e., one can use the shadow tomography protocol as a black-box to solve quantum hypothesis selection.
To obtain a better sample complexity scaling, we instead utilize classical shadow tomography~[68].

Recall that a classical shadow is a succinct classical description of a quantum state that allows us to predict many expectation values accurately.
One can construct this classical shadow description by applying a random unitary to the quantum state and measuring in the computational basis.
The most prevalent examples are random Clifford measurements, where the random unitary is chosen to be a random Clifford circuit, or random Pauli measurements, where the random unitary is chosen to be a tensor product of random Pauli gates.
Moreover, we have the following rigorous guarantee for using classical shadows to predict expectation values.

\begin{theorem}[Theorem 1 in~[68]]
\label{thm:classical-shadow}
Let $O_1,\dots,O_M$ be Hermitian $2^n \times 2^n$ matrices, and let $\epsilon, \delta \in [0,1]$. Then,
\begin{equation}
N = \mathcal{O}\left(\frac{\log(M/\delta)}{\epsilon^2}\max_{1\leq i\leq M} \norm{O_i - \frac{\tr(O_i)}{2^n}\mathbb{I}}^2_{\mathrm{shadow}}\right)
\end{equation}
copies of an unknown quantum state $\rho$ suffice to predict $\hat{o}_i$ such that
\begin{equation}
|\hat{o}_i - \tr(O_i \rho)| \leq \epsilon
\end{equation}
for all $1 \leq i \leq M$, with probability at least $1-\delta$.
\end{theorem}
Here, $\norm{\cdot}_{\mathrm{shadow}}$ denotes the shadow norm, which depends on the ensemble of unitary transformations used to create the classical shadow.
For instance, in the case of random Cliffords, the shadow norm can be controlled via the (unnormalized) Frobenius norm, compare \cite[Proposition S1]{huang2020predicting}.

Now, we can prove a new guarantee for the quantum hypothesis selection by replacing shadow tomography with classical shadow in the proof in~[130].

\begin{prop}[Proposition 5.3 in [130]; Classical Shadow Version]
\label{prop:hypothesis}
Let $0 < \epsilon, \delta < 1/2$. Given access to unentangled copies of a quantum state $\rho$ and classical descriptions of $m$ fixed hypothesis states $\sigma_1,\dots, \sigma_m$, there exists a quantum algorithm that selects $\sigma_k$ such that $\dtr(\rho, \sigma_k) \leq 3\eta + \epsilon$ with probability at least $1-\delta$, where $\eta = \min_i \dtr(\rho,  \sigma_i)$. Moreover, this algorithm uses
\begin{equation}
N = \mathcal{O}\left(\frac{\log (m/\delta)}{\epsilon^2}\right)
\end{equation}
copies of the quantum state $\rho$.
\end{prop}

In~[130], they prove the guarantee on the quantum hypothesis selection algorithm using Helstrom's Theorem.
We follow a similar proof.
Thus, we first state Helstrom's Theorem and recall a corollary of it, which will be useful in the proof of Prop.~\ref{prop:hypothesis}.

\begin{theorem}[Helstrom's Theorem~[69]]
\label{theorem:helstrom}
Consider two $d$-dimensional quantum states $\rho$ and $\sigma$. Then, the trace distance between $\rho$ and $\sigma$ can be written as
\begin{equation}
\frac{1}{2}\norm{\rho - \sigma}_1 = \max_{\norm{O}_\infty \leq 1} |\tr(O\rho) - \tr(O\sigma)|,
\end{equation}
where the maximum is taken over all observables $O \in \mathbb{C}^{d\times d}$.
\end{theorem}

\begin{corollary}
\label{coro:helstrom}
Consider two $d$-dimensional quantum states $\rho$ and $\sigma$. Then, there exists an observable $A$ achieving the maximum such that
\begin{equation}
\tr(A\rho) - \tr(A\sigma) = \frac{1}{2}\norm{\rho - \sigma}_1.
\end{equation}

\end{corollary}

\begin{proof}[Proof of Corollary~\ref{coro:helstrom}]
We will construct an observable $A$ that maximizes $\tr(O(\rho - \sigma))$ over all observables $O$ with $\norm{O}_\infty \leq 1$. Choose a representation of $\rho - \sigma$ in terms of eigenstates $\ket{v}$. Suppose the eigenvalues are discrete:
\begin{equation}
(\rho - \sigma)\ket{v} = \lambda_v \ket{v}.
\end{equation}
Then, we can write the quantity we wish to maximize as
\begin{equation}
\tr(O(\rho - \sigma)) = \sum_v \lambda_v \expval{O}{v}.
\end{equation}
We can maximize this by choosing $A$ such that
\begin{equation}
\expval{A}{v} = \begin{cases}
1 & \text{if } \lambda_v > 0\\
0 & \text{if } \lambda_v \leq 0.
\end{cases}
\end{equation}
In this way, we can write $A$ as a sum of projectors
\begin{equation}
A = \sum_{v : \lambda_v > 0} \ketbra{v}.
\end{equation}
This maximizes $\tr(O(\rho-\sigma))$, so the corollary has been proven.
\end{proof}

\noindent With this, we can now prove Prop.~\ref{prop:hypothesis}.

\begin{proof}[Proof of Prop.~\ref{prop:hypothesis}]
The proof of Proposition 5.3 in~[130] uses shadow tomography as a black box.
We follow the same strategy but use classical shadow tomography~[68] instead of shadow tomography. Recall that in~[130], they run the shadow tomography algorithm from~[93] with observables given by Helstrom's Theorem~[69].
This is the key step that uses samples of the unknown quantum state $\rho$, so we need to analyze it when using classical shadow instead of shadow tomography.
In our setting, Corollary~\ref{coro:helstrom} states that for any $i \neq j$, there exists an observable $A_{ij}$ such that
\begin{equation}
\tr(A_{ij}\sigma_i) - \tr(A_{ij}\sigma_j) = \frac{1}{2}\norm{\sigma_i - \sigma_j}_1.
\end{equation}
Thus, the algorithm in~[130] uses $M = \binom{m}{2} = \mathcal{O}(m^2)$ observables $\{A_{ij}\}$ to select the hypothesis state, where $m$ is the size of the hypothesis set. Using classical shadow instead of shadow tomography requires
\begin{equation}
N = \tilde{\mathcal{O}}\left(\frac{\log(M/\delta)}{\epsilon^2}\max_{i,j}\norm{A_{ij} - \frac{\tr(A_{ij})}{2^n}\mathbb{I}}_{\mathrm{shadow}}^2\right)
\end{equation}
copies of $\rho$ by Theorem~\ref{thm:classical-shadow}, where $M$ is the number of observables $A_{ij}$ that we want to predict. Here, $M = \mathcal{O}(m^2)$ so that we require
\begin{equation}
N = \tilde{\mathcal{O}}\left(\frac{\log(m/\delta)}{\epsilon^2}\max_{i,j}\norm{A_{ij} - \frac{\tr(A_{ij})}{2^n}\mathbb{I}}_{\mathrm{shadow}}^2\right)
\end{equation}
copies of $\rho$.
We claim that
\begin{equation}
\max_{i,j}\norm{A_{ij} - \frac{\tr(A_{ij})}{2^n}\mathbb{I}}_{\mathrm{shadow}}^2 = \mathcal{O}(1).
\end{equation}
The lemma then follows from this claim.
We can prove this bound on the shadow norm using the construction of the observables $A_{ij}$ from Helstrom's Theorem, as seen in Corollary~\ref{coro:helstrom}. In our case, the states $\sigma_i$ are pure, and hence of rank $1$. Thus, the rank of $\sigma_i - \sigma_j$ is at most $2$ so that $A_{ij}$ is a projector of rank at most $2$.
Thus, the Frobenius norm of every $A_{ij}$ is $\mathcal{O}(1)$ and, by \cite[Proposition S1]{huang2020predicting}, the same holds for the shadow norm of the centered version of $A_{ij}$.
\end{proof}

\subsection{Characterizing the complexity of function classes}

In the proof of \Cref{thm:approx-functions} (in \Cref{app:learning-function}), we will need to characterize the complexity of certain function classes.
The following definitions will be useful.
Throughout the work, we use $\mathcal{Y}^\mathcal{X}$ to denote the set of functions from $\mathcal{X}$ to $\mathcal{Y}$.

\begin{definition}[Growth function, {[131]}]
Let $\mathcal{F}\subseteq \mathcal{Y}^\mathcal{X}$ be a class of functions with finite target space $\mathcal{Y}$.
For every subset $\Xi \subseteq X$, define the restriction of $\mathcal{F}$ to $\Xi$ as $\mathcal{F}|_\Xi = \{f\in \mathcal{Y}^\Xi: \exists F\in \mathcal{F}, \forall x\in \Xi, f(x)=F(x)\}$.
We define the growth function $\Gamma$ of $\mathcal{F}$ as
\begin{equation}
\Gamma(\mu) = \max_{\Xi\subseteq \mathcal{X}: |\Xi|\leq \mu} |\mathcal{F}|_\Xi|
\end{equation}
for any $\mu\in\mathbb{N}$.
\end{definition}

The growth function characterizes the size of $\mathcal{F}$ when restricted to a domain of $\mu$ points.
With growth function, we can define the VC dimension that characterizes the complexity of binary functions.

\begin{definition}[VC dimension, {[131]}]
The Vapnik-Chervonenkis (VC) dimension of a function class $\mathcal{F}\subseteq \{0, 1\}^\mathcal{X}$ is defined as
\begin{equation}
\mathrm{VCdim}(\mathcal{F}) = \max\{\mu\in \mathbb{N}: \Gamma(\mu)=2^\mu\},
\end{equation}
or $\infty$ if the maximum does not exist. Here $\Gamma(\mu)$ is the growth function of $\mathcal{F}$.
Or equivalently, $\mathrm{VCdim}(\mathcal{F})$ is the largest $D\in \mathbb{N}\cup\{\infty\}$ such that there exists a set of points $\{x_i\}_{i=1}^D\subseteq \mathcal{X}$ that for all $C\subseteq[D]$, there is a function $f\in \mathcal{F}$ satisfying
\begin{equation}
f(x_i)=1 \iff i\in C.
\end{equation}
These points are said to be shattered by $\mathcal{F}$.
\end{definition}

To go beyond binary functions, we can use pseudo dimension defined below.

\begin{definition}[Pseudo dimension, {[59]}]
\label{def:pdim}
The pseudo dimension of a real-valued function class $\mathcal{F}\subseteq \mathbb{R}^\mathcal{X}$ is defined as
\begin{equation}
\mathrm{Pdim}(\mathcal{F}) = \mathrm{VCdim}(\{\mathcal{X}\times \mathbb{R}\ni (x, y) \to \mathrm{sgn}[f(x)-y]: f\in\mathcal{F}\}).
\end{equation}
Or equivalently, $\mathrm{Pdim}(\mathcal{F})$ is the largest $D\in \mathbb{N}\cup\{\infty\}$ such that there exists a set of points $\{(x_i, y_i)\}_{i=1}^D\subseteq \mathcal{X}\times\mathbb{R}$ that for all $C\subseteq[D]$, there is a function $f\in \mathcal{F}$ satisfying
\begin{equation}
f(x_i)\geq y_i \iff i\in C.
\end{equation}
These points are said to be pseudo-shattered by $\mathcal{F}$.
\end{definition}

We will also use the fat-shattering dimension, a scale-sensitive variant of the pseudo-dimension.

\begin{definition}[Fat-shattering dimension, {[60]}]
\label{def:fat}
Let $\alpha>0$. The $\alpha$-fat-shattering dimension $\mathrm{fat}(\mathcal{F}, \alpha)$ of a real-valued function class $\mathcal{F}\subseteq \mathbb{R}^\mathcal{X}$ is defined as the largest $D\in \mathbb{N}\cup\{\infty\}$ such that there exists a set of points $\{(x_i, y_i)\}_{i=1}^D\subseteq \mathcal{X}\times\mathbb{R}$ that for all $C\subseteq[D]$, there is a function $f\in \mathcal{F}$ satisfying
\begin{equation}
\begin{split}
f(x_i)&\geq y_i + \alpha \quad \mathrm{if} \quad i\in C, \\
f(x_i)&\leq y_i - \alpha \quad \mathrm{if} \quad i\notin C.
\end{split}
\end{equation}
Such a set of points is said to be $\alpha$-fat-shattered by $\mathcal{F}$.
\end{definition}

\subsection{Cryptography}

Our computational complexity lower bounds rely on cryptographic primitives such as pseudorandom functions~[75] and pseudorandom quantum states~[74, 76].
A family of pseudorandom functions is a set of functions such that sampling from this family is indistinguishable from a uniformly random function.
We present the formal definition below, following the presentation in~[32].

\begin{definition}[Pseudorandom functions (PRFs)~[75]]
\label{def:PRF}
Let $\lambda$ denote the security parameter.
Let $\mathcal{K} = \{\mathcal{K}_\lambda\}_{\lambda\in \mathbb{N}}$ be an efficiently sampleable key space.
Let $\mathcal{X} = \{\mathcal{X}_\lambda\}_{\lambda\in \mathbb{N}}, \{\mathcal{Y}_\lambda\}_{\lambda\in\mathbb{N}}$ be finite sets.
Let $\mathcal{F} = \{f_\lambda\}_{\lambda\in\mathbb{N}}$ be family of efficiently-computable keyed functions $f_\lambda: \mathcal{K}_\lambda \times \mathcal{X}_\lambda \to \mathcal{Y}_\lambda$.
$\mathcal{F}$ is a \emph{pseudorandom function} if for every polynomial-time probabilistic algorithm $\mathsf{Adv}$, there exists a negligible function $\mathsf{negl}(\cdot)$ such that for every security parameter $\lambda\in \mathbb{N}$
\begin{equation}
\left|\Pr_{\mathbf{k} \leftarrow \mathcal{K}_\lambda}[\mathsf{Adv}^{f(\mathbf{k}, \cdot)}(\cdot) = 1] - \Pr_{g \in \mathcal{U}_\lambda}[\mathsf{Adv}^{g}(\cdot) = 1]\right| \leq \mathsf{negl}(\lambda),
\end{equation}
where the key $\mathbf{k}$ is picked uniformly at random from the key space $\mathcal{K}_\lambda$ and $g$ is picked uniformly at random from $\mathcal{U}_\lambda$, the set of all functions from $\mathcal{X}_\lambda$ to $\mathcal{Y}_\lambda$.
Here, $\mathsf{negl}(\lambda)$ denotes a negligible function, i.e., a function that grows more slowly than any inverse polynomial in $\lambda$.
\end{definition}

Concretely, it is common to take the input and output spaces to be $\mathcal{X}_\lambda = \{0,1\}^{m}$ and $\mathcal{Y}_\lambda = \{0,1\}$ for some input length $m = m(\lambda)$ that depends on the security parameter $\lambda$.
We consider this setting throughout the work.

\begin{definition}[Quantum secure PRFs~[32]]
Let $\lambda$ denote the security parameter.
A pseudorandom function is \emph{quantum secure against $t(\lambda)$ adversaries} if it satisfies \Cref{def:PRF} where $\mathsf{Adv}$ is a $t(\lambda)$-time quantum algorithm with quantum query access to $f_{\mathbf{k}}$ and $g$.
When $t(\lambda)=\poly(\lambda)$, we say that the PRF is \emph{quantum secure}.
\end{definition}

There are several constructions for implementing PRFs with low-depth circuits~[132, 133, 32].
We will focus on the construction of~[32], which relies on the assumption that the Ring Learning with Errors (\textsf{RingLWE}) problem~[30] is hard even for quantum computers.
Specifically, we assume that \textsf{RingLWE} cannot be solved by a quantum computer in sub-exponential time, which is a commonly believed cryptographic assumption~[34, 32, 35, 33, 31].
Here, \textsf{RingLWE} is a variant of the more well-known Learning with Errors problem~[31] over polynomial rings.
The \textsf{RingLWE} problem is to find a secret ring element $s \in R_q \triangleq \mathbb{Z}_q[x]/\langle x^\lambda - 1 \rangle$ given pairs $(a, a \cdot s + e \bmod R_q)$, where $\lambda$ denotes the security parameter, $e$ is some error, $q$ is a parameter of the problem.
We only state this informally here and refer the reader to~[30] for a formal definition and discussion.
In~[32], assuming that \textsf{RingLWE} cannot be solved by quantum computers in $t(\lambda)$ time, their construction produces a PRF secure against $\bigo(t(\lambda))$ quantum adversaries that is implementable by constant-depth, polynomial-size circuits.
We state the precise result below.

\begin{theorem}[Lemmas 3.15 and 3.16 in~[32]]
\label{thm:PRF}
Let $\lambda$ denote the security parameter.
Let the input size be $m = m(\lambda) =  \omega(\log \lambda)$ and set the parameter $q =\lambda^{\omega(1)}$ to be a power of two such that $\log(q) \leq \mathcal{O}(\poly(\lambda))$.
Let $\mathcal{K} = \{\mathcal{K}_\lambda\}_{\lambda \in \mathbb{N}}$, where $\mathcal{K}_\lambda = R_q^{m+1}$.
There exists a PRF $\mathcal{RF} = \{f_\lambda\}_{\lambda \in \mathbb{N}}$, where $f_\lambda: R_q^{m+1} \times \{0,1\}^m \to \{0,1\}$, satisfying the following two properties.
\begin{enumerate}
\item Every $f_\lambda(\mathbf{k},\cdot) \in \mathcal{RF}$ with $\mathbf{k} \in \mathcal{K}_\lambda$ can be computed by a $\mathsf{TC}^0$ circuit.
\item Suppose there exists a distinguisher $\mathcal{D}$ for $\mathcal{RF}$, i.e., there exists an $\bigo(t(\lambda))$-time quantum algorithm $\mathcal{D}$ that satisfies
\begin{equation}
\left|\Pr_{\mathbf{k} \leftarrow \mathcal{K}_\lambda}[\mathcal{D}^{\ket{f_\lambda(\mathbf{k}, \cdot)}}(\cdot) = 1] - \Pr_{g \in \mathcal{U}}[\mathcal{D}^{\ket{g}}(\cdot) = 1]\right| > \mathsf{negl}(\lambda),
\end{equation}
where the key $\mathbf{k}$ is picked uniformly at random from the key space $\mathcal{K}_\lambda$, $g$ is picked uniformly at random from $\mathcal{U}$, the set of all functions from $\mathcal{X}_\lambda$ to $\mathcal{Y}_\lambda$, and $\mathcal{D}^{\ket{f_\lambda(\mathbf{k}, \cdot)}}$ indicates that $\mathcal{D}$ has quantum oracle access to the function $f_\lambda(\mathbf{k}, \cdot)$. Then, there exists a $t(\lambda)$-time quantum algorithm that solves \textsf{RingLWE}.
\end{enumerate}
\end{theorem}

In Property 2, this is equivalent to saying that the PRF is quantum secure against $\bigo(t(\lambda))$ adversaries, assuming that \textsf{RingLWE} cannot be solved by a $t(\lambda)$-time quantum algorithm.
Also, note that in Property 1, $\mathsf{TC}^0$ circuits refer to constant-depth, polynomial-size circuits with unbounded fan-in \textsf{AND}, \textsf{OR}, \textsf{NOT}, and \textsf{MAJORITY} gates.
We claim that every $\mathsf{TC}^0$ circuit has a quantum circuit computing the same function with poly-logarithmic overhead in depth.

\begin{prop}[Quantum circuits for $\mathsf{TC}^0$]
Let $C$ be a $\mathsf{TC}^0$ circuit on $m$ inputs computing some Boolean function $f:\{0,1\}^m \to \{0,1\}$.
Then, there exists a quantum circuit $C'$ on $n = \mathcal{O}(\poly(m))$ qubits of size $\mathcal{O}(n\polylog(n))$ and depth $\mathcal{O}(\polylog(n))$ that implements $f$.
\end{prop}

Here, when we say that $C'$ implements the function $f$, we mean that $C'\ket{x}\ket{z} = C'\ket{x}\ket{z \oplus f(x)}$.

\begin{proof}
Note that the number of qubits is $n = \mathcal{O}(\poly(m))$ because after each gate in the classical circuit $C$, we must store the result in an ancilla qubit to maintain unitarity.
Recall that $\mathsf{TC}^0$ circuits are constant-depth, polynomial-size circuits with unbounded fan-in \textsf{AND}, \textsf{OR}, \textsf{NOT}, and \textsf{MAJORITY} gates.
Thus, it suffices to find the depth of implementing each of these gates quantumly.
The size then follows because a circuit of depth $d$ on $n$ qubits can have at most $nd$ gates.
\textsf{NOT} gates can clearly be implemented in constant depth since this is just an $X$ gate.
An \textsf{AND} gate with $m$ inputs can be completed in logarithmic depth by computing \textsf{AND} pairwise with \textsf{CNOT}.
Similarly, we can compute an \textsf{OR} gate with the same logarithmic depth.
It remains to analyze the depth needed for computing a \textsf{MAJORITY} gate.
Recall that the \textsf{MAJORITY} gate is defined as
\begin{equation}
\textsf{MAJ}(x_1,\dots,x_m) = \left\lfloor \frac{1}{2} + \frac{\left(\sum_{i=1}^m x_i\right) - 1/2}{m} \right\rfloor = \left\lfloor \frac{1}{2} + \frac{\sum_{i=1}^m x_i}{m} - \frac{1}{2m} \right\rfloor.
\end{equation}
Here, addition is done over the integers and $x_i \in \{0,1\}$.
We first analyze the depth/size required for the addition $\sum_{i=1}^m x_i$.
Note that the maximum value of this sum is $m$, which can be stored in $\mathcal{O}(\log m)$ bits.
Thus, we can write each of the $x_i$ in binary using $\log m$ bits by padding with zeros and perform addition in this way.
We can perform the addition of the $m$ inputs pairwise, parallelized to $\mathcal{O}(\log m)$ depth and requiring $\mathcal{O}(m)$ addition operations.
Moreover, one can perform these addition operations using quantum circuits of size and depth $\mathcal{O}(\log m)$~[134].
The construction in~[134] uses Toffoli gates, but these can be decomposed into two-qubit gates with constant overhead~[135].
In total, we have that $\sum_{i=1}^m x_i$ can be implemented by a quantum circuit of depth $\mathcal{O}(\log^2m)$.

To divide this sum by $m$, note that there exist classical Boolean circuits for integer division of depth $\mathcal{O}(\log \log m)$ since our inputs can be represented in binary using $\log m$ bits~[136].
These Boolean circuits use only standard \textsf{AND}, \textsf{OR}, and  \textsf{NOT} gates.
As explained previously, these can be implemented quantumly, and for fan-in-$2$ \textsf{AND} and \textsf{OR} gates, this can be done with constant overhead.
Thus, this division step requires depth $\mathcal{O}(\log \log m)$ in total.

Finally, we need to compute the remaining addition/subtraction and floor operations.
The addition/subtraction can be ignored since  they only occur once so that the depth is dominated by the other additions.
For the floor, because the quantity inside can only be less than or equal to $1$, then this is the same as deciding whether the quantity inside is less than $1$ or not.
This can be done in a constant number of operations.

Putting everything together, we see that the circuit depth for implementing a \textsf{MAJORITY} gate is dominated by $\mathcal{O}(\log^2 m)$.

Recall again that $\mathsf{TC}^0$ describes constant-depth, polynomial-size circuits with unbounded fan-in \textsf{AND}, \textsf{OR}, \textsf{NOT}, and \textsf{MAJORITY} gates.
We just analyzed the depth for each of these gates individually.
In summary, we computed that $\mathcal{O}(\log m)$ quantum depth is sufficient for \textsf{AND} and \textsf{OR}.
Constant $\mathcal{O}(1)$ depth is sufficient for \textsf{NOT}.
Finally, $\mathcal{O}(\log^2 m)$ depth is sufficient for \textsf{MAJORITY}.
In the overall circuit, this totals to $\mathcal{O}(\polylog(m))$ depth.