Learning the Complexity of Weakly Noisy Quantum States

## Abstract

Abstract Quantum computers capable of fault-tolerant operation are expected to provide provable advantages over classical computational models. However, the question of whether quantum advantages exist in the noisy intermediate-scale quantum era remains a fundamental and challenging problem. The root of this challenge lies in the difficulty of exploring and quantifying the power of noisy quantum states. In this work, we focus on the complexity of weakly noisy states, which we define as the size of the shortest quantum circuit required to prepare the noisy state. To analyze this complexity, we first establish a general relationship between circuit depth, noise model, and purity. Based on this necessary condition, we propose a quantum machine learning (QML) algorithm that exploits the intrinsic-connection property of structured quantum neural networks. The proposed QML algorithm enables efficiently predicting the complexity of weakly noisy states from measurement results, representing a paradigm shift in our ability to characterize the power of noisy quantum computation.

## I Introduction

The concept of quantum complexity has deep connections to high-energy physics, quantum many-body systems, and black-hole physics [, , , , ]. Within the context of quantum computation, the complexity of a quantum state characterizes the necessary quantum resources required to prepare a state that reveals the solution to a problem. We determine the complexity of an $n$-qubit quantum state by finding the minimum number of gates required to prepare it from the initial $\ket{0^{n}}\bra{0^{n}}$ state [, ]. Brown and Susskind’s conjecture, which is supported by the complexity geometry theory proposed by Nielsen et al. [, ], suggested that the random quantum state complexity grows linearly before it saturates after reaching an exponential size [, ]. Recent works have connected quantum state complexity to unitary $t$-designs [, ] and the dimension of semi-algebraic sets [], further supporting Brown and Susskind’s conjecture. This implies that most random quantum circuits are challenging to compress and optimize. Furthermore, given the technical limitations of near-term quantum devices [, ], structured quantum circuits with a brickwall-type layout of gates [, , ] are preferred. It is believed that structured random quantum states are classically difficult to generate under the anticoncentration property in the average-case scenario [, , , , , , , ], implying that structured quantum circuits could provide quantum advantages for industrial applications, such as approximating the ground state energy of physically relevant Hamiltonians [, , , , , ], solving combinatorial optimization problems [, , ], and addressing quantum chemistry problems [, , , , , , , , ].

Despite the remarkable progress in quantum hardware during the Noisy-Intermediate-Quantum (NISQ) era, limitations on gate fidelities still remain a hindrance to realizing the full computational potential of such devices [, , , ].
When a $\Omega(\log n)$-depth noisy circuit is subjected to a depolarizing channel, the resulting state is situated in the classically efficient ‘Gibbs ball’ as demonstrated in []. Furthermore, increasing the depth of the noisy circuit leads to a state that is close to the maximally mixed state in terms of trace distance, thus forfeiting any potential quantum advantages []. These results suggest noisy channels may weaken the complexity of a quantum state. The affect of noise channels have practical implications in various fields, including physics research. For example, in the context of the anti-de-Sitter-space/conformal field theory (AdS/CFT) correspondence, the “complexity equals volume” conjecture [] suggests that the boundary state of the correspondence has a complexity proportional to the volume behind the event horizon of a black hole in the bulk geometry. However, when measuring the boundary state, the interaction with the surrounding environment inevitably introduces noise signal, causing the pure state to become a noisy state.

This thus raises an essential problem: how can the quantum state complexity of an unknown weakly noisy quantum state be predicted with only a few copies available? Here, we investigate this problem. The accumulation of noise caused by the noisy quantum gates significantly increases the challenge in estimating the dimension of the accessible space and constructing a Clifford high-rank point of the noisy state []. Then, prior studies have examined the convergence rate of random noisy states to the maximally entangled state, but these studies require the Haar-random assumption and a specific noise model [, , , ]. Therefore, it is difficult to apply these findings directly to predict the complexity of a particular unknown noisy state. More recently, the overlap tomography approach has been utilized to measure quantum state complexity [], but the efficiency in generating unstructured “proof states” remains unclear. On the other hand, the expressive power [, , ], optimization [, , , ], and applications [, , , , , , , , , , , , , ] of quantum machine learning (QML) have been intensively studied. Furthermore, recent pioneering experiments conducted on quantum computer processors [, ] have shown significant quantum computational advantages, particularly in predicting linear properties of the density matrix. Hence, it is plausible to expect that QML can offer a novel perspective on predicting the quantum state complexity of noisy states.

Due to the signal-weakening nature of noise channels, it is expected a weakly noisy state can be approximated by a much shallower quantum circuit. Following such intuition, this article presents a quantum learning approach for investigating the Structured Complexity Prediction (SCP) problem. Specifically, the problem pertains to determining whether a quantum state $\rho_{\rm un}$, generated from a noisy quantum circuit with at most $\mathcal{O}(\log n)$ depth and a weak noise strength, can be approximated by a shallower $R$-depth structured quantum neural network (QNN) state with $\epsilon$ additive error by trace distance. The QNN represents a periodic structured quantum circuit where each two-qubit gate is determined by a classical tunable parameter (as illustrated in Fig. [1](#S1.F1) (b)). The constraints on the noisy circuit depth and noisy strength ensure a weakly noisy state, denoted as $\Phi_{1}$ in Fig. [1](#S1.F1) (c). In this paper, our first contribution is characterizing the relationship between circuit depth, general noise models, and purity, as claimed in Theorem [1](#Thmtheorem1). This necessary condition is suitable for a wide range of noise models and accurately defines a boundary for using a pure state to approximate a weakly noisy state. To connect the weakly noisy state complexity with the QNN, we leverage a significant property in QNN, termed as intrinsic-connection property (Theorem [2](#Thmtheorem2)). This property asserts that the behavior of an observable $M$, generated by a quantum circuit in $\mathcal{U}_{\mathcal{A}}(R)$, can be emulated by linear combinations of ${\rm poly}(R,n)$ random QNN states from $\mathcal{U}_{\mathcal{A}}(R)$. Here, $\mathcal{A}$ denotes a QNN architecture and $\mathcal{U}_{\mathcal{A}}(R)$ represents a set of $R$-depth QNN circuits induced by $\mathcal{A}$. Based on this property, we propose transforming the complexity prediction task into the recognition of a noisy state from a set of QNN states by utilizing a tunable measurement operator constrained to $\mathcal{U}_{\mathcal{A}}(R)$. Finally, Theorem [3](#Thmtheorem3) indicates a quantum machine learning algorithm can be efficiently trained in recognizing the weakly noisy state from QNN states, and provides a complexity prediction (the minimum $R$). Importantly, our proposed QML approach only requires the shadow tomography [] (classical representation) of related QNN states, instead of a fault-tolerant quantum computer.

In addition to its implications for complexity analysis, the SCP problem and QML method have broad applications. One potential application is the generation of mixed state approximations with a large overlap to the target noisy state (see Corollary [1](#Thmcorollary1)). Moreover, recent work [] suggests that a $\Omega(\log n)$-depth Haar random circuit with local depolarizing channel can be efficiently simulated by a classical computer. However, the complexity of such circuits with depth $o({\rm poly}\log(n))$ remains unclear. The SCP problem serves as a valuable tool in linking weakly noisy states to shallower, noiseless quantum states, and can thus be used to characterize potential quantum advantages in noisy state sampling problems [, , , , , ]. Finally, the proposed QML method is expected be applied in classifying quantum topological phases of matter [, , , , , , ]. Topological phases can be distinguished by their ground state complexity [], and the shadow tomography [, ] method provides a mixed state approximation to the ground state. Thus, the QML method can estimate the ground state complexity from the classical shadow and provide classification results based on this complexity.

This paper is organized as follows. In Sec. [II](#S2) we introduce the setup and definitions that will be used in this work. In Sec. [III](#S3), we present the main result. We provide quantum learning algorithm in Sec. [IV](#S4), and the corresponding theoretical performance analysis is provided in Sec. [V](#S5). We finally discuss applications in Sec. [VI](#S6).

Figure: Figure 1: (a) An efficient quantum-to-classical representation conversion method that leverages the classical shadow of a noisy state. By measuring only a few copies of the state, it can construct a classical representation that enables the prediction of the state’s properties with a rigorous performance guarantee. (b) A QNN model with $R$ layers, where each layer corresponds to a causal slice, and the overall architecture follows the design of $\mathcal{A}$. (c) Illustration of the relationship between a $\tilde{R}$-depth weakly noisy quantum state $\Phi$ and its nearest pure state. All pure states reside on the surface of the $n$-qubit Bloch sphere, with the maximum mixed state $\frac{I_{n}}{2^{n}}$ located at the center of the sphere. In the regime where $\tilde{R}<\mathcal{O}({\rm poly}\log n)$ and for a small noise strength $p$, the weakly noisy state $\Phi=\Phi_{1}$ is located near the surface of the sphere, and it could be approximated by a pure state $U\ket{0^{n}}\bra{0^{n}}U^{\dagger}$ (refer to Theorem [1](#Thmtheorem1) and Lemma [7](#Thmlemma7)). However, if $\Phi=\Phi_{2}$, it is located near the maximum mixed state, and it cannot be approximated by any pure state.
Refer to caption: /html/2303.17813/assets/x1.png

## II Theoretical Background

To clearly demonstrate motivations and contributions in this paper, we review the related theoretical backgrounds in terms of quantum state complexity, noisy quantum state, and quantum machine learning, then a brief discussion on the hardness result in quantum state learning problems is provided.

### II.1 Quantum State Complexity

Here, we consider the quantum state complexity of an $n$-qubit quantum pure state $|\psi\rangle$. The complexity of a quantum state is the minimal circuit size required to implement a measurement operator that suffices to distinguish $|\psi\rangle\langle\psi|$ from the maximally mixed state $I_{n}/2^{n}$. Since any pure state $|\psi\rangle\langle\psi|$ satisfies

$$ $\displaystyle d(\psi,\rho_{0})=\frac{1}{2}\left\||\psi\rangle\langle\psi|-I_{n}/2^{n}\right\|_{1}=1-\frac{1}{2^{n}},$ (1) $$

which is achieved by the optimal measurement strategy $M=|\psi\rangle\langle\psi|$, such trace distance can be used to quantify the quantum state complexity. Let $\mathbb{H}_{2^{n}}$ denote the space of $2^{n}\times 2^{n}$ Hermitian matrices, and for fixed $r\in\mathbb{N}$, we consider a class of measurement operators $M_{r}(2^{n})\subset\mathbb{H}_{2^{n}}$ that can be constructed by at most $r$ $2$-local gates. The maximal bias achievable for quantum states with such a restricted set of measurements of the solution is defined as:

$$ $\displaystyle\beta_{QS}(r,|\psi\rangle)=\max_{M\in M_{r}(2^{n})}\left|{\rm Tr}\left(M(|\psi\rangle\langle\psi|-I_{n}/2^{n})\right)\right|,$ (2) $$

where $|\psi\rangle=V|0^{n}\rangle$ for some $V\in{\rm SU}(2^{n})$. Noting that the above metric $\beta_{QS}(r,|\psi\rangle)$ degenerates to $1-2^{-n}$ when $r\to\infty$. For example, if the quantum state $|\psi\rangle$ can be easily prepared by a quantum computer (such as computational basis), $\beta_{QS}(r,|\psi\rangle)$ convergences to $1-2^{-n}$ rapidly with the increase of $r$, while in general $|\psi\rangle$ requires exponentially large $r$ to convergence to $1-2^{-n}$. Using this property, the quantum state complexity can be defined as follows:

###### Definition 1 (Approximate State Complexity [ 12 ] ) .

Given an integer $r$ and $\epsilon\in(0,1)$, we say a pure quantum state $|\psi\rangle$ has $\epsilon$-strong state complexity at most $r$ if and only if

$$ $\displaystyle\beta_{QS}(r,|\psi\rangle)\geq 1-\frac{1}{2^{n}}-\epsilon,$ (3) $$

which is denoted as $C_{\epsilon}(|\psi\rangle)\leq r$.

###### Definition 1 (Approximate State Complexity [ 12 ] ) .

### II.2 Noisy Quantum State Preparation

Consider implementing an $n$-qubit quantum circuit consisting of $\tilde{R}$ layers $U_{1},U_{2},...,U_{\tilde{R}}$, where each layer $U_{r}$ forms a causal slice with the following property.

###### Definition 2 (Architecture [ 7 , 17 ] ) .

An architecture $\mathcal{A}$ is a directed acyclic graph that contains $\left|\mathcal{V}\right|\in\mathbb{Z}_{>0}$ vertices (gates), and two edges (qubits) enter each vertex, and two edges exit. A quantum circuit induced by the architecture $\mathcal{A}$ is denoted as $U_{\mathcal{A}}$.

We define the single layer $U(\vec{\theta})$ be the unitary constructed by parametrized two-qubit gates with parameters $\vec{\theta}\in[0,2\pi)^{L}$ where $L$ is the number of two-qubit gates. Here the number of parameters is set to correspond to Definition [4](#Thmdefinition4), but actually there should be more than one parameter for a 2-qubit gate.

###### Definition 3 (Causal Slice) .

The circuit $U_{\mathcal{A}}$ is a causal slice if there exists a qubit-reachable path between any two qubit-pairs, where the path only passes through vertices (gates) in the architecture $\mathcal{A}$.

The common causal slice layer $U_{r}$ can take the form of either a brickwork or staircase pattern (an example of the latter is shown in Fig. [1](#S1.F1)(b)), where the minimal causal slice contains $n-1$ gates linking the nearest qubits on a $1\rm D$ qubit chain. However, due to imperfections in quantum hardware devices, two causal slices are separated by a quantum channel $\mathcal{E}$. We assume that the noise channel $\mathcal{E}$ is both gate-independent and time-invariant, and describe the output of the noisy quantum circuit using the quantum channel $\Phi_{p,\tilde{R}}(\cdot)=\bigcirc_{r=1}^{\tilde{R}}\mathcal{E}\circ\mathcal{U}_{r}(\cdot)$, where $\mathcal{U}_{r}(\rho)=U_{r}\rho U_{r}^{\dagger}$. In this paper, we consider $\mathcal{E}$ to represent a general noise channel, such as the local-depolarizing channel, the global-depolarizing channel, bit-flip channel and other common noise models.

###### Definition 4 (Noisy Quantum State) .

We assume that the noise in the quantum device is modeled by a gate-independent noise channel $\mathcal{E}$ with strength $p$. Let $\mathcal{U}$ be a causal slice with $L$ parameters, and let $\mathcal{E}\circ\mathcal{U}$ be the representation of a noisy gate. We define the $\tilde{R}$-depth noisy quantum state with noise strength $p$ as

$$ $\displaystyle\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle 0^{n}|,\vec{\bm{\theta}})=\mathcal{E}\circ\mathcal{U}_{\tilde{R}}(\vec{\theta}_{\tilde{R}})\circ\mathcal{E}\circ\mathcal{U}_{\tilde{R}-1}(\vec{\theta}_{\tilde{R}-1})\circ\cdots\circ\mathcal{E}\circ\mathcal{U}_{1}(\vec{\theta}_{1})(|0^{n}\rangle\langle 0^{n}|).$ (4) $$

Here, the ideal circuit is given by $\mathcal{U}_{\tilde{R}}(\vec{\theta}_{\tilde{R}})\circ\mathcal{U}_{\tilde{R}-1}(\vec{\theta}_{\tilde{R}-1})\circ\mathcal{U}_{1}(\vec{\theta}_{1})$, with parameters $\vec{\bm{\theta}}\in[0,2\pi]^{L\tilde{R}}$. We use the term “weakly noisy states” to refer to noisy states $\Phi_{p,\tilde{R}}$ with $\tilde{R}\leq\mathcal{O}({\rm poly}\log n)$ and small $p$.

###### Definition 2 (Architecture [ 7 , 17 ] ) .

###### Definition 3 (Causal Slice) .

###### Definition 4 (Noisy Quantum State) .

### II.3 Quantum Neural Network State

###### Definition 5 (Quantum Neural Network (QNN) State) .

Suppose $\mathcal{U}_{\mathcal{A}}(R)$ represents an $n$-qubit quantum neural network set induced by a $R$-layer brickwork periodic architecture $\mathcal{A}$, the quantum neutral network state $|\Psi(\vec{\bm{\alpha}})\rangle=U(\vec{\bm{\alpha}})|0^{\otimes n}\rangle=\prod_{r=1}^{R}U_{r}(\vec{\alpha}_{r})|0^{\otimes n}\rangle$ where each layer $U_{r}(\vec{\alpha}_{r})$ contains $L$ two-qubit gate and $U(\vec{\bm{\alpha}})\in\mathcal{U}_{\mathcal{A}}(R)$. A set of $R$-layer QNN states with structure $\mathcal{A}$ is denoted as $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)=\{|\Psi_{i}\rangle=U(\vec{\bm{\alpha}}_{i})|0^{n}\rangle\}_{i=1}^{N}$.

###### Definition 6 (Quantum State Learning) .

We say a QNN model $U(\vec{\bm{\alpha}})$ can learn an unknown quantum state $\rho_{\rm un}$ with $\epsilon$ error if there exists a parameter $\vec{\bm{\alpha}}^{*}$ enabling

$$ $\displaystyle R_{s}(\vec{\bm{\alpha}}^{*})=\mathbb{E}_{O_{\bm{x}}\sim\mathcal{P}_{n}}\left|\langle 0^{\otimes n}|U^{\dagger}(\vec{\bm{\alpha}}^{*})O_{\bm{x}}U(\vec{\bm{\alpha}}^{*})|0^{\otimes n}\rangle-{\rm Tr}(\rho_{\rm un}O_{\bm{x}})\right|\leq\epsilon,$ (5) $$

where $\mathcal{P}_{n}$ represents $n$-qubit Pauli group and $\epsilon=1/{\rm poly}(n)$.

###### Remark 1 .

Suppose the weakly noisy state $\rho_{\rm un}$ is provided, and we wish to estimate its complexity using quantum machine learning (QML) techniques. If we can efficiently train a shallow quantum neural network (SQNN) model to satisfy a certain condition (as expressed in Eq. [5](#S2.E5)), we can use the resulting QNN state to estimate the complexity of $\rho_{\rm un}$. However, recent research suggests that finding the optimal parameters for a SQNN may be a difficult task, and even the optimization of a QNN’s parameters is known to be an $\rm NP$-hard problem in the worst-case scenario []. Nonetheless, in this paper, we demonstrate that it is still possible to quantify the complexity of a noisy quantum state using QML and the intrinsic-connection property of SQNNs, even in the face of these challenges.

###### Remark 2 .

Note that Eq. [5](#S2.E5) can only be used in learning a pure state or a weakly noisy state which is denoted as $\Phi_{1}$ in Fig. [1](#S1.F1) (c).

###### Definition 5 (Quantum Neural Network (QNN) State) .

###### Definition 6 (Quantum State Learning) .

###### Remark 1 .

###### Remark 2 .

## III Quantifying Weakly Noisy State Complexity via Quantum Learning Algorithm

This section is organized as follows. First, we formally define the learning problem in Task [1](#Thmtask1): *what is the complexity of an unknown weakly noisy state?* Next, we present our main result. Theorem [1](#Thmtheorem1) characterizes the relationship between circuit depth, general noise models, and approximation error. This necessary condition accurately defines a boundary for using a pure state to approximate a weakly noisy state. Based on this condition, we demonstrate that quantum machine learning can analyze the complexity of weakly noisy states by utilizing the intrinsic-connection property in QNN models. We prove this claim in Theorems [2](#Thmtheorem2) and [3](#Thmtheorem3).

### III.1 Learning Task Statement

It is important to note that Definition [1](#Thmdefinition1) relies on unstructured quantum circuits to characterize pure state complexity. This approach allows for the use of ancillary qubits to synthesize measurement operators. However, it is generally difficult to exclude shortcuts that could improve the efficiency of a computation. As a result, deriving quantum complexity measures for weakly noisy states can be challenging without additional assumptions. Recent results on the linear growth of the random quantum state complexity suggest that even structured circuits are difficult to compress, either exactly or approximately [, ]. Consequently, structured circuits is employed in the study and benchmarking of weakly noisy state complexity.

###### Definition 7 (Limited-Structured (LS) Complexity of Noisy State) .

Given an integer $r$ and $\epsilon\in(0,1)$, we say a weakly noisy state $\rho$ has $\epsilon$-LS complexity at most $r$ if and only if

$$ $\displaystyle\max\limits_{\begin{subarray}{c}M_{r}=U|0^{n}\rangle\langle 0^{n}|U^{\dagger}\\ U\in\mathcal{U}_{\mathcal{A}}([r/L])\end{subarray}}\left|{\rm Tr}\left(M_{r}(\rho-I_{n}/2^{n})\right)\right|\geq 1-\frac{1}{2^{n}}-\epsilon$ (6) $$

which is denoted as $C^{{\rm lim},\mathcal{A}}_{\epsilon}(\rho)\leq r$. The notation $L$ represents the number of gates in each layer of $U$.

###### Definition 8 (Structured State Approximation Property, ${\rm SSAP}(\mathcal{A},\epsilon)$ ) .

We say an $n$-qubit weakly noisy quantum state $\rho_{\rm un}$ (defined as Eq. [4](#S2.E4)) satisfies ${\rm SSAP}(\mathcal{A},\epsilon)$ if $\rho_{\rm un}$ can be approximated by a $R$-depth ($R<\log n$) SQNN state with architecture $\mathcal{A}$ within LS error $\epsilon$.

Here, an explanation on the concerned pure state boundary $R<\log n$ is provided. If a noisy state is affected by local depolarizing channel with depth $\tilde{R}\geq\Omega(\log n)$, then the resulting output distribution can be efficiently simulated by a classical computer. This implies that any possible quantum advantages are lost. This property is particularly relevant for weakly noisy states with a depth of at most $\mathcal{O}(\log n)$, and the natural weakening of the signal by the noisy channel thus limits the boundary of its pure state approximation to at most $\log n$.

The ${\rm SSAP}(\mathcal{A},\epsilon)$ property of a weakly noisy state $\rho_{\rm un}$ implies the existence of a quantum circuit $U\in\mathcal{U}_{\mathcal{A}}(R)$ such that $\langle 0^{n}|U^{\dagger}\rho_{\rm un}U|0^{n}\rangle\geq 1-\epsilon$, or equivalently, $\frac{1}{2}\|U|0^{n}\rangle\langle 0^{n}|U^{\dagger}-\rho_{\rm un}\|_{1}\leq\sqrt{\epsilon+2^{-n}}$. When $\epsilon=1/n$, if sample from $U|0^{n}\rangle$ is classically hard, then sampling with probability $p(i)=\langle i|\rho_{\rm un}|i\rangle$ is also hard for any classical algorithm, unless the Polynomial Hierarchy collapses [, , , , ]. Therefore, the ${\rm SSAP}(\mathcal{A},\epsilon)$ property gives a non-trivial upper bound for $C_{\epsilon}(\rho_{\rm un})$, that is,

$$ $C_{\epsilon}(\rho_{\rm un})\leq C^{{\rm lim},\mathcal{A}}_{\epsilon}(\rho_{\rm un})\leq{\rm size}(U).$ $$

If $C_{\epsilon}^{\rm lim,\mathcal{A}}(\rho_{\rm un})>L\log n$, then $\rho_{\rm un}$ cannot be approximated by any pure state within $\epsilon$-LS error with architecture $\mathcal{A}$ and depth $R<\log n$. Here, the main task is formally defined as follows.

###### Task 1 (Structured Complexity Prediction ( ${\rm SCP}(\mathcal{A})$ )) .

Given an architecture $\mathcal{A}$ and any $n$-qubit weakly noisy quantum state $\rho_{\rm un}$ (defined as Eq. [4](#S2.E4)) and an approximation error $\epsilon$.
Learn the unknown quantum state $\rho_{\rm un}$ through a quantum machine learning algorithm ${\rm QML}_{n}$ with a poly$(n)$-qubit ideal quantum device, such that the output satisfies:

- 1.
(Completeness/YES) If $\rho_{\rm un}$ satisfies ${\rm SSAP}(\mathcal{A},\epsilon)$, then ${\rm QML}_{n}$ outputs the minimum $R$ with unit probability.
- 2.
(Soundness/NO)
${\rm QML}_{n}$ outputs NO with high probability otherwise.

###### Remark 3 .

Note that the structure of the weakly noisy circuit that generates $\rho_{\rm un}$ is independent to the architecture $\mathcal{A}$ in the SCP($\mathcal{A}$) problem.

###### Definition 7 (Limited-Structured (LS) Complexity of Noisy State) .

###### Definition 8 (Structured State Approximation Property, SSAP ​ ( 𝒜 , ϵ ) SSAP 𝒜 italic-ϵ {\rm SSAP}(\mathcal{A},\epsilon) ) .

###### Task 1 (Structured Complexity Prediction ( SCP ​ ( 𝒜 ) SCP 𝒜 {\rm SCP}(\mathcal{A}) )) .

###### Remark 3 .

### III.2 Main Results

To ensure the ${\rm SSAP}(\mathcal{A})$ property in our framework, it is necessary to present a condition that accounts for the effect of $\mathcal{E}$ on deviating the noisy state from the Bloch spherical.

###### Theorem 1 .

Suppose we are given a general noisy channel $\mathcal{E}(\cdot)=\sum_{l=1}^{r}K_{l}(\cdot)K_{l}^{\dagger}$ and a noisy state $\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle 0^{n}|)=\bigcirc_{r=1}^{\tilde{R}}\mathcal{E}\circ\mathcal{U}_{r}(|0^{n}\rangle\langle 0^{n}|)$, where the $\mathcal{U}_{t}$ are drawn independently from a unitary 2-design set $\mathbb{U}$. Then for each noisy state $\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle 0^{n}|)$, there exists a corresponding $\tilde{R}$-depth pure state $|\Psi_{\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}}}\rangle$ such that

$$ $\displaystyle\mathbb{E}_{\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}}\sim\mathbb{U}}\langle\Psi_{\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}}}|\left(\bigcirc_{r=1}^{\tilde{R}}\mathcal{E}\circ\mathcal{U}_{r}(|0^{n}\rangle\langle 0^{n}|)\right)|\Psi_{\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}}}\rangle\geq\eta(\tilde{R}),$ (7) $$

where

$$ $\displaystyle\eta(\tilde{R})=\left(\frac{F-1}{d^{2}-1}\right)^{\tilde{R}-1}\frac{F-1}{d(d+1)}+\frac{1}{d},$ (8) $$

$d=2^{n}$ and $F=\sum_{l=1}^{r}\left|{\rm Tr}(K_{l})\right|^{2}$.

A particularly noteworthy aspect of the presented theorem is its applicability to general noise models. This allows us to establish a precise relationship between the depth of a quantum circuit $\tilde{R}$, the noise model $\mathcal{E}$, and the quality of approximation (purity) $\eta(\tilde{R})=1-\epsilon$ that can be achieved. In light of this, we observe that while depolarizing channels and more general Pauli channels with weak strength do lead to a decrease $F$, the decrease is not significant enough to preclude the possibility of approximating the noisy state with a pure state. For instance, when $n=50$, a local depolarizing noise model $\mathcal{E}_{i}(\cdot)=(1-p)(\cdot)+p{\rm Tr}_{i}(\cdot)I_{2}/d$ with $p=10^{-3}$ gives rise to a depth bound $\tilde{R}\leq 46\log(1/\eta)$. This finding provides further evidence for a connection between circuit entanglement and the rate at which noise spreads. We leave proof details in Appendix [E.1](#A5.SS1).

###### Theorem 2 (Intrinsic-Connection Property in SQNN) .

Randomly select $N$ unitaries $\left\{U(\vec{\bm{\alpha}}_{i})\right\}_{i=1}^{N}$ from the SQNN model $\mathcal{U_{A}}(R)$ to generate $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)=\{U(\vec{\bm{\alpha}}_{i})|0^{n}\rangle\}_{i=1}^{N}$, where each layer in $U(\vec{\bm{\alpha}}_{i})$ contains $L$ variational gates. Then for any $n$-qubit noisy state $\rho$ and any observable $M(\vec{\bm{x}})=U(\vec{\bm{x}})|0^{n}\rangle\langle 0^{n}|U(\vec{\bm{x}})^{\dagger}$ with $U(\vec{\bm{x}})\in\mathcal{U_{A}}(R)$, there exists a vector $\vec{\bm{\beta}}(\bm{x})$ belongs to an $N$-dimensional compact set $\mathcal{D}_{\beta}$ and $\sum_{j=1}^{N}\vec{\bm{\beta}}_{j}(\bm{x})=1$ such that

$$ $\displaystyle\mathbb{E}_{\vec{\bm{x}}}\left|\sum\limits_{j=1}^{N}\vec{\bm{\beta}}_{j}(\bm{x})\langle 0^{n}|U^{\dagger}(\vec{\bm{\alpha}}_{j})\rho U(\vec{\bm{\alpha}}_{j})|0^{n}\rangle-{\rm Tr}\left(M(\vec{\bm{x}})\rho\right)\right|\leq\sqrt{\frac{LRn^{2}}{N}}.$ (9) $$

Let $N=LRn^{2}/\epsilon^{2}$,
the above approximation error is upper bounded by $\epsilon$.

The details of the proof and the explicit expression of the compact set $\mathcal{D}_{\beta}$ can be found in Appendix [E.2](#A5.SS2) and [E.3](#A5.SS3). Theorem [2](#Thmtheorem2) shows that the observable $M(\vec{\bm{x}})$ can be approximated by a linear combination of random SQNN circuits with the same depth. Using Theorem [2](#Thmtheorem2), we can state the following theorem.

###### Theorem 3 .

Given ${\rm poly}(n)$ copies of an $n$-qubit unknown weakly noisy state $\rho_{\rm un}$ that is generated by a noisy quantum device with depth $\tilde{R}=\mathcal{O}(\log n)$ (Def. [4](#Thmdefinition4)) and a particular architecture $\mathcal{A}$, there exists a ${\rm poly}(n,\tilde{R})$ quantum and classical cost QML algorithm which can efficiently solve the $\rm SCP(\mathcal{A})$ problem.

The proof of Theorem [3](#Thmtheorem3) depends on evaluating the sample complexity of QNN states and unknown noisy state, as well as the related iteration complexity during training the QML. We leave proof details in Sec. [V](#S5).

###### Theorem 1 .

###### Theorem 2 (Intrinsic-Connection Property in SQNN) .

###### Theorem 3 .

## IV Quantum Machine Learning for SCP problem

*Outline of the learning algorithm*—We start by utilizing the intrinsic connection property of $\mathcal{U}_{\mathcal{A}}$ to devise a parameterized function $\mathcal{L}$ for distinguishing $\rho_{\rm un}$ from SQNN states. The essential idea is that if the observable $M$ can differentiate the weakly noisy state $\rho_{\rm un}$ from $\mathcal{S}_{\rm QNN}$, then $\rho_{\rm un}$ cannot be approximated by any quantum circuit in $\mathcal{U_{A}}$. On the other hand, if $\rho_{\rm un}$ can be approximated by some $U\in\mathcal{U_{A}}$, then it cannot be distinguished from $\mathcal{S}_{\rm QNN}$ by $M$. To construct the SQNN state set, we generate $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)=\{|\Psi_{i}\rangle\}_{i=1}^{N}$ with $R=\mathcal{O}({\rm poly}(\log n))$ and $N={\rm poly}(n,R)$. We then optimize the objective function $\mathcal{L}_{R}(\vec{\bm{q}},M)$ by tuning the distribution $\vec{\bm{q}}=(\vec{\bm{q}}_{1},\dots,\vec{\bm{q}}_{N})$, the observable $M=V|0^{n}\rangle\langle 0^{n}|V^{\dagger}$, and $V\in\mathcal{U}_{\mathcal{A}}(R)$. Although optimizing a general observable $M$ is challenging, limiting $M$ to $\mathcal{U}_{\mathcal{A}}(R)$ and utilizing the intrinsic connection property allows for efficient optimization of $M$. If $\max_{\vec{\bm{q}},M}\mathcal{L}\leq\epsilon$, Lemma [1](#Thmlemma1) implies that the noisy state $\rho_{\rm un}$ can be approximated by some $U\in\mathcal{U}_{\mathcal{A}}(R)$ within $\epsilon$ error. Conversely, if $\min_{M}\mathcal{L}$ is greater than $\epsilon+\tilde{\epsilon}$, Lemma [2](#Thmlemma2) implies that $\rho_{\rm un}$ cannot be approximated by any $U\in\mathcal{U}_{A}$ within $\tilde{\epsilon}$ error. A ${\rm QML}_{n}$ can be designed by combining the above approach and binary search framework. The algorithm halts and outputs $C_{\epsilon}^{\rm lim,\mathcal{A}}(\rho_{\rm un})\leq LR$ and $C_{\epsilon}^{\rm lim,\mathcal{A}}(\rho_{\rm un})>L(R-1)$ or $C_{\epsilon}^{\rm lim,\mathcal{A}}(\rho_{\rm un})>L\log n$ after $\mathcal{O}(\log\log n)$ iterations.

### IV.1 Metric Construction

We now present the technical details of our proposed quantum machine learning (QML) method. First, we randomly generate a set of $N={\rm poly}(R,n)$ quantum neural network states $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)=\{U(\vec{\bm{\alpha}}_{i})|0^{n}\rangle\}_{i=1}^{N}$. We then design a variational observable based on the intrinsic-connection property stated in Theorem [2](#Thmtheorem2). This observable takes the form of

$$ $\displaystyle M(\vec{\bm{\beta}})=\sum\limits_{i=1}^{N}\beta_{i}U(\vec{\bm{\alpha}}_{i})|0^{n}\rangle\langle 0^{n}|U^{\dagger}(\vec{\bm{\alpha}}_{i}).$ (10) $$

Specifically, we use this variational observable to test whether there exists a low-depth quantum circuit $U\sim\mathcal{U_{A}}$ that can approximate the target state $\rho_{\rm un}$. To assess the circuit complexity of $\rho_{\rm un}$, we use the dataset $\mathcal{S}_{\rm QNN}$ to maximize the metric

$$ $\displaystyle\mathcal{L}_{R}(\vec{\bm{q}},\vec{\bm{\beta}})=\left|\sum\limits_{i=1}^{N}\vec{\bm{q}}_{i}{\rm Tr}\left(M(\vec{\bm{\beta}})(|\Psi_{i}\rangle\langle\Psi_{i}|-\rho_{\rm un})\right)\right|$ (11) $$

over the set $\mathcal{D}_{\bm{z}}=\{\bm{z}=(\vec{\bm{q}},\vec{\bm{\beta}})\}$, where $\vec{\bm{q}}_{i}\in\mathbb{R}_{\geq 0}$ and $\|\vec{\bm{q}}\|_{1}=1$. The $N$-dimensional parameter $\vec{\bm{\beta}}$ is restricted to a compact set $\mathcal{D}_{\beta}$ with $\sum_{i=1}^{N}\vec{\bm{\beta}}_{i}=1$. In Appendix [E.3](#A5.SS3), we provide a detailed description of an efficient method for estimating the compact set $\mathcal{D}_{\beta}$. By the Heine-Borel theorem [], the set $\mathcal{D}_{\bm{z}}$ is compact, meaning it contains all its limit points and is bounded. Given a specific parameter $(\vec{\bm{q}},\vec{\bm{\beta}})$, we can efficiently calculate the corresponding value of $\mathcal{L}_{R}(\vec{\bm{q}},\vec{\bm{\beta}})$ using classical shadow techniques [, , , , ]. For the noisy state $\rho_{\rm un}$ and each $|\Psi_{i}\rangle\in\mathcal{S}_{\rm QNN}$, the corresponding shadow tomography is obtained by repeatedly performing a simple measurement procedure: apply a random unitary to rotate the state and perform a Pauli Z-basis measurement. On receiving the $n$-bit measurement outcomes, classical descriptions (stabilizer) of target states $\{\rho_{\rm sh}(|\Psi_{1}\rangle),...,\rho_{\rm sh}(|\Psi_{N}\rangle),\rho_{\rm sh}(\rho_{\rm un})\}$ can be efficiently stored in the classical memory []. Recall the parameterized observable $M(\vec{\bm{\beta}})=\sum_{i=1}^{N}\beta_{i}|\Psi_{i}\rangle\langle\Psi_{i}|$, then accumulated shadow tomography can be used in estimating $\left|\langle\Psi_{i}|\Psi_{j}\rangle\right|^{2}$ and $\langle\Psi_{i}|\rho_{\rm un}|\Psi_{i}\rangle$, and finally yield $\mathcal{L}_{R}(\vec{\bm{q}},\vec{\bm{\beta}})$. Before proposing the quantum learning algorithm, we need the following Lemmas to support our method, and corresponding proof details refer to Appendices [E.5](#A5.SS5), and [E.6](#A5.SS6).

###### Lemma 1 .

Consider a parameterized observable $M(\vec{\bm{\beta}})$ defined as Eq. [10](#S4.E10). If the relationship

$$ $\displaystyle\max\limits_{\vec{\bm{q}},M(\vec{\bm{\beta}})}\mathcal{L}_{R}(\vec{\bm{q}},M(\vec{\bm{\beta}}))\leq\epsilon$ (12) $$

holds, then $\rho_{\rm un}$ can be approximated by some state $\rho=U\ket{0^{n}}\bra{0^{n}}U^{\dagger}$ such that $U\in\mathcal{U_{A}}(R)$, and $C^{{\rm lim},\mathcal{A}}_{\epsilon}(\rho_{\rm un})\leq LR$, where $C^{{\rm lim},\mathcal{A}}_{\epsilon}(\cdot)$ is defined in Def. [7](#Thmdefinition7).

###### Lemma 2 .

Let $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)=\{|\Psi_{i}\rangle\}_{i=1}^{N}$ be a quantum neural network state set, where $N=LRn^{2}\epsilon^{-2}$. If there exists a distribution $\vec{\bm{q}}$ such that

$$ $\displaystyle\min\limits_{\vec{\bm{\beta}}}\mathcal{L}_{R}(\vec{\bm{q}},M(\vec{\bm{\beta}}))>\epsilon+\tilde{\epsilon},$ (13) $$

then with nearly unit probability, $\rho_{\rm un}$ cannot be approximated by any $U|0^{n}\rangle\langle 0^{n}|U^{\dagger}$, that is $\langle 0^{n}|U^{\dagger}\rho_{\rm un}U|0^{n}\rangle<1-\tilde{\epsilon}$ for any $U\in\mathcal{U}_{\mathcal{A}}(R)$.

Figure: Algorithm 1 Bayesian Maximize Subroutine, ${\rm BMaxS}(\rho_{\rm un},\mathcal{S}_{\rm QNN}(R,\mathcal{A},N),T,\epsilon)$

In the following, we show how to maximize the loss function $\mathcal{L}_{R}(\bm{z})$ via Bayesian optimization on a compact set. Bayesian optimization is composed by two significant components: $(i)$ a statistical model, in general Gaussian process, provides a posterior distribution conditioned on a prior distribution and a set of observations over $\mathcal{L}_{R}(\bm{z})$. $(ii)$ an acquisition function determines the position of the next sample point, based on the current posterior distribution over $\mathcal{L}_{R}(\bm{z})$.

###### Remark 4 .

A more straightforward choice of the objective function seems to be $\mathcal{L}(\vec{\bm{\beta}})=\sum_{i=1}\vec{\bm{\beta}}_{i}\langle\Psi_{i}|\rho_{\rm un}|\Psi_{i}\rangle$. However, under this construction, $\max_{\vec{\bm{\beta}}}\mathcal{L}\geq 1-\epsilon$ may not directly imply $\rho_{\rm un}$ satisfies the SSAP property. Actually, in such scenario, it is hard to utilize the intrinsic-connection property in using Eq. [6](#S3.E6) to upper bound $\max\mathcal{L}$.

###### Lemma 1 .

###### Lemma 2 .

###### Remark 4 .

### IV.2 Optimization Subroutine

Gaussian process is a set of random variables, where any subset forms a multivariate Gaussian distribution. For the optimization task described as Eq. [11](#S4.E11), the random variables represent the value of the objective function $\mathcal{L}_{R}(\bm{z})$ at the point $\bm{z}=(\vec{\bm{q}},\vec{\bm{\beta}})$.
As a distribution over $\mathcal{L}_{R}(\bm{z})$, a Gaussian process is completely specified by mean function and covariance function

$$ $\begin{split}\mu(\bm{z})&=\mathbb{E}_{\bm{z}}[\mathcal{L}_{R}(\bm{z})]\\ k(\bm{z},\bm{z}^{\prime})&=\mathbb{E}_{\bm{z}}[(\mathcal{L}_{R}(\bm{z})-\mu(\bm{z}))(\mathcal{L}_{R}(\bm{z}^{\prime})-\mu(\bm{z}^{\prime}))],\end{split}$ (14) $$

and the Gaussian process is denoted as $\mathcal{L}_{R}(\bm{z})\sim\mathcal{GP}(\mu(\bm{z}),k(\bm{z},\bm{z}^{\prime}))$. Without loss of generality, we assume that the prior mean function $\mu(\bm{z})=0$. In the $t$-th iteration step, assuming observations
${\rm Acc}(t)=\{(\bm{z}^{(1)},y(\bm{z}^{(1)})),\ldots,(\bm{z}^{(t)},y(\bm{z}^{(t)}))\}$ are accumulated, where $y(\bm{z}^{(i)})=\mathcal{L}_{R}(\bm{z}^{(i)})+\epsilon_{i}$, with Gaussian noise $\epsilon_{i}\sim\mathcal{N}(0,\sigma^{2}_{\rm noise})$ for $i\in[t]$. Here, we set $\sigma_{\rm noise}=1$ in our algorithm. Conditioned on the accumulated observations ${\rm Acc}(t)$, the posterior distribution of $\mathcal{L}_{R}(\bm{z})$ is a Gaussian process with mean function $\mu_{t}(\bm{z})=\mathbb{E}_{\bm{z}}[\mathcal{L}_{R}(\bm{z})|{\rm Acc}(t)]$ and covariance function $k_{t}(\bm{z},\bm{z}^{\prime})=\mathbb{E}_{\bm{z}}[(\mathcal{L}_{R}(\bm{z})-\mu(\bm{z}))(\mathcal{L}_{R}(\bm{z}^{\prime})-\mu(\bm{z}^{\prime}))|{\rm Acc}(t)]$, specified by

$$ $\begin{split}\mu_{t}(\bm{z})&=\bm{k}_{t}^{\mathsf{T}}[\bm{K}_{t}+\sigma^{2}_{\rm noise}\bm{I}]^{-1}\bm{y}_{1:t}\\ k_{t}(\bm{z},\bm{z}^{\prime})&=k(\bm{z},\bm{z}^{\prime})-\bm{k}_{t}^{\mathsf{T}}[\bm{K}_{t}+\sigma^{2}_{\rm noise}\bm{I}]^{-1}\bm{k}_{t},\end{split}$ (15) $$

where $\bm{k}_{t}=[k(\bm{z},\bm{z}^{(1)})\quad\ldots\quad k(\bm{z},\bm{z}^{(t)})]^{\mathsf{T}}$, the positive definite covariance matrix $\bm{K}_{t}=[k(\bm{z},\bm{z}^{\prime})]_{\bm{z},\bm{z}^{\prime}\in\bm{z}_{1:t}}$ with $\bm{z}_{1:t}=\{\bm{z}^{(1)},\dots,\bm{z}^{(t)}\}$ and $\bm{y}_{1:t}=[y(\bm{z}^{(1)}),\dots,y(\bm{z}^{(t)})]^{\mathsf{T}}$.
The posterior variance of $\mathcal{L}_{R}(\bm{z})$ is denoted as $\sigma^{2}_{t}(\bm{z})=k_{t}(\bm{z},\bm{z})$.
The mean function $\mu_{t}(\bm{z})$ is related to the expected value of $\mathcal{L}_{R}(\bm{z})$, while the covariance $k_{t}$ estimates the deviations of $\mu_{t}(\bm{z})$ from the value of $\mathcal{L}_{R}(\bm{z})$. Then the prediction is obtained by conditioning the prior Gaussian process on the observations and returns a posterior distribution described by a Gaussian process multivariate distribution. Using the Sherman-Morrison-Woodbury formula [], the predictive distribution can be explicitly expressed as Eq. [15](#S4.E15).

In the $t$-th iteration of Bayesian optimization, the acquisition function $\mathcal{A}(\bm{z})$ learns from the accumulated observations ${\rm Acc}(t-1)$ and leads the search to the next point $\bm{z}^{(t)}$ which is expected to gradually convergence to the optimal parameters of $\mathcal{L}_{R}(\bm{z})$. This procedure is achieved via maximizing $\mathcal{A}(\bm{z})$. In detail, the design of acquisition function should consider exploration (exploring domains where $\mathcal{L}_{R}(\bm{z})$ has high uncertainty) and exploitation (exploring domains where $\mathcal{L}_{R}(\bm{z})$ is expected to have large image value). The upper confidence bound is a widely used acquisition function, which is defined as

$$ $\displaystyle\mathcal{A}_{\mathrm{UCB}}(\bm{z})=\mu_{t-1}(\bm{z})+\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z}),$ (16) $$

and the next point $\bm{z}^{(t)}$ is decided by $\bm{z}^{(t)}=\arg\max_{\bm{z}\in\mathcal{D}_{\rm domain}}\mathcal{A}_{\mathrm{UCB}}(\bm{z})$. Here, $\kappa_{t}$ is a significant hyper-parameter, and a suitable $\kappa_{t}$ may lead $\bm{z}^{(t)}$ rapidly convergence to $\bm{z}_{opt}$. In Theorem [4](#Thmtheorem4), a specific $\kappa_{t}$ is provided.
Details for maximizing $\mathcal{L}_{R}(\bm{z})$ are shown in Alg [1](#algorithm1).

Figure: Algorithm 2 Quantum Machine Learning for Limited-Structured Complexity approximation

### IV.3 Quantum Learning Algorithm for Limited-Structured Complexity analysis

The Alg. [1](#algorithm1) can efficiently verify whether $\mathcal{L}_{R}(\bm{z})$ satisfies Lemma [1](#Thmlemma1). Specifically, Alg. [1](#algorithm1) outputs *True* if there exists some $U\in\mathcal{U}_{\mathcal{A}}(R)$ that can approximate $\rho_{\rm un}$ within $\epsilon$ additive error, otherwise outputs *False*.
As a result, Alg. [1](#algorithm1) can be leveraged to design a ${\rm QML}_{n}$ in verifying whether the weakly noisy state $\rho_{\rm un}$ satisfies the $\rm SSAP(\mathcal{A})$ property, and thus can efficiently solve Task [1](#Thmtask1).

Since $\mathcal{U}_{\mathcal{A}}(R-1)$ is strictly contained in $\mathcal{U}_{\mathcal{A}}(R)$ [], the boolean function

$$ $\mathcal{P}(R)={\rm BMaxS}(\rho_{\rm un},\mathcal{S}_{\rm QNN}(R,\mathcal{A},N),T,\epsilon)$ $$

is a monotone predicate in $[1,\tilde{R}]$. Therefore the ${\rm QML}_{n}$ can be designed by a binary search program where Alg. [1](#algorithm1) is packaged as an oracle. A monotone predicate $\mathcal{P}$ is a boolean function defined on a totally ordered set with the property: if $\mathcal{P}(R)=\emph{True}$, then $\mathcal{P}(R^{\prime})=\emph{True}$ for all $R^{\prime}\geq R$ in the domain. In our case, $\mathcal{P}(R)$ returns *True* at $R$
but returns *False* at $R-1$ when relationships
$\mathcal{L}_{R}(\bm{z}^{(T)})\leq\epsilon$ and $\mathcal{L}_{R-1}(\bm{z}^{(T)})>\epsilon$ hold at the same time. As a result, if the noisy state $\rho_{\rm un}$ satisfies the $\rm SSAP(\mathcal{A})$ property, the ${\rm QML}_{n}$ outputs the minimum $R_{\min}\in[1,\tilde{R}]$ enabling $C_{\epsilon}^{{\rm lim},\mathcal{A}}(\rho_{\rm un})\leq LR_{\min}$ (*True*). Otherwise, the ${\rm QML}_{n}$ outputs $C_{\epsilon}^{{\rm lim},\mathcal{A}}(\rho_{\rm un})>L\log n$ (*False*).
Details are provided in Alg. [2](#algorithm2).

## V Theoretical Performance Guarantee

We will prove that a quantum ML algorithm can efficiently solve the SCP problem after learning from the unknown noisy state $\rho_{un}$ (Theorem [3](#Thmtheorem3)). Specifically, the complexity of the proposed quantum learning algorithm is determined by the required QNN samples $N$ and the iteration complexity in Alg. [1](#algorithm1) and Alg. [2](#algorithm2).

### V.1 Sample complexity

The sample complexity of QNN states is promised by Theorem [2](#Thmtheorem2), where $N=LRn^{2}/\epsilon^{2}$.
To evaluate $\mathcal{L}_{R}(\bm{z})$, the sample complexity of unknown weakly noisy state as well as QNN states is at most $\mathcal{O}(\log(1/\delta)/\epsilon_{1}^{2})$, where $\epsilon_{1}=\epsilon/N$ and failure probability $\delta\in(0,1)$ by leveraging the classical shadow method [].

### V.2 Iteration complexity

Here, we present the iteration complexity in Alg. [1](#algorithm1) and Alg. [2](#algorithm2). Denote the global maximum $\bm{z}^{*}=\max_{\bm{z}\in\mathcal{D}_{\bm{z}}}\mathcal{L}_{R}(\bm{z})$, and a natural performance metric of ${\rm BMaxS}(\rho_{\rm un},\mathcal{S}_{\rm QNN}(R,\mathcal{A},N),T,\sigma_{\rm noise})$ is the simple regret $s_{T}$ which is the difference between the global maximum $\mathcal{L}_{R}(\bm{z}^{*})$ and $\mathcal{L}_{R}(\bm{z}^{(T)})$, that is $s_{T}=\mathcal{L}_{R}(\bm{z}^{*})-\mathcal{L}_{R}(\bm{z}^{(T)})$. Obviously, simple regret is non-negative and asymptotically decreases with the increasing iteration complexity $T$. To build up an explicit connection between $s_{T}$ and $T$, the average regret $R_{T}$ is introduced, that is,

$$ $\displaystyle R_{T}=\frac{1}{T}\sum_{t=1}^{T}[\mathcal{L}_{R}(\bm{z}^{*})-\mathcal{L}_{R}(\bm{z}^{(t)})].$ (17) $$

Noting that the relationship $s_{T}\leq R_{T}$ holds for any $T\geq 1$. In the following, we show that $R_{T}$ is upper bounded by $\mathcal{O}(N\log T/\sqrt{T})$. Therefore, the simple regret $s_{T}\leq R_{T}\rightarrow 0$ with the increase of $T$. The following theorem derives the average regret bounds for ${\rm BMaxS}(\rho_{\rm un},\mathcal{S}_{\rm QNN}(R,\mathcal{A},N),T,\sigma_{\text{noise}})$.

###### Theorem 4 .

Take the weakly noisy state $\rho_{\rm un}$ and $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)$ into Alg. [1](#algorithm1). Pick the failure probability $\delta\in(0,1)$ and let

$$ $\displaystyle\kappa_{t}=2N\log(t^{2}N)+2\log(t^{2}/\delta)$ (18) $$

in the $t$-th iteration step, then
the average regret $R_{T}$ can be upper bounded by

$$ $\displaystyle R_{T}\leq\mathcal{O}\left(\sqrt{\frac{4N^{2}\log^{2}T+2N\log T\log(\pi^{2}/(6\delta))}{T}}\right)$ (19) $$

with $1-\delta$ success probability.

Specifically, select an integer $k$ such that $k\log(n)<n^{k/2}\epsilon$ for all $n>n_{0}$, and $T=N^{2}n^{k}$ enables the simple regret $s_{T}$ can be upper bounded by $\epsilon$, where $N=LRn^{2}\epsilon^{-2}$ (Theorem [2](#Thmtheorem2)). The proof details refer to Appendix [E.8](#A5.SS8). Alg. [2](#algorithm2) is essentially a binary search program on the interval $[1,\tilde{R}]$ by using the oracle ${\rm BMaxS}(\rho_{\rm un},\mathcal{S}_{\rm QNN}(R,\mathcal{A},N),T,\epsilon)$. Therefore, Alg. [2](#algorithm2) takes $\mathcal{O}(\log(\tilde{R})T)$ iteration complexity to answer the SCP problem. Putting all together, the proposed quantum learning algorithm can efficiently learn from $(L\tilde{R})n^{2}\epsilon^{-2}$ numbers of QNN states, and the sample complexity to QNN states and noisy state is at most $N^{2}\epsilon^{-2}\log(1/\delta)$. This thus completes the proof of Theorem [3](#Thmtheorem3).

###### Theorem 4 .

## VI Discussions

The completeness answer (YES) of SCP provides an noisy state complexity upper bound which may help us understand the power of noisy quantum computation according to the complexity. In the following, we discuss potential applications of the studied SCP problem and QML method.

### VI.1 Approximate Weakly Noisy State

In the above sections, we only focus on predicting the LS complexity as Def. [7](#Thmdefinition7) which is inspired by the pure state complexity in [], rather than discussing how to reproduce an unknown noisy state. Here, we point that Lemma [1](#Thmlemma1) can be used in generating a mixed state approximation.

###### Corollary 1 .

Consider to use the $n$-qubit set $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)=\{|\Psi_{i}\rangle\}_{i=1}^{N}$ to generate a parameterized observable $M(\vec{\bm{\beta}})$
defined as Eq. [10](#S4.E10), where $N={\rm poly}(n,R)$. If $\max_{\vec{\bm{q}},M(\vec{\bm{\beta}})}\mathcal{L}_{R}(\vec{\bm{q}},M(\vec{\bm{\beta}}))\leq\epsilon$ holds, and denote $\vec{\bm{q}}^{*},M(\vec{\bm{\beta}}^{*})=\arg\max_{\vec{\bm{q}},M(\vec{\bm{\beta}})}\mathcal{L}_{R}$,
then we have ${\rm Tr}(M(\vec{\bm{\beta}}^{*})\rho_{\rm un})=\sum_{i=1}^{N}\vec{\bm{\beta}}^{*}_{i}\langle\Psi_{i}|\rho_{\rm un}|\Psi_{i}\rangle\geq 1-\epsilon$.

The above corollary provides a method in approximating a mixed state which has a large overlap to the weakly noisy state $\rho_{\rm un}$. Furthermore, the estimator $\hat{\Phi}=M(\vec{\bm{\beta}}^{*})^{1/2}\rho_{\rm un}M(\vec{\bm{\beta}}^{*})^{1/2}$ is an approximation to $\rho_{\rm un}$ such that $\|\hat{\Phi}-\rho_{\rm un}\|_{1}\leq 2\sqrt{\epsilon}$ by the gentle measurement result []. If $M(\vec{\bm{\beta}}^{*})$ (linear combinations of classical shadows) is a low-rank matrix, the estimator $\hat{\Phi}$ can be efficiently computed by dequantized algorithms []. We leave the proof details in Appendix [E.5](#A5.SS5).

###### Corollary 1 .

### VI.2 Characterizing Quantum Advantages

Our work connects the learning algorithm to the noisy state sampling complexity. The classical hardness results for noiseless quantum random states are clear for depth $R=\Omega(\log n)$ [, , , ], in addition, Napp et al. [] proved that for shallow depth $R\leq\mathcal{O}(1)$ on certain architectures, approximating output probability of noiseless quantum circuit to additive error $2^{-n}$ is classically efficient. As a result, given an unknown noisy state $\rho_{\rm un}$ and running Alg. [2](#algorithm2), if the LS-complexity $C_{1/n}^{{\rm lim},\mathcal{A}}(\rho_{\rm un})\leq\mathcal{O}(1)$, then $\rho_{\rm un}$ can be efficiently simulated by a classical computer [, ]. On the other hand, recent advanced work indicated that a $\Omega(\log(n))$-depth random circuit with local depolarizing noise may be efficiently simulated by a classical computer [], however the classical hardness result of noisy quantum states remains unclear at depth between constant and $o(\log n)$ []. Our result works for noisy states with $\tilde{R}\leq\mathcal{O}({\rm poly}\log n)$, then the proposed QML is expected to be a proxy for connecting a $\tilde{R}=o(\log n)$-depth noisy circuit to an ideal shallower quantum circuit, which may shed light in understanding the noisy state sampling problem in sublogarithm-depth.

## VII Conclusion

In this paper, we investigate the capability of QML algorithms in predicting the complexity of weakly noisy quantum states, then provide a circuit implementation for approximating this weakly noisy state. Our proposed QML method exploits the intrinsic-connection property of SQNN to build a learning model $\mathcal{L}(\bm{z})$. The maximum value of $\mathcal{L}(\bm{z})$ indicates whether the noisy state can be distinguished from the SQNN states, and reveals the limited-structured complexity. It is worth noting that optimizing a variational quantum circuit is NP-hard in the worst-case scenario [].
However, the intrinsic-connection property allows us to construct $\mathcal{L}(\bm{z})$ by linearly combining measurement results with polynomial quantum and classical costs.
This enables us to train the QML model by tuning the combination coefficients on a compact domain. Moreover, we emphasize that the Bayesian optimization algorithm presented in Alg. [1](#algorithm1) is not the only option. Other optimization algorithms may also work with a similar iteration steps. This highlights the universality of the intrinsic-connection property in combination with optimization subroutines. The predicted complexity of the quantum state can be used to verify the existence of quantum advantages and classify quantum phases of matter. Furthermore, the intrinsic-connection property also suggests that shallow-depth QNN models are classically simulable, provided the data pair $\{(\vec{\bm{\alpha}}_{i},y_{i})\}_{i=1}^{N}$, where $\vec{\bm{\alpha}}_{i}$ and $y_{i}$ represent the variational parameters in QNN and the expectation value under a Hermitian observable, respectively. We believe that the proposed QML method can help us deeply understand the computational power of NISQ devices.

This work leaves room for further research on more general quantum state complexity problems. For example, our QML can provide an approximation to the limited-structured noisy state complexity $C^{\rm lim,\mathcal{A}}_{\epsilon}(\rho_{\rm un})$, and indirectly predict the noisy state complexity $C_{\epsilon}(\rho_{\rm un})$. Then whether there exists a learning approach in directly predicting $C_{\epsilon}(\rho_{\rm un})$ deserves to be further investigated.
Additionally, the intrinsic-connection property indicates that representing a large-depth SQNN requires more training data compared to a shallower SQNN model. This observation motivates the exploration of expressivity through the intrinsic-connection property. Furthermore, while QML cannot solve NP-hard problems exactly, the intrinsic-connection property enables searching for nearly optimal solutions in a limited structure. This may stimulate further study of QNN and VQE methods.

## Acknowledgments

We are grateful for the valuable suggestions provided by Jens Eisert and for the insightful discussions with Philippe Faist and Haihan Wu. This work is supported by the China Scholarship
Council (Grant No. 202006470011), and the National Natural Science Foundation of China (Grants No. 12175003).

## Appendix A Relationships to Previous Works

### A.1 Random Quantum State Complexity

Predicting the quantum state complexity lower bound is a long-standing open problem in the field of quantum computation and quantum information theory, where the difficulty comes from gates performed early in the circuit may canceled by gates performed later. And this is the intuition on why the quantum-gate-synthesis algorithm runs for times exponential in the system size. Brandao et al. [] considered to use ensembles of Haar random circuits to derive lower
bounds on complexity which hold with high probability when samples are selected from these ensembles. They rigorously proved that any approximate $k$-design contains exponentially many (in $k$) unitaries that have circuit complexity at least $\Omega(k)$. Jian et al. [] showed that a wide variety
of Brownian quantum many-body systems form good
approximate k-designs in time linear in $k$, which generating quantum randomness by Brownian dynamics. After that, Haferkamp et al. [] employed elementary aspects of differential topology and algebraic geometry to estimate the accessible dimension of a random circuit, then utilized Clifford circuits to construct a high-rank point in lower bounding the accessible dimension. As a result, the exact random state complexity lower bound is obtained. This result is further generalized to approximated-complexity by using approximate
equidistribution, which measures on the space of unitaries and the space of
pure quantum states [].

Compared with previous works, our method studied the noisy state complexity from the machine learning approach, where the circuit depth $\tilde{R}\leq\mathcal{O}({\rm poly}(\log n))$. In the learning procedure, only a few copies of noisy state $\rho_{\rm un}$ are provided, and a QML can provide a *structured state complexity* prediction of $\rho_{\rm un}$ with high probability. The theoretical guarantee does not depend on the unitary $k$-designs and Haar-random ensemble, and it thus may work in the scenario $\tilde{R}=o(\log n)$. According to the ‘No Free Lunch Theorem’, our method only uses very few information of the target noisy state, as a result, it can provide an upper-bound of the exact noisy state complexity, and a *structured* noisy state lower-bound.

### A.2 Limitations of Noisy Circuit

Previous works showed that $\tilde{R}=\Omega(n)$-depth quantum circuits with depolarizing noise channel (global or local) output a distribution that is expected to $\exp(-\Theta(n))$-close to the uniform distribution in terms of the total variation distance [, ], and the corresponding noisy state $\Phi_{p,\tilde{R}}$ thus can be efficiently simulated by a classical computer within imprecision $\mathcal{O}(1/2^{n})$ or larger. For the regime $\tilde{R}=\Omega(\log n)$, Aharonov et al. [] showed that sampling from $\Phi_{p,\tilde{R}}$ can be approximately simulated by a classical algorithm in $\mathcal{O}(1/\epsilon)^{1/p}$ running time, where $\epsilon$ represents the total variation distance. However, noise-agnostic techniques can only work in the regime $\Omega(\log n)\leq\tilde{R}\leq\mathcal{O}(n)$, whether noisy state shows advantages at depth between constant and $\tilde{R}=o(\log n)$ is still unclear [, ]. Our result shows that a QML can verify whether a noisy state is $\epsilon$-close to a pure state, which may be helpful in understanding the sample complexity of $\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle 0^{n}|)$ in the area $\tilde{R}=o(\log n)$.

### A.3 Classifying quantum phases of matter

Classifying quantum phases of matter has been widely studied. The proposals include quantum neural networks [], classical neural networks [, , , , ], and other classical machine learning models [, , ]. Among these literature, Huang et al. [] utilized the shadow tomography of concerned ground states to design an unsupervised machine learning approach which is guaranteed to classify accurately under certain conditions. The proposed ‘shadow kernel’ can generate quantum entropies via tuning hyper-parameters, which has the ability in approximating many different topological phase order parameters.

Another potential application of our QML is to classify quantum topological phases of matter. Ground states in topologically trivial phases can take a simple product form, however, ground states in topological phases are always entangled. For example, to generate $1$D gapped (symmetry protected) topological states from product states, the depth of the local quantum circuits has to grow linearly with the system size []. Therefore, the LS complexity can be naturally used in classifying the trivial state and topological state. Here, we follow the problem setting in Ref [], that is classifying Kitaev’s toric code state [] from trivial product state. Using the Hamiltonian variational ansatz [] $\mathcal{U}_{\mathcal{A}}(\cdot)$ to generate two classes of states $\{|\psi_{i}\rangle\}$ and $\{|\phi_{i}\rangle\}$ from $|0^{n}\rangle$, where $|\psi_{i}\rangle$ are generated by $U\in\mathcal{U}_{\mathcal{A}}(1)$ (trivial phase) and $|\phi_{i}\rangle$ are generated by $V\in\mathcal{U}_{\mathcal{A}}(R)$ (topological phase). In the learning procedure, the shadow tomography $S_{\rm shadow}=\{\Phi(\psi_{i}),\Phi(\phi_{i})\}$ of these states are provided [], and the target is to determine the quantum phase of matter for each $\Phi\in S_{\rm shadow}$. Running the Alg. [2](#algorithm2) on $\Phi\in S_{\rm shadow}$, and the output LS complexity $C^{\rm lim,\mathcal{A}}_{1/n}(\Phi)$ thus provides the classification results.

## Appendix B Discussions on Quantum Circuit Learning and Circuit Complexity

Here, we define the complexity of unitary channels $\mathcal{U}(\rho)=U^{\dagger}\rho U$. This starts with identifying the completely depolarizing channel:

$$ $\displaystyle\mathcal{D}(\rho)=\frac{I}{d}$ (20) $$

for all states $\rho$, where $d=2^{n}$. The diamond distance between $\mathcal{D}$ and any unitary channel is close to maximal:

$$ $\displaystyle\frac{1}{2}\|\mathcal{U}-\mathcal{D}\|_{\diamondsuit}=1-\frac{1}{d^{2}}.$ (21) $$

An optimal strategy for distinguishing $\mathcal{U}$ from $\mathcal{D}$ corresponds to choosing a maximally entangled state $|\Omega\rangle\in C^{d}\otimes C^{d}$ as input and measurement operator $M=(U\otimes I)|\Omega\rangle\langle\Omega|(U^{\dagger}\otimes I)$ Let $G_{r_{1}}\subset U(d^{2})$ be the set of all unitary circuits on $2n$ qubits that are comprised of at most $r_{1}$ elementary gates. Likewise, let $M_{r_{2}}\subset H_{d}\otimes H_{d}$ denote the classs of all two-outcome measurements on $2n$-qubits that require circuit size at most $r_{2}$ to implement. The optimal bias for quantum channels achievable under such restrictions is

$$ $\displaystyle\beta_{QC}(r,U)=\max\limits_{M,|\phi\rangle}\|{\rm Tr}\left(M\left((\mathcal{U}\otimes I)(|\phi\rangle\langle\phi|)-(\mathcal{D}\otimes I)(|\phi\rangle\langle\phi|)\right)\right)\|_{1}$ (22) $$

subject to $M\in M_{r_{1}}$, $|\phi\rangle=V|0^{2n}\rangle$, $V\in G_{r_{1}}$ and $r=r_{1}+r_{2}$. As the increase of $r$, more complicated measurements and quantum state preparations become possible.

###### Definition 9 .

Fix integer $r\in N$ and $\epsilon\in(0,1)$. We say that a unitary $U\in U(d)$ has strong $\epsilon$-unitary complexity at most $r$ if and only if

$$ $\displaystyle\beta_{QC}(r,U)\geq 1-\frac{1}{d^{2}}-\epsilon,$ (23) $$

which we denote as $C_{\epsilon}(U)\leq r$.

###### Definition 10 (Diamond norm) .

The diamond norm is the trace norm of the output of a trivial extension of a linear map, maximized over all possible inputs with trace norm at most one. Specifically, suppose $\Phi:H_{d}\mapsto H_{d}$ be a linear transformation, where $H_{d}$ be a $d$-dimensional Hilbert space, the diamond norm of $\Phi$ is defined by

$$ $\displaystyle\|\Phi\|_{\diamondsuit}=\max\limits_{\|X\|_{1}\leq 1}\|(\Phi\otimes I)X\|_{1},$ (24) $$

where identity matrix $I\in H_{d}$, $X\in H_{2d}$ and $\|\cdot\|_{1}$ represents the trace norm.

###### Definition 11 (Diamond distance) .

Given $n$-qubit quantum channels $\mathcal{G}$ and $\mathcal{F}$, their diamond distance is defined as

$$ $\displaystyle d_{\diamondsuit}(\mathcal{G},\mathcal{F})=\|\mathcal{G}-\mathcal{F}\|_{\diamondsuit}=\max\limits_{\rho}\|(\mathcal{G}\otimes I)(\rho)-(\mathcal{F}\otimes I)(\rho)\|_{1},$ (25) $$

where $\rho$ denotes all density matrices of $2n$ qubits.

###### Definition 12 (Quantum circuit learning) .

A QNN model $U(\bm{\alpha})$ can learn an unstructured quantum circuit $V$ if there exists a parameter $\bm{\alpha}^{*}$ enabling

$$ $\displaystyle R_{c}(\bm{\alpha}^{*})=\frac{1}{4}\sum\limits_{\rho_{\bm{x}}\in S}\|U(\bm{\alpha}^{*})\rho_{\bm{x}}U^{\dagger}(\bm{\alpha}^{*})-V^{\dagger}\rho_{\bm{x}}V\|_{1}^{2}\leq\epsilon,$ (26) $$

where $S$ contains all $n$-qubit quantum state and $\epsilon=1/{\rm poly}(n)$.

Denote the expected risk of $h_{Q,U_{R}}(\rho_{\bm{x}})$ on the training set $S$ as $R_{S}$, we have the following theorem.

###### Theorem 5 .

Given an unstructured quantum circuit $V$ and a set of $n$-qubit Haar random product quantum states $S=\{|\Psi_{0}\rangle,|\Psi_{2}\rangle,...,|\Psi_{M}\rangle\}$, where $|\Psi_{m}\rangle=|\psi_{0}\rangle\otimes...\otimes|\psi_{n}\rangle$, if there exists a quantum machine learning model $h_{Q,U_{R}}$, such that

$$ $\displaystyle R_{S}=\frac{1}{4}\sum\limits_{|\Psi_{m}\rangle\in S}\|h_{Q,U_{R}}(|\Psi_{m}\rangle)-V^{\dagger}|\Psi_{m}\rangle\langle\Psi_{m}|V\|_{1}^{2}\leq\epsilon,$ (27) $$

where $h_{Q,U_{R}}(|\Psi_{m}\rangle)=U_{R}^{\dagger}|\Psi_{m}\rangle\langle\Psi_{m}|U_{R}$,
then the relationship

$$ $\displaystyle C_{\frac{2(d+1)}{d}\epsilon}(V)\leq{\rm size}(U_{R})$ (28) $$

holds.

###### Lemma 3 ( [ 96 ] ) .

Let $d=2^{n}$, $S_{2}$ denotes 2-design quantum state set with $n$ qubits, and $S_{\rm{Haar}^{\otimes n}}$ denotes $n$-qubit Haar random product state set, then the relationship

$$ $\displaystyle\frac{d+1}{d}R_{S_{2}}\leq 2R_{S_{\rm{Haar}^{\otimes n}}}$ (29) $$

holds.

###### Proof of theorem 5 .

Rewrite the trace distance, one obtains

$$ $\displaystyle\begin{split}R_{S_{2}}=&\frac{1}{4}\mathbb{E}_{\rho\sim S_{2}}\|h_{Q,U_{R}}(\rho)-V^{\dagger}\rho V\|_{1}^{2}\\ =&1-\mathbb{E}_{\rho\sim S_{2}}\left[\|{\rm Tr}(\rho U_{R}^{\dagger}V)\|^{2}\right].\end{split}$ (30) $$

Since the training set
$S_{2}$ is generated by unitaries from a $2$-design unitary group $\mathcal{U}$, we have

$$ $\displaystyle\begin{split}&\mathbb{E}_{\rho\sim S}\left[\|{\rm Tr}(\rho U_{R}^{\dagger}V)\|^{2}\right]=\int_{\mathcal{U}_{i}\sim\mathcal{U}}\|\langle 0^{\otimes n}|\mathcal{U}_{i}^{\dagger}U_{R}^{\dagger}V\mathcal{U}_{i}|0^{\otimes n}\rangle\|^{2}{\rm d}\mu(\mathcal{U}_{i})\\ &=\int_{\mathcal{U}_{i}\sim\mathcal{U}}\|\langle 0^{\otimes n}|\mathcal{U}_{i}^{\dagger}U_{R}^{\dagger}V\mathcal{U}_{i}|0^{\otimes n}\rangle\|_{1}\|\langle 0^{\otimes n}|\mathcal{U}_{i}U_{R}V^{\dagger}\mathcal{U}^{\dagger}_{i}|0^{\otimes n}\rangle\|_{1}{\rm d}\mu(\mathcal{U}_{i})\\ &=\frac{1}{d^{2}-1}\left({\rm Tr}(|0^{\otimes n}\rangle\langle 0^{\otimes n}|)^{2}\|{\rm Tr}(U_{R}^{\dagger}V)\|^{2}+d+1\right)-\frac{1}{d(d^{2}-1)}\left({\rm Tr}(|0^{\otimes n}\rangle\langle 0^{\otimes n}|)\|{\rm Tr}(U_{R}^{\dagger}V)\|^{2}+d\right).\end{split}$ (31) $$

Therefore, the expected risk $R_{S_{2}}$ can be further estimated by

$$ $\displaystyle R_{S_{2}}=\frac{d}{d+1}\left(1-\frac{1}{d^{2}}\|{\rm Tr}(U_{R}^{\dagger}V)\|^{2}\right)+\mathcal{O}(d^{-2}).$ (32) $$

Let $|\Omega\rangle$ be the maximally entanglement state on the Hilbert space $\mathcal{H}^{d}\otimes\mathcal{H}^{d}$, we have the relationship

$$ $\displaystyle\|\langle\Omega|U_{R}^{\dagger}V\otimes I|\Omega\rangle\|=\left\|\frac{1}{d}\sum_{i,j}\langle j,j|U_{R}^{\dagger}V\otimes I|i,i\rangle\right\|=\left\|\frac{1}{d}\sum_{j}\langle j|U_{R}^{\dagger}V|j\rangle\right\|=\frac{1}{d}\left\|{\rm Tr}\left(U^{\dagger}_{R}V\right)\right\|.$ (33) $$

Based on Lemma [3](#Thmlemma3), the quantum learning model $h_{Q,U_{R}}$ learns $V$ on the training data set $S_{\rm{Haar}^{\otimes n}}$ with $\epsilon$ implies

$$ $\displaystyle\|\langle\Omega|U_{R}^{\dagger}V\otimes I|\Omega\rangle\|^{2}\geq 1-\frac{2(d+1)}{d}\epsilon,$ (34) $$

and we have

$$ $\displaystyle\begin{split}\beta_{QC}(R,V)&\geq{\rm Tr}\left(M((V\otimes I)|\Omega\rangle\langle\Omega|(V^{\dagger}\otimes I)-(I_{n}/2^{n})^{\otimes 2})\right)\\ &=\|\langle\Omega|U_{R}^{\dagger}V\otimes I|\Omega\rangle\|^{2}-\langle\Omega|U^{\dagger}_{R}I_{n}/2^{n}U_{R}\otimes(I_{n}/2^{n})|\Omega\rangle\\ &\geq 1-\frac{2(d+1)}{d}\epsilon-\frac{1}{d^{2}},\end{split}$ (35) $$

which implies that the quantum circuit complexity $C_{\frac{2(d+1)}{d}\epsilon}(V)\leq{\rm size}(U_{R})$.
∎

###### Definition 9 .

###### Definition 10 (Diamond norm) .

###### Definition 11 (Diamond distance) .

###### Definition 12 (Quantum circuit learning) .

###### Theorem 5 .

###### Lemma 3 ( [ 96 ] ) .

###### Proof of theorem 5 .

## Appendix C A warm up task

###### Task 2 .

Given an arbitrary $n$-qubit noisy quantum state $\rho_{\rm un}=\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle 0^{n}|,\bm{\theta})$ prepared by a $\tilde{R}$-depth noisy quantum device, where $\Phi_{p,\tilde{R}}$ is defined in Eq. [4](#S2.E4). Learn the quantum state $\rho_{\rm un}$ through a quantum algorithm with a poly$(n)$-qubit ideal quantum device, then use the learning results to verify whether the noisy state $\rho_{\rm un}$ is close to the maximally mixed state $\frac{I_{n}}{2^{n}}$ in trace distance.

Noting that the relationship $\frac{1}{2}\|\Phi_{p,\tilde{R}}-\frac{I_{n}}{2^{n}}\|_{1}^{2}<\frac{1}{n}$ implies $\langle\Psi|\Phi_{p,\tilde{R}}|\Psi\rangle\leq 2(1/2^{n}+\sqrt{2/n})$ for any $n$-qubit pure state $|\Psi\rangle$ (^1^11Using Pinsker’s inequality [], $\frac{1}{2}\|\Phi_{p,\tilde{R}}-\frac{I_{n}}{2^{n}}\|_{1}^{2}\leq S(\Phi_{p,\tilde{R}}\|I_{n}/2^{n})$. Then if $S(\Phi_{p,\tilde{R}}\|I_{n}/2^{n})\leq 1/n$, this implies $\frac{1}{2}\|\Phi_{p,\tilde{R}}-\frac{I_{n}}{2^{n}}\|_{1}\leq 1/\sqrt{2n}$. Using triangular inequality, one obtains $\frac{1}{2}\||\Psi\rangle\langle\Psi|-\Phi_{p,\tilde{R}}\|_{1}\geq\frac{1}{2}\||\Psi\rangle\langle\Psi|-\frac{I_{n}}{2^{n}}\|_{1}-\frac{1}{2}\|\Phi_{p,\tilde{R}}-\frac{I_{n}}{2^{n}}\|_{1}\geq 1-2^{-n}-1/\sqrt{2n}$ for any $n$-qubit pure state $|\Psi\rangle$. Combining the inequality $\sqrt{1-\langle\Psi|\Phi_{p,\tilde{R}}|\Psi\rangle}\geq\frac{1}{2}\||\Psi\rangle\langle\Psi|-\Phi_{p,\tilde{R}}\|_{1}$, the relationship $\langle\Psi|\Phi_{p,\tilde{R}}|\Psi\rangle\leq 2(2^{-n}+1/\sqrt{2n})$ is valid.). This naturally violates the SSAP property. However, $\frac{1}{2}\|\Phi_{p,\tilde{R}}-\frac{I_{n}}{2^{n}}\|_{1}^{2}>\frac{1}{n}$ cannot necessarily imply $\rho_{\rm un}$ satisfying the $\rm SSAP(\mathcal{A})$ property. Nevertheless, estimating the trace distance and fidelity between two mixed states is generally a QSZK-hard (Quantum Statistical Zero-Knowledge) problem []. Here, a generalized-Bell-measurement algorithm is designed to estimate the relative entropy $S(\rho_{\rm un}\|I_{n}/2^{n})$ which is an upper bound of the trace distance by Pinsker’s inequality []. If $S(\rho_{\rm un}\|I_{n}/2^{n})\leq n^{-1}$, we can partially answer the SCP problem, that is $\rho_{\rm un}$ cannot be approximated by any pure state. Unfortunately, otherwise it does not suffice to give a completeness answer.

Consider the relative entropy $S(\Phi_{p,\tilde{R}}\|I_{n}/2^{n})=n-S(\Phi_{p,\tilde{R}})$, where $S(\rho)=-{\rm Tr}(\rho\log\rho)$ represents the Von-Neumann entropy. Here, a generalized Bell-measurement procedure is proposed in estimating $S(\rho)$, where the fundamental idea is to approximate $S(x)=-x\ln x$ by
a low-degree polynomial function $P(x)$, and each polynomial term can be efficiently estimated by quantum measurement results.

###### Lemma 4 ( [ 99 ] ) .

For every $\eta,\epsilon\in(0,\frac{1}{4}]$, there is an efficient computable polynomial $P(x)=\sum_{l=1}^{d}a_{l}x^{l}\in\mathbb{R}[x]$ of degree $d=\mathcal{O}\left(\frac{1}{\eta}\log(\frac{1}{\eta\epsilon})\right)$ such that

$$ $\displaystyle\left|P(x)-S(x)\right|\leq 2\epsilon\sqrt{-\ln\eta}$ (36) $$

for any $x\in(0,1]$, where coefficients $a_{l}$ come from the Taylor expansion of $S(x)$ around $x_{0}=1/2$.

Without loss of generality, let $\eta=1/4$ and $\epsilon=n^{-1}$, the von-Neumann entropy can be approximated by a $d=\mathcal{O}(\log n)$-degree polynomial function with $\mathcal{O}(n^{-1})$ additive error, that is, $\left|S(\rho)-\sum_{l=1}^{d}a_{l}{\rm Tr}\left(\rho^{l}\right)\right|\leq\mathcal{O}(n^{-1})$.
Then estimating ${\rm Tr}\left(\rho^{l}\right)$ with $1/(n\log n)$ additive error suffices to provide a $\mathcal{O}(n^{-1})$-approximation to $S(\rho)$. The essential idea is that one can conduct polynomial function on the noisy state $\rho^{l}$ by accessing the generalized Bell-measurement method on $l$ copies of $\rho$, that is

$$ $\displaystyle{\rm Tr}\left(\sigma_{x}{\rm CS}_{l}\left(|+\rangle\langle+|\otimes\rho\otimes\cdots\otimes\rho\right){\rm CS}_{l}^{\dagger}\right)={\rm Tr}\left(\rho^{l}\right),$ (37) $$

where ${\rm CS}_{l}$ represents the controlled swap operator.

This step starts from $N_{Q}$ rounds of $l$-copy entangled measurements, where $l\in[d]$. The initial state is the tensor product of $l$ copies of noisy state $\rho\otimes\rho\otimes\cdots\otimes\rho$. Then for the noisy state index $k\in\{0,1,...,l-1\}$, perform $n$ ${\rm CNOT}$ gates on qubit pairs $\{(nk+j,n(k+1)+j)\}_{j=1}^{n}$ and perform $n$ Hadamard gates on qubits $\{n(k+1)+j\}_{j=1}^{n}$. Repeat such circuit construction for $k\in\{0,1,\dots,l-1\}$, a quantum circuit $U_{1}$ is constructed. Perform $U_{1}$ on $l$ copies of noisy state $\rho\otimes\cdots\otimes\rho$, and measure those $ln$ qubits with $\sigma_{z}$ basis for $N_{Q}=\mathcal{O}(n^{2}\log^{2}n)$ times, the measurement result in the $t$-th step is obtained:

$$ $\displaystyle\mathcal{S}_{t}=\{(s_{t}^{1},s_{t}^{n+1},...s_{t}^{(l-1)n+1}),(s_{t}^{2},s_{t}^{n+2},...s_{t}^{(l-1)n+2}),...,(s_{t}^{n},s_{t}^{2n},...s_{t}^{ln})\},$ (38) $$

where $t\in[N_{Q}]$ and $s_{t}^{j}\in\{0,1\}$ represents the measurement result on qubit $j$ in the $t$-th experiment.

Then we show how to utilize the measured results $\mathcal{S}_{t}$ to estimate ${\rm Tr}(\rho^{l})$. Let $s_{\rm an}(t,j)=s_{t}^{j}\oplus\cdots\oplus s_{t}^{(l-1)n+j}$ for the index $j\in[n]$, and assign $s_{\rm an}(t)=s_{\rm an}(t,1)\oplus\cdots\oplus s_{\rm an}(t,n)$. Finally, one obtains

$$ $\displaystyle\mathbb{E}_{t}\left[s_{\rm an}(t)\right]={\rm Tr}\left(\sigma_{x}{\rm CS}_{l}\left(|+\rangle\langle+|\otimes\rho\otimes\cdots\otimes\rho\right){\rm CS}_{l}^{\dagger}\right)={\rm Tr}\left(\rho^{l}\right),$ (39) $$

where the quantum circuit

$$ $\displaystyle{\rm CS}_{l}=|0\rangle\langle 0|_{\rm an}\otimes I_{2^{nl}}+|1\rangle\langle 1|_{\rm an}\otimes S_{l}$ (40) $$

and the generalized swap operator $S_{l}|\bm{x}_{1},\bm{x}_{2},...,\bm{x}_{l}\rangle=|\bm{x}_{2},...,\bm{x}_{l},\bm{x}_{1}\rangle$ and each $\bm{x}$ represents the computational basis of each copy. The whole procedure can be summarized as Alg. [3](#algorithm3).

Figure: Algorithm 3 Von Neumann Entropy Calculation

###### Task 2 .

###### Lemma 4 ( [ 99 ] ) .

## Appendix D Discussions on noise circuit with local depolarizing channel

In addition, consider the single-qubit depolarizing noise perform on the $i$-th qubit with strength $\gamma$,

$$ $\displaystyle\mathcal{E}^{(i)}_{1}(\cdot)=(1-\gamma)(\cdot)+\gamma{\rm Tr}_{i}(\cdot)I_{\left\{i\right\}}/2,$ (41) $$

where ${\rm Tr}_{i}$ denotes the partial trace of the $i$th qubit, and $I_{S}$ denotes identity operating on qubit set $S$.
and the rank of the contraction map decays exponentially with the circuit depth.

###### Lemma 5 .

For $\Phi_{p,\tilde{R}}$ being a noisy quantum device with $\tilde{R}$-layers, and each qubit is perturbed by a local noisy channel defined as Eq. [41](#A4.E41) with strength $\gamma$ after performing a quantum gate. Then the rank of the contraction map $\mathcal{U}_{\tilde{R}}\mathcal{E}_{1}^{\otimes n}\cdots\mathcal{U}_{1}\mathcal{E}_{1}^{\otimes n}(|0^{n}\rangle\langle 0^{n}|)$ satisfies

$$ $\displaystyle r_{\max}\leq(1-0.75\gamma)^{n\tilde{R}}\tilde{R}.$ (42) $$

###### Proof.

This proof is inspired by the Pauli path method. Let $\rho$ be an $n$-qubit density matrix, we can write $\rho=\sum_{s\in\mathcal{P}_{n}}\alpha_{s}\cdot s$ where

$$ $\displaystyle s\in\mathcal{P}_{n}=\left\{\frac{I_{1}}{\sqrt{2}},\frac{X}{\sqrt{2}},\frac{Y}{\sqrt{2}},\frac{Z}{\sqrt{2}}\right\}^{\otimes n}$ (43) $$

represents the normalized $n$-qubit Pauli operator, and $\alpha_{s}={\rm Tr}(\rho s)$, where $I_{1}$ represent identity in a single qubit. Consider a quantum circuit $U=U_{\tilde{R}}U_{\tilde{R}-1}\cdots U_{1}$ where each $U_{r}$ represents a causal slice. A Pauli path is a sequence $\vec{\bm{s}}=(s_{1},s_{2},...,s_{\tilde{R}})\in\mathcal{P}_{n}^{\tilde{R}}$. Therefore, the unitary approach by $U$ can be written as sum of product of transition amplitudes, that is

$$ $\displaystyle U|0^{n}\rangle\langle 0^{n}|U^{\dagger}=\sum\limits_{s_{\tilde{R}},...,s_{1}}{\rm Tr}\left(s_{\tilde{R}}U_{\tilde{R}}s_{\tilde{R}-1}U^{\dagger}_{\tilde{R}}\right)\cdots{\rm Tr}\left(s_{2}U_{2}s_{1}U^{\dagger}_{2}\right){\rm Tr}\left(s_{1}U_{1}|0^{n}\rangle\langle 0^{n}|U^{\dagger}_{1}\right)s_{\tilde{R}}.$ (44) $$

Consider the single-qubit depolarizing noise defined as Eq. [41](#A4.E41) with strength $\gamma$,

$$ $\displaystyle\mathcal{E}_{1}^{\otimes n}\mathcal{U}_{1}(\ket{0^{n}}\bra{0^{n}})=\mathcal{E}_{1}^{\otimes n}\left(\sum\limits_{s_{1}}{\rm Tr}\left(s_{1}U_{1}|0^{n}\rangle\langle 0^{n}|U^{\dagger}_{1}\right)s_{1}\right)=\sum\limits_{s_{1}}{\rm Tr}\left(s_{1}U_{1}|0^{n}\rangle\langle 0^{n}|U^{\dagger}_{1}\right)\mathcal{E}_{1}^{\otimes n}(s_{1}).$ (45) $$

Denote the $n$-qubit normalized Pauli operator $s=s^{(1)}\otimes\cdots\otimes s^{(n)}$, where each

$$ $s^{(i)}\in\{I_{1}/\sqrt{2},X/\sqrt{2},Y/\sqrt{2},Z/\sqrt{2}\},$ $$

then $\mathcal{E}^{\otimes n}_{1}(s)=\mathcal{E}_{1}(s^{(1)})\otimes\cdots\otimes\mathcal{E}_{1}(s^{(n)})$. If $s^{(i)}=I_{1}/{\sqrt{2}}$, then $\mathcal{E}_{1}(s^{(i)})=(1-\gamma)I_{1}/{\sqrt{2}}+\gamma{\rm Tr}(I_{1}/{\sqrt{2}})I_{1}/2=I_{1}/{\sqrt{2}}$, otherwise, ${\rm Tr}(s^{(i)})=0$, and $\mathcal{E}_{1}(s^{(i)})=(1-\gamma)s^{(i)}+\gamma{\rm Tr}(s^{(i)})I_{1}/2=(1-\gamma)s^{(i)}$. As a result, $\mathcal{E}^{\otimes n}_{1}(s)=(1-\gamma)^{\left|s\right|}s$, where $\left|s\right|$ represents the number of non-identity operator in $s_{1},...,s_{n}$. Using the above relationship, the noisy quantum circuit $\mathcal{U}$ can be expressed as

$$ $\displaystyle\mathcal{E}^{\otimes n}\mathcal{U}_{\tilde{R}}\mathcal{E}^{\otimes n}\cdots\mathcal{E}^{\otimes n}\mathcal{U}_{1}(\ket{0}\bra{0})=\sum\limits_{s_{\tilde{R}},...,s_{1}}(1-\gamma)^{\left|\vec{\bm{s}}\right|}{\rm Tr}\left(s_{\tilde{R}}U_{\tilde{R}}s_{\tilde{R}-1}U^{\dagger}_{\tilde{R}}\right)\cdots{\rm Tr}\left(s_{2}U_{2}s_{1}U^{\dagger}_{2}\right){\rm Tr}\left(s_{1}U_{1}|0^{n}\rangle\langle 0^{n}|U^{\dagger}_{1}\right)s_{\tilde{R}},$ (46) $$

where $\vec{\bm{s}}=(s_{1},\dots,s_{\tilde{R}})\in\mathcal{P}_{n}^{\tilde{R}}$. For relatively low-degree weight $\left|\vec{\bm{s}}\right|$, $\mathcal{U}$ can manipulate the factor on such $\vec{\bm{s}}$ by tuning $U_{i}$, and thus has relatively larger freedom on $\vec{\bm{s}}$. However, high-degree weight $\left|\vec{\bm{s}}\right|$ results in an exponentially small factor and enables $\mathcal{U}$ losses its original freedom on these basis $\vec{\bm{s}}$. Therefore, the accessible dimension of the $\tilde{R}$-depth quantum circuit $\mathcal{U}$ on the basis set $s_{\tilde{R}}\in\mathcal{P}_{n}$ can be estimated by

$$ $\displaystyle\begin{split}\mathbb{E}_{\vec{\bm{s}}\in\mathcal{P}_{n}^{\tilde{R}}}\left[(1-\gamma)^{\left|\vec{\bm{s}}\right|}\tilde{R}\right]&=\sum\limits_{\vec{\bm{s}}\in\mathcal{P}_{n}^{\tilde{R}}}{\rm Pr}(\vec{\bm{s}})(1-\gamma)^{\left|\vec{\bm{s}}\right|}\tilde{R}\\ &=\left(\sum\limits_{s\in\mathcal{P}_{n}}{\rm Pr}(s)(1-\gamma)^{\left|s\right|}\right)^{\tilde{R}}\tilde{R}\\ &=\left(\frac{1}{4^{n}}\sum\limits_{k=0}^{n}\binom{n}{k}3^{k}(1-\gamma)^{k}\right)^{\tilde{R}}\tilde{R}\\ &=(1-0.75\gamma)^{n\tilde{R}}\tilde{R}.\end{split}$ (47) $$

Furthermore, the rank of an algebraic set and the dimension of its image by polynomial map can be connected by Sard’s theorem [], that is $r_{\rm max}(\mathcal{U})={\rm dim}(\mathcal{U})$. As a result, $r_{\max}(\mathcal{U})\leq(1-0.75\gamma)^{n\tilde{R}}\tilde{R}$.
∎

###### Lemma 5 .

###### Proof.

## Appendix E Proof Details in the Main File

### E.1 Proof of Theorem 1

###### Proof.

Here, we are interested in measuring the quantity $\mathbb{E}_{\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}}}\left[{\rm Tr}(\rho_{1,\tilde{R}}\rho_{2,\tilde{R}})\right]$, where $\rho_{1,\tilde{R}}=\bigcirc_{r=1}^{\tilde{R}}\mathcal{E}\circ\mathcal{U}_{r}(\rho_{1})$, $\rho_{2,\tilde{R}}=\bigcirc_{r=1}^{\tilde{R}}\mathcal{U}_{r}(\rho_{2})$ and $\rho_{1}$, $\rho_{2}$ represent initial pure states. Suppose $\mathcal{E}$ can be decomposed by Kraus operators, that is $\mathcal{E}(\cdot)=\sum_{l=1}^{r}K_{l}(\cdot)K_{l}^{\dagger}$. Then we first consider the scenario $\tilde{R}=1$:

$$ $\displaystyle\begin{split}{\rm Tr}\left(\rho_{1,1}\rho_{2,1}\right)=&{\rm Tr}\left[\left(\mathcal{E}\circ\mathcal{U}_{1}(\rho_{1})\mathcal{U}_{1}(\rho_{2})\right)\right]\\ =&{\rm Tr}\left[{\rm Swap}\left(\mathcal{E}\circ\mathcal{U}_{1}(\rho_{1})\otimes\mathcal{U}_{1}(\rho_{2})\right)\right]\\ =&\sum\limits_{l=1}^{r}{\rm Tr}\left[{\rm Swap}\left(K_{l}\mathcal{U}_{1}(\rho_{1})K_{l}^{\dagger}\otimes\mathcal{U}_{1}(\rho_{2})\right)\right].\end{split}$ (48) $$

Then taking the average value on a unitary $2$ design set, we obtain

$$ $\displaystyle\mathbb{E}_{\mathcal{U}_{1}}{\rm Tr}\left(\rho_{1,1}\rho_{2,1}\right)=\sum\limits_{l=1}^{r}\mathbb{E}_{\mathcal{U}_{1}}{\rm Tr}\left[{\rm Swap}\left((K_{l}\otimes I_{n})(U_{1}\otimes U_{1})(\rho_{1}\otimes\rho_{2})(U_{1}^{\dagger}\otimes U_{1}^{\dagger})(K_{l}^{\dagger}\otimes I_{n})\right)\right].$ (49) $$

Considering the relationship

$$ $\displaystyle\begin{split}\mathbb{E}_{\mathcal{U}\sim\mathbb{U}}\left[(U\otimes U)A(U^{\dagger}\otimes U^{\dagger})\right]=&\left(\frac{{\rm Tr}(A)}{d^{2}-1}-\frac{{\rm Tr}({\rm Swap}A)}{d(d^{2}-1)}\right)I_{n}\otimes I_{n}+\left(\frac{{\rm Tr}({\rm Swap}A)}{d^{2}-1}-\frac{{\rm Tr}(A)}{d(d^{2}-1)}\right){\rm Swap}\\ =&\alpha I_{n}\otimes I_{n}+\beta{\rm Swap}\end{split}$ (50) $$

where $\mathbb{U}$ is unitary $2$-design, then Eq. [49](#A5.E49) can be further calculated by

$$ $\displaystyle\begin{split}\mathbb{E}_{\mathcal{U}_{1}}{\rm Tr}\left(\rho_{1,1}\rho_{2,1}\right)=&\sum\limits_{l=1}^{r}\mathbb{E}_{\mathcal{U}_{1}}{\rm Tr}\left[{\rm Swap}\left((K_{l}\otimes I_{n})(\alpha I_{n}\otimes I_{n}+\beta{\rm Swap})(K_{l}^{\dagger}\otimes I_{n})\right)\right]\\ =&\alpha\sum\limits_{l=1}^{r}{\rm Tr}\left[{\rm Swap}(K_{l}K^{\dagger}_{l}\otimes I_{n})\right]+\beta\sum\limits_{l=1}^{r}{\rm Tr}\left[{\rm Swap}(K_{l}\otimes I_{n}){\rm Swap}(K_{l}^{\dagger}\otimes I_{n})\right]\\ =&\alpha\sum\limits_{l=1}^{r}{\rm Tr}\left[K_{l}K^{\dagger}_{l}\right]+\beta\sum\limits_{l=1}^{r}\left|{\rm Tr}\left[K_{l}\right]\right|^{2}.\end{split}$ (51) $$

The last inequality comes from

$$ $\displaystyle\begin{split}{\rm Tr}\left[{\rm Swap}(K_{l}\otimes I_{n}){\rm Swap}(K_{l}^{\dagger}\otimes I_{n})\right]&={\rm Tr}\left[{\rm Swap}(K_{l}\otimes I_{n})(I_{n}\otimes K_{l}^{\dagger})\right]\\ &={\rm Tr}\left[{\rm Swap}(K_{l}\otimes K_{l}^{\dagger})\right]\\ &=\left|{\rm Tr}\left[K_{l}\right]\right|^{2}.\end{split}$ (52) $$

Consider $\sum_{l=1}^{r}{\rm Tr}\left[K_{l}K^{\dagger}_{l}\right]={\rm Tr}[\mathcal{E}(I_{n})]=d$ and denote $F=\sum\limits_{l=1}^{r}\left|{\rm Tr}\left[K_{l}\right]\right|^{2}$,
Eq. [49](#A5.E49) can be finally expressed as

$$ $\displaystyle\begin{split}\mathbb{E}_{\mathcal{U}_{1}}{\rm Tr}\left(\rho_{1,1}\rho_{2,1}\right)&=\left(\frac{1}{d^{2}-1}-\frac{{\rm Tr}(\rho_{1}\rho_{2})}{d(d^{2}-1)}\right){\rm Tr}[\mathcal{E}(I_{n})]+\left(\frac{{\rm Tr}(\rho_{1}\rho_{2})}{d^{2}-1}-\frac{1}{d(d^{2}-1)}\right)F\\ &=\frac{F-1}{d^{2}-1}{\rm Tr}(\rho_{1}\rho_{2})+\frac{1}{d^{2}-1}\left(d-F/d\right),\end{split}$ (53) $$

where $d=2^{n}$. Therefore, we obtain a recursive formula for the overlap of the output states, as defined in [53](#A5.E53). We have

$$ $\displaystyle\begin{split}\mathbb{E}_{\mathcal{U}_{1},\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}}}{\rm Tr}\left(\rho_{1,\tilde{R}}\rho_{2,\tilde{R}}\right)=\frac{F-1}{d^{2}-1}\mathbb{E}_{\mathcal{U}_{1},\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}-1}}{\rm Tr}(\rho_{1,\tilde{R}-1}\rho_{2,\tilde{R}-1})+\frac{1}{d^{2}-1}\left(d-F/d\right).\end{split}$ (54) $$

Then, we can use this iteration relationship to construct a geometric sequence, that is

$$ $\displaystyle\begin{split}\mathbb{E}_{\mathcal{U}_{1},\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}}}{\rm Tr}\left(\rho_{1,\tilde{R}}\rho_{2,\tilde{R}}\right)-\frac{1}{d}=&\left(\frac{F-1}{d^{2}-1}\right)\left(\mathbb{E}_{\mathcal{U}_{1},\mathcal{U}_{1},...,\mathcal{U}_{\tilde{R}-1}}{\rm Tr}(\rho_{1,\tilde{R}-1}\rho_{2,\tilde{R}-1})-\frac{1}{d}\right)\\ =&\left(\frac{F-1}{d^{2}-1}\right)^{\tilde{R}-1}\left(\mathbb{E}_{\mathcal{U}_{1}}{\rm Tr}\left(\rho_{1,1}\rho_{2,1}\right)-\frac{1}{d}\right)\\ =&\left(\frac{F-1}{d^{2}-1}\right)^{\tilde{R}-1}\left(\frac{F-1}{d^{2}-1}+\frac{d^{2}-F}{d(d^{2}-1)}-\frac{1}{d}\right)\\ =&\left(\frac{F-1}{d^{2}-1}\right)^{\tilde{R}-1}\frac{F-1}{d(d+1)},\end{split}$ (55) $$

where the last equality comes from initial states $\rho_{1}=\rho_{2}=|0^{n}\rangle\langle 0^{n}|$.
∎

###### Proof.

### E.2 Proof of Theorem 2

###### Proof.

Consider $U(\bm{\alpha})=\prod_{r=1}^{LR}U(\bm{\alpha}_{r})$ is composed of $LR$ two-qubit gates

$$ $\displaystyle U(\bm{\alpha}_{r})=\exp\left(-i\sum\limits_{j_{1},j_{2}=0}^{4}\alpha_{r}(j_{1},j_{2})\left(P_{j_{1}}\otimes P_{j_{2}}\right)\right)=\exp\left(-i\langle\bm{\alpha}_{r},\bm{P}_{r}\rangle\right),$ (56) $$

where $P_{j}\in\{I,X,Y,Z\}$ and each $\alpha_{r}(j_{1},j_{2})\in[0,2\pi]$.
Using Taylor series, one obtains

$$ $\displaystyle U(\bm{\alpha})=\prod\limits_{r=1}^{LR}\sum\limits_{k=0}^{\infty}\frac{(-i\langle\bm{\alpha}_{r},\bm{P}_{r}\rangle)^{k}}{k!}.$ (57) $$

Denote

$$ $\displaystyle U(\bm{\alpha}_{r})_{\rm tr}=\sum\limits_{k=0}^{K}\frac{(-i\langle\bm{\alpha}_{r},\bm{P}_{r}\rangle)^{k}}{k!},$ (58) $$

therefore $U(\bm{\alpha}_{r})-U(\bm{\alpha}_{r})_{\rm tr}=\sum_{k=K+1}^{\infty}\frac{(-i\langle\bm{\alpha}_{r},\bm{P}_{r}\rangle)^{k}}{k!}$. For arbitrary bit-string $x,y$, we can apply standard bound on Taylor series to bound $\|\langle x|(U(\bm{\alpha}_{r})-U(\bm{\alpha}_{r})_{\rm tr})|y\rangle\|_{1}\leq\kappa/K!$ for some constant $\kappa$.
Therefore

$$ $\displaystyle\begin{split}&\langle 0^{n}|U^{\dagger}(\bm{\alpha})\rho U(\bm{\alpha})|0^{n}\rangle=\sum\limits_{i,j=0}^{2^{n}-1}\rho_{ij}\langle 0^{n}|U^{\dagger}(\bm{\alpha})|i\rangle\langle j|U(\bm{\alpha})|0^{n}\rangle\\ &=\sum\limits_{i,j=0}^{2^{n}-1}\rho_{ij}\left(\sum\limits_{\begin{subarray}{c}y_{1},y_{2},...y_{LR-1}\in\{0,1\}^{n}\\ y_{LR}={\color[rgb]{0,0,1}i}\end{subarray}}\prod\limits_{r=1}^{LR}\langle 0^{n}|U(\bm{\alpha}_{r})|y_{r}\rangle\right)\left(\sum\limits_{\begin{subarray}{c}y_{1},y_{2},...y_{LR-1}\in\{0,1\}^{n}\\ y_{LR}=j\end{subarray}}\prod\limits_{r=1}^{LR}\langle y_{r}|U(\bm{\alpha}_{r})|0^{n}\rangle\right)\\ &=\sum\limits_{i,j=0}^{2^{n}-1}\rho_{ij}\left(\sum\limits_{\begin{subarray}{c}y_{1},y_{2},...y_{LR-1}\in\{0,1\}^{n}\\ y_{LR}={\color[rgb]{0,0,1}i}\end{subarray}}\prod\limits_{r=1}^{LR}\langle 0^{n}|\sum\limits_{k=0}^{\infty}\frac{(-i\langle\bm{\alpha}_{r},\bm{P}_{r}\rangle)^{k}}{k!}|y_{r}\rangle\right)\left(\sum\limits_{\begin{subarray}{c}y_{1},y_{2},...y_{LR-1}\in\{0,1\}^{n}\\ y_{LR}=j\end{subarray}}\prod\limits_{r=1}^{LR}\langle y_{r}|\sum\limits_{k=0}^{\infty}\frac{(-i\langle\bm{\alpha}_{r},\bm{P}_{r}\rangle)^{k}}{k!}|0^{n}\rangle\right),\end{split}$ (59) $$

where the $y_{1},.y_{2},...$ represent Feymann integration path. Since $\langle y_{r}|U(\bm{\alpha}_{r})|0^{n}\rangle$ can be approximated by a polynomial of degree $K$ based on Taylor truncated method, the above expression can be rewritten by

$$ $\displaystyle\sum\limits_{r,s=0}^{2^{n}-1}\rho_{rs}\left(f_{r}(\bm{\alpha}_{1},...\bm{\alpha}_{LR})+\mathcal{O}\left(\frac{2^{LRn}}{(K!)^{LR}}\right)\right)\left(f_{s}(\bm{\alpha}_{1},...\bm{\alpha}_{LR})+\mathcal{O}\left(\frac{2^{LRn}}{(K!)^{LR}}\right)\right),$ (60) $$

where $f_{r}$ represents a polynomial of degree $LRK$. Furthermore, $f_{r}(\bm{\alpha}_{1},...,\bm{\alpha}_{LR})$ can be approximated by a low-degree function with at most $\binom{LR}{q}(K)^{q}$ terms, where $q=\mathcal{O}(1)$. Denote

$$ $f_{r}(\vec{\bm{\alpha}})=2^{LRn}\sum_{\vec{\bm{i}}}\sum_{j_{1},j_{2}}\bm{a}_{\vec{\bm{i}}}\alpha_{1}^{i_{1}}(j_{1},j_{2})\cdots\alpha_{LR}^{i_{LR}}(j_{1},j_{2}),$ $$

where $\vec{\bm{i}}=(i_{1},...,i_{LR})$, $\vec{\bm{\alpha}}=(\alpha_{1}(j_{1},j_{2}),\ldots,\alpha_{LR}(j_{1},j_{2}))$, $j_{1},j_{2}\in[15]$ and each $i_{l}\in[K]$, $l\in[LR]$. For the convenience of the proof, we omit the index $(j_{1},j_{2})$ in $f_{r}$ in the following procedure.

For every term $\bm{a}_{\vec{\bm{i}}}\alpha_{1}^{i_{1}}\cdots\alpha_{v}^{i_{v}}$ with $i_{1}=\cdots=i_{v}=K$ and $v>q$, its corresponding parameter $\left|\bm{a}_{\vec{\bm{i}}}\right|\leq 1/(K!)^{q}$ (based on Taylor series). Truncate above high-degree terms, therefore, the relationship

$$ $\displaystyle\Delta f_{r}(\vec{\bm{\alpha}})=\left|f_{r}-\tilde{f}_{r}\right|=2^{LRn}\left|\sum_{\vec{\bm{i}}}\bm{a}_{\vec{\bm{i}}}\alpha_{1}^{i_{1}}\cdots\alpha_{LR}^{i_{LR}}-\sum_{\begin{subarray}{c}j_{1},...,j_{q}\leq K-1\\ s_{1}\leq s_{2}...\leq s_{q}\leq LR\end{subarray}}\bm{a}_{\vec{\bm{j}},\vec{\bm{s}}}\alpha_{s_{1}}^{j_{1}}\cdots\alpha_{s_{q}}^{j_{q}}\right|\leq 2^{LRn}\left(\frac{K^{LR}}{(K!)^{q}}\right)$ (61) $$

holds.
Then let $q=\mathcal{O}(1)$, $LR=\mathcal{O}(n\log(n))$, $K=(nLR/\log n)$, $\tilde{f}_{r}$ can provide an estimation to $f_{r}$ within $2^{-{\rm poly}(n)}$ additive error according to the Stirling’s formula. Specifically, let $q=1$ and use Stirling’s formula, the error

$$ $\displaystyle\begin{split}2^{LRn}\left(\frac{K^{LR}}{(K!)^{q}}\right)=\frac{2^{n^{2}\log n}K^{n\log n}}{K!}\approx\frac{2^{n^{2}\log n}e^{K}K^{n\log n}}{\sqrt{2\pi K}K^{K}}.\end{split}$ (62) $$

Let $K=n^{2}$, one obtains

$$ $\displaystyle\frac{2^{n^{2}\log n}e^{n^{2}}(n^{2})^{n\log n}}{\sqrt{2\pi n^{2}}(n^{2})^{n^{2}}}=\frac{(2^{\log n}e)^{n^{2}}(n^{2})^{n\log n}}{\sqrt{2\pi n^{2}}(n^{2})^{n^{2}}}=\frac{n^{2n\log n}}{\sqrt{2\pi n^{2}}}\left(\frac{e}{n}\right)^{n^{2}}=\frac{1}{\sqrt{2\pi n^{2}}}\frac{(e)^{n^{2}}}{n^{n^{2}-2n\log n}}\leq\frac{1}{\sqrt{2\pi n^{2}}}\frac{(e)^{n^{2}}}{n^{n^{2}/2}}$ (63) $$

where the last inequality comes from $n\geq 4\log n$. Then the above error can be upper bounded by $(e/\sqrt{n})^{n^{2}}<2^{-n^{2}}$. Then Eq. [60](#A5.E60) can be represented by a muti-variable polynomial function $f(\vec{\bm{\alpha}},\rho)$ with $R$ variables and at most ${\rm poly}(n)$ terms, and the relationship

$$ $\displaystyle\|\langle 0^{n}|U^{\dagger}(\vec{\bm{\alpha}})\rho U(\vec{\bm{\alpha}})|0^{n}\rangle-f(\vec{\bm{\alpha}},\rho)\|\leq 2^{-n^{2}}$ (64) $$

holds [].
Suppose the target observable $M=U(\bm{\alpha}^{*})|0^{n}\rangle\langle 0^{n}|U^{\dagger}(\bm{\alpha}^{*})$, then

$$ $\displaystyle{\rm Tr}(M\rho)\approx f(\vec{\bm{\alpha}}^{*},\rho)=\sum_{\begin{subarray}{c}j_{1},...,j_{q}\leq(K-1)\\ s_{1}\leq s_{2}...\leq s_{q}\leq LR\end{subarray}}\bm{a}_{\vec{\bm{j}},\vec{\bm{s}}}(\rho)\alpha_{s_{1}}^{j_{1},*}\cdots\alpha_{s_{q}}^{j_{q},*}.$ (65) $$

On other hand, consider a machine learning procedure with data points $\{(x_{i}=\vec{\bm{\alpha}}_{i},y_{i}=f(\vec{\bm{\alpha}}_{i},\rho))\}$. Let the feature map $\Psi(\vec{\bm{\alpha}})=(\alpha_{s_{1}}^{j_{1}}\cdots\alpha_{s_{q}}^{j_{q}})_{\vec{\bm{s}},\vec{\bm{j}}}$, and the target is to synthesis the function $f(\vec{\bm{\alpha}},\rho)=\langle\vec{\bm{a}},\Psi(\vec{\bm{\alpha}})\rangle$, where $\vec{\bm{a}}\in\mathbb{R}^{LRn^{2}}$. Consider the loss function

$$ $\displaystyle\min\limits_{\vec{\bm{a}}}\lambda\langle\vec{\bm{a}},\vec{\bm{a}}\rangle+\sum\limits_{i=1}^{N}\left(\langle\vec{\bm{a}},\Psi(\vec{\bm{\alpha}}_{i})\rangle-y_{i}\right)^{2},$ (66) $$

where $\lambda>0$ is a hyper-parameter. Define the feature matrix $\Psi=(\Psi(\vec{\bm{\alpha}}_{1}),\dots,\Psi(\vec{\bm{\alpha}}_{N}))$ and the kernel matrix

$$ $\displaystyle{\rm K}=\Psi^{\dagger}\Psi=\left[{\rm K}(\vec{\bm{\alpha}}_{i},\vec{\bm{\alpha}}_{j})\right]_{i,j=1}^{N},$ (67) $$

where the kernel function

$$ $\displaystyle{\rm K}(\bm{\alpha},\bm{\alpha}^{\prime})=\sum_{l=0}^{K}\sum_{1\leq i_{1}<\cdots<i_{q}\leq LR}(\alpha_{i_{1}}\alpha_{i_{1}}^{\prime}+\cdots+\alpha_{i_{q}}\alpha_{i_{q}}^{\prime})^{l}.$ (68) $$

Without loss of generality, we can normalize ${\rm K}(\bm{\alpha},\bm{\alpha}^{\prime})$ enabling ${\rm Tr}(\rm K)=N$. Therefore, the optimal solution

$$ $\displaystyle\vec{\bm{a}}_{\rm opt}=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\Psi(\vec{\bm{\alpha}}_{i})\left(\rm K+\lambda I\right)^{-1}_{ij}f(\vec{\bm{\alpha}}_{j}).$ (69) $$

As a result, the trained machine learning model

$$ $\displaystyle\begin{split}g(\vec{\bm{x}})=\langle\vec{\bm{a}}_{\rm opt},\Psi(\vec{\bm{x}})\rangle&=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\left(\rm K+\lambda I\right)^{-1}_{ij}{\rm K}(\vec{\bm{\alpha}}_{i},\vec{\bm{x}})f(\vec{\bm{\alpha}}_{j})\\ &=\sum\limits_{j=1}^{N}\left(\sum\limits_{i=1}^{N}\left({\rm K}+\lambda I\right)^{-1}_{ij}{\rm K}(\vec{\bm{\alpha}}_{i},\vec{\bm{x}})\right)f(\vec{\bm{\alpha}}_{j})\\ &=\sum\limits_{j=1}^{N}\vec{\bm{\beta}}_{j}(\bm{x})f(\vec{\bm{\alpha}}_{j})\\ &=\sum\limits_{j=1}^{N}\vec{\bm{\beta}}_{j}(\bm{x})\langle 0^{n}|U^{\dagger}(\vec{\bm{\alpha}}_{j})\rho U(\vec{\bm{\alpha}}_{j})|0^{n}\rangle+\mathcal{O}\left(\frac{2^{LRn}}{(K!)^{LR}}\right).\end{split}$ (70) $$

Now we analyze the prediction error of $g(\vec{\bm{x}})$ on the domain $[0,2\pi]^{LR}$. Denote

$$ $\displaystyle\begin{split}\tilde{\epsilon}(\vec{\bm{x}})=\epsilon(\vec{\bm{x}})+\left|{\rm Tr}(M(\vec{\bm{x}})\rho)-f(\vec{\bm{x}},\rho)\right|&=\left|g(\vec{\bm{x}})-f(\vec{\bm{x}},\rho)\right|+\left|{\rm Tr}(M(\vec{\bm{x}})\rho))-f(\vec{\bm{x}},\rho)\right|\\ &\leq\left|g(\vec{\bm{x}})-f(\vec{\bm{x}},\rho)\right|+2^{-{\rm poly}(n)},\end{split}$ (71) $$

and the expected prediction error

$$ $\displaystyle\mathbb{E}_{\vec{\bm{x}}}\epsilon(\vec{\bm{x}})=\frac{1}{N}\sum\limits_{i=1}^{N}\epsilon(\vec{\bm{x}})+\left(\mathbb{E}_{\vec{\bm{x}}}\epsilon(\vec{\bm{x}})-\frac{1}{N}\sum\limits_{i=1}^{N}\epsilon(\vec{\bm{x}})\right).$ (72) $$

Using the Cauchy-Schwartz inequality, the above first term can be upper bounded by

$$ $\displaystyle\frac{1}{N}\sum\limits_{i=1}^{N}\epsilon(\vec{\bm{x}})\leq\sqrt{\frac{\lambda^{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\left({\rm K}+\lambda I\right)^{-1}_{ij}y_{i}y_{j}}{N}}.$ (73) $$

Therefore, if the matrix $\rm K$ is invertable and hyper-parameter $\lambda=0$, the training error is zero. Without loss of generality, we set $\lambda=1/{\rm poly}(n)$.

The generalized error can be characterized by the Rademacher complexity [], that is

$$ $\displaystyle\mathbb{E}_{\vec{\bm{x}}}\epsilon(\vec{\bm{x}})-\frac{1}{N}\sum\limits_{i=1}^{N}\epsilon(\vec{\bm{x}})\leq\sqrt{\frac{\sup({\rm K}(x,x))\|\vec{\bm{a}}_{\rm opt}\|_{\Psi}}{N}}=\sqrt{\frac{\|\vec{\bm{a}}_{\rm opt}\|_{\Psi}}{N}},$ (74) $$

where $\|\vec{\bm{a}}\|_{\Psi}=\langle\vec{\bm{a}}_{\rm opt},\vec{\bm{a}}_{\rm opt}\rangle$. Ideally, $\vec{\bm{a}}_{\rm opt}=(\bm{a}_{\vec{\bm{j}},\vec{\bm{s}}}(\rho))$ for $j_{1},...,j_{q}\leq K-1$, $s_{1}\leq s_{2}...\leq s_{q}\leq LR$, and $\vec{\bm{a}}$ is induced by the polynomial kernel function, therefore the $2$-norm of the vector $(\bm{a}_{\vec{\bm{j}},\vec{\bm{s}}}(\rho))_{\vec{\bm{j}},\vec{\bm{s}}}$ can be used to estimate $\|\vec{\bm{a}}\|_{\Psi}$. Noting that the multi-variable polynomial function $\sum_{\vec{\bm{j}},\vec{\bm{s}}}\bm{a}_{\vec{\bm{j}},\vec{\bm{s}}}(\rho)\alpha_{s_{1}}^{j_{1}}\cdots\alpha_{s_{q}}^{j_{q}}$ belongs to $[0,1]$ for all $\vec{\bm{\alpha}}\in[0,2\pi]^{LR}$. Let $\vec{\bm{\alpha}}$ takes value from $\{0,1\}^{LR}$, we know that all $\bm{a}_{\vec{\bm{j}},\vec{\bm{s}}}(\rho)\in[0,1]$. Therefore, we can upper bound $\|\vec{\bm{a}}\|_{\Psi}$ by $(LR)K=(LR)n^{2}$.

Combine all together, for any $M(\vec{\bm{x}})=U(\vec{\bm{x}})|0^{n}\rangle\langle 0^{n}|U^{\dagger}(\vec{\bm{x}})$ for $U\in\mathcal{U}_{\mathcal{A}}(R)$ and arbitrary density matrix $\rho$, the relationship

$$ $\displaystyle\mathbb{E}_{\vec{\bm{x}}}\left|\sum\limits_{j=1}^{N}\vec{\bm{\beta}}_{j}(\bm{x})\langle 0^{n}|U^{\dagger}(\vec{\bm{\alpha}}_{j})\rho U(\vec{\bm{\alpha}}_{j})|0^{n}\rangle-{\rm Tr}\left(M(\vec{\bm{x}})\rho\right)\right|\leq\sqrt{\frac{\lambda^{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\left({\rm K}+\lambda I\right)^{-1}_{ij}y_{i}y_{j}}{N}}+\sqrt{\frac{LRn^{2}}{N}}$ (75) $$

In the above first term, hyper-parameter $\lambda$ can take arbitrary value, and $\lambda=\sqrt{\lambda_{\min}(\rm K)}/(nN)$ enables that the first term is upper bounded by $1/n$, where $\lambda_{\min}(\rm K)$ represents the minimum eigenvalue of the kernel matrix $\rm K$. In the second term, let $N=(LR)n^{2}\epsilon^{-2}$, and the above error can be upper bounded by $\epsilon$.

Finally, we point that $\sum_{j=1}^{N}\vec{\bm{\beta}}_{j}(\bm{x})=1$ and all the parameters $\vec{\bm{\beta}}_{j}(\bm{x})$ can be limited into a bounded domain. The first relationship naturally holds since $\sum_{j=1}^{N}\vec{\bm{\beta}}_{j}(\bm{x})U(\vec{\bm{\alpha}}_{j})|0^{n}\rangle\langle 0^{n}|U^{\dagger}(\vec{\bm{\alpha}}_{j})$ is essentially an approximation of $U(\vec{\bm{\alpha}}^{*})|0^{n}\rangle\langle 0^{n}|U^{\dagger}(\vec{\bm{\alpha}}^{*})$, and by the trace function on both sides, we obtain $\sum_{j=1}^{N}\vec{\bm{\beta}}_{j}(\bm{x})=1$. Since the normalized kernel function $K(\vec{\alpha}_{i},\bm{x})\in[0,1]$, each parameter $\vec{\beta}_{j}(\bm{x})=\sum_{i=1}^{N}({\rm K}+\lambda I)_{ij}^{-1}K(\vec{\alpha}_{i},\bm{x})$ naturally belongs to the interval $[d_{j,1},d_{j,2}]$, where $d_{j,1}=\sum_{({\rm K}+\lambda I)_{ij}^{-1}<0}({\rm K}+\lambda I)_{ij}^{-1}$ and $d_{j,2}=\sum_{({\rm K}+\lambda I)_{ij}^{-1}>0}({\rm K}+\lambda I)_{ij}^{-1}$. Finally, the close set $\mathcal{D}_{\beta}=[d_{1,1},d_{1,2}]\times\cdots\times[d_{N,1},d_{N,2}]$. This is a rough estimation to the compact set, and an exactly estimation of $\mathcal{D}_{\beta}$ is provided as the following section.
∎

###### Proof.

### E.3 Estimate the compact domain 𝒟 β subscript 𝒟 𝛽 \mathcal{D}_{\beta}

From the Eq. [62](#A5.E62), we know that $q=1$ suffices to provide a polynomial function approximation in $\vec{\bm{\alpha}}$ to $\langle 0^{n}|U^{\dagger}(\vec{\bm{\alpha}})\rho U(\vec{\bm{\alpha}})|0^{n}\rangle$ within $2^{-n^{2}}$ additive error. This thus gives rise to the kernel function

$$ $\displaystyle\begin{split}{\rm K}(\bm{\alpha},\bm{\alpha}^{\prime})&=\sum_{l=0}^{K}\sum_{1\leq i_{1}<\cdots<i_{q}\leq LR}(\alpha_{i_{1}}\alpha_{i_{1}}^{\prime}+\cdots+\alpha_{i_{q}}\alpha_{i_{q}}^{\prime})^{l}\\ &=\sum_{l=0}^{K}\sum_{1\leq i_{1}\leq LR}(\alpha_{i_{1}}\alpha_{i_{1}}^{\prime})^{l}.\end{split}$ (76) $$

Therefore, each parameter

$$ $\displaystyle\begin{split}\vec{\beta}_{j}(\bm{x})=&\sum_{i=1}^{N}({\rm K}+\lambda I)_{ij}^{-1}K(\vec{\alpha}_{i},\bm{x})\\ =&\sum_{i=1}^{N}({\rm K}+\lambda I)_{ij}^{-1}\sum_{l=0}^{K}\sum_{i_{1}=1}^{LR}(\vec{\alpha}_{i,i_{1}}\bm{x}_{i_{1}})^{l}\\ =&\sum_{i_{1}=1}^{LR}\sum_{l=0}^{K}s(K,j)(\vec{\alpha}_{i,i_{1}}\bm{x}_{i_{1}})^{l}\\ =&\sum_{i_{1}=1}^{LR}h_{j}(\bm{x}_{i_{1}}),\end{split}$ (77) $$

where $s(K,j)=\sum_{i=1}^{N}({\rm K}+\lambda I)_{ij}^{-1}$ and the uni-variable $K$-degree polynomial function $h_{j}(x)=\sum_{l=0}^{K}s(K,j)\vec{\alpha}_{i,i_{1}}^{l}x^{l}$. For each $x_{i_{1}}\in[0,2\pi]$, using the Bayesian optimization algorithm with a suitable kernel (such as Gaussian kernel or polynomial kernel) can provide an $\epsilon_{i_{1}}$-approximations to $\sup_{x_{i_{1}}\in[0,2\pi]}h_{j}(x_{i_{1}})$ and $\inf_{x_{i_{1}}\in[0,2\pi]}h_{j}(x_{i_{1}})$, respectively. The relationship to required computational complexity $T$ is $\epsilon_{i_{1}}=\mathcal{O}(\log T/\sqrt{T})$ []. Let $\mathcal{D}_{\beta}=D_{1}\times D_{2}\times...\times D_{N}$, where each $D_{j}=[D_{j,L},D_{j,R}]$ represents a bounded interval. Repeat such optimization $LR$ times, the range of $\vec{\beta}_{j}(\bm{x})$ can be approximated within $LR\epsilon_{i_{1}}$ error, that is

$$ $\vec{\beta}_{j}(\bm{x})\in\left[\sum_{i_{1}}\inf_{x_{i_{1}}\in[0,2\pi]}h_{j}(x_{i_{1}})-LR\epsilon_{i_{1}},\sum_{i_{1}}\sup_{x_{i_{1}}\in[0,2\pi]}h_{j}(x_{i_{1}})+LR\epsilon_{i_{1}}\right].$ $$

As a result, an approximation to the exact compact set $\mathcal{D}_{\beta}$ is obtained, that is

$$ $\displaystyle\mathcal{D}_{\beta}^{\epsilon}=D_{1}^{\epsilon}\times D^{\epsilon}_{2}\times...\times D_{N}^{\epsilon},$ (78) $$

where $\left|D_{i,R}-D^{\epsilon}_{i,R}\right|\leq 2LR\epsilon_{i}$ (also holds for lower bound) and $\epsilon_{i}=\mathcal{O}(\log T/\sqrt{T})$.

### E.4 Upper bound of the depolarizing strength p 𝑝 p

###### Lemma 6 (Theorem 1 in [ 43 ] ) .

For a Haar-random circuit on any parallel structure $\mathcal{A}$ subject to local Pauli noise with a uniform upper bound on the local noise rate $p$, then we have the lower bound

$$ $\displaystyle\frac{1}{2}\mathbb{E}_{\Phi_{p,\tilde{R}}\sim\mathcal{A}}\left\|\Phi_{p,\tilde{R}}-\frac{I_{n}}{2^{n}}\right\|_{1}\geq\frac{(1-2p)^{2\tilde{R}}}{4\times 30^{\tilde{R}}}.$ (79) $$

using the above lemma, we immediately obtain the following statement.

###### Lemma 7 .

If $\tilde{R}\leq\log(n)$ and the local noise rate $p\leq\frac{1}{2}(1-e^{-\epsilon})$, for each $\Phi_{p,\tilde{R}}\sim\mathcal{A}$, there exists a pure state $|\Psi_{i}\rangle$ such that

$$ $\displaystyle\mathbb{E}_{\Phi_{p,\tilde{R}}\sim\mathcal{A}}\langle\Psi_{i}|\Phi_{p,\tilde{R}}|\Psi_{i}\rangle\geq\frac{1}{4n^{\epsilon+1.7}}+\frac{1}{2^{n}}.$ (80) $$

###### Proof.

According to the property of trace distance [], one obtains

$$ $\displaystyle\mathbb{E}_{\Phi_{p,\tilde{R}}\sim\mathcal{A}}\max\limits_{M=|\Psi\rangle\langle\Psi|\in\mathbb{H}(2^{n})}{\rm Tr}\left(M(\Phi_{p,\tilde{R}}-I_{n}/2^{n})\right)=\mathbb{E}_{\Phi_{p,\tilde{R}}\sim\mathcal{A}}\frac{1}{2}\left\|\Phi_{p,\tilde{R}}-\frac{I_{n}}{2^{n}}\right\|_{1}\geq\frac{(1-2p)^{2\tilde{R}}}{4\times 30^{\tilde{R}}},$ (81) $$

where $M\leq I$ represents a projector in the Hilbert space. Let $\tilde{R}\leq\log(n)$ and $p\leq\frac{1}{2}(1-e^{-\epsilon})$, we immediately obtain

$$ $\displaystyle\mathbb{E}_{\Phi_{p,\tilde{R}}\sim\mathcal{A}}\langle\Psi_{i}|\Phi_{p,\tilde{R}}|\Psi_{i}\rangle\geq\frac{1}{4n^{\epsilon+1.7}}+\frac{1}{2^{n}},$ (82) $$

where $|\Psi_{i}\rangle=\arg\max\limits_{M=|\Psi_{i}\rangle\langle\Psi_{i}|\in\mathbb{H}(2^{n})}{\rm Tr}\left(M(\Phi_{p,\tilde{R}}-I_{n}/2^{n})\right)$.
∎

###### Lemma 6 (Theorem 1 in [ 43 ] ) .

###### Lemma 7 .

###### Proof.

### E.5 Proof of Lemma 1

###### Proof.

According to the assumption, the relationship

$$ $\displaystyle\begin{split}\epsilon&\geq\max\limits_{\vec{\bm{q}},M(\vec{\bm{\beta}})}\left|\sum\limits_{i=1}^{N}q_{i}{\rm Tr}\left(M(\vec{\bm{\beta}})(|\Psi_{i}\rangle\langle\Psi_{i}|-\Phi_{p,\tilde{R}})\right)\right|\\ &=\max\limits_{\vec{\bm{q}},M(\vec{\bm{\beta}})}\left|\sum\limits_{i=1}^{N}q_{i}\left[{\rm Tr}\left(M(\vec{\bm{\beta}})(|\Psi_{i}\rangle\langle\Psi_{i}|-\sigma)\right)-{\rm Tr}\left(M(\vec{\bm{\beta}})(\Phi_{p,\tilde{R}}-\sigma)\right)\right]\right|\end{split}$ (83) $$

holds, where maximal entangled state $\sigma=I/d$ and $M(\vec{\bm{\beta}})$ is defined as Eq. [10](#S4.E10). Randomly choose an index $t\in[N]$, and let

$$ $\displaystyle M_{t}=\arg\max\limits_{M=V|0\rangle\langle 0|V^{\dagger}}{\rm Tr}\left(M(|\Psi_{t}\rangle\langle\Psi_{t}|-\sigma)\right),$ (84) $$

where $V\in\mathcal{U}_{\mathcal{A}}(R)$.
Based on the intrinsic-connection property in SQNN, there exists a unit vector $\vec{\bm{\beta}}^{(t)}$ such that

$$ $\displaystyle\left|{\rm Tr}\left(M_{t}(|\Psi_{t}\rangle\langle\Psi_{t}|-\sigma)\right)-{\rm Tr}\left(M(\vec{\bm{\beta}}^{(t)})(|\Psi_{t}\rangle\langle\Psi_{t}|-\sigma)\right)\right|\leq\epsilon$ (85) $$

with the number of samplings $N=LRn^{2}\epsilon^{-2}$.
Note that there will always exist such $t\in[N]$ that satisfies the above inequality, otherwise the intrinsic-connection property will be violated.
Then set the probability distribution $p_{t}=1-(N-1)/d$ and $p_{j}=1/d$ ($j\neq t$). As a result, Eq. [83](#A5.E83) can be further lower bounded by

$$ $\displaystyle\left|\left(1-\frac{N-1}{d}\right){\rm Tr}\left(M(\vec{\bm{\beta}}^{(t)})(|\Psi_{t}\rangle\langle\Psi_{t}|-\sigma)\right)+\frac{1}{d}\sum\limits_{j\neq t}{\rm Tr}\left(M(\vec{\bm{\beta}}^{(t)})(|\Psi_{j}\rangle\langle\Psi_{j}|-\sigma)\right)-{\rm Tr}\left(M(\vec{\bm{\beta}}^{(t)})(\Phi_{p,\tilde{R}}-\sigma)\right)\right|.$ (86) $$

Since $|\Psi_{t}\rangle$ is generated by a $R$-depth quantum circuit $U_{t}\in\mathcal{U}_{\mathcal{A}}(R)$, then $C_{\epsilon}(\Psi_{t})\leq LR$ which implies

$$ $\displaystyle{\rm Tr}\left[M_{t}\left(|\Psi_{t}\rangle\langle\Psi_{t}|-\frac{I}{d}\right)\right]\geq 1-\frac{1}{d}-\epsilon,$ (87) $$

then the relationship

$$ $\displaystyle{\rm Tr}\left[M(\vec{\bm{\beta}}^{(t)})\left(|\Psi_{t}\rangle\langle\Psi_{t}|-\frac{I}{d}\right)\right]\geq{\rm Tr}\left[M_{t}\left(|\Psi_{t}\rangle\langle\Psi_{t}|-\frac{I}{d}\right)\right]-\epsilon\geq 1-\frac{1}{d}-2\epsilon$ (88) $$

holds. Therefore, $\left(1-\frac{N-1}{d}\right){\rm Tr}\left(M(\vec{\bm{\beta}}^{(t)})(|\Psi_{t}\rangle\langle\Psi_{t}|-\sigma)\right)\geq(1-\frac{N-1}{d})(1-\frac{1}{d}-2\epsilon)$, and considering

$$ $\frac{1}{d}\sum\limits_{j\neq t}{\rm Tr}\left(M(\vec{\bm{\beta}}^{(t)})(|\Psi_{j}\rangle\langle\Psi_{j}|-\sigma)\right)\geq\frac{(N-1)(-1+N)}{d},$ $$

as a result,

$$ $\displaystyle\begin{split}{\rm Tr}\left(M(\vec{\bm{\beta}}^{(t)})(\Phi_{p,\tilde{R}}-\sigma)\right)&\geq\left(1-\frac{N-1}{d}\right)\left(1-\frac{1}{d}-2\epsilon\right)-\frac{(N-1)^{2}}{d}-\epsilon\\ &=1-\frac{1}{d}-3\epsilon-\frac{N-1}{d}\left(1-\frac{1}{d}-2\epsilon+(N-1)\right).\end{split}$ (89) $$

Note that $N=LRn^{2}\epsilon^{-2}$, $d=2^{n}$, therefore

$$ $\displaystyle\frac{N-1}{d}\left(1-\frac{1}{d}-2\epsilon+(N-1)\right)=\frac{{\rm poly(n)}}{2^{n}}\left(1-\frac{1}{2^{n}}-2\epsilon+{\rm poly}(n)\right)<\mathcal{O}(\epsilon)$ (90) $$

for large $n\in\mathbb{Z}_{>0}$. Finally,

$$ $\displaystyle\begin{split}\max\limits_{M(\vec{\bm{\beta}})}\left|{\rm Tr}\left(M(\vec{\bm{\beta}})(\Phi_{p,\tilde{R}}-I_{n}/2^{n})\right)\right|&\geq\max\limits_{M=V|0^{n}\rangle\langle 0^{n}|V^{\dagger}}\left|{\rm Tr}\left(M(\Phi_{p,\tilde{R}}-I_{n}/2^{n})\right)\right|\\ &\geq{\rm Tr}\left(M_{t}(\Phi_{p,\tilde{R}}-I_{n}/2^{n})\right)\\ &\geq{\rm Tr}\left(M(\vec{\bm{\beta}}^{(t)})(\Phi_{p,\tilde{R}}-I_{n}/2^{n})\right)-\epsilon\\ &\geq 1-\frac{1}{d}-\mathcal{O}(\epsilon)\end{split}$ (91) $$

equivalently, $C_{\epsilon}(\Phi_{p,\tilde{R}})\leq C^{\rm lim,\mathcal{A}}_{\epsilon}(\Phi_{p,\tilde{R}})\leq LR$.
∎

###### Lemma 8 (Gentle Measurement Lemma [ 86 ] ) .

Let $\rho\in\mathbb{H}^{2^{n}\times 2^{n}}$ be a density matrix and $O\leq M\leq I$ a measurement operator for $M\in\mathbb{H}^{2^{n}\times 2^{n}}$ such that ${\rm Tr}(M\rho)\geq 1-\epsilon$. Then $\|\rho-\sqrt{M}\rho\sqrt{M}\|_{1}\leq 2\sqrt{\epsilon}$.

###### Remark 5 .

Note that $M\rho M$ above is not necessarily normalized.

###### Proof of corollary 1 .

Finally, we show how to generalize above results to corollary [1](#Thmcorollary1). Since

$$ $\displaystyle\max\limits_{M(\vec{\bm{\beta}})}\left|{\rm Tr}\left(M(\vec{\bm{\beta}})(\Phi_{p,\tilde{R}}-I_{n}/2^{n})\right)\right|\geq 1-\frac{1}{d}-\mathcal{O}(\epsilon),$ (92) $$

then the relationship ${\rm Tr}(M(\vec{\beta}^{*})\Phi_{p,\tilde{R}})\geq 1-\epsilon$ holds, where $M(\vec{\bm{\beta}}^{*})=\arg\max_{\vec{\bm{q}},M(\vec{\bm{\beta}})}\mathcal{L}_{R}$. Then using the Gentle Measurement Lemma,
the estimator $\hat{\Phi}=\sqrt{M(\vec{\bm{\beta}}^{*})}\Phi_{p,\tilde{R}}\sqrt{M(\vec{\bm{\beta}}^{*})}$ provides an approximation to $\Phi_{p,\tilde{R}}$ within $2\sqrt{\epsilon}$ trace distance.
∎

###### Proof.

###### Lemma 8 (Gentle Measurement Lemma [ 86 ] ) .

###### Remark 5 .

###### Proof of corollary 1 .

### E.6 Proof of Lemma 2

###### Proof.

The proof of Lemma [2](#Thmlemma2) depends on the intrinsic-property of the SQNN model. Let $M_{\rm opt}$ represent an observable

$$ $\displaystyle M_{\rm opt}=\arg\max_{M=V|0^{n}\rangle\langle 0^{n}|V^{\dagger},V\in\mathcal{U}_{\mathcal{A}}(R)}\left|{\rm Tr}\left(M(\Phi_{p,\tilde{R}}-I_{n}/2^{n})\right)\right|.$ (93) $$

Given the SQNN set $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)=\{|\Psi_{i}\rangle\}_{i=1}^{N}$ with $N=LRn^{2}\epsilon^{-2}$, the intrinsic-connection property promises that there exists a vector $\vec{\bm{\beta}}_{\rm opt}$ such that

$$ $\displaystyle\left|\sum\limits_{i=1}^{N}\beta^{\rm opt}_{i}\langle\Psi_{i}|\rho|\Psi_{i}\rangle-{\rm Tr}\left(M_{\rm opt}\rho\right)\right|\leq\epsilon$ (94) $$

for any $n$-qubit density matrix $\rho$.
According to the assumption in Lemma [2](#Thmlemma2),

$$ $\displaystyle\begin{split}\epsilon+\tilde{\epsilon}&<\min\limits_{\vec{\bm{\beta}}}\left|\mathbb{E}_{|\Psi_{i}\rangle\sim(\mathcal{S}_{\rm QNN},\vec{\bm{q}})}\left[{\rm Tr}(M(\vec{\bm{\beta}})(|\Psi_{i}\rangle\langle\Psi_{i}|-\Phi_{p,\tilde{R}}))\right]\right|\\ &\leq\left|\mathbb{E}_{|\Psi_{i}\rangle\sim(\mathcal{S}_{\rm QNN},\vec{\bm{q}})}\left[{\rm Tr}(M(\vec{\bm{\beta}}_{\rm opt})(|\Psi_{i}\rangle\langle\Psi_{i}|-\Phi_{p,\tilde{R}}))\right]\right|\\ &\leq\left|\mathbb{E}_{|\Psi_{i}\rangle\sim(\mathcal{S}_{\rm QNN},\vec{\bm{q}})}\left[{\rm Tr}(M_{\rm opt}(|\Psi_{i}\rangle\langle\Psi_{i}|-\Phi_{p,\tilde{R}}))\right]+\epsilon\right|\\ &=\left|\mathbb{E}_{|\Psi_{i}\rangle\sim(\mathcal{S}_{\rm QNN},\vec{\bm{q}})}\left[{\rm Tr}(M_{\rm opt}(|\Psi_{i}\rangle\langle\Psi_{i}|-I_{n}/2^{n}))\right]-{\rm Tr}(M_{\rm opt}(\Phi_{p,\tilde{R}}-I_{n}/2^{n}))+\epsilon\right|\\ &\leq 1-\frac{1}{2^{n}}-{\rm Tr}(M_{\rm opt}(\Phi_{p,\tilde{R}}-I_{n}/2^{n}))+\epsilon,\end{split}$ (95) $$

where the third line comes from the intrinsic-connection property, the last inequality comes from $\sum_{i}q_{i}=1$ and $\left|\langle\Psi_{i}|\Psi_{j}\rangle\right|^{2}\leq 1$. As a result,

$$ $\displaystyle{\rm Tr}(M_{\rm opt}(\Phi_{p,\tilde{R}}-I_{n}/2^{n}))<1-\frac{1}{2^{n}}-\tilde{\epsilon}.$ (96) $$

∎

###### Proof.

### E.7 More discussions on the learning lower bound

###### Lemma 9 .

Let $\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)=\{|\Psi_{i}\rangle\}_{i=1}^{N}$ be a quantum neural network state set with $N=LRn^{4}$. If the relationship

$$ $\displaystyle 1/n+\eta_{u}\geq\max_{M=V|0\rangle\langle 0|V^{\dagger}}\mathcal{L}_{R}(\vec{\bm{q}},M)\geq\Omega(1/n),$ (97) $$

holds, where $V\in\mathcal{U}_{\mathcal{A}}$
and $\eta_{u}\leq 1/\sqrt{n}$, then with probability at least $2/3$, $\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle 0^{n}|)$ cannot be approximated by any $U|0^{n}\rangle\langle 0^{n}|U^{\dagger}$ within $\Omega(1/n)$-LS error for $U\in\mathcal{U_{A}}(R)$.

We first introduce the following lemma to support our proof.

###### Lemma 10 .

Suppose two random variables $0<m_{1}\leq a_{i}\leq M_{1}$ and $0<m_{2}\leq b_{i}\leq M_{2}$ for $i\in[N]$, then the relationship

$$ $\displaystyle\left(\sum\limits_{i=1}^{N}a_{i}^{2}\right)\left(\sum\limits_{i=1}^{N}b_{i}^{2}\right)\leq\frac{1}{4}\left(\sqrt{\frac{m_{1}m_{2}}{M_{1}M_{2}}}+\sqrt{\frac{M_{1}M_{2}}{m_{1}m_{2}}}\right)^{2}\left(\sum\limits_{i=1}^{N}a_{i}b_{i}\right)^{2}$ (98) $$

holds.

###### Proof.

Since $0<m_{1}\leq a_{i}\leq M_{1}$ and $0<m_{2}\leq b_{i}\leq M_{2}$ for $i\in[N]$, we have

$$ $\displaystyle\frac{m_{1}}{M_{2}}\leq\frac{a_{i}}{b_{i}}\leq\frac{M_{1}}{m_{2}}.$ (99) $$

Then, the relationship

$$ $\displaystyle\left(\frac{a_{i}}{b_{i}}-\frac{m_{1}}{M_{2}}\right)\left(\frac{a_{i}}{b_{i}}-\frac{M_{1}}{m_{2}}\right)\leq 0$ (100) $$

holds, and equivalently,

$$ $\displaystyle a_{i}^{2}-\left(\frac{m_{1}}{M_{2}}+\frac{M_{1}}{m_{2}}\right)a_{i}b_{i}+\frac{m_{1}M_{1}}{m_{2}M_{2}}b_{i}^{2}\leq 0.$ (101) $$

Summation the index $i\in[N]$,

$$ $\displaystyle\sum\limits_{i=1}^{N}a_{i}^{2}+\frac{m_{1}M_{1}}{m_{2}M_{2}}\sum\limits_{i=1}^{N}b_{i}^{2}\leq\left(\frac{m_{1}}{M_{2}}+\frac{M_{1}}{m_{2}}\right)\sum\limits_{i=1}^{N}a_{i}b_{i},$ (102) $$

then consider the LHS is lower bounded by $2\sqrt{\frac{m_{1}M_{1}}{m_{2}M_{2}}\left(\sum\limits_{i=1}^{N}a_{i}^{2}\right)\left(\sum\limits_{i=1}^{N}b_{i}^{2}\right)}$, and Eq. [98](#A5.E98) thus holds.
∎

###### Proof of Lemma 9 .

Denote the function

$$ $\displaystyle\bm{g}(|\Psi_{\alpha}\rangle\langle\Psi_{\alpha}|,\Phi_{p,\tilde{R}})={\rm Tr}\left(M\left(|\Psi_{\alpha}\rangle\langle\Psi_{\alpha}|-\Phi_{p,\tilde{R}}\right)\right),$ (103) $$

where $M=\arg\max_{M=V|0^{n}\rangle\langle 0^{n}|V^{\dagger}}\mathcal{L}_{R}(\vec{\bm{q}},M)$.
In the QML procedure, all the function $\bm{g}$ are estimated from polynomial time quantum measurements, and the estimated $\bm{g}$ is thus at least $1/\rm poly(n)$. This proof is valid under a reasonable assumption $\bm{g}\geq 15/N=15/(LRn^{4})$.

According to the condition in Lemma, one obtains

$$ $\displaystyle\begin{split}\mathbb{E}_{|\Psi_{\bm{\alpha}}\rangle\sim(\mathcal{S}_{\rm QNN},\vec{\bm{q}})}\left[\bm{g}(|\Psi_{\alpha}\rangle\langle\Psi_{\alpha}|,\Phi_{p,\tilde{R}})\right]=\max_{M}\mathcal{L}_{R}(\vec{\bm{q}},M)\geq\Omega(1/n),\end{split}$ (104) $$

where $|\Psi_{\bm{\alpha}}\rangle\sim\mathcal{S}_{\rm QNN}$ represents
the SQNN state $|\Psi_{\bm{\alpha}}\rangle$ is uniformly sampled from $\mathcal{S}_{\rm QNN}$,
$\Phi_{p,\tilde{R}}$ denotes the abbreviation of $\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle 0^{n}|)$. Using the Chebyshev inequality on the $\mathcal{U}_{\mathcal{A}}$, the relationship

$$ $\displaystyle{\rm Pr}\left[\left|\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})-\mathbb{E}_{|\Psi_{\bm{\alpha}}\rangle=U|0^{n}\rangle,U\sim\mathcal{U}_{\mathcal{A}}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right|\geq\epsilon_{1}\right]\leq\frac{{\rm Var}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]}{\epsilon_{1}^{2}}$ (105) $$

holds, where the variance

$$ $\displaystyle{\rm Var}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]=\mathbb{E}_{|\Psi_{\bm{\alpha}}\rangle=U|0^{n}\rangle,U\sim\mathcal{U}_{\mathcal{A}}}\left[\bm{g}^{2}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]-\mathbb{E}_{|\Psi_{\bm{\alpha}}\rangle=U|0^{n}\rangle,U\sim\mathcal{U}_{\mathcal{A}}}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]^{2}.$ (106) $$

After that, the Hoeffding inequality is used to link the relationship between $\mathcal{S}_{\rm QNN}$ and $\mathcal{U}_{\mathcal{A}}$ in terms of mean-value function and variance function, that is $\left|\mathbb{E}_{S_{\rm QNN}}[\bm{g}^{k}]-\mathbb{E}_{\mathcal{U}_{\mathcal{A}}}[\bm{g}^{k}]\right|\leq t$ with probability at least $1-e^{-N^{2}t}$ for $k=1,2$. As a result,

$$ $\displaystyle{\rm Var}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]\leq\mathbb{E}_{S_{\rm QNN}}[\bm{g}^{2}]+t-\left(\mathbb{E}_{S_{\rm QNN}}[\bm{g}]-t\right)^{2}$ (107) $$

holds with probability at least $(1-e^{-N^{2}t})^{2}$. Let $t=1/n$ and $N=LRn^{4}$, the success probability $\leq(1-e^{-(LR)^{2}n^{7}})^{2}$
Then taking $a_{i}=\bm{g}(\Psi_{i},\Phi_{p,\tilde{R}})$, $b_{i}=1$, $m_{1}=\min(g)$, and $M_{1}=m_{2}=M_{2}=1$ into Lemma [98](#A5.E98), one obtains

$$ $\displaystyle\mathbb{E}_{S_{\rm QNN}}[\bm{g}^{2}]\leq\frac{1}{4N}\left(\sqrt{\min(\bm{g})}+\frac{1}{\sqrt{\min(\bm{g})}}\right)^{2}\left(\mathbb{E}_{S_{\rm QNN}}[\bm{g}]\right)^{2}.$ (108) $$

According to the assumption $\bm{g}\geq 15/(N)=15/((LR)n^{4})$ and Eq. [104](#A5.E104), then one obtains

$$ $\displaystyle{\rm Var}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]\leq\frac{1}{60}\left(\frac{1}{n}+\eta\right)^{2}+t-\left(\frac{1}{n}-t\right)^{2}.$ (109) $$

Let $\eta\leq 1/\sqrt{n}$, the variance function can be upper bounded by $1/(10n)$. Therefore,

$$ $\displaystyle\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})\leq\mathbb{E}_{\mathcal{U}_{\mathcal{A}}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})-\epsilon_{1}$ (110) $$

with probability at most $\frac{1}{10n}\epsilon_{1}^{-2}$. Meanwhile, Hoeffding inequality suggests that $\mathbb{E}_{\mathcal{U}_{\mathcal{A}}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\leq\mathbb{E}_{\mathcal{S}_{\rm QNN}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})+t$ with nearly unit probability, and one obtains

$$ $\displaystyle\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})\leq\mathbb{E}_{\mathcal{S}_{\rm QNN}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})+t-\epsilon_{1}\leq\frac{1}{n}+\eta+t-\epsilon_{1}$ (111) $$

with probability at most $\frac{1}{10n}\epsilon_{1}^{-2}$. Let $\epsilon_{1}=\sqrt{3/(10n)}$, we finally obtain

$$ $\displaystyle\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})\leq\mathcal{O}(1/\sqrt{n})$ (112) $$

with probability $\leq 1/3$. Equivalently, for any $|\Psi_{i}\rangle$ generated from $\mathcal{U}_{\mathcal{A}}$, the relationship

$$ $\displaystyle\frac{1}{2}\||\Psi_{i}\rangle\langle\Psi_{i}|-\Phi_{p,\tilde{R}}\|_{1}\geq\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})>\mathcal{O}(1/\sqrt{n})$ (113) $$

with the probability $>2/3$. This immediately implies $\langle\Psi_{i}|\Phi_{p,\tilde{R}}|\Psi_{i}\rangle<1-\mathcal{O}(1/n)$ for any $|\Psi_{i}\rangle=U|0^{n}\rangle$ where $U\in\mathcal{U}_{\mathcal{A}}$.

∎

###### Lemma 9 .

###### Lemma 10 .

###### Proof.

###### Proof of Lemma 9 .

### E.8 Proof of theorem 4

We need following two lemmas to support our proof.

###### Lemma 11 (Lemma 5.1 in [ 101 ] ) .

Pick faliure probability $\delta\in(0,1)$ and set $\kappa_{t}=2\log(\left|\mathcal{D}_{\rm domain}\right|\pi_{t}/\delta)$, where $\sum_{t\geq 1}\pi_{t}^{-1}=1$ and $\pi_{t}>0$. Then

$$ $\displaystyle\left|\mathcal{L}(\bm{z})-\mu_{t-1}(\bm{z})\right|\leq\kappa_{t}^{1/2}\sigma_{t-1}(\bm{z})$ (114) $$

holds for any $t\geq 1$ and $\bm{z}\in\mathcal{D}_{\rm domain}$.

###### Lemma 12 (Lemma 5.4 in [ 101 ] ) .

Pick failure probability $\delta\in(0,1)$ and let $\kappa_{t}$ be defined as in Lemma [11](#Thmlemma11). Then the following holds with probability $\geq 1-\delta$:

$$ $\displaystyle\sum\limits_{t=1}^{T}4\kappa_{t}\sigma^{2}_{t-1}(\bm{z}_{t})\leq\kappa_{T}\gamma_{T},$ (115) $$

where $\gamma_{T}=\max_{A\in\mathcal{D}_{\rm domain}}\frac{1}{2}\log\left|I+\sigma^{-2}K_{A}\right|$, and $K_{A}$ represents the used covariance matrix in Bayesian optimization.

###### Proof.

We first consider the continuity of the loss function $\mathcal{L}(\bm{z})$. Considering $\sum_{i=1}^{N}\bm{\beta}_{i}=1$, the gradient function can be upper bounded by

$$ $\displaystyle\left|\frac{\partial\mathcal{L}(\bm{z})}{\partial\bm{p}_{j}}\right|=\left|\sum\limits_{i=1}^{N}\bm{\beta}_{i}\left(|\langle\Psi_{i}|\Psi_{j}\rangle|^{2}-\langle\Psi_{i}|\rho|\Psi_{i}\rangle\right)\right|\leq\left|\sum\limits_{i=1}^{N}\bm{\beta}_{i}\right|=1$ (116) $$

($\left|\partial\mathcal{L}(\bm{z})/\partial\bm{\beta}_{j}\right|$ has the same upper bound), where the inequality comes from $|\langle\Psi_{i}|\Psi_{j}\rangle|^{2}-\langle\Psi_{i}|\rho|\Psi_{i}\rangle<1$. Therefore, the relationship

$$ $\displaystyle\left|\mathcal{L}(\bm{z})-\mathcal{L}(\bm{z}^{\prime})\right|\leq\left|\bm{z}-\bm{z}^{\prime}\right|_{1}$ (117) $$

holds for any $\bm{z},\bm{z}^{\prime}\in\mathcal{D}_{\rm domain}$. Now let us choose a discretization $\mathcal{D}^{t}_{\rm domain}$ of size $(\tau_{t})^{N}$ such that for all $\bm{z}\in\mathcal{D}_{\rm domain}$,

$$ $\displaystyle\|\bm{z}-[\bm{z}]_{t}\|_{1}\leq N/\tau_{t},$ (118) $$

where $[\bm{z}]_{t}$ represents the closest point in discretization on $\mathcal{D}^{t}_{\rm domain}$ to $\bm{z}$. Combine Eqs. [117](#A5.E117)-[118](#A5.E118), one obtains

$$ $\displaystyle\left|\mathcal{L}(\bm{z})-\mathcal{L}([\bm{z}]_{t})\right|\leq N\tau_{t}^{-1}=t^{-2},$ (119) $$

where the last inequality comes from $\tau_{t}=t^{2}N$, furthermore, $\left|\mathcal{D}^{t}_{\rm domain}\right|=(t^{2}N)^{N}$.

Using Lemma [11](#Thmlemma11), we know that

$$ $\displaystyle\kappa_{t}=2\log(\left|\mathcal{D}_{\rm domain}\right|a_{t}/\delta)$ (120) $$

enables the relationship

$$ $\displaystyle\left|\mathcal{L}(\bm{z})-\mu_{t-1}(\bm{z})\right|\leq\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z})$ (121) $$

holds with probability at least $1-\delta$, where $a_{t}>0$ and $\sum_{t\geq 1}a_{t}^{-1}=1$. A common selection is $a_{t}=\pi t^{2}/6$. Taking $\left|\mathcal{D}^{t}_{\rm domain}\right|=(t^{2}N)^{N}$ into $\kappa_{t}$ (Eq. [120](#A5.E120)), one obtains

$$ $\displaystyle\kappa_{t}=2\log\left((t^{2}N)^{N}a_{t}/\delta\right).$ (122) $$

Combine Eq. [119](#A5.E119) and [121](#A5.E121), we have

$$ $\displaystyle\left|\mathcal{L}(\bm{z}^{*})-\mu_{t-1}([\bm{z}^{*}]_{t})\right|\leq\left|\mathcal{L}(\bm{z}^{*})-\mathcal{L}([\bm{z}^{*}]_{t})\right|+\left|\mathcal{L}([\bm{z}^{*}]_{t})-\mu_{t-1}([\bm{z}^{*}]_{t})\right|\leq t^{-2}+\sqrt{\kappa_{t}}\sigma_{t-1}([\bm{z}^{*}]_{t})$ (123) $$

for any $t\geq 1$, where $\bm{z}^{*}=\arg\max_{\bm{z}\in\mathcal{D}_{\rm domain}}\mathcal{L}(\bm{z})$. Now we connect the relationship between above inequality to the regret bound.

By the definition of $\bm{z}^{(t)}$ (maximizing the $\mathcal{A}_{\rm UCB}(\bm{z})$ in the $t$-th step): $\mu_{t-1}(\bm{z}^{(t)})+\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z}^{(t)})\geq\mu_{t-1}([\bm{z}^{*}]_{t})+\sqrt{\kappa_{t}}\sigma_{t-1}([\bm{z}^{*}]_{t})$. Also, by Eq. [123](#A5.E123), we have $\mathcal{L}(\bm{z}^{*})\leq\mu_{t-1}([\bm{z}^{*}]_{t})+\sqrt{\kappa_{t}}\sigma_{t-1}([\bm{z}^{*}]_{t})+1/t^{2}$. Therefore, instantaneous regret

$$ $\displaystyle\begin{split}r_{t}&=\mathcal{L}(\bm{z}^{*})-\mathcal{L}(\bm{z}^{(t)})\\ &\leq\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z}^{(t)})+1/t^{2}+\mu_{t-1}(\bm{z}^{(t)})-\mathcal{L}(\bm{z}^{(t)})\\ &\leq 2\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z}^{(t)})+1/t^{2},\end{split}$ $$

where the last inequality comes from Eq. [121](#A5.E121).
Using Lemma [12](#Thmlemma12), $\sum_{t=1}^{T}4\kappa_{t}\sigma_{t-1}(\bm{z}_{t})\leq\kappa_{T}\gamma_{T}$, where

$$ $\gamma_{T}=\max_{A\in\mathcal{D}_{\rm domain}}\frac{1}{2}\log\left|I+\sigma^{-2}K_{A}\right|,$ $$

and $K_{A}$ represents the used covariance matrix in ${\rm BMaxS}(\Phi_{p,\tilde{R}},\mathcal{S}_{\rm QNN}(R,\mathcal{A},N),T)$. In the linear regression case, $K_{A}$ can be selected as the polynomial kernel function, and $\gamma_{T}=\mathcal{O}(N\log(T))$ []. Furthermore, using the Cauchy-Schwartz inequality to $\sum_{t=1}^{T}4\kappa_{t}\sigma_{t-1}^{2}(\bm{z}_{t})\leq\kappa_{T}\gamma_{T}$, one obtains $\sum_{t=1}^{T}2\kappa_{t}^{1/2}\sigma_{t-1}(\bm{z}_{t})\leq\sqrt{T\kappa_{T}\gamma_{T}}$

Finally, we have the result

$$ $\displaystyle\begin{split}R_{T}&=\frac{1}{T}\sum\limits_{t=1}^{T}r_{t}\\ &\leq\frac{1}{T}\sum\limits_{t=1}^{T}2\kappa_{t}^{1/2}\sigma_{t-1}(\bm{z}_{t})+\frac{\pi^{2}}{6T}\\ &\leq\sqrt{\frac{\kappa_{T}\gamma_{T}}{T}}+\frac{\pi^{2}}{6T}\\ &=\mathcal{O}\left(\sqrt{\frac{2N^{2}\log(T^{2}N)\log(T)+2N\log(T^{2}\pi^{2}/(6\delta))\log(T)}{T}}\right)\\ &\leq\mathcal{O}\left(\sqrt{\frac{4N^{2}\log^{2}T+2N\log T\log(\pi^{2}/(6\delta))}{T}}\right),\end{split}$ (124) $$

where the first inequality results from $\sum_{t\geq 1}t^{-2}=\pi^{2}/6$ and the last inequality comes from $N\leq T$.
∎

###### Lemma 11 (Lemma 5.1 in [ 101 ] ) .

###### Lemma 12 (Lemma 5.4 in [ 101 ] ) .

###### Proof.

## Appendix F Review of Shadow tomography

In quantum computation, the basic operators are the Pauli operators $\{I,\sigma^{x},\sigma^{y},\sigma^{z}\}$ which provide a basis for the density operators of a single qubit as well as for the unitaries that can be applied to them. For an $n$-qubit case, one can construct the Pauli group according to

$$ $\mathbf{P}_{n}=\{e^{i\alpha\pi/2}\sigma^{j_{1}}\otimes...\otimes\sigma^{j_{n}}|j_{k}\in\{I,x,y,z\},1\leq k\leq n\},$ $$

where $e^{i\alpha\pi/2}\in\{0,\pm 1,\pm i\}$ is a global phase. Then the Clifford group $\mathbf{Cl}(2^{n})$ is defined as the group of unitaries that normalize the Pauli group:

$$ $\mathbf{Cl}(2^{n})=\left\{U|U\mathbf{P}^{(1)}U^{\dagger}=\mathbf{P}^{(2)},\left(\mathbf{P}^{(1)},\mathbf{P}^{(2)}\in\mathbf{P}_{n}\right)\right\}.$ $$

The $n$-qubit Clifford gates are then defined as elements in the Clifford group $\mathbf{Cl}(2^{n})$, and these Clifford gates compose the Clifford circuit.

Randomly sampling Clifford circuit $U$ can reproduce the first $3$ moments of the full Clifford group endowed with the Haar measure $\mathbf{d}\mu(U)$ which is the unique left- and right- invariant measure such that

$$ $\int_{\mathbf{Cl}(2^{n})}\mathbf{d}\mu(U)f(U)=\int\mathbf{d}\mu(U)f(VU)=\int\mathbf{d}\mu(U)f(UV)$ $$

for any $f(U)$ and $V\in\mathbf{Cl}(2^{n})$. Using this property, one can sample Clifford circuits $U\in\mathbf{Cl}(2^{n})$ with the probability ${\rm{Pr}}(U)$, and the corresponding expectation ${\rm{E}}_{U\in\mathbf{Cl}(2^{n})}[\left(U\rho U^{\dagger}\right)^{\otimes t}]$ can be expressed as

$$ $\sum\limits_{U\in\mathbf{Cl}(2^{n})}{\rm{Pr}}(U)\left(U\rho U^{\dagger}\right)^{\otimes t}=\int_{\mathbf{Cl}(2^{n})}\mathbf{d}\mu(U)\left(U\rho U^{\dagger}\right)^{\otimes t},$ $$

for any $n$-qubit density matrix $\rho$ and $t=1,2,3$, where ${\rm{Pr}}(U)$ indicates the probability on sampling $U$. The right hand side of the above equation can be evaluated explicitly by representation theory, this thus yields a closed-form expression for sampling from a Clifford group.

To extract meaningful information from an $n$-qubit unknown quantum state $\rho$, the shadow tomography technique was proposed by H. Huang et al.[]. The Clifford sampling is implemented by repeatedly performing a simple measurement procedure: apply a random unitary $U\in\mathbf{Cl}(2^{n})$ to rotate the state $\rho$ and perform a $\sigma^{z}$-basis measurement. The number of repeating times of this procedure is defined as the Clifford sampling complexity. On receiving the $n$-bit measurement outcome $|b\rangle\in\{0,1\}^{n}$, according to the Gottesman-Knill theorem [], we can efficiently store an classical description of $U^{\dagger}|b\rangle\langle b|U$ in the classical memory. This classical description encodes meaningful information of the state $\rho$ from a particular angle, and it is thus instructive to view the average mapping from $\rho$ to its classical snapshot $U^{\dagger}|b\rangle\langle b|U$ as a quantum channel:

$$ $\displaystyle\mathcal{M}(\rho)=\textmd{E}_{U\in\mathbf{Cl}(2^{n})}\left(\textmd{E}_{b\in\{0,1\}^{n}}[U^{\dagger}|b\rangle\langle b|U]\right),$ (125) $$

where the quantum channel $\mathcal{M}$ depends on the ensemble of unitary transformation, and the quantum channel $\mathcal{M}$ can be further expressed as

$$ $\displaystyle\mathcal{M}(\rho)=\textmd{E}_{U\in\mathbf{Cl}(2^{n})}\sum\limits_{\widehat{b}\in\{0,1\}^{n}}\langle\widehat{b}|U\rho U^{\dagger}|\widehat{b}\rangle U^{\dagger}|\widehat{b}\rangle\langle\widehat{b}|U=\frac{\rho+{\rm{Tr}}(\rho)I}{(2^{n}+1)2^{n}},$ (126) $$

where $I$ indicates the $2^{n}\times 2^{n}$ identity matrix.
Therefore the inverse of quantum channel $\mathcal{M}^{-1}(\rho)=(2^{n}+1)\rho-I$, and an estimation of $\rho$ is defined as

$$ $\widehat{\rho}=\mathcal{M}^{-1}\left(U^{\dagger}|b\rangle\langle b|U\right).$ $$

Repeat this procedure $M$ times results in an array of Clifford samples of $\rho$:

$$ $\displaystyle S(\rho;M)=\left\{\widehat{\rho}_{1}=\mathcal{M}^{-1}\left(U_{1}^{\dagger}|b_{1}\rangle\langle b_{1}|U_{1}\right),...,\widehat{\rho}_{M}=\mathcal{M}^{-1}\left(U_{M}^{\dagger}|b_{M}\rangle\langle b_{M}|U_{M}\right)\right\},$ (127) $$

which is defined as the *classical shadow* of the quantum state $\rho$.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Could the authors provide further clarification on how it is possible to predict the circuit complexity of a state in polynomial time? There are a plethora of existing results proving that circuit complexity is not efficiently learnable. Assuming the claims given in this work are correct, could the authors provide a detailed exposition for how this seemingly contradictory statements can be resolved?

Could the authors provide numerical simulations demonstrating their learning algorithm's performance on concrete examples of noisy quantum states? This would help validate the theoretical guarantees and provide intuition about the practical performance.

The paper focuses on weakly noisy states with specific noise parameters (O(1/n) strength and O(poly log n) depth). Could the authors comment on whether similar techniques could be extended to more general noise models or stronger noise regimes? If not, could the authors describe if stronger results are simply impossible for any learning algorithm?
soundness: 2
strengths: - The algorithm is rigorously analyzed with provable guarantees on both sample and computational complexity.

- The work studies quantum state complexity in noisy environments which better reflect real quantum devices.

- The approach cleverly leverages classical shadows and intrinsic properties of quantum circuit architectures to make the learning problem tractable.

- The sample complexity is shown to be optimal with respect to circuit depth.
summary: This paper investigates a fundamental question in quantum state complexity: how to predict/learn the complexity of weakly noisy quantum states. The authors develop an efficient learning algorithm that:

1. Uses classical shadow representation of quantum states
2. Provides optimal sample complexity with polynomial classical processing time
3. Works specifically for weakly noisy states (noise strength O(1/n) and depth O(poly log n))

The main contribution is establishing an efficient algorithm for learning quantum state complexity in noisy environments.
weaknesses: - It is well known in quantum complexity theory that the circuit complexity of a quantum state cannot be efficiently learned [1, 2, 3]. For example, the existence of pseudorandom states that can be generated in polylog depth on 1D circuits [3] immediately implies that no polynomial-time quantum algorithm can distinguish between polylog circuit complexity (complexity defined in terms minimum circuit depth) and exponential circuit complexity. Hence, it is not possible to predict complexity of a state in polynomial processing time without first solving quantumly hard cryptographic problems. I find it very confusing that the authors claim to predict circuit complexity in polynomial time.

- Despite the focus of practical importance (the presence of noise), the paper did not provide any numerical experiments to validate the theoretical claims (including both efficient sample and computational complexity). I think it is important for this work to have supporting numerical experiments for system size that scales to 50-100 qubits.

- While the paper focuses on weakly noisy states, it's unclear how the approach would scale to more general noise models or stronger noise regimes. I think the work did not provide enough justification for the focus on weakly noisy states.

[1] "Pseudorandom quantum states." Advances in Cryptology–CRYPTO 2018.
[2] "Quantum pseudoentanglement." arXiv preprint arXiv:2211.00747 (2022).
[3] "Random unitaries in extremely low depth." arXiv preprint arXiv:2407.07754 (2024).

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: - Could you provide a more compelling motivation for studying weakly noisy quantum states? How do they relate to real-world quantum systems, and what are the potential applications of your findings?
- Given that quantum noise can accumulate rapidly in depth significantly in each quantum system, how does your proposed learning approach remain feasible in practice? Why gate-independent noise channel? Please clarify the practicality of your noise model and its implications for the scalability of your method. Better to compare with an explicit circuit model example.
- Several parameters in the theorems, such as Theorem 4, are not clearly explained. Could you provide more context and explanations for these parameters to improve the readability of the paper?
- The use of the same letter R to define both the noise numbers in the definition of Weakly Noisy Quantum States and the regrets in later sections is confusing. Please consider using different notations for clarity and consistency throughout the paper.
- To support the effectiveness and practicality of your proposed algorithm, could you provide detailed examples that illustrate its workings and benefits?
- Do you assume quantum noises in the main algorithm 1?
- Numerical experiments on benchmark datasets or simulated quantum systems would strengthen the empirical evidence for your method. Could you include such experiments to demonstrate the performance of your algorithm in various settings?
- While your paper introduces a new quantum learning algorithm, it would be helpful to provide a more comprehensive comparison with existing methods in the field of quantum learning theory. Could you discuss how your approach differs from and improves upon prior work?
- Could you elaborate on how your work on learning the complexity of weakly noisy quantum states is relevant to the broader ICLR community?
soundness: 3
strengths: The paper studies a fundamental problem of understanding the learning complexity of noisy quantum states, which has potential applications in various fields claimed for black-hole theory and condensed-matter physics. The authors propose a novel quantum learning algorithm that leverages the intrinsic structure of quantum circuit architectures to predict the complexity of weakly noisy quantum states. The theoretical analysis provides provable guarantees on the sample complexity and efficiency of the proposed algorithm.
summary: The paper proposes a quantum learning algorithm to predict the complexity of weakly noisy quantum states. The authors introduce the concepts of Weakly Noisy Quantum State and Limited-Structured Complexity and prove that their algorithm achieves optimal sample complexity with respect to their definition of noisy circuit depth. They also provide a lower bound for sample complexity. This work also shows meaningful connections between learning algorithms and quantum state complexity.
weaknesses: - The setting of weakly noisy quantum states is not well-motivated, and it is unclear how the proposed learning approach can be feasible in practice. The accumulation of quantum noise on each quantum system can be significant, and the considered noise model may not be sufficiently practical or meaningful. Not sure about the the noise channel is assumed to be gate-independent.
- The paper is difficult to follow, with various parameters in the theorems that are not clearly explained (e.g., Theorem 4). The use of the same letter R to define both the noise numbers in the definition of Weakly Noisy Quantum States and the regrets in later sections adds to the confusion.
- The paper does not provide detailed examples or numerical experiments to support the proposed algorithm's effectiveness and practicality. This lack of empirical evidence makes the results less convincing.
- It is not very clear to me whether the main algorithms consider quantum noises.
- It is not convincing that the results are of a broad interest in the ICLR community.
- The results presented in the paper do not appear to be particularly surprising or groundbreaking in the field of quantum learning theory.

---

confidence: 2
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. Could the authors elaborate on specific quantum hardware requirements for implementing the algorithm? Are there particular quantum systems where the algorithm's performance has been or can be practically tested?

2. How does the algorithm perform under different types of quantum noise models? Is the accuracy in the complexity predictions different between, e.g., local-depolarizing versus global-depolarizing channels?

The paper could be enhanced by considering the following suggestions:

- The paper should include a more detailed discussion of the computational and practical limitations of the algorithm (for example, stress-testing the algorithm under increased complexities and reporting on its degradation or stability performance.)
- Incorporating key proofs and insights from the appendices into the main body would enhance the paper's value, as some essential concepts, like the subroutine BMaxS, are only briefly mentioned in the main text.
- It would also be very useful if the manuscript provided a framework for empirical testing and validation of the algorithm, including benchmark selection and metrics of validation. This would help bridge the missing gap between theoretical research and practical applications and give a much stronger justification for the effectiveness of the algorithm in noisy quantum environments.
soundness: 3
strengths: 1. The paper confirms that the proposed approach can handle such complex quantum states even in noisy environments, validated through a robust theoretical framework based on theorems and proofs, including the sample complexity and the efficacy of Bayesian optimization in the noisy quantum environment.
2. The application of classical shadow representation in quantifying the complexity of weakly noisy quantum states is novel and crucial from a quantum perspective. This subsequently gives way to efficient quantum information processing classically, making the theoretical methods introduced more feasible.
summary: The paper proposes a quantum learning algorithm that estimates the complexity of weakly noisy quantum states, unlike prior research focusing primarily on pure states, thereby connecting theoretical principles to practical scenarios observed in real-world quantum devices. The proposed algorithm is based on quantum circuit architecture (QCA) combined with classical shadow representation. It reaches near-optimal sample efficiency in the estimation of state complexity, which is theoretically analyzed in this paper to underscore its efficacy. The paper points out several promising research studies that may open up when the expressivity of QCA can be improved, and methodologies for direct complexity predictions in noisy quantum states are developed.
weaknesses: 1. The paper acknowledges that the proposed algorithm approximates the complexity of noisy quantum states and refers to further research on more direct prediction methods. However, it would benefit from an in-depth analysis of limitations, such as sensitivity on different noise models or how scaling issues may affect deployment to larger quantum systems.
2. The paper lacks a detailed discussion of the specific hardware requirements and the practical steps needed for real-world implementation. Details such as compatibility with existing quantum hardware, scalability in practical quantum systems, and specific technological constraints are not thoroughly explored.

Meta-review: Summary:
This paper introduces an efficient quantum learning algorithm for predicting the complexity of weakly noisy quantum states. The authors develop a method that leverages classical shadow representation of quantum states and provides optimal sample complexity with polynomial classical processing time, specifically designed for weakly noisy states with noise strength O(1/n) and depth O(poly log n). The work establishes important connections between learning theory and quantum state complexity in noisy environments.

Main Strengths:
The technical soundness is demonstrated through rigorous theoretical analysis, with provable guarantees on both sample and computational complexity. The approach cleverly leverages classical shadows and intrinsic properties of quantum circuit architectures to make the learning problem tractable. The work addresses an important practical challenge by studying quantum state complexity in noisy environments that better reflect real quantum devices.

Main Weaknesses:
Initially, there were concerns about the paper's claims regarding efficient complexity prediction given known hardness results in quantum complexity theory. The experimental validation was limited, lacking numerical experiments to validate theoretical claims. The initial presentation also needed improvement in explaining technical concepts and practical implementation details.

Decision: Accept (Poster)