Learning the Complexity of Weakly Noisy Quantum States
Authors: Yusen Wu
Bujiao Wu
Yanqi Song
Xiao Yuan
Jingbo Wang
Venue: ICLR 2025 Poster (2025)
Keywords: Quantum State Complexity
Quantum Learning Algorithm
Primary area: applications to physical sciences (physics, chemistry, biology, etc.)
TL;DR: This paper proposes a learning algorithm that learns from the classical shadow and predicts the quantum state complexity.

Abstract: Quantifying the complexity of quantum states is a longstanding key problem in various subfields of science, ranging from quantum computing to the black-hole theory. The lower bound on quantum pure state complexity has been shown to grow linearly with system size [J. Haferkamp et al., 2022, *Nat. Phys.*]. However, extending this result to noisy circuit environments, which better reflect real quantum devices, remains an open challenge. In this paper, we explore the complexity of weakly noisy quantum states via the quantum learning method. We present an efficient learning algorithm, that leverages the classical shadow representation of target quantum states, to predict the circuit complexity of weakly noisy quantum states. Our algorithm is proved to be optimal in terms of sample complexity accompanied with polynomial classical processing time. Our result builds a bridge between the learning algorithm and quantum state complexity, meanwhile highlighting the power of learning algorithm in characterizing intrinsic properties of quantum states.

Published as a conference paper at ICLR 2025
LEARNING THE COMPLEXITY OF WEAKLY NOISY QUANTUM STATES
Yusen Wu! Bujiao 3,,5,4,5,6 Yanqi Song", Xiao Yuan & Jingbo B. Wang
School of Artificial Intelligence, Beijing Normal University, Beijing, 100875, China
2 Department of Physics, The University of Western Australia, Perth, WA 6009, Australia
3 Shenzhen Institute for Quantum Science and Engineering,
Southern University of Science and Technology, Shenzhen 518055, China
4 International Quantum Academy, Shenzhen 518048, China
5 Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
6 Center on Frontiers of Computing Studies, Peking University, Beijing 100871, China
7 China Academy of Information and Communications Technology, Beijing, 100191, China
"bu poujjaan jiaowu@ 1 com, t Tjingbo. wange uwa. edu.au
ABSTRACT
Quantifying the complexity quantum states a longstanding key problem various subfields of science, ranging from quantum computing to the black-hole theory. The lower bound on quantum pure state complexity has been shown to grow linearly with system size (Haferkamp al. (022). However, extending this result to noisy circuit environments, which better reffect real quantum devices, re- mains an open challenge. In this paper, we explore the complexity of weakly noisy quantum states via the quantum learning method. We present an efficient learning algorithm, that leverages the classical shadow representation of target quantum states, to predict the circuit complexity of weakly noisy quantum states. Our al- gorithm is proved to optimal terms of sample complexity accompanied with polynomial classical processing time. Our result builds a bridge between the learn- ing algorithm and quantum state complexity, meanwhile highlighting the power of learning algorithm in characterizing intrinsic properties of quantum states.
INTRODUCTION
The concept of quantum complexity has deep connections to high-energy physics, quantum many- body systems, and black-hole physics (Bouland et al., 2019b; Brown et al. 2016a by Stanford & Susskind, 2014; Susskind (016). problem is deemed "easy" it soluble with a (quantum) cir- cuit whose size grows polynomially with the size of the inputs, while the problem is deemed "hard" the size of the (quantum) circuit scales exponentially. In the context of quantum computation, the complexity of n-quhit quantum state corresponds the minimum number of gates required to prepare it from the initial state 10*) (Haferkamp et al., 2022). Brown and Susskind's conjec- ture suggests that the complexity of quantum states generated by random quantum circuits grows linearly before it saturates after reaching an exponential size (Brown & Susskind [2018; Susskind] 2018), which is supported by the complexity geometry theory proposed by Nielsen al. (2006). Re- cent works theoretically proved this conjecture by connecting quantum state complexity to unitary t-designs (Brandão al. [202T] Jian al. 2022) and the dimension of semi-algebraic sets (Hafer- kamp et 2022), demonstrating rigorous computational ability separation between shallow and deep quantum circuits.
However, in the practical world, the quantum system may interact with the surrounding environment, which inevitably introduces a noise signal, making the pure state noisy. For example, in the current hawaiiierreeeeiatts-aa-l-aaaaaaa
device (Boixo et al. 2018 Arute et al. 2019: Zhong et al. 2020 Wu et al., 2021), a certain level (constant) of noise exists in each quantum gate, resulting in noisy states prepared by 2(log n)) -depth noisy circuits classically simulable in both mean value com- putation and random circuit sampling problems (Stilck França & Garcia- Patron [02T]] Aharonov
al. 2022). These facts exhibit trend that is completely different from the case of pure quantum

---

Published as a conference paper at ICLR 2025
states: increasing the depth of the noisy circuit reduces the quantum state complexity. However, it is still unclear how to extend previous arts (Brandão et al. 2021 Jian et al. 2022 Haferkamp et al. 2022) to the noisy environment, and how to characterize the noisy quantum state complexity is still an open problem.
On the other hand, learning algorithms have recently been considered powerful means to study and understand many- Saany-articce quantum systems and the associated quantum processes (Carleo & Troyer 2017: Carrasquilla & Melko 2017 Glasser al. 2018;; Torlai al., 2018 Moreno al.,
2020 Torlai & Melko, 2016; Schindler er et al. 2017; Greplova et al., 2020, Wetzel 2017] Huang
al. 2022 Wu et al. 2023b Du et al. 2022). Specifically, Huang et al. (2022) explored the power of the learning algorithm in classifying quantum phases of matter by learning through the classical shadow (Huang et al., 2020), an efficient classical representation of the quantum state. The strong connection between quantum state complexity and quantum phase transition phenomena Huang jet al. (2015) motivates us to explore the complexity of noisy quantum states using a learning algo- rithm.
Here, we focus primarily on the complexity of weakly noisy quantum states to avoid the anti- concentration property (Deshpande et al., 2022), an undesirable distribution in quantum simulation and quantum approximate optimization algorithms. The n-qubit weakly noisy quantum states are generated by circuits with a depth of R s (poly log n) and a noise strength of (11nn). We focus on an essential and natural problem: Given poly(n) copies of n-qubit unknown weakly noisy quantum state, how to predict its complexity?
To answer this question, we develop a learning approach to solve this problem, which is illustrated in Fig. [ Following the strong quantum state complexity proposed by Brandão et al. (22TT), the learning algorithm pertains to determine whether an unknown weakly noisy state p can be distinguished from the maximally mixed state by a measurement operator induced by a specific quantum circuit architecture (QCA) (shown in Fig. [7] (b)). The size of the measurement operator provides a state complexity upper bound (Brandão et al. (021). More specifically, the problem asks whether there exists a measurement operator M induced by a specific QCA, such that
max M=U (0000"000000" jut (E)
[Tr (M In.22')) )I 2 2(1 - c),
(1)
where A denotes a QCA architecture and (R) contains all R-depth QCA circuits induced by A. The quantum state complexity can be bounded by Onlt), provided that Eq. D is satisfied. In general, the circuit set UA contains an exponential number of candidate circuits U. making direct enumeration impractical. We address this challenge by revealing a specific property of QCA circuits, as outlined in Theorem [T] This property allows the behavior of an observable M, generated by any circuit in MA, to be approximated by linear combination of poly(n) random QCA circuits from MA. Leveraging this, we reformulate the complexity prediction problem into the optimization of a linear function over compact set, which is both sample-efficient and computationally efficient, as demonstrated in Theorem 2 and illustrated in Fig. D (c). We finally show the sample complexity of our learning algorithm is optimal with respect to the noisy circuit depth R, as demonstrated in Theorem
We note that learning the quantum state complexity has broad applications Firstly, the predicted complexity enables the classification of the target unknown state p into one of the following scenar- ios: (i) p can be approximated by an estimator generated by constant-depth noiseless circuits, which is amenable classical simulation (Napp et al. 2022 Bravyi et al. 2021), (ii) p can be approximated using noiseless circuits with sub-logarithmic depth, a task that may present classical computational challenges, as discussed in Ref. (Deshpande et al. 2022), and (iii) p cannot be approximated by any linear combination of circuits constrained to a specific architecture with a depth of at most log n. Besides benchmarking the NISQ computational power (whether its output can be classically sim- ulated), the proposed quantum algorithm and predicted weakly noisy state complexity may have
'The noise strength (1/n) follows the settings used in quantum error mitigation algorithms Temme et al.
2017
Fidd al. 2018).
"Here, the analyzed weakly noisy quantum states may represent ground states of many-body systems, the output state of noisy NISQ algorithm, or the boundary state of black hole, which all can be characterized through shadow tomography (Huang et al. 2020), as depicted in Fig. (a).
2

---

Published as a conference paper at ICLR 2025
practical applications in various fields, including understanding the black hole theory and the quan- tum phase transition. For example, the context of the waade-Sttterssacc//Cooooeeee ory (AdS/CFT) correspondence, the "complexity equals volume" conjecture (Stanford & Susskind, 2014) suggests that the boundary state of the correspondence has a complexity proportional to the volume behind the event horizon of black hole in the bulk geometry. However, when measuring the boundary state, the interaction with the surrounding environment inevitably introduces a noise signal, making the pure state noisy. Furthermore, in quantum many-body systems, quantum phase transitions occur when the external parameters varies (Sachdev) 1999), and the ability to correctly predict the quantum phase transition boundary can help us understand many strong-correlate tems (Zheng et al. 2017). It is known that quantum topological phases can be distinguished by their ground state complexity (Huang al. 2015), and the shadow tomography (Huang al. 2020) 2022) method utilized quantum channels to provide noisy state approximation to the ground state. Predicting complexity of such noisy ground state approximations may recognize the topological phases of matter.
Field The-
sys-
Many-Boo Body Ststem
Shadone Cammuni
P2
1
Noiss CEAKEM
Quaniton
LS-complexily Prediction
Black Hale
Pun
Data Collection
(b)
La (B. P..Poca. P)
Soca (oCA]
B
X XN
Quantum Leaming Algorithm
Figure I: (a) An efficient quantum-to-classical representation conversion method that leverages the classical shadow of noisy state (Huang et al., 2020). By measuring poly(n) copies of the state, it can construct a classical representation P that enables the prediction of the state's 's properties with a rigorous performance guarantee. Here, Pun represents a noisy state generated by a R-depth noisy quantum circuit model which defined Def. 2 and á represents the classical shadow of Pan- (b) QCA model with blocks, where each block corresponds to causal slice, and the overall architecture follows the design of A. (c) Visualization of the complexity prediction process via quantum learning algorithm (Alg- 1), where Ln(3, POCA. () represents metric in measuring the distance between and ọQCA states, which is defined in Eq. T1 The blue Bloch sphere illustrates the relationship between R-block weakly noisy quantum state á and its nearest pure state. All pure states reside on the surface of the n-qubit Bloch sphere, with the maximum mixed state Tn./2" located at the center of the sphere. In the regime where R < Ologn) and for small noise strength p 1/n, the weakly noisy state = Pi located near the surface of the sphere, while و P2 locates near the maximum mixed state.
THEORETICAL BACKGROUND
To clearly demonstrate the motivation and contribution of this work, review the related theoretical backgrounds in terms of quantum state complexity, noisy quantum states, and the architecture of quantum circuits.
Here, we consider the quantum state complexity of an n-qubit quantum pure state (e). The complex- ity of quantum state is the minimal circuit size required implement measurement operator that
3

---

Published as a conference paper at ICLR 2025
suffices to distinguish ( (v6 from the maximally mixed state I,/2". Since any pure state (16) satisfies (16) - 11/2 = 2_", which achieved by the optimal measurement strategy be used to quantify the quantum state complexity. Let H2 denote the space of 2 2 Hermitian matrices, and for fixed e E N, we consider a class of measure- ment operators (2*) Hig that can be constructed by most c 2-local gates. The maximal bias achievable for quantum states with such a restricted set of measurements of the solution is defined
M 1 (1%.. such trace distance
as:
(a [b))
max [Tr (M( (2
where (eb) = V(0") for some V E SU")"). Noting that the above metric (qs(c, (ı)) degenerates to 1 - 2- when с oC. For example, if the quantum state (e) can be easily prepared by quantum computer (such as computational basis states), Eas (c, (tb)) converges to 1 2- rapidly increases. In contrast, for general quantum state (t)), Êqs requires an exponentially large to approach 1 - -_ Using this property, the quantum state complexity can be defined as follows:
Definition 1 (Approximate State Complexity (Brandão et al. 2021) Given an integer e and (0, 1), we say pure quantum state (1b has e-strong state complexity at most e if and only if
Eas(c|1)) 2 1
2 -,
(3)
which is denoted as C.(lv)) Sc..
Due to imperfections in quantum hardware devices, two causal slices are separated by a quan- tum channel E. In this paper, we consider & to represent a general noise channel which is both gate-independent and time-invariant, such as the local-depolarizing channel, the global-depolarizing channel, the bit-flip channel and other common noise models.
Definition 2 (Weakly Noisy Quantum State) We assume that the noise in the quantum device is modeled by gate-independent Pauli noise channel & with error rate p. Let be causal slice, and let & oul be the representation of noisy gale. We define the R-depth noisy quanium state with noise strength
Pp. = E Ul o E o 0R .... ......& E o ([1((00))000
(4)
We use the term "weakly noisy quantum states" to refer to noisy states P.. with R 2 Oppoly log n) and small error rate p such that p < O(n
PROBLEM STATEMENT
3.1 WEAKLY NOISY STATE COMPLEXITY
In this paper, we assume multiple copies of a weakly noisy quantum state p are provided, and utilize learning approach prediet its quantum state complexity, accessing only one copy at time. In the learning phase, we don't have any information on p. as a result, it is generally difficult to exclude shortcuts that could improve the efficiency of a computation. As result, deriving quantum complexity measures for weakly noisy states may be challenging without additional assumptions. Here, we supplement limitations to the operator architecture, which leads to the strutuudt quantum state complexity.
(LS) Complexity of Weakly Noisy State) Given an integer c and e (0, 1), we say weakly noisy state p has e-LS complexity most if and only if
Definition
max M,= (EMA((e/L))
Tr (Melp - Tn./²))] 2
(5)
2
which is denoted as Alim,A(p) (p) S c. The notation L represents the number of gates in each layer of U E u and is termed as the LS error.
'Details refer to Appendix A. WWe leave rigorous definitions Def.
4

---

Published as a conference paper at ICLR 2025
The measurement operator Mc (in D is limited by the architecture U4. It is interesting to note that the LS complexity provides an upper bound for Ce Ce(Pun), that is,
Ce(p) - Cllmm.A (p) c.
Now, provide insight why Def. [ can be modificd to Def. Def.ehwhich characterized the weakly noisy quantum state complexity.
Fact 1 Suppose we are given general noise channel E(- = Σx K((-Kii and R-depth noisy
state PR E (10(("")0000) where the K₃ represent n--uubit Kraus operators and the Up are drawn independently from unitary 2 2edesg set U. If the following relationship holds:
log
F-1 (1 1/d)-1) a((+1)
R 2
(6)
log(d (d² 1) log( F 1)
where d = =" and F Et= [T((K)) P. then for each noisy state Pie their corresponding R-depth pure state (Ve...... On Ur (10%) satisfies
Eu (W ual
(ORIIE "oo((10100"") (uul....aa) 2 n.
Specifically, it saturates to the bound given in Eq. implies
R-1
1 d(d d'
F
nRR) = d2
+
(8)
We leave proof details to Appendix F A particularly noteworthy aspect of the presented fact is its applicability to general noise models. This allows us to establish a precise relationship between the depth of quantum circuit R, the noise model ε, and quality of approximation (purity) that can be achieved. This result further implies using measurement operators prepared by pure states suffice to distinguish weakly noisy quantum state to the maximally mixed state, as defined by Def. [ In light of this, we consider noisy quantum state with depth It = Opoly log n), where the noise modeled as local depolarizing channel Ei(.) = (1- p-) + + pTTr()))22/? and we have (R) ~ (1 (1-pft) by Eq, Furthermore, we note that Eq, 7 immples that there exists a quantum weakly noisy state ORI (10m)((0)) and a quantum pure state (/44....!a!! = Un u. 10m)
(R)
such that
Tr Mug-uu (O 2440))0000000000 - Inn = - pR 2
(9)
in the worst-case scenario the choice of Ui Ui....,uA U (otherwise Eq. may be violated), where the measurement operator M4 = |V (V As a consequence, Defini-
tion can be naturally transferred into Definition which characterizes the complexity of quantum weakly noisy states.
4 QUANTUM LEARNING TASK AND ALGORITHM
We start by introducing the intrinsic structure of UA to devise a parameterized observable M for distinguishing o from the maximal entangled state. In general, optimizing observable M = U'00">O0''U" with (A( is challenging, however, the intrinsic structure of a specific QCA allows for efficient optimization
the observable M. Specifically, we randomly generate set of N polyyyR, (R, r1) quantum neural network states POCA (RR, N) (ALN with P; represents the classical shadow representation of U,!0") for U, E (R) (Huang et al. 2020) (Details refer to Appendix We then design a parameterized operator that takes the form M( = - Bapr.
Theorem (Intrinsic Structure of specific QCA) Randomly select N unitaries from the QCA model UA to generate PQca (R, A, { where each layer in U contains L gates. Then for any n-qubit quantum state p and projector Mj U(#))0)) Ut()) with
5

---

Published as a conference paper at ICLR 2025
U E (R Σラ ())
there exists vector ((t)) belongs N-dimensional compact set D and
such that
N Σ (
LRn log ni
Ex
Tr
-
[Map] S
(10)
N
=
= LRn logn/e n the above approximation error is upper bounded by c (We leave proof details the Appendix Cp.
4.1 METRIC CONSTRUCTION
Here, we assume QCA states Pú are sampled from (A(R) following the probability distribution q. result, the metric
CR(B) = E M(
pi] -
(11)
defined over the compact set B Dz- Given specific parameter B3, we can efficiently calculate
the corresponding value of (3) using classical shadow techniques (Huang al. 2020 Wu al,
2023a Nguyen et al. 2022: Akhtar et al. 2022, Bertoni et al. 2022).
To clarify our algorithm, we define the upper decision interval UDI(e) and the lower decision inter- val LDI(e) as follows.
Definition 4 (Decision interval) UDI(E) is defined as the integer interval [u, xc) such that for any
R E UDI(e), it holds that max; CR 3 S e. Similarly, LDI(e) defined as the integer interval
[0, I] such that for any R E LDD(e),, we have ming LR
B 2 2e.
Before proposing the quantum learning algorithm, we need the following lemmas to support our method. We elaborate proof details in Appendices H.T and H.2
Lemma Consider the metric function (R(3). If the relationship max CR S holds for any
distribution q, then Pun has the state complexity Climm.A S LR, where Cli),.(.) is defined in
Def. 3
Lemma If there exists a distribution q such that min Ln(3) 2e, then with nearly unit proba-
bility, Pun follows the quantum state complexity lower bound (limn > LR.
4.2 LEARNING TASK STATEMENT
Given the preliminary background above, we now formally define the learning task.
Task (Structured Complexity Prediction (SCP c)) Given an architecture A, an n-qubit weakly noisy quantum state Pum (as defined in Eq. 4g. and approximation error c, design a learn- ing algorithm QL,, that runs on an ideal quantum device with polynomially many qubits in n, and learns from the unknown quantum state Pun such that the following conditions hold:
1. (Completeness) If there exists an integer x < logg such that æ E UDI(E)) then QL returns True.
2. (Soundness) If log n LDI(e)), then Qu returns False.
3. (Indeterminate case) If all integers æ E [0, log lie in (LLD()) then QL,, may return either True or False arbitrarily.
'Here, vector z E [0, 2xx 1.R uniquely determines quantum circuit (z) E (R.)). "To keep the semi-definite property of M (()), we generally assume the compact D2 [0, 10.1)* 1

---

by Published as a conference paper at ICLR 2025
To provide clearer analysis of this task, we introduce the following definition.
Definition (Distinguishable Property, (P(A, We say an n-qubit weakly noisy quantum state
Pun satisfies (P(A, if Pun can be distinguished from In/2" with the bias at least 1--2 2-
using a R-depth (R < log n) QCA measurement MaCA (10)) (0")U, where U E EAA.
We note that the learning algorithm QL, returns True (respectively, False) to indicate that Pun does (does not) satisfy the (P(A,)) property.
4.3 QUANTUM LEARNING ALGORITHM FOR SAMITED-STRUCTURE COMPLEXITY ANALYSIS
Based on Theorem optimizing the metric function Cr((3) can be limited into a compact set. Taking the maximization task as an example, we show how to utilize the Bayesian optimization on compact as Alg. in Appendix [[ which is termed as the BMaxS. Specifically, the subroutine BMaxS, which is essentially a Bayesian optimization, takes unknown state Pun. QCA state set, and LS-error inputs, after T steps, it outputs True if R UDI(e) holds, outputs False otherwise. This subroutine can be used as a building block to construct quantum learning algorithm that verifies whether the completeness condition of Task 1 holds. Likewise, BMaxS can also be applied to verify the soundness condition. For the remaining (inconclusive) case, we return random outcome (True or Fa se), thereby providing an efficient solution to Task 1.
Given the fact that a structured unitary set that that (R - is strictly contained in (R( HHaferkamp ct al. 2022). the boolean function
P(R, c) BMaxS(pun. ÁQCA A, T,c)
(12)
a monotone predicate in the interval [1, log n). Therefore a quantum learning algorithm can be designed by binary search program where PRR, is packaged an oracle. A monotone predicate P is boolean funetion defined on totally ordered set with the property: if P P(R,c) = True, then P(R', c) True for all R' 2 R in the domain. In our case, P returns True for the input R when R UDI(e) holds. As a result, if the noisy state Pun satisfies the DP(A, e) property, the QL, outputs the minimum Rmin E [1, log n] enabling (lun.A(pun) < LRmin (True). Otherwise, we test whether logn E LDI(e). If this holds, the QL,, outputs (iim:A(pun) > L log n (F a aese). Otherwise, the studied Pun and threshold would be an invalid case. Details are provided in Alg.
Algorithm 1: Quantum Learning Algorithm for Limited-Structuree Complexity Prediction
Input :
Noisy quantum state Pun. C; Output: The minimum depth R (R log n) such that Clim..(pmm) < LR (True); False if such Rt does not exist; Or return True/False arbitrarily for invalid cases;
Initialize R 1, s + log(n);
while - R > do
Set N = T.Rn² log n/² and T 2 such that & log(n) < n/22111 for large n; if ((R /2 e) -True do
s t [R + /)
else do
R t [(R+ s)
((R, = True do
return Ali (Pun)= & LR (True) else do
if P R, 2c) =False, return Clim.A(pun) > L logn n (False)
12
clse do return True False arbitrarily
THEORETICAL PERFORMANCE GUARANTEE
We will demonstrate that the required number of samplings and processing time for Alg. both efficient, and the sample complexity is optimal with respect to the noisy circuit depth. Using Theorem [ we can state the following result.
7

---

Published as a conference paper at ICLR 2025
Theorem 2 Given (nly(n) copies of an n-qubit unknown weakly noisy state Pun that is generated by a noisy quantum device with depth R O(log n) (Deff 2 and a particular architecture A, there exists poly(n, R. 1/e) quantum and classical cost learning algorithm which can efficiently solve the SCP(A, problem.
The proof of Theorem depends dependds on evaluating the sample complexity of QCA states and unknown noisy state, well as the related iteration complexity during training the quantum learning algo- rithm. We analyze the sample and classical computational complexity in the next two subsections part of the proof outline for this theorem.
5.1 SAMPLE COMPLEXITY
The sample complexity of QCA states is promised by Theorem where the number of copies of QCA states N LRt2 log n/e². To evaluate (R(3) for R < R < (logn) within e-additive erro, the classical shadow representation of Pun is shared by all QCA states, by leveraging the classical shadow method (Huang al., 2020). As result, the sample complexity of an unknown weakly noisy state is at most < O L'RR R.llog L log(1/))) where the failure probability å E (0,1). 1).
Meanwhile, we also give a sample complexity lower bound to demonstrate our learning algorithm optimal in terms of the circuit depth R.
Theorem Given an unknown weakly noisy quantum state prepared by a R-depth quantum cir- cuit affected by p-strength local Pauli noise channels, then any algorithm designed to learn p re- quires least m samplings in the worst-case scenario, where m and constant E (1).
(1-p) (1-p))2eRi (1 (1-6)² c 1m
2n
From the above result and the definition of the quantum weakly noisy state, we know that O(n=1) which results in the sample complexity lower bound (2(1 + 2cpPt)(1 8)2/(2n)) This implies the sample complexity lower bound may linearly growth with the increasing of the circuit layer it, and our learning algorithm nearly-optimal in terms the circuit depth ft. We leave proof details to Appendix ]
5.2 RUNNING TIME ANALYSIS
Here, we provide an analysis of the computational complexity for Alg. including the number of iterations in Alg. [ and the subroutine BMaxS (Alg. () which is a Bayesian optimization algo- rithm. Denote the global optimum 3 = BLaXBEDg CR(3), and natural performance metric for optimizing P(R) is the simple regret ST LR(B²) (3()), which is the difference between the global maximum CR(3r) and (R(3)T). Here, (TT) represents the updated parameter in the T-th step. Obviously, simple regret is non-negative and asymptotically decreases with the increasing iteration complexity T. To build up an explicit connection between 87 and T, the average regret avIr is introduced. Specifically, avir 1/T 1/T CR(3)) (B((T)) Noting that the rela- tionship < avvr holds for any T 2 1. In the following, we show that avrr is upper bounded by O log T/VT), and the simple regret sT & avrT -> O with the increase of T. The following theorem derives the average regret bounds for P(R) = BMaxS(pun POCA (R, A, N,,
Theorem Take the target weakly noisy state Pun and QCA state set POCA (R, N) into the sub- routine P(R) (Eq. 12). Pick the failure probability 5 (0, 1), then there exists a Bayesian approach (details refer to Alg. 2 such that the average regret avTT can be upper bounded by
(V
1og + 2N log T log x² 266))
avIT S SO
(13)
T
after T optimization steps with success probability, where represents the number of samples in the QCA state set.
8

---

Published as a conference paper at ICLR 2025
(a)
(c)
0.45
0.55
0.40
0.50
0.45
66)
x/B
0.35
161 x/4
0.40
0.30
0:35
0:30
0.20
0.25
0.15
0.10
0.15
0.05
2.0
2.5
3.0
3.5
4.0
4.5
5.0
2.0
2.5
3.0
3.5
4.0
4.5
5.0
R
R
(d)
(e)
0.5
Am
A=2
0.5
A=2
0.6
-X- 1
R=2
0.4
AdC
Adrt
3x/4
hdd
minn
0.3
0.4
0.3
0.2
0.1
0.2
0.1
2.0
2.5
0.1
2.5
R
Figure 2: (a) Visualization of the 2D transverse field Ising model. (b)-(d) illustrate the trend of the function min 3 Ln as it varies with the circuit depth R of QCA set. To extract the complexity lower bound of the target quantum state from the plot, we begin by drawing horizontal line representing approximation error of the quantum state. For example, (b), we set é' = 0.25. Next, we identify the last point where the curve remains above this horizontal line before crossing it, and record the corresponding horizontal coordinate R. This represents the complexity lower bound of the target quantum state. For instance, in Fig. (b), the blue eurve remains above c' 0.25 until R indicating complexity lower bound of Co.125 (PTI(2,
4L. Similarly, the green curve last remains above e' = 0.25 at R 2, yielding a complexity lower bound Cllim (101(10,pp) p)) 2L, where L represents the number of two-qubit gates in each layer of the architecture A.
Specifically, select integer i such that log(n) n for all no. where no represents a fixed integer. Then T = 2 enables the simple regret 8y can be upper bounded by c, where N LRn log -2 (Theorem l.. The proof details refer Appendix [
Finally, noting that Alg. is essentially binary search program the interval [1, R] by using the oracle (). BMaxS (Pun. (Pans PQCA R, A, N), c). Therefore, Alg. requires
( ( ++ 1,2, ft2 log( Rt), (1g())))
classical time complexity to answer the SCP problem. This thus completes the proof of Theorem
NUMERICAL SIMULATIONS
Here, we demonstrate how to use the proposed learning method to benchmark the capabilities of noisy state computation, providing numerical evidence to support our theoretical findings. Specif- ically, we address the fundamental question: Does the complexity of weakly noisy quantum states grow linearly with circuit depth?
We consider to simulate the time dynamics of the Hamiltonian H ==J ((.))) + h h X; on
two-dimensional grid with (a x 6) size, where J > 0 represents the coupling of nniibot- spins and à represents the global transverse field strength (see Fig. [ (a)). To simulate the time evolution circuit -ilf,, the first-order Trotter decomposition is utilized (Kim et al. 2023). that is e --H Ie iim26 e 66 7/8t + (( where Hzz represents the spin term, Hx repre- sents the transverse- field term and the evolution time t is discretized into (r/6t) time slices. Then its quantum circuit implementation can be decomposed by e e-iH225t = [I( Rz,z, (-2J5() and

---

Published as a conference paper at ICLR 2025
e = II, Rx, (2hôt). We focus small-scale scenario studied in Ref. (im et al. 2023
where the system size is 3 x 4, angle rotations -2Jöt = x / hôt E (m/8, and each quantum gate is affected by local depolarizing channel & with strength p 10 Let
R [T/ōt], then we denote the output quantum weakly noisy state
Pr)(R. = Of [Ep Uzz Ep o Ux (10*)(01))
(14)
where (z) eiittzztt ())2 (-) - i (-)etH and the quantum noise channel Ep 80_ E. In the numerical simulation, we demonstrated our algorithm on server with 64 vCPUs and 128 GiB of memory, where the density matrix PTi (). p) and classical shadow set are prepared by the Pennylane package (Bergholm et al. 2018).
In our analysis, we mainly focus on the circuit complexity lower bound of noisy quantum states pTI(R,p) p) with It E {2, 10] by using Alg. considering a standard 2D lattice quantum circuit archi- tecture A to prepare PQCA. where each layer has = (n) random two-qubit gates. Visualization of the architecture A in ID scenario is given by Fig. (b). To estimate the lower bound, we thus set a small error (e = 10 10-21 2 and randomly generate N = n I quantum circuits with varying circuit depths Rt E {2, 3,4, based on the architecture A. Precisely, we tune the linear coefficient 3 to minimize the metric functions outlined in Lemma 2 as depicted in Figure where each point repre- sents the mean value of ming Ln by repeating 10 independent experiments, and the error bar repre- sents the standard variance. This strategic adjustment allows us to derive an estimate for the quantum circuit lower bound. More specifically, in Figure (b), we showcase a clear circuit complexity sepa- ration between weakly noisy quantum states pri p) and p11 p). To see this relationship, Fig- ure 2 (b) demonstrated that min 5 C2(Pr p)) > 0.25, meanwhile ming La (P(r((2.))) > 0.25
(PTI( = 10. p)) > 2L and C (PTI = p)) > 4L (according to Lemma 2). where L = =n represents the number of random two qubit gates in each layer. This result highlights weakly noisy quantum state complexity lower bound may not grow with the circuit depth, which is dramatically different that of pure states. Similar phe- nomenons are witnessed in (ubfi where a shallower circuit depth weakly noisy states possess higher state complexity lower bound.
which demonstrate that the circuit complexity
CONCLUSION
The quantum state complexity serves as measure of inherent properties within quantum states, thereby facilitating a deeper understanding of quantum entanglement information, quantum topo- logical phases, and computational capabilities. In practical applications, collected quantum states are often subject to noise originating from state preparation and quantum measurement (SPAM), as well as limitations imposed by the quantum hardware. Consequently, original pure states are trans- formed to noisy states through quantum channels. Thus, investigating the quantum state complexity of noisy states holds significant importance in studying information scrambling, the spread of lo- cal noise and entanglement throughout the entire system, which is expected to illuminate studies in the field of black-hole theory and condensed-matte physics. In this paper, we investigate the complexity of weakly noisy quantum states through a quantum learning algorithm, which connects two significant concepts in the quantum computational theory. The proposed quantum learning al- gorithm exploits the intrinsic structure of QCA to build learning model Ln((3), whose extreme points reveal the limited-strucctrred complexity. Meanwhile, when considering the sample complex- ity of target noisy quantum state, our algorithm achieves optimal in terms of the circuit depth n. Moreover, we emphasize that the Bayesian optimizer (given by Alg. 2 is not the unique option, and other optimization algorithms may also work with similar iteration steps. This highlights the universality of the intrinsic structure of QCA in combination with optimization subroutines.
'Here, the numerical simulation mainly aims to find the circuit lower bound. Therefore, we set small error threshold such that the measurement operators constructed in Alg I cannot lead to P(R) = true. In this case, the algorithm will proceed to the final step determine the lower bound of the quantum state's complexity.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Jens Eisert, Philippe Faist, Haihan Wu, Tavis Bennett, John Tanner, and all anonymous reviewers for their helpful comments on this paper. Y. Wu acknowledges the support from the Natural Science Foundation of China Grant (No. 62371050). B. Wu acknowledges the support from the National Natural Science Foundation of China Grant (No. 12405014) and the Research fund of the post-doctor who came to Shenzhen. X. Yuan supported by the Innovation Program for Quantum Science and Technology Grant (No. 20237/00000200), the National Natural Science Foundation of China Grant (No. 12175003 and No. 12361161602) NSAF Grant (No. U2330201). J. B. Wang acknowledges continued support from Pawsey Supercomputing Research Centre.
REFERENCES
Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. arXiv preprint arXiv:22 1.0:999 2022.
Ahmed A Akhtar, Hong-Ye Ye Hu, and Yi-Zhuang You. Scalable and flexible classical shadow tomog- raphy with tensor networks, arXiv preprint arXivv2209.0200 2022.
Eric R Anschuetz and Bobak T Kiani. Quantum variational algorithms are swamped with traps.
Nature Communications, 13(1):7760, 2022.
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 programmable superconducting processor. Nature, 574(7779):505-510 2019.
Matthew JS Beach, Anna Golubeva, and Roger G Melko. Machine learning vortices at the kosterlitz- thouless transition. Physical Review B, 9744)045207,
Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M Sohaib Alam, Guillermo Alonso-Linaje, AkashNarayynan, Ali Asadi, et al. Penny- lane: Automatic differentiation of hybrid quantum-classical computations. arXiv preprint 1xXiv:811.00900 2018
Christian Bertoni, Jonas Haferkamp, Marcel Hinsche, Marios loannou, Jens Eisert, and Hakop Pashayan. Shallow shadows: Expectation estimation using low-depth random clifford circuits. arXiv preprint arXiv:2209. 12924, 2022.
Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael Bremner, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14(6))595-600, 2018.
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, 2019a.
Adam Bouland, Bill Fefferman, and Umesh Vazirani. Computational pseudorandomness, the worm- hole growth paradox, and constraints on the ads/cft duality. arXiv preprint arXiv:1910.14644 14646, 2019b.
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.
Sergey Bravyi, David Gosset, and Ramis Movassagh. Classical algorithms for quantum mean values. Nature Physics, 1733)337-341, 2021.
Adam R Brown and Leonard Susskind. Second law of quantum complexity. Physical Review D, 97 (8):086015, 2018
Adam R Brown, Daniel A Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao. Complexity, action, and black holes. Physical Review D, 93(8):086006, 2016a.
Adam R Brown, Daniel A Roberts, Leonard Susskind, Brian Swingle, and Ying Zhao. Holographic complexity equals bulk action? Physical review letters, 191(11)) 2016b.

---

Published as a conference paper at ICLR 2025
Giuseppe Carleo and Matthias Troyer. Solving the quantum many-body problem with artificial neural networks. Science, 355(6325)602--606 2017.
Juan Carrasquilla and Roger G Melko. Machine learning phases of matter. Nature Physics, 13(5): 431-434, 2017.
M Cerezo, Guillaume Verdon, Hsin- Yuan Huang, Lukasz Cincio, and Patrick Coles. Challenges and opportunities in quantum machine learning. Nature Computational Science, 2(9):567-576,
2022.
Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost function depen- dent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12(1): 1-1 2021.
Senrui Chen, Yunchao Liu, Matthew Otten, Alireza Seif, Bill Fefferman, and Liang Jiang. The learnability of pauli noise. Nature Communications, 14(1):52, 2023.
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics, ((12):1273-1278) 2019.
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.
Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, and Dacheng Tao. Efficient measure for the expressivity of variational quantum algorithms. Physical Review Letters, 128(0))080506, 2022.
Suguru Endo, Simon Benjamin, and Ying Li. Practical quantum error mitigation for near-future applications. Physical Review X, ((3):031227 2018.
Ivan Glasser, Nicola Pancotti, Moritz August, Ivan D Rodriguez, and Ignacio Cirac. Neural- network quantum states, string-bond boon states, and chiral topological states. Physical Review X, (106011006, 2018.
Daniel Gottesman. Stabilizer codes and quanium correction. California Institute of Technol- ogy, 1997.
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.
Jonas Haferkamp, Philippe Faist, Naga BT Kothakonda, Jens Eisert, and Nicole Yunger Halpern. Linear growth of quantum circuit complexity. Nature Physics, 1-5, 2022.
Hisin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of quantum system from very few measurements. Nature Physics, 10500)10000-005, 2020.
Hsin-Yon Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean. Power data in quantum machine learning. Nature Communica- fions, 12(1) (111))1-99990)00 2021.
Hsin-Yual Huang, Richard Kueng, Giacomo Torlai, Victor Albert, and John Preskill. Provably ficient machine learning for quantum many-body problems. Science, 377(6613) 2022.
Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R McClean. Learning shallow quantum circuits. arXiv preprint 1...i:2441..0099 2024.
Yichen Huang, Xie Chen, al. Quantum circuit complexity of one-dimensional topological phases. Physical Review B, 91(19):195143, 2015.
Sofiene Jerbi, Lukas J Fiderer, Hendrik Poulsen Nautrup, Jonas M Kübler, Hans J Briegel, and Vedran Dunjko. Quantum machine learning beyond kernel methods. arXiv preprint 10. 2021.
12

---

Published as a conference paper at ICLR 2025
Shao-Ka Kai Jian, Gregory Bentsen, and Brian Swingle. Linear growth of circuit complexity from brownian dynamics. arXiv preprint arXiv:2206. 14205, 2022.
Hamza Jnane, Jonathan Steinberg. Zhenyu Cai, H Chau Nguyen, and Bálint Koczor. Quantum error mitigated classical shadows. PRX Quantum, 5(1):010324, 2024.
Youngseok Kim, Andrew Eddins, Sajant Anand, KenXuan Wei, Ewout van den Berg, Sami Rosen- blatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala. Evi- dence for the utility of quantum computing before fault tolerance. Nature, 618:500-505, 2023.
Zeph Landau and Yunchao Liu. Learning quantum states prepared by shallow circuits in polynomial time. arXiv preprint arXiv:2410.23611, 2024.
Jarrod McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Bar- ren plateaus in quantum neural network training landscapes. Nature Communications, 91)::166, 2018.
Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. Quantum circuit learning. Physical Review A, 98(3):032309, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Javier Robledo Moreno, Giuseppe Carleo, and Antoine Georges. Deep learning the hohenberg-kohn maps of density functional theory. Physical Review Letters, 125(7):076402, 2020.
John 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):02121,, 2022.
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.
Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information, volume 2. Cambridge university press Cambridge, 2001.
Michael A Nielsen, Mark R Dowling, Mile Gu, and Andrew C Doherty. Quantum computation as geometry. Science, 3116656)):1133-11333 2006.
Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert. Ex- ponentially tighter bounds limitations quantum error mitigation. Nature Physics, 20(10): 1648-1658, 2024.
Joaquin F Rodriguez-Nieva and Mathias S Scheurer. Identifying topological order through unsuper- vised machine learning. Nature Physics, 15(8):790-795 2019.
Subir Sachdev. Quantum phase transitions. Physics World, 12(4):33, 1999.
Frank Schindler, Nicolas Regnault, and Titus Neupert. Probing many-body localization with neural networks. Physical Review B, 95(24);245134 2017.
Thomas Schuster, Jonas Haferkamp, and Hsin- Yuan Huang. Random unitaries in extremely low depth. arXiv preprint axXiv:2407.07754 2024.
Matthias Seeger. Gaussian processes for machine learning. International journal of neural systems, 14(02):69-106, 2004.
Peter W Shor. Fault-tolerant quantum computation. In Proceedings of 37th conference on founda- fions of computer science, pp. 56-65. IEEE, 1996.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias W Seeger. -heoorationttheoretiic regret bounds for gaussian process optimization in the bandit setting. IEEE transactions on infor- mation theory, 58(5):325--2266 2012.
13

---

Published as a conference paper at ICLR 2025
Douglas Stanford and Leonard Susskind. Complexity and shock wave geometries. Physical Review D, 90(12):126007 2014.
Daniel Stilck França and Raul Garcia-Patron. Limitations of optimization algorithms on noisy quan- tum devices. Nature Physics, 17(11):1221-1227 2021.
Leonard Susskind. Computational complexity and black hole horizons. Fortschritte der Physik, 64 (1):24 43, 2016.
Leonard Susskind. Black holes and complexity classes. arXiv preprint arXtv:180..02175, 2018.
Kristan Temme, Sergey Bravyi, and Jay M Gambetta. Error mitigation for short-depth quantum circuits. Physical review letters, 119(18): 180509, 2017.
Giacomo Torlai and Roger G Melko. Learning thermodynamics with boltzmann machines. Physical Review B, 94(16):165134, 2016.
Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo. Neural-network quantum state tomography. Nature Physics, 14(5):447-450, 2018.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference Artificial Intelligence and Statistics, pp. $2-90. PMLR, 2021.
Evert PL Van Nieuwenburg, Ye-Hua Liu, and Sebastian D Huber. Learning phase transitions by confusion. Nature Physics, 13(5):335 439, 2017.
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 com- mumications, 12(1):1-11, 2021.
Sebastian J Wetzel. Unsupervised learning of phase transitions: From principal component analysis to variational autoencoders. Physical Review E, 96(2):221400, 2017.
Bujiao Wu, Jinzhao Sun, Qi Huang, and Xiao Yuan. Overlapped grouping measurement: unified framework for measuring quantum states. Quantum, 7:896, 2023a.
Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming- Chen, Xiawei Chen, Tung-Hsu 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.
Yusen Wu, Bujiao Wu, Jingho Wang, and Xiao Yuan. Quantum phase recognition via quantum kernel methods. Quantum, 7:981, 2023b.
Feidiao Yang, Jiaqing Jiang, Jialin Zhang, and Xiaoming Sun. Revisiting online quantum state learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 6607- 6614, 2020.
Bo-Xiao Zheng, Chia-Min Chung, Philippe Corboz, Georg Ehlers, Ming-Pu Qin. Reinhard M Noack, Hao Shi, Steven White, Shiwei Zhang, and Gareet Kin-Lic Chan. Stripe order in the underdoped region of the two-dimensional hubbard model. Science, 358(6367): 2017.
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 Quantum computational advantage using photons. Science, 37066523):1460-1446 2020.
14

---

Published as a conference paper at ICLR 2025
A COMPARISON WITH RELATED WORKS
In the context of condensed matter physics, a topological phase transition occurs when the ground states of family of Hamiltonians exhibit different circuit complexities. This suggests that topolog- ical phase classification may help distinguish between low-complexity and high-complexity ground states. The use of learning algorithms to classify quantum phases of matter has been widely studied. Proposals include quantum neural networks (Cong et al. 2019), classical neural networks (Beach) et burg et all] (2177), and other classical machine learning models Huang et al. [2022] Rodriguez-
2018 2018 Carrasquilla & Melko 2017 Greplova et al. 2020 Schindder et al., [017]] Van Nieuwen-
& Scheurer 2019 Wetzel, 2017). However, most previous works lack rigorous theoretical guaran- tees. Among these studies, Huang et al. (Huang et al. (022) utilized shadow tomography of the concerned ground states to design an unsupervised machine learning approach guaranteed to clas- sify accurately under certain conditions. The proposed "shadow kernel" can generate quantum en- tropies by tuning hyperparameters. enabling the approximation of various topological phase order parameters. Compared with Ref. Huang et al. (2022), our learning algorithm can be applied to noisy states and predict complexity, whereas Ref. (Huang et al. (2022) mainly focuses on pure ground state classification without providing explicit metric for characterizing complexity.
On the other hand, learning quantum states and circuits is long-standing task in the field of quan- tum machine learning. Previous works generally utilized parameterized circuits to learn approxima- tions of target states and circuits (Mitarai et al., 2018 Yang et al.) 2020 Huang et al. 2021 Jerbi et al. 2021 Cerezo et al. 2022). However, variational-basee methods generally lack theoretical guarantees and may suffer from the barren plateau phenomenon even in low-depth parameterized circuits (McClean et al.] 2018; Cerezo et al. 2021 Anschuetz & Kiani 2022). Very recently, clas-
sical shadow-based learning algorithms have been proposed for reconstructing shallow quantum circuits U (Huang et al., [2024] [Landau & Liu 2024). Nevertheless, these methods require querying UT, which introduces intrinsic limitations in noisy environments since most noisy channels (CPTP maps) may not be invertible. Compared with related works, our method bypasses these limitations by introducing the "Intrinsic Structure property" (as given by Theorem 1), which enables an efficient quantum learning algorithm to predict state complexity in noisy environments.
we would like to point out that Ref. Schuster et al. (024)) does not rule out the possibility that the pure state complexity can be predicted when the target states exhibit certain physical structures, such the ground state of XXZ models and the toric code, as studied in Ref. [Huan et al. (2022). Furthermore, recent works (Huang et al. 2024] Landau & Liu 2024) have also demonstrated that fixed shallow quantum circuits and quantum pure states (including 1D-O(log n) depth and all-to- all (log log ni) ddepthh can be efficiently learned. These results demonstrate sigmificant differences between scenarios with and without 'randomness'. Compared with Ref. (Schuster et al. 2024). our
work is more similar to Refs. (Huang et al., 2022; 2024 Landau & Liu 2024), which focus on a specific quantum state rather than an ensemble.
Furthermore, we would like to highlight the differences between weakly noisy quantum states and pseudorandom quantum states. Specifically, we consider the second- moment statistic property of set of pseudorandom quantum circuits U whose circuit depth R S poly log n. In Ref. (Schuster et al. 2024), they claimed that even (log(n))-deeg 2-design property given by Haar measure. Then, we may suppose U UI... & representing a random Clifford circuit, then for the initial state 10") (0r) and arbitrary observable O we have
Clifford circuits may approximate the unitary
M2(U)= = I
JU-CK3r) Tr (0" (tt))) Tr [110")00// = d(d? - 1) [T + Tr
1
(15)
On the other hand, in the context of weakly noisy environment, the Clifford circuit U may transform to the channel representation U -OR o U, where E represents n--ubii Pauli channel and U4 = U represents a layer of Clifford gate. According to the "Channel Pushing" lemma given by Ref Quek et al. (224)) (Lemma 10), we may rewrite the noisy channel by U E' o O Uu, where El also represents an n--ubit Pauli channel. Let the channel E' = Σ, Kf()) where K;
15

---

Published as a conference paper at ICLR 2025
represents the Kraus operator satisfying E, K/ K; I, we have
M2((1) = /
Tr ("
UUNC((2))
Tr (,K",,0(00)00000000 of Ir KK, (000000000
(16)
11./2 UNO1(29)
Σ 11
+ Tr(K,, OKL, K ((,OK())
d(d -1
We note that the interaction term Ei,,, Tr(Ki, OKI, K1,KKi may not equal to Tr(O*), and this leads M2) M2(U). This comparison indicates that even if algorithm can learn the difference between noisy ensembles and Haar-randon states, this does not imply that the algorithm can be used to distinguish between pseudorandom ensembles and Haar-randa
ensembles.
The above discussions demonstrate the fundamental difference between our work and Ref. (Schuster et al.) 2024). Such difference implies that the efficiency of our learning algorithm may not contradict the findings presented in Ref. (Schuster et al.) 2024).
B NOISE MODELS ASSUMPTION IN THIS WORK
In the proposed learning approach (Alg 1), the algorithm requires (i) the target weakly noisy quan- tum state Pun, and (ii) the QCA state set PQCA- The target weakly noisy state naturally contains noise signals, while the QCA state set ÀQCA is provided by the classical shadow representation (Huang al.) 2020). When preparing the classical shadow, recent result successfully embedded the quan- tum emrrr mitigation method into the classical shadow protocol, which provides rigorous theoretical guarantees even in the noisy environment (Jnane et 2024).
In quantum computing research, the gate-independent noise model assumes that the noise affecting quantum operations uniform across all gates, regardless of their type or implementation. This simplification is widely adopted for several reasons:
Theoretical Simplification: Assuming gate-independent noise allows researchers to de- velop and analyze error correction protocols and fault-tolerant methods without delving into the complexities introduced by gate-specific noise characteristics. This uniformity fa- cilitates the derivation general results and theoretical bounds (Nielsen Chuang 2001).
Practical Approximations: In certain quantum systems, particularly those with well- calibrated gates operating on the same number of qubits and utilizing uniform control mechanisms, noise variations across different gates can be negligible (Shor) 1996; [Arute] et al.) 2019). In such cases, the gate-independent noise model serves reasonable ap- proximation, streamlining analysis without significantly compromising accuracy.
Alignment with Twirled Noise Models: transform complex noise channels into diagonal forms on the Pauli basis (Chen et al.) 2023). While twirling simplifies the noise structure, it does not inherently eliminate gate dependence. However, in many scenarios, the resulting noise can be approximated as gate- independent, aligning with the assumptions of the model.
Techniques like Pauli twirling are employed to
The gate-independent noise model provides a foundational framework for understanding error prop- agation and developing correction strategies, which is useful abstraction for theoretical exploration and the initial development of error correction methods. We leave an open question of how to depict the gate-dependent noise, which usually happens in larger, more complex quantum architectures.
C QUANTUM HARDWARE REQUIREMENT
We note that our learning algorithm has very few limitations to the practical quantum hardware. In the Alg. 1, we only require (i) the target weakly noisy quantum state Pun. and (ii) the QCA state set PQCA, which is essentially the classical shadow representation Huang al. (2020). When preparing
16

---

Published as a conference paper at ICLR 2025
the classical shadow, recent work has successfully integrated quantum enror mitigation methods into the classical shadow protocol, providing rigorous theoretical guarantees in preparing shadows even in noisy environments Unane al. 2024). As result, our Alg only require quantum computer which supports the quantum error mitigation function, which should have 50 100 noisy qubits with 2 0.99 quantum gate fidelity. Some popular quantum computation platforms may satisfy these requirements and can be used to prepare the required classical shadow, such as Eagle used in Ref. Kim et al. (2023) and Sycamore Arute et al. (2019). This work essentially a theoretical research, and the algorithm has not yet been explicitly tested on these practical platforms.
D COMPARISON BETWEEN LOCAL AND GLOBAL NOISE MODELS
We note that the global depolarizing channel is essentially special case of contracting n local noise models. Specifically, given the global depolarizing channel with noisy strength Py and local depolarizing channel E with strength pt, according to the relative entropy inequality, for any input state p. we can observe the relationships
D(E(0)l44/2") < (1- ((l)))D((l()n/2))
(17)
and
D ((()),1()))) S (1 (00-))"
(18)
hold. These inequalities indicate that the global depolarizing channel is much weaker than local noise, given the same noise strength. Consequently, for the global depolarizing channel, our algo- rithm is capable of handling scenarios where Py I O(1), while maintaining comparable prediction accuracy. This suggests that the algorithm can effectively handle both types of noise, with only a minor difference in performance under different noise strengths.
E RELATED DEFINITIONS
Definition 6 (Architecture Haferkamp et al. 2022); Bouland et al. (2019a) An architecture A directed acyelic graph that contains [V] E Z,20 vertices (gates), and two edges (qubits) en- ter each vertex, and two edges exit. A quantum circuit induced by the architecture A is denoted as U. The circuit set which contains all quantum circuits induced by the architecture A is denoted by Ua The circuit set (R) contains all R-depth quantum circuits induced by the architecture A. and we have the relationship
UA = UAZ)
(19)
Definition 7 (Causal Slice) The circuit UA is a causal slice if there exists qubit-reachable path between any two qubit-pairs where the path only passes through vertices (gates) in the architecture A.
F PROOF OF FACT 1
Here, we are interested measuring the quantity Eu.... [H where PI, O Eo (p(p))) P2. = ( (p2) and Pl, P2 represent initial pure states. Suppose E can be decomposed by Kraus operators, that is E(.) = Ei= K! Then we first consider the scenario R = 1:
Tr (p1,11221) =Tr [(E o 24 (PT)
-Tr (Swap (E ol (01) 8 Ui (p2))
(20)
Σ Tr Swap (K) 8U((p2))
17

---

Published as a conference paper at ICLR 2025
Then taking the average value unitary 2 design set, obtain
Σ Ban Tr Swap ((K) 60 (U) @o Uer p2) a (k) m.)]
Ber Tr (P1,1P21)
(21)
Considering the relationship
Eusu [(U @ UUA @ OUT) = Tr((A) Tr(SwapA)) In & In +
(Tr(SwapA)
Tr(4)
)
de -1 d(dP -
d2 1
d(d2 - 1)
Swap (22)
=aI, @ I, + SSwapp
where U is unitary 2-design, then Eq. 21 can be further caleulated by
Exg Tr (01,1P2.1) Be Tr Swap (Ki @ In)(ann In + (SW
Tr Swap((KK)) In)]
B
Σ 1=1
Tr
Swap(Ki @ L.)Swap(K/ @ [n) (23)
Tr KiK? +
IIr [K]]
2=1
1=1
The last equality comes from Tr Swap(K) & S,)Swap(K// @ [n) = Tr [wap((K & (T) @ K])]
Tr Swap(Kr & Ki)]
(24)
Tr [K,]
Consider Ei Tr KiKj] Tr(E(T,)] = d and denote F = Tr [Ki]] Eq. 21 can be finally
expressed as Eu, Tr (P1,1221))
1 Tr(p1p2) ) Tr(E(In)]+
(Tr(p122)
d/d 102--1 _ F
d2 1 did - 11) F - d² Tr(pip2) + x -ー (d (d-
(25)
1
where d = 2n. Therefore, we obtain a recursive formula for the overlap of the output states, as defined in 25 We have
F-1
EsG, ur.... Up Tr (PI.EP2.R) d² - Eu MR Tr(p1, R d (d F/d). (26)
Then, we can use this iteration relationship to construct a geometric sequence, that
Beg Mg Tr (P..nP2.))
1-1
Bahhll Tr(pp,n---222.211) d
d -1
R-1
F-1
Bei TT(P11121)) 1
d
(27)
F F--1)
R-1
F
d- 1
de
d(d 1)
R-1
F
F-1
d(d + T)
where the last equality comes from initial states P1 = P2 10") (0a). Generally, F S d?, then if
F-1 (1) 1/d) log d(d+1)
R
(28)
log(d? dl - 1) log 1t 1)²
we have Ezg, Mi u4 Tr (pr (1,.8e2,,)) 2
18

---

Published as a conference paper at ICLR 2025
G PROOF OF THEOREM
Consider U(a) -I U(ar) is composed of LR two-qubit gates
U(a,) exp
Σ
(r(
@ Piz))
exp(-ii(as Pr)),
(29)
JiJ==0
where P3 E (1,X,Y, } and each at (f1,)2))) E 1-1,1
Using Taylor series, one obtains
LR
(-i(a Pr))*
U(a)
(30)
k!
r= 1=
Denote
(-ilar Pa))
U(
(31)
h!
k=0
therefore U(a,) U(r)).r = _k=K K+1
P.)1
For arbitrary bit-string x, y, we can apply
1d
standard bound Taylor series bound
((n( SKKK
(32)
for some constant
Therefore we have
2
(0" (()
= Σ
P.y (1((0111((())133310))0000
1==0
2
LR
Σ
Σ
Il
(0" (ar)))
Σ
II (I=1U((),))0))
Pij
1,5=0
V1:W/2---MMa
MLR (0.1)"
V1..22m-L _0011)" VLR=)
(33)
2n
(-ilar, Pa))*
Σ Pij
Σ
II
0""
1pr)
k!
1,==
V1 B.-l2-----R----- 10.11"
k=0
VEn=i
(-ila, )*
Σ
II
(r
(0m)
VER- ((01))
k=0
(LA=]
where the V1, 12 ... represent the Feymann integration path. According inequality 32 (yr (a,lU( can be approximated by polynomial of degree K based on Taylor truncated method, the above expression can be rewritten by
21
)) (1.(01....aa.))) -0 ((K]EER
2
2 [KI]LR)
Σ Prs (I((a),...n..) +0 V.smO
(34)
where fr fa11,...aai represents a multi-variable polynomial of degree LRK.
Furthermore, will show that Eq. can be approximated by a low-degree function with at most (I.f) (K)* terms, where q O(1). To show this fact, we rewrite Eq. by
nn
(35)
r==00
'Without loss of generality, assume or (21 [-1, For rotation parameters (o.-(i. E [1. 2m repeat the related twa-qubit gate constant times keep all rotation angles fixing in the interval [-1,
19

---

Published as a conference paper at ICLR 2025
For the convenience of the proof, denote fr (aIR...aLR) fr. Let
J... - Rn
ΣΣ azaj (1,,))) ... of. (i,,22; Ji
where the factor 4 aims 'normalize' each term in the summation, i = (i1, a (LR((1.52)) j2)). J1, E [15] and each < 4 S 2K, / [LR]. For the convenience of the proof, we omit the index (f1:J2) in fr in the following procedure.
Given a constant value q S O(1), for every term like a;a)" ..-." ...a."" with and v > q, its corresponding parameter ag I 1/(K))* (based on Taylor series). Truncate above high-degree terms, and denote
i, K
Σ S So,
aj ... o
(36)
therefore, the relationship
[LL
frf. Froo R
Σ
azaj
inn aLR
Σ An Seg
aj a3,0
.. adu
4
(K1)9
(37)
holds. Above inequality comes from the fact that there are OKK terms in fr where the norm of each truncated term is upper bounded by I O (1/(K)))).
Then let g (1), LR O(n log())))) fr.. can provide an estimation fr within 2 poly(n) additive error according to the Stirling's formula. Specifically, let 1 and use Stirling's 's formula, the error
KLR
4 log K log
4 log K loglog
4 LRR
(38)
(K!)9
K!
(T/((K
Let K = n² log n. one obtains
n log n (n² log m log
(alogn log (ni² log n)) log
V 2n 2 log n n2 log n n? logn log
(n² log n/e ne/e) en² log n
2nn log
(n² log n) log
logn
22m log n
log n
(39)
(e" log n) (log
n log
2nn log
2 n
2nn
where the last incquality holds for large n. Then Eq. 34 can be represented by a muti-variable polynomial function f(ā p) with LR variables and at most (oly(n) terms, and the relationship
100 (Z)) - f(ä p) 2 2-
(40)
holds. Suppose the target observable M = U((x') =00a"")0)))(000))(((( Then may write
Tr(Mp) ~ f(ā" ,) p)
Σ
b b),a())a ... ady.
(41)
(K-1)
Se.... So,
-1 where bj,5(p) - Pr, On other hand, consider machine learning procedure with data
points ((x d; Vi f(ā,, p))) Let the feature map V ((x) (o%) ...2% o22)) a.. and the target is
20

---

Published as a conference paper at ICLR 2025
to synthesis the function f(ä, p) (b(p). (()), where b(p) E E...R." Consider the loss function
Σ ((.)). 1/1 )
min (((()) b(0)
(42)
where À 0 is hyper--araameter. Define the feature matrix v (V( ((xx)) and the
kernel matrix
== v [K(d, a d
(43)
where the kernel function
K
K(a, a') =
Σ Σ
(as,0' + Oig diy''
(44)
I=0 15ih
Without loss of generality, we can normalize K(a,, a') enabling Tr(K) = N. Therefore, the optimal solution
p(p) = ΣΣΣ
v(ā.) (K X1) f(ā,).
(45)
i=1
As result, the trained machine learning model
N
N
g( = (b(p)opt. (())) =
Σ
(K + +1) K(ā,, k))())
1= j=1
(K + A1) K(āū x)) ((a))
(46)
Σ
{z)){((
2
Σ [(aa)0""(()))))))0 + (KI)LR)
Now we analyze the prediction error of g( on the domain [0, 2n LR Denote (z) = ( + [T( f( p)l (g(Ø) f( p)1 + (T(( f(
(47)
< (g( - [ p) + poly(n),
and the expected prediction error
Eg (<()))
Σ
( +
E. (c()))
N Σ (
(48)
Using the Cauchy-Schwarde inequality, the above first term be upper bounded by
x² >E Exn (K + X)) 9:ll
1
(T.)
(49)
N
Therefore, if the matrix K is invertable and hyper-parameter À 0, the training error is zero. Without loss of generality, we set X = 1
The generalized error be characterized by the Rademacher complexity Mohri al. (2018) that is
1
N
sup(K(r, x:)
Tapt llv
[b(()optlle
|
Ege
<(t,) <
(50)
N 1=
N
N
21

---

Published as a conference paper at ICLR 2025
where []b(p)] (b(p))pt. b(p)opt). Ideally, b(p)opt (bz,((0) for j1,.... S K 1, 81 S $2... 8q LR, and b(() is induced by the polynomial kernel function, therefore the 2-norm of the vector (b),(()))j. can be used estimate [|b(p)]l lv- Noting that the multi-variable polynomial function Σj bj, (p)())aa) ... as, belongs to [0, 1] for all o' E [0, 2m] Let takes value from the bitstring 10.1) know that all [,,=(0)) [0. 1]. Therefore, we upper bound [[b(p)]l by (LR)K (LLR)²2oo logn.
Combine all together, for any M(ā) = U ( for U E (A(R) and arbitrary density matrix /4 have the relationship
12 D N En
(K
XD yeus
LRn log
(((=))""("(())))))))))" - Tr Tr (M))))) F5
+
N
N
(51)
In the above first term, hyper-parameter À can take arbitrary value, and À v Amiu (nN))) enables that the first term is upper bounded by 1/n, where Amin (K) represents the minimum eigen- value the kernel matrix K. In the second term, let = Ô ((IR))n& and the above error can be upper bounded by
H PROOF OF QUANTUM LEARNING PRINCIPLES
H.1 PROOF OF LEMMA 2
The proof of Lemma 2 depends on the intrinsic structure the QCA model. Let Mopt represent an observable
max Mopt- arg M v100) (R)
Tr -na/2))
(52)
Given the QCA circuit set ĀQCA (R, A, { with N LRoite the intrinsic structure of QCA promises that there exists vector gont such that
N 3yph (r (U(Z) Tr (T(Mott)) SE
(53)
for any n--ubii density matrix p and projector Po (0") Denote
MR(3) = Σ 8.
according to the assumption in Lemma
we have
e c+ ē < min
E (P
(3) - Py.R))
B
E v. ((
TrMM ) (/ - Pp.
E (.) Ø
Tr(Mop 11 ( Pp.aa) +
(54)
E v. V. Φ
[Top (V, I../2")) Tr(Mope In/2")) +
Mrop (Pp. )n/2")) + c,,
2
where the third line comes from the intrinsic structure of specific quantum circuit architecture, the last inequality comes from E. q 1 and (ool (V,) < 1. As result, have
Tr(Mope (P In/2")) <
2 ē.
(55)
22

---

Published as a conference paper at ICLR 2025
H.2
PROOF OF LEMMA
According to the assumption, the relationship
Tr (( pr.
max T. (.M(A)
E ((u.))(AQca.u qj
(56)
Tr (V) (ovl--o) -01)
Tr (M(3)(pp.
max 4.M(3)
(AG.AA(
2 holds, where maximal entangled state o I/d, d= 2" and M(3) is defined Eq. choose an index t E [N] and let
Randomly
M, =
max 1o
Tr (M) - -)))
(57)
where V e (R)... Based on the intrinsic structure in QCA, there exists unit vector 3 such that
Tr (M.((W.) o)) - Tr (M (M w.) (v.l - o)) Se
(58)
Then assign the probability distribution q: = (N 1)/d and qj 1/d for j & tt. As a result, Eq. |6)caa be further lower bounded by
(1 N d _) Tr (M. o)) + Σ j
Tr [
(()))) -o)) - Ir (
(59)
Since (Vr) is generated by a R-depth quantum circuit U2 E (R()), then Cc((V.)) S LR which implies
Me (W.)\Wal 100_Wall111 -4 2 -c,
(60)
then the relationship
Tr (330) (W,) 1 2) > Ir No (M=)( 2)
E 2 1 - 1
2e (61)
d
holds. Therefore,
(1- Ir (3 (1 ( -o) 2 (1 -- (1- -2).. Combining
the result 1 Tr Tr
- 0)) 2 - where Tr
[ (3 1/ (4,1 o)) >
jstt
-1/d, we thus have
Tr (M -00pppn-o) - (1-1-N11 N-1
1
(N (N-1) 1)
1 N
2e
+
d
d²
(62)
--1
2
3c
2
d
Note that N = I.Rr2 log(n)e -2, -2.d -= 2", therefore
N -
2e
(nly
1
1
22 O(e))
(63)
2
2
for large n E 2 and e = 1/poly(n). Finally,
Tr (M(pp.a-- 1l//²)) > Tr (Milpp.h -l./2m))
max M=V VV
Tr (M( (P, - -I,12*)
(64)
- O(e).
2 -
where the first inequality is valid since M, (defined by Eq. 57) is one of the instances in the set (V]0")(0"[V") the second line comes from the intrinsic structure of QCA, and the third line comes from inequality 62 This implies Cllmm.A (pp.it) LR.
23

---

Published as a conference paper at ICLR 2025
1 BAYESIAN OPTIMIZATION
1.1 OPTIMIZATION SUBROUTINE
In the following, we show how maximize the loss function (R(3) via Bayesian optimization on compact set. Bayesian optimization is composed by two significant components: (i) statistical model, general Goussian process, provides a posterior distribution conditioned on a prior distri- bution and a set of observations over Ca (it) an acquisition function determines the position of the next sample point, based on the current posterior distribution over Ln(
Gaussian process set of random variables, where any subset forms a multivariate Gaussian distribution. For the optimization task considered in the main file, the random variables represent the value of the objective function LR(3) the point B. As distribution over CR( a Gaussian process is completely specified by mean function and covariance oovariancefunctionn
m(3) Eg(CR((3]
(65)
k(3 Eg((Cn(()) - (L))) - (3))))
and the Gaussian process is denoted Lā( (P(m()),k((,,B))) Without loss of gener- ality, we assume that the prior mean function 3(3) In the 1-th iteration step, assuming observations Acc(t) = ((@(1, v(,("))),,...... (300) y ))) are accumulated, where v(3()) = (R( + es. with the quantum measurement error represents the measurement complexity our algorithm. Conditioned on the accumulated ob- servations Acc(t), the posterior distribution of Ln(ß) is a Gaussian process with mean function (3) [g([n(())Aco()) and covariance function ky (B, E (Ln(() (()))())())) m(3')) Aco()), specified by
NoO, 1/4M) for E [4. where M
M+(3) (. I,/4M]- -1 V1st
(66)
Ne (3, k(3, - N. K, + I./4M)
k(3,3t [T the positive definite covariance matrix K; (11,, with = (3(1)) ...., } and yır (((())).....(((()) The poste- rior variance of (ā) is denoted as (و) (. The mean function (x(3) is related to the expected value of CR(B), while the covariance k, estimates the deviations of pt (3) from the value of (3). Then the prediction is obtained by conditioning the prior Gaussian process on the observations and returns posterior distribution described by Gaussian process multivariate distri- bution. Using the
where k; = (k()
Woodduur formula (Seeger 2004), the predictive distribution can be explicitly expressed Eq. 66
In the I-th iteration of Bayesian optimization, the acquisition function A(ğ) learns from the aceu- mulated observations Acc(t - 1) and leads the search to the next point g0(0 which is expected to gradually convergence to the optimal parameters of CR(B). This procedure is achieved via maxi- mizing A(5). In detail, the design of acquisition function should consider exploration (exploring domains where LR(3) has high uncertainty) and exploitation (exploring domains where (R(3) is expected to have large image value). The upper confidence bound is a widely used acquisition function, which defined as
AVeR (5) = 1::0=(--1(6 ( + (oTo:-1(3)
(67)
and the next point g(t) is decided by g]t) arg max Be AUC Here, Kr is significant hyper-parameter, and a suitable K₂ may lead (Lt)) rapidly convergence Bopt- In Theorem 4 specific K4 = 2NV N) + 22 1ogg(t//)) is used. Details for maximizing (3( are shown in Alg
24

---

Published as a conference paper at ICLR 2025
Algorithm 2: Bayesian Maximize Subroutine, B. PQCA A, A,,,
Input Noisy quantum state Pum- quantum state set PQCA (R, N), failure probability de (0, 1), iteration steps T, approximation error
Output: True/False;
Initialize (3) 0, on the covariance function k(;:);;
for / 1, 2, 7 do
Select H2 2N log(t 2 N) 2og(t?2
Choose { arg max 1 ( + ( (3): BED;
Estimate ((()) with shadow tomography of Pun and PQCA (obtained from M-snapshot measurements), that is v(B()) CR(Blt) S Et where & NN(0, 1/4M);
Update (zx, of Eq.
(B e do
return True
else do return False
10
1.2 PROOF OF THEOREM
Theorem (Formal version of Theorem 4) Take the weakly noisy state Pun and POCA A
into Alg. 2 Pick the failure probability 8 E (0, 1) and let
Kt 2N log (12 N) 2 log (
(68)
in the t-th iteration step, then the average regret avIT can be upper bounded by
4.N T 2N log log( (0g(2(((6)))
avIr SO
(69)
T
with success probability.
We need following two lemmas to support our proof.
Lemma (Lemma 5.1 in Srinivas et al. (2012)) Pick faliure probability E (0, 1) and set Ki llog[ (dommiin| Te (), where Σ1>1 nh and mi > Then
[(3) - (3-)
1/2 $ k4
(70)
holds for any and 3 E Domaain
Lemma (Lemma 5,4 in Srinivas et al. (2012)) Pick failure probability 5 E (0, 1) and let Kt be defined as 3 Then the following holds with probability 1-8:
Σ
i S KT
(71)
1=1
where "T mmax AEDommain 2 log / - - KA and KA A represents the used covariance matrix in
Bayesian optimization.
We first consider the continuity of the loss function L(3). Considering ΣN Br 1, the gradient function can be upper bounded by
ac(3) 03,
E TT Pun))l
(72)
25

---

Published as a conference paper at ICLR 2025
where the inequality comes from [Tr (py Puu)]l S 1. Therefore, the relationship
[( - -(3') 3
(73)
holds for any 3, E Domain Now let us choose discretization D Domaain of size (T.) such that for all B E D Domainn
|| 13,1 N/To,
(74)
where [3], represents the closest point in discretization on D to B. Combine Eqs. 73 74 one obtains
[(3) - [((3))) S N =t
(75)
where the last inequality comes from Tr = N2N, furthermore, [D (f2N)
Using Lemma
3
we know that
K₂ = 2 log( (Demmmiil (
(76)
enables the relationship
[ -L-1((3 S V
(77)
holds with probability least 6, where a 0 and Σ1>1 a 1. A common selection is = (1) into Ki (Eq. 76 one obtains
a₂ =12/// /6. Taking DD Ddomain
Ke = 2 log 1//
(78)
Combine Eq. 75 and 77 have
((3") - -1-1((3))) < (( -(17)))) - - st² (M(o)-1(0011)
(79)
for any 2 1, where 3 arg max BED, C(B). Now we connect the relationship between above inequality to the regret bound.
By the definition of g (maximizing the Aucn(3 in the 1-th step): ( + 1 2 p ([=))) ((²*).). Also, by Eq. 79 have L(3*) pt- ((3))) (
1/12. Therefore, instantaneous regret
rt -(g-) C(3(1))
< V (3311)
1/122 2 + μ4 11 (B3(0) L(((())
2 2 +1 1/12
where the last inequality comes from Eq. 77 Using Lemma 4 ET 4kror-1 KT where
2 log 1
2M2
7T
max
AE
KA represents the used covariance matrix in BMaxS fo PQCA R, A, N), T) and M represents the number of measurement in generating the shadow tomography. the linear function case, KA can be selected as the polynomial kernel function, and pr O(N log(T)) Vakili al. (2021) Furthermore, using the Cauchy-Schward inequality to I 1 S Br one obtains
Σi 2x 1/2 (.)) VTETTT
26

---

Published as a conference paper at ICLR 2025
Finally, we have the result
1
aviT
F1
T
t=1
T
n²a
2kg
1/2
(3.)
67
KTYT
π²
(80)
T
6T
2N log (T 2N Log(TTTT (65) log (T)
T
4N2 log" T + 2N log T log( (
00
T
where the first inequality results from Σi21 1- = 7² and the last inequality comes from $
J PROOF OF SAMPLE COMPLEXITY LOWER BOUND
we require the following lemmas to support our proof.
Lemma (Lemma in Wang al. (2021) Consider a single instanoise channel N N2 N18... 11.8..0
Nn where each local noise channel (Nif== is Pauli noise channel that satisfies N2((r) 9,0 for E (X and ya be the Pauli strength. Then we have
Ton
D2 N(P)
S
20
D2
pl
(81)
2
n
where D2(-1-) represents the 2- 2-Renyi relative entropy, q max, Oa and 1/(2ln2).
Lemma 6 Given an arbitrary n-qubit density matrix and maximally mixed state I /2", have
D (pll @n (2"") < D2 (pll18m/2"))
(82)
where D(-II-) denotes the relative entropy and D2(-Il-) denotes the 2-Renyi relative entropy.
Proof: Given quantum states p and a, the quantum 2-Renyi entropy
(o-1/4 1/4 por 1/4 -/-
D2(pll0) log Tr
(83)
When σ = 10 /2", we have (2(p) pn /2") = log Tr [(I 12000/2----"00 = n+log [r]p Noting
that the function y = xlog x 2 when x E [0, 1}. and this implies Tr(p²) 2 Tr(p p). Finally, we have
D T 12") = Tr Tplpgg + S Tr [p]] +n D2 (pIlT8n/2")
(84)
Task Consider a pure quantum state and two quantum circuit C₁ and C2 with Rí and R2 depth (Ri <. R2), respectively. Each quantum circuit is affected by by p-strength Pauli channel in each layer. Suppose that distinguisher is given access to copies of the quantum states Pe, (po) and
Pc, (po). then what the fewest number of copies sufficing to identify quantum states te. (po) and Pc,(Po) (Po) with high probability?
Obviously, if quantum state complexity prediction problem can predict the complexity R, and Rg. then classify quantum states &c, (po) and &c, (Po) easily. The sample complexity of Task
27

---

Published as a conference paper at ICLR 2025
thus can be used benchmark the sample complexity lower bound of the quantum state complexity prediction problem.
Now prove the sample complexity lower bound to Task 2 We consider the sample complexity m in distinguishing quantum states Pc, (Po) and (p)). When their trace distance is quite large, let 5 E (0, 1) and we have
1
1- 8 ~ Pe, (po) 8mm Pc2 (Po) (00
1
- 4c, (po)sm
8m (4n/ ) + || de., (po) (
(85)
$ V2 (DV2 (&& (po) (1 )om)) 122
@ (po) (L (2)))))mm)))
where the second line comes from the triangle inequality and the third line comes from the Pinsker's inequality. Using Lemmas 5 and 6
we have
1-85
12 2m (P))[((I
+ 1222 (0e 80m
(pu)l((Tn/2"0000
V2
V2 ((1 - p) + (1 - p))
/um
(86)
S V 2n p)
As result we have
(1 2oR (1 5)2
(87)
2n
K REVIEW OF SHADOW TOMOGRAPHY
In quantum computation, the basic operators are the Pauli operators {I,o", ,", which provide a basis for the density operators of single qubit well for the unitaries that can be applied to them. For an n-qubit case, one can construct the Pauli group according to
PA = {e fo /2
8 e nn' live E (T, v. v,=), I k S n):
where 2 E {0, +1, -i} is a global phase. Then the Clifford group C1(2") is defined as the group of unitaries that normalize the Pauli group:
C1(2") = (viUPo0 = pP2)
(pm), (2) E PP..)
The n-qubit Clifford gates are then defined elements in the Clifford group Cl(2"), and these Clifford gates compose the Clifford circuit.
Randomly sampling Clifford circuit U can reproduce the first 3 moments of the full Clifford group endowed with the Haar measure du(U) which the unique left- and right- invariant measure such that
du(U)f(U)- = f du(U))(VU)) du(U))(UV) /
c1(2)
for any f(U) and V E CI(2"). Using this property, sample Clifford circuits U CI(2") with the probability Pr(U), and the corresponding expectation E @1 can be ex- pressed as
Σ
Pr(U) (UpU1) 31
Jape dy(U) (UpUt)
UECI(2")
for any n-qubit density matrix P and 1,2, where Pr(U) indicates the probability sampling U. The right hand side of the above equation can be evaluated explicitly by representation theory, this thus yields closed-form expression for sampling from Clifford group.
To extract meaningful information from an rt-qubit unknown quantum state p. the shadow tomog- raphy technique was proposed by Huang al. 2000). The Clifford sampling is implemented by
28

---

Published as a conference paper at ICLR 2025
repeatedly performing simple measurement procedure: apply a random unitary U E CI rotate the state and perform a ---bssis measurement. The number of repeating times of this proce- dure is defined as the Clifford sampling complexity. On receiving the n-bit measurement outcome 16) E {0, I according to the -ottesman-Knill theorem (Gottesman) 1997). we can efficiently store classical description of U (T]]))(B( in the classical memory. This classical description en- codes meaningful information of the state from a particular angle, and it is thus instructive to view the average mapping from P its classical snapshot U 6)) (blU' as a quantum channel:
) to
M(p) = E (0.1)- [ (b) (b|U))
(88)
where the quantum channel M depends on the ensemble of unitary transformation, and the quantum channel M can be further expressed as
P+ Tr(p)4
M(p) EUECI(2))
Σ BE(0,13
(89)
(2" + 1)2n
where I indicates the 2n 2" identity matrix. Therefore the inverse of quantum channel M-1(p) (2 + 1)p I, and an estimation of is defined as
ύ= -- (U
Repeat this procedure M times results in an array of Clifford samples of p::
S(p { = M (1>00)))).) = - (U (br)
(90)
and 1 MI Em=1 Pm is defined as the classical shadow of the quantum state p.
L NUMERICAL SIMULATIONS FOR STRESS-TESTING
Here, we conducted stress testing of the quantum learning algorithm in this study. Specifically, applied the algorithm to estimate the complexity lower bound of quantum states under noisy environments for oieedimensional dynamical evolution. We tested the transverse-fied fieel Ising model with system sizes of x 6, x and 1 x 10, and the numerical results are presented in Figure Our findings indicate that the complexity lower bound of noisy quantum circuits does not grow linearly with circuit depth, which consistent to the results given by Figure in the main file.
Furthermore, we observed that as the system size and complexity increase, the curves corresponding to two different quantum states, R = 2 and R 10, exhibit similar overall trends for the system size n {6, 8, 10). Moreover, the variance of the algorithm does not increase with the growing system size but remains consistently stable. At the same time, the gap between the curves of quantum states with different complexities does not show a closing trend as the system size grows. These characteristics demonstrate the robustness of our learning algorithm against increases in system size and complexity. Therefore, our algorithm remains reliable for predicting the complexity large- scale weakly noisy quantum states.
29

---

Published as a conference paper at ICLR 2025
A-2
A-2
0.7
0.6
0.5
0.5
0.35
0.4
0.4
n1
0 0.30
10
0.3
0.25
0.2
0.2
0.20
0 0.15
0.1
0.1
3.5
4.5
0 10
2.0
2.5
3.5
4.5
Figure 3: These three subfigures illustrate the trend of the function min g L as it varies with the circuit depth R of QCA set.In the stress-testing experiments, focus the Hamiltonian dynamics of ID transverse field Ising models, with system sizes ranging from to 10. all cases, we observe that the weakly noisy state with R = exhibits larger quantum state complexity lower bound compared to the weakly noisy state with 10.
30


Reviews:
[{"review_id": "q2jjCwO8IM", "reviewer": "Reviewer_m7qv", "summary": "This paper investigates a fundamental question in quantum state complexity: how to predict/learn the complexity of weakly noisy quantum states. The authors develop an efficient learning algorithm that:\n\n1. Uses classical shadow representation of quantum states\n2. Provides optimal sample complexity with polynomial classical processing time\n3. Works specifically for weakly noisy states (noise strength O(1/n) and depth O(poly log n))\n\nThe main contribution is establishing an efficient algorithm for learning quantum state complexity in noisy environments.", "questions": "Could the authors provide further clarification on how it is possible to predict the circuit complexity of a state in polynomial time? There are a plethora of existing results proving that circuit complexity is not efficiently learnable. Assuming the claims given in this work are correct, could the authors provide a detailed exposition for how this seemingly contradictory statements can be resolved?\n\nCould the authors provide numerical simulations demonstrating their learning algorithm's performance on concrete examples of noisy quantum states? This would help validate the theoretical guarantees and provide intuition about the practical performance.\n\nThe paper focuses on weakly noisy states with specific noise parameters (O(1/n) strength and O(poly log n) depth). Could the authors comment on whether similar techniques could be extended to more general noise models or stronger noise regimes? If not, could the authors describe if stronger results are simply impossible for any learning algorithm?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The algorithm is rigorously analyzed with provable guarantees on both sample and computational complexity.\n\n- The work studies quantum state complexity in noisy environments which better reflect real quantum devices.\n\n- The approach cleverly leverages classical shadows and intrinsic properties of quantum circuit architectures to make the learning problem tractable.\n\n- The sample complexity is shown to be optimal with respect to circuit depth.", "weaknesses": "- It is well known in quantum complexity theory that the circuit complexity of a quantum state cannot be efficiently learned [1, 2, 3]. For example, the existence of pseudorandom states that can be generated in polylog depth on 1D circuits [3] immediately implies that no polynomial-time quantum algorithm can distinguish between polylog circuit complexity (complexity defined in terms minimum circuit depth) and exponential circuit complexity. Hence, it is not possible to predict complexity of a state in polynomial processing time without first solving quantumly hard cryptographic problems. I find it very confusing that the authors claim to predict circuit complexity in polynomial time.\n\n- Despite the focus of practical importance (the presence of noise), the paper did not provide any numerical experiments to validate the theoretical claims (including both efficient sample and computational complexity). I think it is important for this work to have supporting numerical experiments for system size that scales to 50-100 qubits.\n\n- While the paper focuses on weakly noisy states, it's unclear how the approach would scale to more general noise models or stronger noise regimes. I think the work did not provide enough justification for the focus on weakly noisy states.\n\n[1] \"Pseudorandom quantum states.\" Advances in Cryptology–CRYPTO 2018.\n[2] \"Quantum pseudoentanglement.\" arXiv preprint arXiv:2211.00747 (2022).\n[3] \"Random unitaries in extremely low depth.\" arXiv preprint arXiv:2407.07754 (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MZouDiHqDe", "reviewer": "Reviewer_eyDN", "summary": "The paper proposes a quantum learning algorithm to predict the complexity of weakly noisy quantum states. The authors introduce the concepts of Weakly Noisy Quantum State and Limited-Structured Complexity and prove that their algorithm achieves optimal sample complexity with respect to their definition of noisy circuit depth. They also provide a lower bound for sample complexity. This work also shows meaningful connections between learning algorithms and quantum state complexity.", "questions": "- Could you provide a more compelling motivation for studying weakly noisy quantum states? How do they relate to real-world quantum systems, and what are the potential applications of your findings?\n- Given that quantum noise can accumulate rapidly in depth significantly in each quantum system, how does your proposed learning approach remain feasible in practice? Why gate-independent noise channel? Please clarify the practicality of your noise model and its implications for the scalability of your method. Better to compare with an explicit circuit model example.\n- Several parameters in the theorems, such as Theorem 4, are not clearly explained. Could you provide more context and explanations for these parameters to improve the readability of the paper?\n- The use of the same letter R to define both the noise numbers in the definition of Weakly Noisy Quantum States and the regrets in later sections is confusing. Please consider using different notations for clarity and consistency throughout the paper.\n- To support the effectiveness and practicality of your proposed algorithm, could you provide detailed examples that illustrate its workings and benefits?\n- Do you assume quantum noises in the main algorithm 1?\n- Numerical experiments on benchmark datasets or simulated quantum systems would strengthen the empirical evidence for your method. Could you include such experiments to demonstrate the performance of your algorithm in various settings?\n- While your paper introduces a new quantum learning algorithm, it would be helpful to provide a more comprehensive comparison with existing methods in the field of quantum learning theory. Could you discuss how your approach differs from and improves upon prior work?\n- Could you elaborate on how your work on learning the complexity of weakly noisy quantum states is relevant to the broader ICLR community?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper studies a fundamental problem of understanding the learning complexity of noisy quantum states, which has potential applications in various fields claimed for black-hole theory and condensed-matter physics. The authors propose a novel quantum learning algorithm that leverages the intrinsic structure of quantum circuit architectures to predict the complexity of weakly noisy quantum states. The theoretical analysis provides provable guarantees on the sample complexity and efficiency of the proposed algorithm.", "weaknesses": "- The setting of weakly noisy quantum states is not well-motivated, and it is unclear how the proposed learning approach can be feasible in practice. The accumulation of quantum noise on each quantum system can be significant, and the considered noise model may not be sufficiently practical or meaningful. Not sure about the the noise channel is assumed to be gate-independent.\n- The paper is difficult to follow, with various parameters in the theorems that are not clearly explained (e.g., Theorem 4). The use of the same letter R to define both the noise numbers in the definition of Weakly Noisy Quantum States and the regrets in later sections adds to the confusion.\n- The paper does not provide detailed examples or numerical experiments to support the proposed algorithm's effectiveness and practicality. This lack of empirical evidence makes the results less convincing.\n- It is not very clear to me whether the main algorithms consider quantum noises.\n- It is not convincing that the results are of a broad interest in the ICLR community.\n- The results presented in the paper do not appear to be particularly surprising or groundbreaking in the field of quantum learning theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A0jMlDmm8L", "reviewer": "Reviewer_wYLf", "summary": "The paper proposes a quantum learning algorithm that estimates the complexity of weakly noisy quantum states, unlike prior research focusing primarily on pure states, thereby connecting theoretical principles to practical scenarios observed in real-world quantum devices. The proposed algorithm is based on quantum circuit architecture (QCA) combined with classical shadow representation. It reaches near-optimal sample efficiency in the estimation of state complexity, which is theoretically analyzed in this paper to underscore its efficacy. The paper points out several promising research studies that may open up when the expressivity of QCA can be improved, and methodologies for direct complexity predictions in noisy quantum states are developed.", "questions": "1. Could the authors elaborate on specific quantum hardware requirements for implementing the algorithm? Are there particular quantum systems where the algorithm's performance has been or can be practically tested?\n\n2. How does the algorithm perform under different types of quantum noise models? Is the accuracy in the complexity predictions different between, e.g., local-depolarizing versus global-depolarizing channels?\n\nThe paper could be enhanced by considering the following suggestions:\n\n- The paper should include a more detailed discussion of the computational and practical limitations of the algorithm (for example, stress-testing the algorithm under increased complexities and reporting on its degradation or stability performance.)\n- Incorporating key proofs and insights from the appendices into the main body would enhance the paper's value, as some essential concepts, like the subroutine BMaxS, are only briefly mentioned in the main text.\n- It would also be very useful if the manuscript provided a framework for empirical testing and validation of the algorithm, including benchmark selection and metrics of validation. This would help bridge the missing gap between theoretical research and practical applications and give a much stronger justification for the effectiveness of the algorithm in noisy quantum environments.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper confirms that the proposed approach can handle such complex quantum states even in noisy environments, validated through a robust theoretical framework based on theorems and proofs, including the sample complexity and the efficacy of Bayesian optimization in the noisy quantum environment.\n2. The application of classical shadow representation in quantifying the complexity of weakly noisy quantum states is novel and crucial from a quantum perspective. This subsequently gives way to efficient quantum information processing classically, making the theoretical methods introduced more feasible.", "weaknesses": "1. The paper acknowledges that the proposed algorithm approximates the complexity of noisy quantum states and refers to further research on more direct prediction methods. However, it would benefit from an in-depth analysis of limitations, such as sensitivity on different noise models or how scaling issues may affect deployment to larger quantum systems.\n2. The paper lacks a detailed discussion of the specific hardware requirements and the practical steps needed for real-world implementation. Details such as compatibility with existing quantum hardware, scalability in practical quantum systems, and specific technological constraints are not thoroughly explored.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)