# Complexity analysis of weakly noisy quantum states via quantum machine
learning

Yusen Wu  Department of Physics, The University of Western Australia, Perth,
WA 6009, Australia  Bujiao Wu<EMAIL_ADDRESS>Dahlem Center for Complex
Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany  Center on
Frontiers of Computing Studies, Peking University, Beijing 100871, China
Yanqi Song  State Key Laboratory of Networking and Switching Technology,
Beijing University of Posts and Telecommunications, Beijing, 100876, China
Xiao Yuan  Center on Frontiers of Computing Studies, Peking University,
Beijing 100871, China  Jingbo B. Wang<EMAIL_ADDRESS>Department of
Physics, The University of Western Australia, Perth, WA 6009, Australia

###### 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 [1, 2, 3, 4, 5]. 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 [6, 7]. Brown and Susskind’s
conjecture, which is supported by the complexity geometry theory proposed by
Nielsen et al. [8, 9], suggested that the random quantum state complexity
grows linearly before it saturates after reaching an exponential size [10,
11]. Recent works have connected quantum state complexity to unitary
$t$-designs [12, 13] and the dimension of semi-algebraic sets [7], 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 [14, 15], structured
quantum circuits with a brickwall-type layout of gates [14, 15, 7] are
preferred. It is believed that structured random quantum states are
classically difficult to generate under the anticoncentration property in the
average-case scenario [16, 17, 18, 19, 20, 21, 6, 22], implying that
structured quantum circuits could provide quantum advantages for industrial
applications, such as approximating the ground state energy of physically
relevant Hamiltonians [23, 24, 25, 26, 27, 28], solving combinatorial
optimization problems [29, 30, 31], and addressing quantum chemistry problems
[32, 33, 34, 35, 36, 37, 38, 39, 40].

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 [16,
14, 41, 15]. 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 [42]. 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 [43]. 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 [4] 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 [7]. 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
[43, 17, 44, 19]. 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 [45], but the efficiency in generating unstructured “proof states”
remains unclear. On the other hand, the expressive power [46, 47, 48],
optimization [49, 50, 51, 52], and applications [53, 54, 55, 56, 57, 58, 59,
60, 61, 62, 63, 64, 65, 66] of quantum machine learning (QML) have been
intensively studied. Furthermore, recent pioneering experiments conducted on
quantum computer processors [67, 66] 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 (b)). The constraints on
the noisy circuit depth and noisy strength ensure a weakly noisy state,
denoted as $\Phi_{1}$ in Fig. 1 (c). In this paper, our first contribution is
characterizing the relationship between circuit depth, general noise models,
and purity, as claimed in Theorem 1. 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). 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 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 [68] (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). Moreover, recent work [69] 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 [18, 16, 17, 19, 21, 43].
Finally, the proposed QML method is expected be applied in classifying quantum
topological phases of matter [70, 53, 71, 72, 73, 74, 75]. Topological phases
can be distinguished by their ground state complexity [76], and the shadow
tomography [68, 70] 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 we introduce the setup and
definitions that will be used in this work. In Sec. III, we present the main
result. We provide quantum learning algorithm in Sec. IV, and the
corresponding theoretical performance analysis is provided in Sec. V. We
finally discuss applications in Sec. VI.

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 and Lemma 7).
However, if $\Phi=\Phi_{2}$, it is located near the maximum mixed state, and
it cannot be approximated by any pure state.

##  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$.

###  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, 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(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$.

###  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), 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 [77]. 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 can only be used in learning a pure state or a weakly noisy
state which is denoted as $\Phi_{1}$ in Fig. 1 (c).

##  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: _what is the complexity of an unknown weakly noisy state?_
Next, we present our main result. Theorem 1 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 and 3.

###  III.1 Learning Task Statement

It is important to note that Definition 1 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
[78, 7]. 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) 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 [18, 16, 17, 19, 21].
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) 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. 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. 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.

###  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.

######  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 and E.3. Theorem 2 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, 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) 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 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.

##  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 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
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. 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, we provide a detailed description of an efficient method for estimating
the compact set $\mathcal{D}_{\beta}$. By the Heine-Borel theorem [79], 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 [68, 80, 81, 82, 83]. 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 [84].
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, and E.6.

######  Lemma 1.

Consider a parameterized observable $M(\vec{\bm{\beta}})$ defined as Eq. 10.
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.

######  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)$.

Input : Noisy quantum state $\rho_{\rm un}$, a quantum state set
$\mathcal{S}_{\rm QNN}(R,\mathcal{A},N)$, failure probability
$\delta\in(0,1)$, approximation error $\epsilon$

Output : True/False;

1 Initialize $\mu_{0}(\bm{z})=0$, $\sigma_{0}$, the covariance function
$k(\cdot,\cdot)$;

2 for  _$t=1,2,...,T$_ do

3 Select $\kappa_{t}=2N\log(t^{2}N)+2\log(t^{2}/\delta)$;

4

5 Choose $\bm{z}^{(t)}=\arg\max\limits_{\bm{z}\in\mathcal{D}_{\rm
z}}\mu_{t-1}(\bm{z})+\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z})$;

6

7 Using the shadow tomography of $\rho_{\rm un}$ and $\mathcal{S}_{\rm QNN}$
to estimate $\mathcal{L}_{R}(\bm{z}^{(t)})$;

8

9 Calculate $y(\bm{z}^{(t)})=\mathcal{L}_{R}(\bm{z}^{(t)})+p_{t}$ for
$p_{t}\sim\mathcal{N}(0,1)$;

10

11 Update $\mu_{t}$, $\sigma_{t}^{2}$ as Eq. 15;

12

13 if  _$\mathcal{L}_{R}(\bm{z}^{(T)})\leq\epsilon$_ do

14 return _$\rm True$_

15 else do

16 return _$\rm False$_

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 to upper
bound $\max\mathcal{L}$.

###  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, 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
[85], the predictive distribution can be explicitly expressed as Eq. 15.

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, a specific
$\kappa_{t}$ is provided. Details for maximizing $\mathcal{L}_{R}(\bm{z})$ are
shown in Alg 1.

Input : Noisy quantum state $\rho_{\rm un}$ and $\epsilon$;

Output : The minimum depth $R$ $({R<\log n})$ such that ${\rm BMaxS}(\rho_{\rm
un},\mathcal{S}_{\rm QNN}(R,\mathcal{A},N),T=N^{2}n^{k},\epsilon)=$_True_ and
${\rm BMaxS}(\rho_{\rm un},\mathcal{S}_{\rm
QNN}(R-1,\mathcal{A},N),T=N^{2}n^{k},\epsilon)=$_False_ ; Or _False_ if such
$R$ does not exist

1 Initialize $R\leftarrow 1$, $s\leftarrow\log(n)$;

2 while  _$s-R >1$_ do

3 Set $N=LRn^{2}\epsilon^{-2}$ and $T=N^{2}n^{k}$ such that
$k\log(n)<n^{k/2-1}\epsilon$ for large $n$;

4 if  _${\rm BMaxS}(\rho_{\rm un},\mathcal{S}_{\rm
QNN}([(R+s)/2],\mathcal{A},N),T,\epsilon)=$_True_ ,_ do

5 $s\leftarrow(R+s)/2$

6 else do

7 $R\leftarrow(R+s)/2$

8

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

10 return _$C^{{\rm lim},\mathcal{A}}_{\epsilon}(\rho_{\rm un})\leq LR$_

11 else do

12 return _$C^{{\rm lim},\mathcal{A}}_{\epsilon}(\rho_{\rm un}) >L\log n$
_(False)__

13

Algorithm 2 Quantum Machine Learning for Limited-Structured Complexity
approximation

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

The Alg. 1 can efficiently verify whether $\mathcal{L}_{R}(\bm{z})$ satisfies
Lemma 1. Specifically, Alg. 1 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 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.

Since $\mathcal{U}_{\mathcal{A}}(R-1)$ is strictly contained in
$\mathcal{U}_{\mathcal{A}}(R)$ [7], 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 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.

##  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).
Specifically, the complexity of the proposed quantum learning algorithm is
determined by the required QNN samples $N$ and the iteration complexity in
Alg. 1 and Alg. 2.

###  V.1 Sample complexity

The sample complexity of QNN states is promised by Theorem 2, 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 [68].

###  V.2 Iteration complexity

Here, we present the iteration complexity in Alg. 1 and Alg. 2. 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. 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). The
proof details refer to Appendix E.8. Alg. 2 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 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.

##  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
which is inspired by the pure state complexity in [12], rather than discussing
how to reproduce an unknown noisy state. Here, we point that Lemma 1 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, 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 [86]. 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 [87]. We leave the proof
details in Appendix E.5.

###  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)$ [43, 17, 44, 19], in addition, Napp et
al. [88] 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, 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 [89, 88].
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 [69], however the classical
hardness result of noisy quantum states remains unclear at depth between
constant and $o(\log n)$ [43]. 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
[77]. 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 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).

## References

  * [1] Adam Bouland, Bill Fefferman, and Umesh Vazirani.  Computational pseudorandomness, the wormhole growth paradox, and constraints on the ads/cft duality.  arXiv preprint arXiv:1910.14646, 2019.
  * [2] Adam R Brown, Daniel A Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao.  Complexity, action, and black holes.  Physical Review D, 93(8):086006, 2016.
  * [3] Adam R Brown, Daniel A Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao.  Holographic complexity equals bulk action?  Physical review letters, 116(19):191301, 2016.
  * [4] Douglas Stanford and Leonard Susskind.  Complexity and shock wave geometries.  Physical Review D, 90(12):126007, 2014.
  * [5] Leonard Susskind.  Computational complexity and black hole horizons.  Fortschritte der Physik, 64(1):24–43, 2016.
  * [6] Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  arXiv preprint arXiv:1612.05903, 2016.
  * [7] Jonas Haferkamp, Philippe Faist, Naga BT Kothakonda, Jens Eisert, and Nicole Yunger Halpern.  Linear growth of quantum circuit complexity.  Nature Physics, pages 1–5, 2022.
  * [8] Michael A Nielsen.  A geometric approach to quantum circuit lower bounds.  arXiv preprint quant-ph/0502070, 2005.
  * [9] Michael A Nielsen, Mark R Dowling, Mile Gu, and Andrew C Doherty.  Quantum computation as geometry.  Science, 311(5764):1133–1135, 2006.
  * [10] Adam R Brown and Leonard Susskind.  Second law of quantum complexity.  Physical Review D, 97(8):086015, 2018.
  * [11] Leonard Susskind.  Black holes and complexity classes.  arXiv preprint arXiv:1802.02175, 2018.
  * [12] Fernando GSL Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill.  Models of quantum complexity growth.  PRX Quantum, 2(3):030316, 2021.
  * [13] Shao-Kai Jian, Gregory Bentsen, and Brian Swingle.  Linear growth of circuit complexity from brownian dynamics.  arXiv preprint arXiv:2206.14205, 2022.
  * [14] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [15] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al.  Strong quantum computational advantage using a superconducting quantum processor.  Physical review letters, 127(18):180501, 2021.
  * [16] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven.  Characterizing quantum supremacy in near-term devices.  Nature Physics, 14(6):595–600, 2018.
  * [17] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani.  On the complexity and verification of quantum random circuit sampling.  Nature Physics, 15(2):159–163, 2019.
  * [18] Ramis Movassagh.  Quantum supremacy and random circuits.  arXiv preprint arXiv:1909.06210, 2019.
  * [19] Adam Bouland, Bill Fefferman, Zeph Landau, and Yunchao Liu.  Noise and the frontier of quantum supremacy.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1308–1317. IEEE, 2022.
  * [20] Yasuhiro Kondo, Ryuhei Mori, and Ramis Movassagh.  Quantum supremacy and hardness of estimating output probabilities of quantum circuits.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1296–1307. IEEE, 2022.
  * [21] Hari Krovi.  Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent.  arXiv preprint arXiv:2206.05642, 2022.
  * [22] Dominik Hangleiter and Jens Eisert.  Computational advantage of quantum random sampling.  arXiv preprint arXiv:2206.04079, 2022.
  * [23] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  Nature, 549(7671):242–246, 2017.
  * [24] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C Benjamin, and Xiao Yuan.  Variational ansatz-based quantum simulation of imaginary time evolution.  npj Quantum Information, 5(1):1–6, 2019.
  * [25] Bryan T Gard, Linghua Zhu, George S Barron, Nicholas J Mayhall, Sophia E Economou, and Edwin Barnes.  Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithm.  npj Quantum Information, 6(1):1–9, 2020.
  * [26] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al.  Variational quantum algorithms.  Nature Reviews Physics, 3(9):625–644, 2021.
  * [27] Ho Lun Tang, VO Shkolnikov, George S Barron, Harper R Grimsley, Nicholas J Mayhall, Edwin Barnes, and Sophia E Economou.  qubit-adapt-vqe: An adaptive algorithm for constructing hardware-efficient ansätze on a quantum processor.  PRX Quantum, 2(2):020310, 2021.
  * [28] Vladimir V Bazhanov, Sergei L Lukyanov, and Alexander B Zamolodchikov.  Quantum field theories in finite volume: Excited state energies.  Nuclear Physics B, 489(3):487–531, 1997.
  * [29] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al.  Quantum optimization using variational algorithms on near-term quantum devices.  Quantum Science and Technology, 3(3):030503, 2018.
  * [30] Nathan Wiebe, Daniel Braun, and Seth Lloyd.  Quantum algorithm for data fitting.  Physical review letters, 109(5):050505, 2012.
  * [31] Ashley Montanaro.  Quantum algorithms: an overview.  npj Quantum Information, 2(1):1–8, 2016.
  * [32] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C Benjamin, and Xiao Yuan.  Quantum computational chemistry.  Reviews of Modern Physics, 92(1):015003, 2020.
  * [33] Peter JJ O’Malley, Ryan Babbush, Ian D Kivlichan, Jonathan Romero, Jarrod R McClean, Rami Barends, Julian Kelly, Pedram Roushan, Andrew Tranter, Nan Ding, et al.  Scalable quantum simulation of molecular energies.  Physical Review X, 6(3):031007, 2016.
  * [34] James D Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik.  Simulation of electronic structure hamiltonians using quantum computers.  Molecular Physics, 109(5):735–750, 2011.
  * [35] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik.  The theory of variational hybrid quantum-classical algorithms.  New Journal of Physics, 18(2):023023, 2016.
  * [36] Jonathan Romero, Ryan Babbush, Jarrod R McClean, Cornelius Hempel, Peter J Love, and Alán Aspuru-Guzik.  Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz.  Quantum Science and Technology, 4(1):014008, 2018.
  * [37] Yusen Wu, Zigeng Huang, Jinzhao Sun, Xiao Yuan, Jingbo B Wang, and Dingshun Lv.  Orbital expansion variational quantum eigensolver: Enabling efficient simulation of molecules with shallow quantum circuit.  arXiv preprint arXiv:2210.06897, 2022.
  * [38] Weitang Li, Zigeng Huang, Changsu Cao, Yifei Huang, Zhigang Shuai, Xiaoming Sun, Jinzhao Sun, Xiao Yuan, and Dingshun Lv.  Toward practical quantum embedding simulation of realistic chemical systems on near-term quantum computers.  arxiv:2109.08062, 2021.
  * [39] Changsu Cao, Jiaqi Hu, Wengang Zhang, Xusheng Xu, Dechin Chen, Fan Yu, Jun Li, Hanshi Hu, Dingshun Lv, and Man-Hong Yung.  Towards a larger molecular simulation on the quantum computer: Up to 28 qubits systems accelerated by point group symmetry.  arxiv:2109.02110, 2021.
  * [40] Yifei Huang, Yuguo Shao, Weiluo Ren, Jinzhao Sun, and Dingshun Lv.  Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity.  arXiv preprint arXiv:2203.11112, 2022.
  * [41] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al.  Quantum computational advantage using photons.  Science, 370(6523):1460–1463, 2020.
  * [42] Daniel Stilck França and Raul Garcia-Patron.  Limitations of optimization algorithms on noisy quantum devices.  Nature Physics, 17(11):1221–1227, 2021.
  * [43] Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V Gorshkov, Bill Fefferman, and Michael J Gullans.  Tight bounds on the convergence of noisy random circuits to the uniform distribution.  PRX Quantum, 3(4):040329, 2022.
  * [44] Alexander M Dalzell, Nicholas Hunter-Jones, and Fernando GSL Brandão.  Random quantum circuits anticoncentrate in log depth.  PRX Quantum, 3(1):010333, 2022.
  * [45] Nengkun Yu and Tzu-Chieh Wei.  Learning marginals suffices!  arXiv preprint arXiv:2303.08938, 2023.
  * [46] Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, and Dacheng Tao.  Efficient measure for the expressivity of variational quantum algorithms.  Physical Review Letters, 128(8):080506, 2022.
  * [47] Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner.  The power of quantum neural networks.  Nature Computational Science, 1(6):403–409, 2021.
  * [48] Zoë Holmes, Kunal Sharma, Marco Cerezo, and Patrick J Coles.  Connecting ansatz expressibility to gradient magnitudes and barren plateaus.  PRX Quantum, 3(1):010313, 2022.
  * [49] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven.  Barren plateaus in quantum neural network training landscapes.  Nature Communications, 9(1):1–6, 2018.
  * [50] Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles.  Noise-induced barren plateaus in variational quantum algorithms.  Nature communications, 12(1):1–11, 2021.
  * [51] Kunal Sharma, Marco Cerezo, Lukasz Cincio, and Patrick J Coles.  Trainability of dissipative perceptron-based quantum neural networks.  Physical Review Letters, 128(18):180505, 2022.
  * [52] Martin Larocca, Piotr Czarnik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick J Coles, and M Cerezo.  Diagnosing barren plateaus with tools from quantum optimal control.  Quantum, 6:824, 2022.
  * [53] Iris Cong, Soonwon Choi, and Mikhail D Lukin.  Quantum convolutional neural networks.  Nature Physics, 15(12):1273–1278, 2019.
  * [54] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii.  Quantum circuit learning.  Physical Review A, 98(3):032309, 2018.
  * [55] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta.  Supervised learning with quantum-enhanced feature spaces.  Nature, 567(7747):209–212, 2019.
  * [56] Maria Schuld and Nathan Killoran.  Quantum machine learning in feature hilbert spaces.  Physical Review Letters, 122(4):040504, 2019.
  * [57] Maria Schuld.  Quantum machine learning models are kernel methods.  arXiv2101.11020, 2021.
  * [58] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme.  A rigorous and robust quantum speed-up in supervised machine learning.  Nature Physics, 17:1013–1017, 2021.
  * [59] Jin-Guo Liu and Lei Wang.  Differentiable learning of quantum circuit born machines.  Physical Review A, 98(6):062324, 2018.
  * [60] Hai-Ling Liu, Yu-Sen Wu, Lin-Chun Wan, Shi-Jie Pan, Su-Juan Qin, Fei Gao, and Qiao-Yan Wen.  Variational quantum algorithm for the poisson equation.  Physical Review A, 104(2):022418, 2021.
  * [61] Carsten Blank, Daniel K Park, June-Koo Kevin Rhee, and Francesco Petruccione.  Quantum classifier with tailored quantum kernel.  npj Quantum Information, 6(1):41, 2020.
  * [62] Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean.  Power of data in quantum machine learning.  Nature Communications, 12(1):1–9, 2021.
  * [63] Tobias Haug, Chris N Self, and MS Kim.  Large-scale quantum machine learning.  arXiv:2108.01039, 2021.
  * [64] Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Eisert.  On the quantum versus classical learnability of discrete distributions.  Quantum, 5:417, 2021.
  * [65] Yusen Wu, Bujiao Wu, Jingbo Wang, and Xiao Yuan.  Quantum phase recognition via quantum kernel methods.  Quantum, 7:981, 2023.
  * [66] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al.  Quantum advantage in learning from experiments.  Science, 376(6598):1182–1186, 2022.
  * [67] Andrea Rocchetto, Scott Aaronson, Simone Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco Bentivegna, and Fabio Sciarrino.  Experimental learning of quantum states.  Science advances, 5(3):eaau1946, 2019.
  * [68] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  Nature Physics, 16(10):1050–1057, 2020.
  * [69] Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani.  A polynomial-time classical algorithm for noisy random circuit sampling.  arXiv preprint arXiv:2211.03999, 2022.
  * [70] Hsin-Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V Albert, and John Preskill.  Provably efficient machine learning for quantum many-body problems.  Science, 377(6613):eabk3333, 2022.
  * [71] Matthew JS Beach, Anna Golubeva, and Roger G Melko.  Machine learning vortices at the kosterlitz-thouless transition.  Physical Review B, 97(4):045207, 2018.
  * [72] Juan Carrasquilla and Roger G Melko.  Machine learning phases of matter.  Nature Physics, 13(5):431–434, 2017.
  * [73] Eliska Greplova, Agnes Valenti, Gregor Boschung, Frank Schäfer, Niels Lörch, and Sebastian D Huber.  Unsupervised identification of topological phase transitions using predictive models.  New Journal of Physics, 22(4):045003, 2020.
  * [74] Frank Schindler, Nicolas Regnault, and Titus Neupert.  Probing many-body localization with neural networks.  Physical Review B, 95(24):245134, 2017.
  * [75] Evert PL Van Nieuwenburg, Ye-Hua Liu, and Sebastian D Huber.  Learning phase transitions by confusion.  Nature Physics, 13(5):435–439, 2017.
  * [76] Yichen Huang, Xie Chen, et al.  Quantum circuit complexity of one-dimensional topological phases.  Physical Review B, 91(19):195143, 2015.
  * [77] Lennart Bittel and Martin Kliesch.  Training variational quantum algorithms is np-hard.  Physical Review Letters, 127(12):120502, 2021.
  * [78] Michał Oszmaniec, Michał Horodecki, and Nicholas Hunter-Jones.  Saturation and recurrence of quantum complexity in random quantum circuits.  arXiv preprint arXiv:2205.09734, 2022.
  * [79] Nicole R Andre, Susannah M Engdahl, and Adam E Parker.  An analysis of the first proofs of the heine-borel theorem.  Convergence, 10, 2013.
  * [80] Bujiao Wu, Jinzhao Sun, Qi Huang, and Xiao Yuan.  Overlapped grouping measurement: A unified framework for measuring quantum states.  Quantum, 7:896, 2023.
  * [81] H Chau Nguyen, Jan Lennart Bönsel, Jonathan Steinberg, and Otfried Gühne.  Optimizing shadow tomography with generalized measurements.  Physical Review Letters, 129(22):220502, 2022.
  * [82] Ahmed A Akhtar, Hong-Ye Hu, and Yi-Zhuang You.  Scalable and flexible classical shadow tomography with tensor networks.  arXiv preprint arXiv:2209.02093, 2022.
  * [83] Christian Bertoni, Jonas Haferkamp, Marcel Hinsche, Marios Ioannou, Jens Eisert, and Hakop Pashayan.  Shallow shadows: Expectation estimation using low-depth random clifford circuits.  arXiv preprint arXiv:2209.12924, 2022.
  * [84] Daniel Gottesman.  Stabilizer codes and quantum error correction.  California Institute of Technology, 1997.
  * [85] Matthias Seeger.  Gaussian processes for machine learning.  International journal of neural systems, 14(02):69–106, 2004.
  * [86] Sevag Gharibian and Jamie Sikora.  Ground state connectivity of local hamiltonians.  ACM Transactions on Computation Theory (TOCT), 10(2):1–28, 2018\.
  * [87] Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang.  Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.  Journal of the ACM, 69(5):1–72, 2022.
  * [88] John C Napp, Rolando L La Placa, Alexander M Dalzell, Fernando GSL Brandao, and Aram W Harrow.  Efficient classical simulation of random shallow 2d quantum circuits.  Physical Review X, 12(2):021021, 2022.
  * [89] Sergey Bravyi, David Gosset, and Ramis Movassagh.  Classical algorithms for quantum mean values.  Nature Physics, 17(3):337–341, 2021.
  * [90] Masanori Ohya and Dénes Petz.  Quantum entropy and its use.  Springer Science & Business Media, 2004.
  * [91] Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D Lukin, Boaz Barak, and Soonwon Choi.  Limitations of linear cross-entropy as a measure for quantum advantage.  arXiv preprint arXiv:2112.01657, 2021.
  * [92] Joaquin F Rodriguez-Nieva and Mathias S Scheurer.  Identifying topological order through unsupervised machine learning.  Nature Physics, 15(8):790–795, 2019.
  * [93] Sebastian J Wetzel.  Unsupervised learning of phase transitions: From principal component analysis to variational autoencoders.  Physical Review E, 96(2):022140, 2017.
  * [94] A Yu Kitaev.  Fault-tolerant quantum computation by anyons.  Annals of physics, 303(1):2–30, 2003.
  * [95] Ken N Okada, Keita Osaki, Kosuke Mitarai, and Keisuke Fujii.  Identification of topological phases using classically-optimized variational quantum eigensolver.  arXiv preprint arXiv:2202.02909, 2022.
  * [96] Matthias C Caro, Hsin-Yuan Huang, Nicholas Ezzell, Joe Gibbs, Andrew T Sornborger, Lukasz Cincio, Patrick J Coles, and Zoë Holmes.  Out-of-distribution generalization for learning quantum dynamics.  arXiv preprint arXiv:2204.10268, 2022.
  * [97] Using Pinsker’s inequality [90], $\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.
  * [98] John Watrous.  Limits on the power of quantum statistical zero-knowledge.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 459–468. IEEE, 2002.
  * [99] Qisheng Wang, Ji Guan, Junyi Liu, Zhicheng Zhang, and Mingsheng Ying.  New quantum algorithms for computing quantum entropies and distances.  arXiv preprint arXiv:2203.13522, 2022.
  * [100] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of machine learning.  MIT press, 2018.
  * [101] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias W Seeger.  Information-theoretic regret bounds for gaussian process optimization in the bandit setting.  IEEE transactions on information theory, 58(5):3250–3265, 2012\.
  * [102] Sattar Vakili, Kia Khezeli, and Victor Picheny.  On information gain and regret bounds in gaussian process bandits.  In International Conference on Artificial Intelligence and Statistics, pages 82–90. PMLR, 2021.

##  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. [12] 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. [13] 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. [7] 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 [78].

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 [91, 43], 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. [69] 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 [69, 43]. 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 [53], classical neural networks [71, 72, 73,
74, 75], and other classical machine learning models [70, 92, 93]. Among these
literature, Huang et al. [70] 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 [76]. Therefore, the LS
complexity can be naturally used in classifying the trivial state and
topological state. Here, we follow the problem setting in Ref [70], that is
classifying Kitaev’s toric code state [94] from trivial product state. Using
the Hamiltonian variational ansatz [95] $\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
[68], and the target is to determine the quantum phase of matter for each
$\Phi\in S_{\rm shadow}$. Running the Alg. 2 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, 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})$. ∎

##  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. 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$ 111Using Pinsker’s inequality
[90], $\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 [98]. 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 [90]. 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.

Input : noisy state $\rho_{\rm un}=\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle
0^{n}|,\vec{\bm{\theta}}_{x})$

Output : von Neumann entropy $\hat{S}(\rho_{\rm un})$

1

2for  _$l=1,2,\cdots,d$_ do

3 for  _$i=1,2,...,N_{Q}$_ do

4 Prepare the initial state $\rho_{\rm un}^{\otimes l}$;

5 Apply $U_{1}$ on the initial state $\rho_{\rm un}^{\otimes l}$;

6 Measure the state $U_{1}(\rho_{\rm un}^{\otimes l})U_{1}^{\dagger}$ and
obtain the result $\mathcal{S}_{t}$;

7 Calculate the estimator $s_{\rm
an}(t)=\bigoplus\limits_{j=1}^{n}\left(\bigoplus\limits_{m=1}^{l}s_{t}^{(m-1)n+j}\right)$;

8

9 Estimate the value ${\rm Tr}\left(\rho_{\rm
un}^{l}\right)=\frac{1}{N_{Q}}\sum_{t=1}^{N_{Q}}s_{\rm an}(t)$;

10

return _$\hat{S}(\rho_{\rm un})=\sum_{l=1}^{d}a_{l}{\rm Tr}(\rho_{\rm
un}^{l})$_

Algorithm 3 Von Neumann Entropy Calculation

##  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 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 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 [7], 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}$. ∎

##  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 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 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. 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}|$. ∎

###  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 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 [17]. 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 [100],
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. ∎

###  E.3 Estimate the compact domain $\mathcal{D}_{\beta}$

From the Eq. 62, 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})$ [101]. 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$

######  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 [12], 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)$. ∎

###  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. 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 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. 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. ∎

###  E.6 Proof of Lemma 2

###### Proof.

The proof of Lemma 2 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,

$\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)

∎

###  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}$