Symmetric Pruning in Quantum Neural Networks
Authors: Xinbiao Wang
Junyu Liu
Tongliang Liu
Yong Luo
Yuxuan Du
Dacheng Tao
Venue: ICLR 2023 notable top 25% (2023)
Keywords: quantum neural networks
symmetry
pruning
quantum neural tangent kernel
effective dimension

Abstract: Many fundamental properties of a quantum system are captured by its Hamiltonian and ground state. Despite the significance,  ground states preparation (GSP) is classically intractable for large-scale Hamiltonians. Quantum neural networks (QNNs), which exert the power of modern quantum machines, have emerged as a leading protocol to conquer this issue. As such, the performance enhancement of QNNs becomes the core in GSP. Empirical evidence showed that QNNs with handcraft symmetric ans\"atze generally experience better trainability than those with asymmetric ans\"atze, while theoretical explanations remain vague. To fill this knowledge gap, here we propose the effective quantum neural tangent kernel (EQNTK) and connect this concept with over-parameterization theory to quantify the convergence of QNNs towards the global optima. We uncover that the advance of symmetric ans\"atze attributes to their large EQNTK value with low effective dimension, which requests few parameters and quantum circuit depth to reach the over-parameterization regime permitting a benign loss landscape and fast convergence. Guided by EQNTK, we further devise a symmetric pruning (SP) scheme to automatically tailor a symmetric ansatz from an over-parameterized and asymmetric one to greatly improve the performance of QNNs when the explicit symmetry information of Hamiltonian is unavailable. Extensive numerical simulations are conducted to validate the analytical results of EQNTK and the effectiveness of SP. 

Published as a conference paper at ICLR 2023
SYMMETRIC PRUNING IN QUANTUM NEURAL NET- WORKS
Xinbiao Wang Junyu Liu3.4.5,6, Tongliang Liu", Yong Luo Yuxuan Du Dacheng Tao?
'Institute of Artificial Intelligence, School of Computer Science, Wuhan University, China RJD Explore Academy "Pritzker School of Molecular Engineering, The Universily of Chicago *Chicago Quantum Exchange "Kadanfff Center for Theoretical Physics "qBraid Co. "Sydney AI Centre, The Universily of Sydney, NNtional Engineering Research Center for Multimedia Software, School of Computer Science, Institute of Artificial Intelligence and Hubei Key Laboratory of Multimedia and Network Communication Engineering, Wuhan University, China Hubei Luojia Laboratory, Wuhan, China f: corresponding author
ABSTRACT
Many fundamental properties of a quantum system are captured by its Hamiltonian and ground state. Despite the significance, ground states preparation (GSP) is classically intractable for most large-scale Hamiltoni- ans. Quantum neural networks (QNNss, which exert the power of modern quantum machines, have emerged as leading protocol to conquer this is- suc. As such, the performance enhancement of QNNs becomes the core GSP. Empirical evidence showed that QNNs with handcraft symmetric an- sälze generally experience better trainability than those with asymmet ansätze, while theoretical explanations remain vague. To fill this knowledge gap, here we propose the effective quantum neural tangent kernel (EQNTK) and connect this concept with over- parametrrizaiion theory to quantify the convergence of QNNs towards the global optima. We uncover that the ad- vance of symmetric ansätze attributes to their large EQNTK value with low effective dimension, which requests few parameters and quantum circuit depth to reach the over-parameterization regime permitting a benign loss landscape and fast convergence. Guided by EQNTK, we further devise a symmetric pruning (SP) scheme to automatically tailor a symmetric ansatz from an over-paras weeetparaeteriiee and asymmetric one to greatly improve the per- formance of QNNss when the explicit symmetry information of Hamiltonian is unavailable. Extensive numerical simulations are conducted to validate the analytical results of EQNTK and the effectiveness of SP.
INTRODUCTION
The law of quantum mechanics advacases that any quantum system can be described by Hamiltonian, and many important physical properties are reflected by its ground state. For this reason, the ground state preparation (GSP) of Hamiltonians is the key to understanding and fabricating novel quanturn matters. Due to the intrinsic hardness of GSP (Poulin & Wocjan 2009 Carleo et al. 2019), the required computational resources of classical methods are unaffordable when the size of Hamiltonian becomes large. Quantum computers, whose operations can harness the strength of quantum mechanics, promise to tackle this problem with potential computational merits. In the noisy intermediaaee-caale quanium (NTSQ) era Preskill] 2018), ) quantum neural works (QNNs) (Farhi & Neven, 2018: Cong al. 2019 Cerezo et al. 202 are leading candidates toward this goal. The building blocks of QNNs, analogous to deep neural networks, consist variational ansätze (also called parameterized
quantum circuits) and classical optimizers. In order to enhance the power of QNNs in
GSP, great efforts have been made to design advanced ansätze with varied circuit structures
Peruzzo et al. 2014 Weeker et al., 2015 Kandala et al., 2017).
Despite the achievements aforementioned,, recent progress has shown that QNNs may suffer from severe trainability issues when the circuit. depth of ansätze is either shallow deep.

---

Published as a conference paper at ICLR 2023
Namely, for the deep ansätze, the magnitude of the gradients exponentially decays with the increased system size (McClean et al.) 2018 Cerezo et al. 2021b). This phenomenon, dubbed the barren plateau, hints at the difficulty of optimizing deep QNNs, where exponential runtime is necessitated for eonvergence. The wisdom to alleviate barren plateaus
is exploiting shallow ansätze to accomplish learning tasks (Grant et al.] 2019 Skolik al.
2021 Zhhang et al.] 2020; Pesah et al.) 2021b, while the price to pay 18 incurring another
serious trainability issue convergence (Boyd & Vandenberghe 2004 Du et al. 2021). The
trainable parameters may get stuck into sub-optimal local minima or saddle points with high probability bocause of the unfavorable loss landscape (Anschuctz) 2021 Anschuetz &
Kiani 2022). Orthogonal to these negalive results, several studies pointed out that when the depth of ansälze becomes overwhelmingly deep and surpasses a critical point, the over- parameterized QNNs embrace benign landscape and permit. fast convergence towards good local minima (Kiani et al. 2020 Wiersema et al. 2020 Larocca et al., 2021b). Nevertheless, the criteria to reach such critical point is stringent, i.e., the number of parameterized gates or the circuit depth scales exponentially with the problem size, which hurdles the application of over- nen--paraetterieed QNNs in practice.
Empirical evidence sheds new light on exploiting over- parameterized QNNs to tackle GSP. QNNs with sym- metric ansätze only demand a polynomial number of trainable parameters and the circuit depth with the problem size to reach the over wer-parameterized region and achieve a fast convergence rate (Herasymennko &
Under-paramen Under-parametertzed
O war-pparaeterrzeed
Slow convergence Local minimum
Fast convergence Global minimum
O'Brien 2021 Gard et al. 2020
Zheng et al.
2021
2022 Shaydulin
Wild 2021;
Mernyei ct al.
2022
Marvian 2022; Mever et al. 2022
Larocca et al. 2022
Sauvage et al. 2022). A common leature these sym- metric ansätze is capitalizing on the symmetric prop- erties underlying the problem Hamiltonian to shrink the solution space and facilitate seeking near-optimal solutions. Unfortunately, current symmetric ansätze are inapplicable to a broad class of Hamiltonians whose symmetry is implicit, since their constructions rely on the explicit information for the symmetry of Hamiltonians. Besides, it is unknown whether the symmetry contributes lowering the critical point to reach the over-paramettriiation regime.
critical point
parameterized gate
The critical point of the peeepparamteerieed regime. When the number of parameters beyond the critical point (the red circle), the training error exponentially converges to a nearly global minimum. Symmet- ric ansätze (the blue curve) require few parameters to reach the critical point over the asymmetric ansätze.
Figure I:
Here we fill the above knowledge gap from both theo- retical and practical aspects. Concretely, we develop a novel notion effective quantum neural tangent ker- nel (EQNTK) to capture the training dynamic of var- ious ansätze via their effective dimension. In do- ing so, we expose that compared with the asymmetric ansätze, the symmetric ansätze possess dramatically lower effective dimensions and the required number of parameters and circuit. depth to reach the wee-parrameterizaiinn may polynomially scale with the problem size (see Fig. for an intuition). By leveraging FQNTK, we next prove that when the condition of parararrttttiiiiiioonn is satisfied, the trainable parameters of QNNs with symmetric ansätze can exponentially converge to the global optima with the increased iterations. Taken together, our analysis recognizes that over- parameterized QNNs with symmetric ansätze is possible solution toward large-scale GSP tasks. Envisioned by EQNTK and pruning techniques in deep neural networks (Han et al, 2015 Blalock et. al. 2020; Frankle et. al.) 2020 Wang et al. (002). we further devise symmetric pruning scheme (SP) to automatically lailor a symmetric ansatz from an peer-porameterized and asymmetric one with the enhanced trainability and applicability. Conceptually, SP continuously eliminates the redundant quantum gates from the given asymmetric ansatz and correlates parameters to assign different types of symmetries on the slimmod ansatz. In this way, SP generates a modest-dopth symmetric ansatz with a fast convergence guarantee and thus improves the hardware efficiency. Extensive simulations on many-body physics and combinatorial problems validate the theory of EQNTK and the
2

---

Published as a conference paper at ICLR 2023
efficacy of SP. These results deepen understating about how to merge symmetry with over rreeeparamtttiiiaioon theory and indicate the signification of designing symmetric ansätze.
Contributions. We summarize main contributions as follows:
1. We propose the notion of EQNTK to quantify the training dynamics of QNNs with symmetric ansätze, which reconciles the QNTK theory with the symmetry of the problem Hamiltonian (scc Sec. 2.2 As shown in Fig. [ since the train- ing dynamic between symmetric and asymmetric ansätze is evidently disparate, our results provide deep understanding towards QNNs with symmetric ansätze, especially for unraveling how the structure information effects the convergence rale.
2.
Our key technical contribution is achieving tighter convergence bound of QNNs with various symmetric ansätze (see Theorem 2 and Lemma D. Particularly, our bound yields 7 = Opooy(LK,, def ")); where LK is the number of parameters and doff is the effective dimension. The comparison with prior results is summarized in Table [] Our results not only greatly reduce the threshold parameterization but promise improved convergence rate. These two conclusions are indispensable in applying over rreapaaameterized QNNs to solve practical problems.
reaching over-
Larocra nl. 2021b [dpo))
Anschuets 2021
You al. 2022
Liu et al. 2022b ((expta)) loof
Our results (polyyddaa)) de lox!
[[exp[n]]
U(poly(dar))
x
X
((log(derr) (og(
o
Table 1: A comparison of the convergence rate for over-parameterized QNNs. The label 'C' and "T" refers to the critical point and e-convergence rate respectively. 'he label "X" denotes that the paper did not study certain regimes. Note that the achieved results in Ref. (Laroccal al. 2021b do not exhibit how the problem Hamiltonian effects der.
3. Our last contribution is devising SP, an automatic scheme to identify the implicit symmetries of the problem Hamiltonian and utilize them design symmetric amsatz (see Section 3 An attractive feature of SP is its flexibility, where any heuristic that has the ability to capture certain symmetries of the problem Hamil- tonian can be scamlessly embedded into SP to further boost its performance.
EFFECTIVE QNTK ALLOWS AN IMPROVED CONVERGENCE OF QNNS
Here we establish foundations about why symmetric ansätze have the ability to enhance the trainability of QNNs in ground state preparation (GSP) tasks. To do so, we propose novel concept effective quantum neural tangent kernel (EQNTK), to reconcile the QNTK theory with the symmetry of the problem Hamiltonian. Attributed to EQNTK, we uncover that the advance of symmetric ansâtze originates from their ability to dramatically decrease the over- parameterization Uhreshold. For elucidating, we first interpret the necessary backgrounds in Sec. 2. and then present our main theoretical results in Sec. 2.2
2.1 PROBLEM SETUP
Ground state preparation. Given an n-qubit Hamiltonian H E x2", GSP aims to find the eigenvector (b*)) e C (i.e., the ground state) of H corresponding its minimum eigen- value. For any n-qubit state 115), the variational principle ensures (w**) H (x**) & (1b) H ())
and the equality is satisfied iff (1)) (b**). Since the dimension of (1*)) scales exponentially with n, GSP is classically intractable for a large n.
Quantum neural networks. A QNN can be described by a triplet (Ivo) U(),, H). When it is applied to solve GSP, an ansalz U(0) (i.e., a parameterized unitary) prepares a varia- tional state (0)) = (@) /2/) with fixed input state (10).. The parameters 0 are optimized by minimizing the loss function
(( = ((vb) U(0) HU(O) ((b) Ea)
(1)
3

---

Published as a conference paper at ICLR 2023
where Eg [150| H (/*)) refers to the ground state energy of H. The optimization follows an iterative manner, i.e. the classical optimizer continuously leverages the output of the quantum circuits to update 0 and the update rule is @(++1) 0()) n where refers to the learning rate. See Appendix A for details.
Remark. We adopt Eg to facilitate the convergence analysis and results cover general loss functions where Eg is replaced by C E R with C. I Eg. See Appondix B for details.
Constructions of (symmetric) ansätze. The power of QNNs depends on the employed ansalz (0)). A general form of (() covering many typical ansätze such as Hamillonian variational ansatz (HVA) and hardware efficient ansatz (HEA) (Bharti et. al., 2022
Qian
et al. 2021 yields
K ((0) = II UN))), U2(O,) = II k=1
e G
(2)
8=1
where L refers to the layer number,
(0,.... Or.) E O C RLK is trainable parameters
living in the parameter space θ O2 00==00 Oek) is trainable parameters at the f-th layer,
and A = {G1. ......... Gx} is a set of Hermitian traceless operators called an ansatz design. Given O and A, set of ansätze forms a subgroup of SU(2") with Uy U (U(() E θ). The difference of ansätze originates from the varied @ and A. Given a Hermitian matrix Σ, the ansatz (0) is said to be symmetrie with respect to Σ if each element in UA is commutable with Σ. Mathematically, denote Σ = ン E Ay where Xÿ is the eigenvalue with A, * A for i # j, Vyk is the corresponding eigenvector, and Σ)= The explicit form of E leads to a direct sum decomposition H. V of the quantum state space, where V, is the invariant subspace spanned by the eigenvectors (U)1,-.. U.s,}.
2".
Convergence of QNNs. A crucial metric to assess the performance of different QNNs is the e-convergence rate towards the global minimum L(0") with 0" minge L(0). Definition (--covvrgencee).
QNN instance (woo), U()). H) achieves an 6-converyence if the trained parameters after T iterations ((T) satisfy ((((T)) S with c c R.
This quantity measures the distance between the estimated and the optimal loss values, which can be derived via the quantum neural tangent kernel (QNTK)
Q = VE Ve,,
(3)
where e = (M/l ( Wo) Eg denotes the residual training error and Ve, is the gradicnts of Et with respect to 0. The following thcorem describes the e-convergence of the wver-parameterized QNN with an arbitrary ansatz.
(U()
Theorem 1 (Liu et al. (022b)), ). Following notations in Eqns. i when (0)) matches the Haar distribution up to the fourth moment, the number of parameters satisfies LK > 1, and the learning rate n7 < 1, the training dynamics of a QNN instance (Iyo) U (0), H) yields
6, = (1 Tt))=E R E e
(4)
where = = Q is the indicator of the decay rate and Q = (H2)/44))))4 refers to the expectation of Q Haar average.
It indicates that the critical point to reach the over prre-aaraettiiiiiioonn region is 0
(44"/(1) Tr(H)))). In this setting, the exponent in Eqn. (4) meets O(1) and promises an exponential convergence. Besides, Eqn. (4) hints that the convergence rate of QNNs continuously enhanced by increasing the value of QNTK, which can be achieved by growing the number of parameters or decreasing the system size.
2.2 EFFECTIVE QUANTUM NEURAL TANGENT KERNEL
The exponential scaling behavior with the number of qubits n in Theorem causes the realization of the over-parameterized QNNs be impractical for large systems. Moreover, the corresponding convergence rate is independent of the refined structure informa- tion of ansätze. This contradicts with the empirical evidence such that symmetric ansätze outperform asymmetric ansätze with fast convergence in training QNNs. It thus highly demands carrying out new thcories to stress these issucs.
4

---

Published as a conference paper at ICLR 2023
Here propose novel concept-effective QNTK (EQNTK) to resolve the above dilemma and exhibit how symmetry improves the trainability of QNNs. As shown in Fig. 2 given a QNN (1vb)), (U(), H) whose input state (o) and the ground state l15") live in the same subspace V C C and V is invari- ant with the employed symmetric ansatz U(), the training dy dynamics of [v²()) = (0) (o) can be exactly captured by V a much smaller space than the whole state space. Suppose that the state space H under the symmetric ansatz design A can be de- composed into H = V and there exists j" E 'p] such that Vj. = V* includes the input state [vo), the ground state ( and all possible variational states (1)))) @ E θ). Then the dynamics of (e)) can be derived by the dimension of this subspace delt = [V*), dubbed the effective dimension of the QNN.
> ** Optimization path
Figure 2: ies of QNNs with symmetric an- sätze. The left and right panels illustrate the dynamic of variational states corresponding to the asymmet- ric and symmetric ansätze, respectively. The shadow region means the soln- tion space, which is the whole Hilbert space for asymmetric ansatz, and the stricted invariant subspace for symmet- ric ansatz.
Training dynam-
Definition 2 (Effectiie dimension). Consider a QNN instance (1vo) (O),, H) with symmetric ansatz design A. Suppose V is the in- variant subspace covering (Wo), (v())) 10 E (),,, and (²).. Then the effective dimension of this QNN is dat -V' The projection on this subspace is defined as II = PPt, where P E ddxde is an arbitrary set of orthonormal basis.
As a result, for symmetric ansätzo, Q and Q in Theorem 1 should be controlled by der instead of 2". This integration of the effective dimension transforms QNTK in Equ. (3) to EQNTK, which reduces the threshold to reach over- weerpprrametriizaionn and accelerates the convergence (see Fig. D. The following theorem establishes the convergence theory of QNNs with symmetric ansätze under EQNTK, whose proof is deferred to Appendix C
Theorem 2. Consider the QNN instance (Ivo). UO),, H) with the effective dimension den-. Following nolations in Equs. 3) when the distribution of U(0) construined to the in- variant. subspace with projection II ppt matches the Haar distribution up to the fourth moment, the ramberr of parameters satisfies LK >>> 1, the learnóng rate n < 1, and denoting I PPPP the training dynamics of a QNN instance (Woo) (0), H) gields
& (1 n re-
(5)
where Qs- (H(T))((())))/GCC refers to the expectation of EQNTK Qs on Hoar average.
The above results indicate that when the number of trainable parameters scales with LK ~ Old )+()) the adopted symmetric ansatz reaches the over-parameterization regime. Compared with QNTK, the reduction of parameters in the order of (2" /dar)² not only ensures the practical utility of over- pre-pparameterized QNNs, but also explains the em- pirical observations that symmetric ansätze require fewer parameters to reach the critical point than that of the asymmetric ansätze. More importantly, unlike prior results arguing that the trainability can always be improved by over- wver-parameterization. our bound suggests that involving more parameters beyond the critical point may degrade the convergence since the underlying symmetry may be broken and the elfective dimension den could be large.
Remark. (i)
The derived FQNTK can be used to diagnose the barren plateaus of QNNs. Particularly, the quantity (L/(LK) amounts to the variance of the gradient whose average is zero under the 4-design assumption. In other words, when the mumber of parameters LK is fixed, large EQNTK value is preferred to avoid barren platcaus. (ii) The effective di- mension can be quantificd by other metrics beyond the dimension of the invariant subspacc. An alternative is the dynamical Lie algebra (DLA) (Larocca al., 2021b), which measures the controllability of the quantui un system. The following lemma shows the convergence of QNNs with symmetric ansätze under this measure, whose proof is given in Appendix D
Proposition 1 (Informal). Following notations in Theorem g denote the dynamical Lic algebra of the QNN instance (Ivo). (0), H) as g, and assume that the number of parameters I.K > and the learning rale n < 1. Tf there erists an invariant subspace Vg with dimension
5

---

Published as a conference paper at ICLR 2023
dg under the DLA including the input state (b)) and the ground state (b"), the DLA-based EQNTK QD corresponding to the ansatz U()) leads to the training dynomics
E, R (1- rQD)) Eo = se
(6)
where QD - OOLK ((HL))) refers to the expectation of QD on Haar average.
3 SYMMETRICAL PRUNING WITH EQNTK
Beyond analyzing the convergence rate, another ad-hoc topic in GSP is design-
ing advanced ansätze to improve the trainability of QNNs. Although over- parameterizaatin and contemporary sym- metric ansälze partially address this prob lem, both of them have evident caveats. The former may request exponential pa- rameters to satisfy the condition of over- parameterization, while the latter requires explicit information for the symmetries of the problem Hamiltonian. To compensate for these deficiencies, here we devise sym- metrical pruning (SP), an automatic scheme to design symmetric ansätze with the enhanced trainability of QNNs. Con- ceptually, SP distills a symmetric over- parameterized ansatz from an asymmet- ric over-varamnnn per-parameterized ansatz. Supported by the EQNTK theory, the extracted ansatz resourco-friendly in implementa- tion since it holds small effective dimen-
Algorithm 1: Symmetric pruning (SP)
Input Problem Hamiltonian
H = ( 0g H,H,) ) & I0m, the ansatz design A and the parameter space θ in Equ. (2)
Step 1. Initialize an over-parameterized and asymmelric ansatz via A and O; Step 2. Symmetry identification:
2-1. Remove the gates wires corrosponding to the redundant part of H in A, i.e., [0m
2-2. Remove the gates such that the pruned ansatz design Apr = {H,,.... Hgg) 2-3. Assign the spatial symmetry of Apr by correlating some parameters and obtain Opr O
Output: Pruned ansatz design Apr and parameter space Opr.
sion and only needs a few trainable parameters to compass the over-paranmeterizatioon.
The Pseudo code of SP is summarized in Alg. 1 and its schematic illustration is shown in Fig. 3 Suppose the problem Hamiltonian is H H @ 18m, where // اا a,Hlj, aj is the real coefficient and Hj is the lensor product of Pauli matrices on n qubits, SP builds the symmetric ansatz of I with two primary steps, i.e., initialization and symmetry identification. The initialization step is choosing an initial wwer-aarameterized QNN by setting down the ansatz design and the parameter space θ. Note that should contain all Pauli terms in H and θ should ensure e-convergence of QNNs, e.g., a possible choice adopting a sufficient deep hardware efficient ansalz. Next, the symmetry identification step iteratively discovers the system symmetry, structure symmetry, and spatial symmetry, which completed by three sub-steps. Step 2-1 symmetrically prunes the qubit wires. That is, all qubit gates interact with the rodundant part of H. i.c., the identity term 190m are removed. Step 2-2 symmetrically prunes the structure, This step drops the parameterized single-qubit gates and the two-qubit gates so that the pruned ansatz design Apr can be block diagonalized under the projection on the eigenspace И E3=1a Hy. A possible solution setting Apr (H..... Hg} and the pruned ansatz Upr takes the form of Eqn. (2) with (e)) IIg_ e Den Step 2-3 correlates symmetric parameters to demystify the spatial symmetry of H. which is accomplished by heurist related to identifying the graph automorphism group (Stoichev 2019). See Appendix for more details.
Remark. (i) We emphasize that although both SP and the pruning techniques used in deep neural networks orient to remove redundant parameters and (quantum) neurons, they are fundamentally different. This is because classical pruning methods generally leverage the magnitude weights or the gradient information to recognize such redundancy, which is impermissible in QNNs (refer to Appendix F for elaborations). (ii) SP is a flexible framework. Besides three symmetric properties in Alg. [ SP can effectively integrate with methods in the second step.
other symmetry

---

Published as a conference paper at ICLR 2023
SP2
SP3
+00 +
00
400
Gates to be removed
Correlated parameters
Figure 3: Schematic of symmetric pruning. The proposed symmetric pruning (SP) distills the symmetric ansatz from given asymmetric ansatz, completed by removing the redundant gates (highlighted by the red dashed boxes) and correlating the parameters in the gate respecting the spatial symmetry (highlighted by the solid boxes with the same color).
4 EXPERIMENTS
We carry out numerical simulations to explore the theoretical properties of EQNTK and validate the effectiveness of the SP scheme in GSP. Two typical problem Hamiltonians in many-body physics and combinatorial optimization are considered. The omitted details are postponed to Appendix G
Problem Hamiltonian. Let us first recap the two problem Hamiltonians.
1) Transverse-field Ising model. Transverso-field Ising model (TFIM) has been em- ployed to explore many interesting quantum systems. An n-qubit Hamiltonian of 1D TFIM with an open boundary condition is defined as HTFIM = Žド= ojo - - of, where df denotes the y-Pauli matrix (with μ x, acting on the j-th qubit, and is the strength of the transverse field. For simplicity, we set h = 1 in the following simulations.
2) Maximum cut. Maximum cut (MaxCut) problem aims to partition the set of nodes V in graph G = EV) into two parts such that the number of edges spanning multiple parts is maximized. The MaxCut problem can be recast to GSP. Namely, the objective of n-node graph is encoded by an n-qubit Hamiltonian HMc E(urjee(T azat) and the optimal solution corresponds to the ground state of HMC as formulated Equ. ① Here we focus on the Erdos-Renyi graphs, which are generated by randomly connecting any pair nodes among n nodes with probability p = 0.6.
To verify the effectiveness of SP, the above problem Hamiltonians modified qubit Hamiltonian H HM @ 1nT (HM = HTFMM, HMC) with n = and m = 2.
(n+m)-
Initialization of QNNs. The hardware efficient ansatz (HEA) with the form of Equ. (2) used as the initial ansatz, which over-parameterizee and asymmetric. The layer number is set as L E f4,6, 6........ 28} and L E {4, 10, 36) for TFIM and MaxCut, respectively.
For each problem Hamiltonian, the input state is set as ((0) = 10). The parameters 0 are uniformly sampled from the uniform distribution [-T,, x]. The variational ansatz is trained by the Adam optimizer where the learning rate is 0.001 and the rest syper-parametert follow the default settings. The training of QNNs stops when the loss value is less than 10- or when the change in the loss function is less than 10-8 three times in row. The maximum number of iterations is set T 10000. The value in Definition is set 10-5 for both TFIM and MaxCut. Each setting is repeated with 5 times to collect the statistical results.
Evaluation metrics. We utilize three metrics assess the convergence rate of QNNs, ie., (1) the loss value ((O(T)) at the convergence stage; (2) the number of iteration steps T(c) S T required to achieve the c-convergence; (3) the minimum number of paramcterized gates required to achieve e-convergence, which can also be interpreted as the threshold to achieve the praaaccaanttiiiiiooonn regime. Additionally, we record the norm of the gradient at the initialization to verify the effectiveness of EQNTK in predicting the convergence.
4.1 SIMULATION RESULTS
EQNTK at initialization. Fig. b(b) and Fig. 5 (b) show that each symmetric pruning
step Alg. [ (i.e., the sub-steps 2- 2-2, and 2-3 refer to 'SP1', 'SP2, 'SP3', respectively) constantly improves the squared norm of gradients (i.e., the EQNTK value Qs) for both
7

---

Published as a conference paper at ICLR 2023
(a)
Qs
(b)
1(00)
(C) 10
T(e)
10
120
SP1
8P2
6
Gritical point
7-
60
10
5
40
900 10
Figure 4: Results for TFIM model under symmetric pruning. The panels (a)-(c) plot the EQNTK value Qs at initialization, the loss value after convergence ((O(7), and the iteration number to achieve the e-convergence T(s) versus the number of parameters LK, respectively. The labels 'SPO'-'PP3' refer to the initial ansalz, the prumed ansalz alter system symmetric pruning, structure symmetric pruning, and spatial symmetric pruning, respectively.
TFIM and MaxCut. This implicates that SP capable of accelerating convergence of QNNs and alleviating barren plateaus based on Theorem 2 Notably, the EQNTK Qs of the pruned ansatz (labeled by 'SP3') improved by 20 (or 14) times compared the initial wer-parameterized ansatz (labeled by 'SPO") in the problem of TFIM (or MaxCut).
Critical point of QNNs. Fig. ((c) and Fig. 5(c) illustrate that when the number of parameters surpasses threshold, QNNs experience a computational phase transition where the loss value L(0(2) at the convergence stage sharply drops by an order of the magnitude. Moreover, the minimum number of parameters required to reach the pee-paarameterization regime, highlighted by the 'critical point', dramatically reduced by SP. Specifically, the mumber of parameters of naive QNNs at the critical point in TFIM (or MaxCut), ie., labeled by 'SPO', scales exponentially with the system size. By contrast, it is gradually reduced from 800 (or 1000) to 300 (or 300) after SP1, then to 120 (or 150) after SP2, and finally to 50 (or 100) after SP3, which scales polynomially with the system size and is resource-friendde for modern quantum devices (see Appendix G for hardware efficiency analysis).
Convergence of QNNs. Fig. (d and Fig. 5)d) reflect that SP dramatically improves the convergence of QNNs. In the common over-parameten prraaattetttiiiiooonn regime of 'SP1'"'PP'' (i.e., LK 2 300), the total iterations required to achieve e-convergence can be reduced by up to 6000 steps for TFIM and 5000 steps for MaxCut. For the same ansatz design, increasing the number of parameters linearly improves the convergence, which echoes with Theorem
EQNTK and trainability of QNNs. Fig- 4 and Fig. indicate the relation between the EQNTK value and the trainability of QNNs. That is, the convergence rate and the number of parameters around the critical point decrease with the increased EQNTK value. MaxCut, regime in the cases of "PI'''SP3" the corresponding EQNTK value yields Q1 Q2 Q3 R3 11:2 4 and the iteration steps T(e) follows T1 T3 T3 4: 2: 1 (T, and Q, refer to T(e) and Qs in 'SPj' with j E (3). similar phenomenon observed in the task of TFIM. These results accord with Theorem such that EQNTK guide the trainability of QNNs.
when the number of parameters LK 450 reaches the over-paramelerizatdee
RELATED WORK
Prior literature related to work can be cast into two categories: the trainability theories of QNNs and the design of symmetric ansätze.
Trainability of QNNs. McClean et al. (2018) first discovered the barren plateau of QNNs..
Since then, a line of rescarch is uncovering intrinsic reasons leading to this phenomenon. Current progress has revealed that these reasons include high entanglement of QNNs (Mar- rero et al. 2021), the used global measurements (Cerezo et al.) (021b), and the presence of noise [Wang et. al. 2021 To mitigate barren plateaus, two popular ways adopting
8

---

Published as a conference paper at ICLR 2023
(a)
2,5
(b)
[(0))
10a
T(e)
10
1210
200
150
10-1
7-
130
Critial point
5-
10
50
4
0
10'1
300
600
900
1200
1500
300
600
300
1200
1500
300
600
900
1200
1500
LK
LR
LR
Figure 5: Results for MaxCut under SP. The notations are identical to those in Fig.
shallow QNNs with local measurements (Uvarov & Biamonte 2021
Pesah et al. 2021 Du
et al. 2022a Zhang et al. 2020) and correlating parameters Volkoft & Coles 2021
Another crucial line of research is investigating the convergence rate of QNNs. Several empirical studies have observed that over-parameterized QNNs promise faster convergence,
and the trained parameters are near-oplimal (Kiani et al. 2020 Wiersema et al. 2020
Zhang & Cui 2020). Afterward, initial attempts have been made to theoretically explain the superiority of paeettrramteri QNNs. Specifically, Larocca et al (2021b) and Anschuetz (2021) separately leveraged the tools of dynamical Lie algebra and random matrix theory to quantify the critical point of waee-parameterrieed QNNs; You et al. (2022) extended the result of Xu et al.] (0118) to the quantum regime and proved the exponential convergence rate of QNNs; Liu et al. (2022c
proposed the quantum neural tangent kernel to exhibit an exponential convergence rate of over-paran wver-parameterized QNNs. A common caveat of prior literature is that their convergence analysis either requires an exponential circuit depth for reaching prer-arammterization or omits the factor of the circuit depth. By rast, EQNTK greatly reconciles the harsh requirement reach wver-parameteriiation and allows a tighter convergence rate for the symmetric ansatz.
over-parameterizer
Ansätze with symmctric properties. Previous studics focus on uncarthing inherent symmetry behind the problem Hamiltonian to design problem-specific ansätze. The main- stream approaches contain arranging the layout of ansätze (Liu et al, 2019 Seki et al.
2020
Gard al.] 2020 Zheng et al. 2021
2022). correlating trainable parameters (Shay- Shaydulin & Wild 2021 Sauvage et al. 2022), and utilizing results from
dulin et al.] 2021
The geometric deep learning (Shaydulin et al. 2021 Shaydulin & Wild 2021 Sauvage el. al. 2022 Meyer et al.) 2022), where the symmetry comes from the training data. Compared with asymmetric ansätze, these ansätze enable better trainability in GSP. However, none of the previous proposals can identify the implicit symmetry of the problem Hamiltonian. Moreover, although there is numerical evidence that symmetric ansätze can accelerate con- vergence, thcoretical analysis is still rare. EQNTK readily compensates these issues, which provides an efficient measure to compare the trainability of various ansätze and allows an automatic method (symmetric pruning) to design symmetrical ansalz with fast convergence.
6 CONCLUSIONS
In this study, we investigate the training performance of QNNs for the GSP problem by developing novel tool -oo-EQTNK, which is capable of capturing the training dynamics of various ansätze via their effective dimension. We prove that a symmetric ansatz design with a small effective dimension enables an improved trainability of QNNs, including alleviating the barren platcaus and reducing the number of parameters and the circuit depth required to reach the over- paramttrrizaaaionnn regime. Besides, we propose a novel symmetric pruning algorithm to automatically extract the symmetric ansatz from asymmetric ansatz. Empirical results confirm the offectiveness direction is extending the results of EQNTK from GSP to the regime of machine learning and exploring whether over paeepparatterizee QNNs can simultancously attain good trainability
werrparameterized and SP. future research
and generalization (Abbas et al. 2021
Du al.
2022b Caro et al. 2022

---

Published as a conference paper at ICLR 2023
7 ACKNOWLEDGEMENTS
Yong Luo was supported by the Special Fund of Hubei Luojia Laboratory under Grant 220100014 and the National Natural Science Foundation of China under Grant 62276195. Tongliang Liu was partially supported by Australian Research Council Projects IC- 190100031, LP-220100527, DP-220102121, and FTT-220100318.
REFERENCES
Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner. The power of quantum neural networks. Nature Computational Science, 16)) 403 409, 2021.
Eric R Anschuetz. Critical points in hamiltonian agnostic variational quantum algorithms. arxiv preprint arXiv:2109.000 06957, 2021.
Eric R Anschuetz and Bobak T Kiani. Beyond barren plateaus: Quantum variational algorithms are swamped with traps. arXiv preprint ar orXi:22205.004 2022.
Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Ab- hinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kottmann, Tim Menke, et al. Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics, 94(1): 015004, 2022.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag, What is the state neural network pruning? arXiv preprinl urx::22003. 03033, 2020.
Stephen Boyd and Lieven Vandenberghe. Convez optimization. Cambridge university press, 2004.
Giuseppe Carleo, Ignacio Cirac, Kyle Cranmer, Laurent Daudet, Maria Schuld, Naftali Tishby, Leslic Vogt-Maranto, and Lenka Zdeborová. Machine learning and the physical sciences. Reviews of Modern Physics, (44)040000, 2019.
Matthias C Caro, Hsin-Yuan Huang, Marco Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick Coles. Generalization in quantum machine learning from few training data. Nature Communications, 13(1):1 11, 2022.
Marco Cerezo and Patrick J Coles. Higher order derivatives of quantum neural networks with barren plateaus. Quamlum Science and Technology, 6(3):035006, 2021.
Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, el Variational quantum algorithms. Nature Reviews Physics, pp. 1-20, 2021a. doi: https: //doi.org/100
021-00348-9,
Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature communi- calions, 12(1):1-12 12, 2021b.
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physies, 15(12):1273-1277 2019.
Paul T Darga, Mark H Liffiton, Karem Sakallah, and Igor I. Markov. Exploiting structure in symmetry detection for enf. In Proceedings of the 41st Annual Design Automation Conference, pp. 530 534, 2004.
Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao. Learnability of quantum neural networks. PRX Quantum, 2(4):040337, 2021.
Yuxuan Du, Tao Huang, Shan You, Min-Hsiu Hsich, and Dacheng Tao. Quantum circuit architecture search for variational quantum algorithms. npj Quantum Information, 8(1): 1-8, 2022a.
10

---

Published as a conference paper at ICLR 2023
Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, and Dacheng Tao. Efficient measure for the expres- sivity of variational quantum algorithms. Physical Review Letters, 128(8))050506, 2022b.
Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near
term processors. arXiv preprint 0rXiv:1802060000 2018. URL httpss:/arxxv..rrg/ /bs//
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint 1r 441.14181,,,, 2014.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, train- able neural networks. ar preprint arxi:: 03635, 2018.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Prun- ing neural networks at initialization: Why are we missing the mark? arXiv preprint arXiv:2009.cm 085766 2020.
Motohisa Fukuda, Robert König, and Ion Nechita. Runi symbolic integrator for haar- random tensor networks. Journal of Physics A: Mathematical and Theoretical, 52(42): 425303, 2019.
Bryan T Gard, Linghua Zhu, George Barron, Nicholas J Mayhall, Sophia E Economou, and Edwin Barnes. Efficient symmeerr-ppreeevvin state preparation circuits for the variational quantum eigensolver algorithm. rejj Quantum Information, 6(1):1 9, 2020.
Edward Grant, Leonard Wossnig, Matcusz Ostaszewski, and Marcello Benedetti. An initial- ization strategy for addressing barren platcaus in parametrized quantum circuits. Quan- lum, 3:214, 2019.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neu- ral networks with pruning, trained quantization and huffman coding. arXiv preprint PrXiv:1510.0014/ 2015.
Babak Hassibi and David Stork. Second order derivatives for network pruning: Optimal brain surgeon. Advances in newral information processing systems, 5, 1992.
Herasymenko and TE O'Brien. A diagrammatic approach to variational quantum ansatz construction. Quantum, 5:596, 2021.
Tommi Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In 2007 Proceedings of the Ninth Workshop on Algorillm Engineering and Experiments (ALENEX), pp. 135 135-149. SIAM, 2007.
Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Hardware-effcieet variational quantum eigensolver for small molecules and quantum magnets. Nature, 549(7777):2222 246, 2017.
Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pp. 85-103. Springer, 1972.
Bobak Toussi Kiani, Seth Lloyd, and Reevu Maity. Learning unitaries by gradient descent. arXio preprint 2001 2020.
Martin Larocca, Piotr Czarnik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick Coles, and M Cerezo. Diagnosing barren plateaus with tools from quantum optimal control. arXiv preprint arXiv:2105.14377 2021a.
Martin Larocca, Nathan Ju, Diego García- García-Martín, Patrick J Coles, and M Cerezo. Theory of overparametrization quantum neural networks. arXiv prepriat arXiv:2109. 11676, 2021b.
Martin Larocca, Frederic Sauvage, Faris M Sbahi, Guillaume Verdon, Patrick Coles, and Marco Cerezo. Group-invariant quantum machine learning. arXiv preprint ar oorxi:22000000 02261, 2022.
11

---

PPX.uuntumm.3000 Published as a conference paper at ICLR 2023
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advonces in neural information processing systems, 2, 1989.
Namhoon Lee, Thalatyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network
pruming based on connection sensitivity. ur preprinl arXiv:1810.0233 02340, 2018.
Jin-Guo Liu, Yi-Hong Zhang, Yuan Wan, and Lei Wang. Variational quantum eigensolver with fewer qubits. Physical Review Research, 1(2):023025, 2019.
Junyu Liu, Zexi Lin, and Liang Jiang. Laziness, barren plateau, and noise in machine learning. Xiv preprint arXic:2206. 09313, 2022a.
Junyu Liu, Khadijeh Najafi, Kunal Sharma, Francesco Tacchino, Liang Jiang, and Antonio Mezzacapo. An analytic theory for the dynamics of wide quantum neural networks. arXiv preprint arXiv:2203 16711, 2022b.
Junyu Liu, Francesco Tacchino, Jennifer R. Glick, Liang Jiang, and Antonio Mezzacapo. Representation Learning via Quantum Neural Tangent Kernels. PRX Quantum, 3(3): 030323, 2022c. doi:
Junyu Liu, Changchun Zhong, Matthew Otten, Cristian L. Cortes, Chaoyang Ti, Stephen K. Gray, and Xu Han. Quantum Kerr Learning. 2022d.
José Luis López-Presa, Luis Chiroque, and Antonio Fernández Anta. Novel techniques to speed up the computation of the automorphism group of a graph. Journal of Applied Mathematics, 2014, 2014.
Carlos Ortiz Marrero, Mária Kieferová, and Nathan Wiebe. Entanglement-indueed barren plateaus. PRX Quantum, 2(4):040316, 2021.
Iman Marvian. Restrictions on realizable unitary operations imposed by symmetry and locality. Nature Physics, 18(3):283-22) 2022.
Jarrod McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature commu- nications, 9(1):1 6, 2018.
Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii Journal of symbolic computation, 60:94-112, 2014.
Brendan D McKay et al. Practical graph isomorphism. 1981.
Péter Mernyei, Konstantinos Meichanetzidis, and Ismail Ilkan Ceylan. Equivariant quan- tum graph circuits. In International Conference on Machine Learning, pp. 15401-15420. PMLR, 2022.
Johannes Jakob Meyer, Marian Mularski, Elies Gil-Fuster, Antonio Anna Mele, Francesco Arzani, Alissa Wilms, and Jens Eisert. Exploiting symmetry in variational quantum machine learning. arxie preprint orXiv:2205, 06217, 2022.
Kosuke Mitarai, Makoto Negoro, Masahiro Kilagawa, and Keisuke Fujii. Quantum circuit learning. Physical Review A, (833)003 2018.
Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man- Man-Hong Yung, Xiao Qi Zhou, Peter Love, Alán Aspuru-Guzik, and Jeremy O'brien. A variational eigenvalue solver on photonic quantum processor. Nature communications, 5:4213, 2014.
Arthur Pesah, M Cerezo, Samson Wang, Tyler VolkofT, Andrew T Sornborger, and Patrick Coles. Absence of barren plateaus in quantum convolutional neural networks. Physical Review X. 1144):041011, 2021.
David Poulin and Pawel Wocjan. Preparing ground states of quantum many- body systems a quantum computer. Physical review letters, 102(13))130503, 2009.
12

---

Published as a conference paper at ICLR 2023
John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018. doi: 10..220121///0
/--331/--200 10-2018-088 08--08---7.
Yang Qian, Xinbiao Wang, Yuxuan Du, Xingyao Wu, and Dacheng Tao. The dilemma of quantum neural networks. ar preprint or Xiv:2106. 04975, 2021.
Frederic Sauvage, Martin Larocca, Patrick J Coles, and M Cerezo. Building spatial symmetrics into parameterized quantum circuits for faster training. arXiv preprint 141X::2207.1443,, 2022.
Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data encoding on the expressive power of variational quantun-nachine-lariing models. Physical Review A, 103(3):032430, 2021.
Kazuhiro Seki, Tomonori Shirakawa, and Seiji Yunoki. Symmetry-adapted variational quan- tum eigensolver. Physical Review A, 15)(5)0553340 2020.
Ruslan Shaydulin and Stefan M Wild. Exploiting symmetry reduces the cost of training qaoa. IEEE Transactions Quantum Engineering, 2:1-9, 2021.
Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Πya Safro. Classical symmetries and the quantum approximate optimization algorithm. Quantum Information Processing, 20(11): 1-28, 2021.
Andrea Skolik, Jarrod McClean, Masoud Mohseni, Patrick van der Smagt, and Martin Leib. Layerwise learning for quantum neural networks. Quantum Machine Intelligence, 3(1):1 11, 2021.
Stoicho D Stoichev. New exact and houristic algorithms for graph automorphism group and graph isomorphism. Journal of Experimental Algorithmics (JEA), 24:1 27, 2019.
AV Uvarov and Jacob D Biamonte. On barren platcaus and cost function locality in varia- tional quantum algorithms. Journal of Physics A: Mathematical and Theoretical, 54(24): 245301, 2021.
Tyler Volkoff and Patrick J Coles. Large gradients via correlation random parameterized quantum circuits. Quantum Science and Technology, 6(2):025008, 2021.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.01 07376, 2020.
Hanrui Wang, Yongshan Ding, Jiaqi Gu, Yujun Lin, David Z Pan, Frederic T Chong, and Song Han. Quantumnas: Noise-adaptive search for robust quantum circuits. In 2022 IEEE International Symposium on Performmre Computer Architecture (HPCA),
pp. 692-708. IEEE, 2022.
Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles. Noise-induced barren plateaus in variational quantum algorithms. Nature communications, 12(1):1-11, 2021.
Dave Wecker, Matthew B Hastings, and Matthias Troyer. Progress towards practical quan- lum variational algorithms. Physicaa Review A, (24):00433,,, 2015.
John W Wheeler. An invostigation of the max-cut problem. University of Iowa, 2004.
Roeland Wiersema, Cunlu Zhou, Yvette de Sereville, Juan Felipe Carrasquilla, Yong Baek Kim, and Henry Yuen. Exploring entanglement and optimization within the hamiltonian variational ansatz. PRX Quantum, 1(2):020319, 2020.
Zhiqiang Xu, Xin Cao, and Xin Gao. Convergence analysis of gradient descent for eigen- vector computation. International Joint Conferences on Artificial Intelligence, 2018.
Xuchen You, Shouvanik Chakrabarti, and Xiaodi Wu. A convergence theory for over- parameterized variational quantum eigensolvers. arXiv preprint ar Xiv:22005. 12481, 2022.
13

---

Published as a conference paper at ICLR 2023
Kaining Zhang, Min-Hsiu Hsich, Liu Liu, and Dacheng Tao. Toward trainability of quantum neural networks. arXiv preprint arXi::2011.0625. 2020.
Stephen Zhang and Wentao Cui. Overparametrization qaoa. Written Report, 2020.
Han Zheng, Zimu Li, Junyu Liu, Sergii Strelchuk, and Risi Kondor. Speeding up learning quantum states through group equivariant convolutional quantum ans {\" a} tze. arXiv preprint arxiv:2 1200761, 2021.
Han Zheng, Zimu Li, Junyu Liu, Sergii Strelchuk, and Risi Kondor. On the Super- exponential Quantum Speedup of Equivariant Quantum Machine Learning Algorithms with SU(d) Symmetry. 7 2022.
Zeqiao Zhou, Yuxuan Du, Xinmei Tian, and Dacheng Tao. Qaos-in-qaoa: solving large-scale maxcut problems on small quantum machines. arXiv preprinl arXiv:2205.11 11762, 2022.
A OPTIMIZATION OF QNNs IN GSP
In this section, we separately claborate the clementary notions in quantum computing, the preliminary of Hamiltonian and the ground state preparation (GSP), and the optimization strategy of QNNs the task of GSP.
Basics of quantum computation. The elementary unit of quantum computation is qubit (or quantum bit), which the quantum mechanical analogue of a classical bit. A qubit is two-level quantum-mechaniee
system described by unit vector in the Hilbert space C², In Dirac notation, a qubit state defined as (Ø) = co (0) + ci [1) E C² where 10) [1,0] and [I] [0, 1)" specify two unit bases and the coefficients cp, E C yield leol + la = 1. Similarly, the quantum state n qubits defined as a unit vector in C²" i.e. (b) -5=1 9j lez), where lej) E I2a is the computational basis whose j-th entry is and other entries are 0, and Σ3= 1c,12 1 with сj E C. Besides Dirac notation, the density matrix can be used to describe more general qubit states. For example, the density matrix of the state (&b) is p (+) (el C2"x2" where (vll w)) refers to the complex conjugate transpose (t)). For a set of qubit states {pj, ) with pj > 0, Σy= Pj = 1,
and 11b)) E C2" for [m], its density matrix is p Σグ= PjPj with Pj |wb (1yy) and Tr(p)= 1.
A quantum gate is an unitary operator which can evolve quantum state p to another
quantum state p'. Namely, an n-qubit gate U U(2)) obeys UUt Ut = I2", where u(2") refers to the unitary group in dimension 2". Typical single-qubit quantum gates include the Pauli gates, which can be written as Pauli matrices:
0 1 0
[
1 0
X
Y
2
0 -1
1
The more general quantum gates are their corresponding rotation gates Rx = - Ry-(0) e e and Rz( = -182 with tunable parameter 0, which can be writlen in the matrix form as
(0) = [ cos 0
-i -is 0
cos sin q
c 0
2 cos
(0)
Rz(0)
- sin 2
sin
cos
0
(8)
They are equivalent to rotating a tunable angle 0 around x, y, and z axes of the Bloch sphere, and recovering the Pauli gates X, Y, and Z when 0 = Moreover, multi-qubit gate can be either an individual gate (e.g., CNOT gate) or a tensor product of multiple singlo-qubit gates.
The quantum measurement refers to the procedure of extracting classical information from the quantum state. It is mathematically specified by Hermitian matrix H called the observable. Applying the observable H to the quantum state (*) yields a random variable whose expectation value is (1b H (1)).
14

---

Published as a conference paper at ICLR 2023
Hamiltonian and GSP. In quantum computation, Hamiltonian is Hermitian matrix that is used to characterize the evolution of a quantum system or as an observable to extract the classical information from the quantum system. Specifically, under the Schrödinger equation, a quantum gate has the mathematical form of U e- where H is a Hermitian matrix, called the Hamiltonian of the quantum system, and refers to the evolution time of the Hamiltonian. Typical single-qubit Hamiltonians include the Pauli matrices defined in Equ. (7). As result, the evolution time refers to the tunable parameter in Eqn. (8). Any single-qubit Hamiltonian can be decomposed as the lincar combination of Pauli matrices, i.., H a1 a2 + agY + az with a, E C. In the same way, a multi-qubit Hamiltonian is denoted by H -==1,;,,, where P3 E (I,X,Y, 2) is the tensor product of Pauli matrices. In quantum chemistry and quantum many-body physics, the Hermitian matrix describing the quantum system to be solved denoted as the problem Hamiltonian.
When taking the problem Hamiltonian the observable, the quantum state (b*) is said to be the ground state of problem Hamiltonian if the expectation value (vi* H (&*) takes the minimum cigenvalue of H, which is called the ground eneryy. GSP refers to preparing the ground state the problem Hamiltonian. parameterized unitary (0) to prepare variational quantum state lvb(0)) (() vvo) with
popular protocol for GSP is to employ
a fixed input state (W)) and then optimize the parameters by minimizing a predefined loss function such the Equ. (
Optimization of QNNs. The optimization the loss function [(0) in Eqn. can be completed by gradient-based methods. A plethora of optimizers has been designed to estimate the optimal parameters 0" = ming (()). Here we introduce the implementation of the first-order gradient-based optimizer for self-consistency. Refer to Cerezo et al. (022aa for a comprehensive review.
Based Eqn. (2), the trainable parameters of QNNs are denoted by 0 (O) O (ek)""
where the subscript 'Ek' refers to the k-th parameter of the b-th layer Ue for vk E [K] and AE E [Z]. Recall the loss function takes the form
with 0₂ = (0a1... ....
( (wvol U(O) (O) (/o) Eo)
and the corresponding update rule at the t-th iteration Vt E [T] is
((+1)
AC((())
(()) " 00
- Eo) ((vbol U( (0()) (to) E④)
0 ((Vol U00
(O (
00
where refers to the learning rate. The derivative in the last equality be calculated via the parameter shift rule Mitarai et al. (2018). Mathematically, the derivative with respect to the parameter te for Ve and vk [K] is
a ((vol (0)* (U) (//)) Eo)
00m
1
((1bo) (U((())) 1 Ea) - ((1bl
Eo)
2
where 0+ aeek, 0- 0 werk, en is the unit vector along the Oz axis and can be any real number but the multiple of because of the diverging denominator.
B EQUIVALENT TRAINING DYNAMICS UNDER THE MEAN SQUARE ERROR LOSS
In the main text, to facilitate the convergence analysis, the loss function L( in Eqn. I adopts the term Eg, as the ground state energy of the problem Hamiltonian. Here we elucidate how to extend results to more general loss function in which Fo is replaced
15

---

Published as a conference paper at ICLR 2023
by any C' E R with C S Eg. More specifically, the general mean square enror loss function defined as
1 C( ((vol (() HU( (vb) -=²²=
1 =0,,0
(9)
where
e c C) (v'ol ((O) 140)
refers to the training error associated with C. For clarity, we denote the training error at the I-th iteration as & (x(((), C). Given two loss functions L(O, C) and L(O, C") with C,C" S Eg, their convergence behavior or training dynamics is said to be equivalent if the variational quantum state (b)) converges to a same quantum state with the same convergence rate. More concretely, for the same initial state (o())), the evolved state (e(t) at each iteration for V1 E [T] is the same.
The following lemma indicales the equivalent training dynamic of QNNs under the loss functions L(O, C) and [(O, (") with C,C" Eg.
Lemma 1. Under the framework of the quantum neural tangent kernel Eqn. given any loss function C(0,C) in Eqn. (1) with C Fo, QNN obeys the same convergence rale with L(O, Fo) and the oplimized varialional quantum state (v(()) converges to the ground state of the problem Hamältonian H.
3 the QNTK of the loss function in Proof of Lemma In the same manner with Eqn. Equ. 9 can be denoted by
Qc = Ve(0, о) V)(
According to the explicit form of s(0, C) in Equ. the QNTK Qc and Qc is the same for any given constant C and C" as Ve(0, C) = (E C²). For this reason, in the following, Q to refer the QNTK with any constant C.
Recall the results of Theorem i.e, in the case of C = Eo, the training error =(0, Ex) decays as
((()))), Eo) ee -0 Eo). Moreover, due to (0()), Eg) (0(,) ,0) + (C Eo) for VI [7], the training error of QNNs under the loss C(O, C*) is
((()() C) + (C- Eo) n
(C
(10)
Since the right-hand side tends to zero with a sufficienlyy large number 1, this suggests e, (0(0), +)+ (C'- Eb) x O. In other words, e(0, C*) converges to the minimal value of Eg with the decay rate nQ. Supported by the variational principle, the optimized variational
quantum state ((O(T)) (voo at the converging stage is exactly the ground state in which the corresponding energy estimates Eg.
C PROOF OF THEOREM
The proof of Theorem 2 employs the following two lemmas whose proofs are given in the subsequent two subsections.
Lemma (Adapted from You al. (2022), Lemma D.1). Following Definition let UA be matrin subgroup of (U(d) where each element in UA commutes with Hermition matrir E. The corresponding direct decomposition is denoted by = Ez= V, with projection Iy, Let V* be the subspace of interest which includes the input state (wo) and ground state l()). Denote II PPP P as the projection on V*. Then for any Hermitian W and any unitary matriz U in the group UA we have
NUUWU' = IU II" TUM.
(11)
Lemma 3. Following notations in Lemma denote
1-1
k-1
K
I. II Ur(Or), 2'2+1
U c
II
Up (0x) II
Ga U+ = II
G Gy
(12)
1=1
--1
k' =k
16

---

Published as a conference paper at ICLR 2023
the EQNTK takes the form
16 (U4 (u+)))) [G (U=,,x) HH U7ees 16 )
Qs
(13)
where (16) = P ) and A = PAPt with A E (U+,th, Gk. U U- _kk, HJ.
Proof of Theorem 2 Following the gradient descent optimizer Equ. 1
with the learning
rate 1/ S 1, the change of the training error of QNN can be expressed
ds = Σ E
de
dO =
Σ t
de de
C = -1ss..
(14)
a0
a0g
d0ek
where de Er-1 Ex and d0 =
0 (++1)
ih
0 the second equality comes from the update
rule with d0n ys0e/00s. and the third equality uses the definition of QNTK in Equ. (3)
Following the results in Liu al. (2022c Theorem 1), when the EQNTK value Q constant, the training error decays with
6 (1 - n0 (2) eoo -0 so.
(15)
which guarantees an exponential convergence towards the global optima. To this end, the proof of Thcorem 2 amounts to proving that when the number of paramcters satisfics @ LK > 1, the EQNTK can be regarded as constant. This can be achieved by deriving an analytical solution of Q average well as the fluctuations around the average for all iterations.
Following the above explanations, we next analyze the average of Q When no confusion arises, the superscript (t) of ( and U(O()) are dropped in the subsequent analysis. By the Haar average of EQNTK yields
leveraging Lemmas and 3
K
aU and an (16 (U2, H [x] ee (/6)
Qs =
K
au en du .kk Tr (x)(U),(x) 'M MM uxmoo (U M- U (e(.ess)
km1
Tt (M- Ir ((p))))
Tr Ir ((pi)2)
dUFtek
d2t Tr ((M- )x)))) Tr ((p6)²)
&
k1k=
Tt2 (M- .kk Tr? (p))
dott
dolf dat
K
Tr ((M-())) Latt + deft
dUi
(tE(UI,))tHHU- )²) 2Th (GG)(U
-
K
2TH
dU dU+tek
det
doff
t= k=
2
dest (
Tr 1 (G))
&a + dell
d
TK ((H)))
(16)
d2
where the second equality employs the assumption such that U U= and U U+ match the Haar distribution the group SU (des) up to the second moment, / (1/8) (v% is the projection
17

---

Published as a conference paper at ICLR 2023
of Po (vb) (Hu) the subspace V and M- [G (U= " -ex, the third equality exploits the RTNI package (Fukuda et al. 2019) to calculate the integration with respect to the Haar measure, the fourth equality uses the fact Tr((p))) = Tr(p)) = with Pa being the pure state, the fifth equality utilizes Tr[[A, B}²) 2 (AABAB Tr)43)²), the last second equality uses the RTNI package again, and the last equality utilizes the fact
Tr(G G&II" TT((GT))) EE G.I.I)
deff
Tr(G))
2" deff
(17)
2"
with Tr( [r( = 2".
The fluctuation of EQNTK can be expressed as AQ's = B(Q²)) Q33 i.e.,
/ aii i dU 1ik1
AQ'S -2 E
- dU 12kk x
Tr ( M-A ( Po
t.liks M Rike U U.eeshs)
Tr (P6(U=eess) ) M (U laka) ) PGU +.ekk M 12ks U2
dU dUF,uddU".n (
Tr TT MM _ (U=.ex) ex M- MeN U.UUF.R
-ex
Tr (P60UU7,.0) MM POU= Me F.ekk
E.k
Q3
LK
(8 (ST2((13))+12222(77))) +
da
LK
....
dett
LK
~ doff
(18)
where k < l2 22 refers to & K + k < LgK + k2, the derivation of the second equality mainly follows the results of Liu et al. [202bb] Appendix C), and the approximation comes from the truncation and the preservation of the leading order term.
Taken together, when the number of parameters LK >> such that Qs/AQs VLK 1, the EQNTK can be viewed as constant and Equ.
15 is satisfied.
C.1 PROOF OF LEMMA
Proof of Lemma The two conditions in the lemma, i.c., (i) any unitary U in U commutes with the Hermitian matrix Σ and (ii) Σ leads to the decomposition V = ey-1 with projection Ny, imply that U is block-diagonal under the projection (Ty} In other words, we have U1,, 0 for j' and YU e UA. This observation gives the following results, ie.,
NUUUUM
p
-ITU Σ Hu Σ n,u'm
f'11
Σ (LUI)) W (IşUti))
J
-IU U'I'
WUTTW TUMI
(19)
where the first equality employs the fact of I = Σj Hy and the last equality uses the property of projections T13 II,
18

---

Published as a conference paper at ICLR 2023
C.2 PROOF OF LEMMA
Proof of Lemma 3 The explicit form of the training error s(0) = (vol (() HU ()) leads to the explicit form of QNTK, i.e.,
Eo
Q (Ve(O))TVeet
Vo Uu t.ek [G es .ex) U+ U4.ea//0)))
(20)
Similarly, for the symmetric ansatz (() with the projection IIo = PPt, the FQNTK yields
Tr (u (1wo)(
uee [Gh. UJ HU-HH, U+,e6)
Qs
1 K
U HU- HU-,ek eek U+.el) 2
[I Poll
k=
K
Tr [1 Poll 4.00 GRI
U+ U+.eell")
K
(TT po IT
GK. U!
-ex OU- +(
Tr II u II" [IGG,,,, II IT +x
Tr (plmoPPIUL.cm e (PIGPPI P uf P p'U
k=
K
(pG(U [Gt, (U U= U+.ek)
0/ (UF [Gr, (U HH H'U", [x] Ui.ek (v6)
(21)
Ł=1 R=1
where the second equality utilizes the assumption such that (2/)) lies in V* the third, fourth and fifth equalities employ the properly of projection operator (II*)2 = II and Lemma
the final equality follows from the definitions with ( pt (éo) and A AP with A E {U- U+.0,, Gk, po
D PROOF OF PROPOSITION
Before moving to elaborate on the proof of Proposition we first briefly review the definition of dynamical Lie algebra (DLA).
Definition (Definition 3, Larocca al. 2021a)). Given ansatz design A, the dynam- ical Lie algebra (DLA) g is generated by the repented nested commutators of the operators in A. That is
g = span (iG1,-. ... ,iGr) Lic
(22)
where span (8) Lie denotes the Lie closure, i.e., the set obtained by repeatedly taking the comemutator of the elements in S.
The proof of Lemmn employs the following Lemma.
Lemma 4. Consider the QNN instance (Ivo) (0), H) whose DLA is g. If there exists invoriant subspace Vg inchuding the input state (e)) and the ground state l15)) with dimension dg under g, then the effective dimension of this ansatz design A yields dest dg-
19

---

Published as a conference paper at ICLR 2023
Proof of Lemma 4 We first demonstrate the equivalence between the group Uu - 0 R r. and the group generated by the elements in g, i.e.,
U^ iee,Veg
(23)
UA - {e V E g). To facilitate understanding, consider single-layer unitary (0) with L= 1 and the ansatz design A {G1, G2). From the Baker-Campbell-Haatee Haassoorf formula, we have
U = c Gi d
G = ed1(0)
(24)
where
10,02 1 0..i+000G2 (10))i(0,G1+0002)
0,0g G1. [G,, G2ll Gall+ +....
=i =1
J1(0)
2 (G.GGl
(25)
12
Eqn. (5 implies that by merging e e0 and e e00aG2 into single term, the new evolution generated by an operator Jr (0) depending on both 0, and 02, which contains nested commutator between G1 and G2. Therefore, we have (0) E g and (()) E {e", V E g}.
For the case of multiple layers, Lee, U() I e0,, c we have (()) (0) fer, V E g} by recursively applying the Baker- Campbell-Hausdeee formula to reformulate (()) by the (z) E g.
MA - {e V E g}- Since each element in is linear combination of the nested commuta-
tors in Eqn. (55). there always exists A E R2L for any V E g such that (0) = V and thus e2(00) = (0) E (U()( : E RRLK..
Taken together, obtain Equ. 23 in the case of K == 2. The results for the ansatz design A with more than two elements can be derived in the same manner. More details can be found in Section IV of Larocca et al. (2021b).
= The equivalence of UA and {ec G E g} indicates that for any G E and U E EAA, G and U commutes with the same Hermitian matrix Σ since U can be expressed as eG and hence has the same Eigen-space with G. This implies that the invariant subspace induced by UA the same with the one induced by g and thus d d= dg.
Proof of Proposition 7 Following Lemma 4 the DLA-based FQNTK is the same as the EQNTK discussed in @esoorem@bcatuee the corresponding U (0) induces the same invariant subspace. Hence, the results achieved in Theorem 2 can be applied to the DLA-based EQNTK by replacing the effective dimension def with dg.
E IMPLEMENTATION DETAILS OF THE SYMMETRIC PRUNING ALGORITHM
In this section, we elucidate Steps 2-1, 2-2, and 2-3 of the proposed SP in Alg, 1 Recall the considered problem Hamiltonian is expressed as = H @ 10m with = - H,Hj, where a, is the real coefficient and H, is the tensor product of Pauli matrices on n qubits. A symmetry S of a Hamiltonian H is a unitary operator leaving H invariant, ie.,
SHSt = H.
(26)
All of those symmetrics form a symmetry group S where for any two symmetrics S2, S2 S, their compositions S1 o S2 or S2 o Si and their inverses ST and S are also symmetries in S. In SP, these symmetrris are classified into three categories, namely, the system symmetry (Step 2-1), the structure symmetry (Step 2-2), and the spatial symmetry (Step 2-3). Suppose that the initialized asymmetric ansatz is U(O), SP adopts the following methods to tailor this ansatz to obey the above symmetries.
System symmetry. System symmetry considers the symmetry on qubit wires. Specifically, since the problem Hamiltonian A can be decomposed into a tensor product of Pauli terms, the symmetry condition in Eqn. 226 holds for any unitary of the form Says 1 SU, where
20

---

Published as a conference paper at ICLR 2023
U is arbitrary unitary in SU") All such unitaries are called the system symmetry and form a subgroup of the symmetry group S, i.e.,
Says = {Say= = 1 & U (U))))).
The system symmetry of unitary V can be recognized if Saye V Says V. With this regard, SP assigns the system symmetry to (0) by removing the redundant parameterized gates and the two-qubit gates associated with the last m qubit wires. In doing so, the pruned ansatz has the form
(r) = (0) & Io.. which yields (U)((U)( & 1 sys (0) @ 1 where U1( is the unitary extracted from (0) (the gates applied on the first n qubit wires).
Structure symmetry. The structure symmetry Satr refers to the symmetry for the effec- tive Hamiltonian H, which satisfies
San = H.
Morcover, an ansatz V(0) is said to be structure symmotric to the problem Hamiltonian H if there exists non-trivial symmetry Satr (i.c., not the identity operation) and 0 E () such that S (())
V(0). feasible solution of constructing the structure symmetric ansatz is restricting the corresponding ansatz design that only contains the Pauli terms of H. Given the pruned ansatz Up, returned by Step 2-1, SP (Step 2-2) assigns the structure symmetry on it by removing specific the single-qubit gates and the two-qubit gates so that the pruned ansatz design follows A = . H. The tailored ansatz returned by Step 2- 2 coincides with HVA, i... (0) transforms to the new ansatz whose f-th layer is expressed as [ij= e H0 for AI E [L].
Spatial symmetry. Spatial symmetry is a discrete symmetry considering the permutation invariance for the sites of the problem Hamiltonian, which tightly relates to the problem of graph automorphism that has been widely studied in graph theory. For this reason, here we introduce the spatial symmetry from the graphical perspective and elucidate the implemen- lations of Step 2-3 in Alg. [ The key in this step is leveraging the algorithms developed in graph theory to automatically identify the spatial symmetry of problem Hamiltonians.
From the graphical view, an n-qubit Hamiltonian H refers to a graph G = (V, E) with n vertices, where the j-th node Vj V represents the j-th site (qubit) of H and the edge Eig E E characterizes the interaction strength of the i-th and the j-th sites (qubits). This graph can further be described by an adjacency matrix D.
Recall that spatial symmetry of Hamiltonian H is permutation over the sites leaving И invariant, i.e. πH И (or equivalently [T, H] 0). In other words, the spatial symmetry preserves the topology invariance of G' such that for any (u, v) E E, we have
((U))((u)) E E, and Dm = D.
In GSP, the action of on an n-qubit state (b) T (b)) means permuting the indices of qubits. For instance, a permutation क with x(1) 3, 32) (2(2)=1 1,, 13) = 2 acting on the state (91) l12) (us) yields T (([11 (122) (t))) = (4a)) (b)) (22). All these permutations form a discrete group of symmetries S, with the cardinality O(n)). Particularly, the spatial symmetries of the Hamiltonian the automorphism group of its corresponding graph, defined as
Aut(H) (Ta Sp H):
or equivalently (u)(H) = (m. E Sm DT- D}. The qubits (or qubit-pairs) in the ansatz corresponding to the nodes (or edges) that can be swapped are called equivalent qubits (or qubit-pairs). More precisely, for any node (or edges) u V (or (u,v) E E), there exists E Aut(!f) such that (u) = (or T (u, (z, v)), then the qubits (or qubit- pairs) corresponding to the node (or edge) u (or (u, v)) and x (or (x. y)) are called equivalent qubits (or gubit-pairs). Given the ansatz returned by Step 2-2, Step 2-3 assigns the spatial symmetry on it by correlating the single-qubit parameterized gates on the equivalent qubits or the two-qubit parameterized gates the equivalent qubit-pairs.
21

---

Published as a conference paper at ICLR 2023
(0)
28
12
10)
SPI
SP2
B2
(0)
13
63--
10)
22
8
182
3. CNOT gate
: gate
share one parameter
Figure Evolution of ansatz structure during symmetric pruning From to right shows the initial hardware efficient ansatz and ansatz structure at different stages of symmetric pruning, where 'PP1, 'SP2', 'SP3' refer to the sub-steps 2-1, 2-2, and 2-3 in Alg. respectively and L' < T.- The symbol 'RX' (RRY", 'RZ') refers the single qubit rotation around the (y, =)axiss and I refers to the identity gale. The rotation gales with the same color of pruned ansatz are correlated by one individual parameter per layer.
The flexibility of SP. The automorphism group for the graphs corresponding to the Hamiltonians with the complicated topological structure is hard compute manually. In this work, we employ nauty to automatically recognize the automorphism group of graph corresponding to the Hamiltonian nauty (McKay al.) 1981). Besides nauty there are many heuristic algorithms to compute the automorphism group. including Traces (McKay Piperno 2014), saucy (Darga et. al. 2004), Bliss (Junttila Kaski 2007) and canaulo López-Presa al. 2014). All of them can be easily integrated into SP. Moreover, these heuristic algorithms are capable solving most graphs for up to tens thousands of nodes
in loss than sccond (McKay & Piperno 2014
F THE LIMITATIONS APPLYING CLASSICAL PRUNING METHODS TO QNNs
Although both SP in Alg. and the classical pruning techniques distill smaller network (or an ansatz) from an over-parameterized one in the view of algorithmic implementation, the latter cannot be directly employed to enhance the power of QNNs.
Recall that a common feature classical pruning methods scoring each parameter or network element and then removing those accompanied with low scores. Such scores gener- ally correspond Lo the magnilude of parameters (Frankle & Carbin 2018), the gradient of parameters (Lee et al. 2018 Wang et al. 2020), and the Hessian matrix (LeCun
1989 Hassibi & Stork 1992] at the imtialization stage or the phase of terminal. Unfortunately,
Cerezo Coles [2021] proved that the gradient information in QNNs with random deep ansatz exponentially vanishes with the increased number of qubits. In other words, the gradient information fails to provide any useful information guide pruning. Mcanwhile, the output of QNNs can be regarded a periodic function of parameters (Schuld et al.) 2021,, which forbids employing the parameters' magnitude as the metric guide the prun- ing. Therefore, it is inappropriate to straightforwardly apply classical pruning methods to QNNs, where the extracted ansatz may not promise the enhanced trainability.
proposal does not require any gradient information to construct the symmetric ansätze. Instead, it removes the rodundant gates and shrinks the solution space according to the information of the problem Hamiltonian.
In contrast with classical pruning methods,
G MORE NUMERICAL SIMULATION DETAILS
In this section, we provide the simulation dotails omitted in the main text.
Hardware efficient ansatz. As shown in the left panel of Fig. HEA yields the layer- stacking structure following Eqn. (2), where each layer consists multiple single-qubit Pauli rotation gates and fixed two-qubit CNOT gates. In numerical simulations, the f-th layer
22

---

the number free Published as a conference paper at ICLR 2023
(a)
(b)
Z
X
u
hX
ZZ
W
p 0.6
Figure 7: Graph representation of problem Hamiltonian. The left panel and the right panel depict the graph representation of the TFIM model and Erdos-Renyi graph with p 0.6, respectively.
of the employed HEA takes the form
72
Uz(0) =U= ent
Rx (y (6, (U)
j=1
x U
II
Rx Rx J,4 (0))))
(27)
j=1
where (0,( = -i N with μ E {X,Y denotes the parameterized single-qubit gate, 8 / CNOT refer to the entangled layers with [a_ being the greatest integer no larger than a.
and (. |1 CNOT 21-1 and (:()]
Transverse-field Ising model. A central problem in quantum many-body physics is predicting the properties of these quantum systems from the first principles of quantum mechanics, Traasverse-field Ising model (TFIM) has been employed to explore many inter- esting quantum systems. In our numerical simulation, we employ an n-qubit Hamiltonian ΣE=
of ID TFIM with an open boundary condition, i.e., HIFIM = = -E where of denotes the p-Pauli matrix (with x, acting on the j-th qubit. The effective dimension for HVA under this Hamiltonian is given by dest = n² (Larocca et al. 2021a) The Hamiltonian graphically depicted Fig. a
0f0j+1 - oj.
MaxCut, Although many important problems in statistical physics and operation rescarch [Wheeler 2004) can be formulated as MaxCut, finding the optimal solution of MaxCut has been proven to be NP-hard (Karp) 1972) and quantum computers are expected to attain better approximated solutions than those of classical computers (Farhi et al. 2014 Zhou et al. 2022 In this work, we consider the MaxCut problem of the Erdos-Ross Renyi graphs whose topology is less structured. An Erdos-Remt Renyi (ER) graph on the vertex set V a random graph in which each pair of nodes (u, v) connects independently with probability p. Fig. b) shows the instance of the ER graph used in the numerical simulation with setting
0.6.
Evolution of ansätze. Here present the evolution of the ansatz structure for the transverse-field Ising model during symmetric pruning in Fig. D which serves as an example for better understanding the learning dynamies of our proposal. Specifically, we adopt the Hardware efficient ansatz as the initial over-parameterized ansatz, as shown in the left side of Fig. 6 The gates on the last two wires corresponding
p are first removed through Step 2-I (referred to 'SP1') in Alg. to ensure the system symmetry. Subsequently, in Step 2-2, SP employs the symmetric information of problem Hamiltonian HIrmm remove the parameterized single-qubit gates and two-qubit gates the first six wires such that the pruned ansatz design is Apr .oj..... . oiojj -.j])) Finally, in Step 2-3, the spatial symmetry pruning correlates the parameterized gates the equivalent qubits and qubit- pairs through the returned automorphism by the package nauty. In the case of TIFM, the package nauty returns non-trivial automorphism T(j) from each side of the chain. This operation leads to a reduction
+ 1- that permutes qubits
parameters from 11 for the ansatz pruned by 'SP2' to 6 for the ansatx returned by 'SP3.
23

---

Published as a conference paper at ICLR 2023
TFIM
MaxCut (ER graph)
Max (3 regulargraph)
Depc Shots (X:)
1003
Dapch Stots (X-)
Depth
Shots
405
300
200
150
70
200
300
103
SPD
SP1
SP2
SP3 5PD SP1 SP2
SP3
SPD
SP1
SP2
SP3
Figure 8: The quantum resource required for achieving é-convergence. The left panel, the middle panel, and the right panel depict the number of measurements required to complete one optimization step and the circuit depth required to achieve the e-convergence in the task of TFIM, MaxCut for Erdos-Reny Renyi graph, and MaxCut for 3-regular graph, respectively. Particularly, the label 'xs' refers that the total number of shots M is the product of the displayed value in the histogram and the number of shots for updating a single parameter The labels 'SPO'-'S3"' refer to the initial ansatz, the pruned ansatz after system symmetric pruning, structure symmetric pruning, and spatial symmetric pruning, respectively.
Hardware efficiency analysis. We use two standard metrics to quantify the hardware efficiency, i.e., (1) the number of measurements (shots) M required to complete one opti- mization step; (2) the circuit depth l(e) required to reach the over prre-aarrmtttizttioonn criteria characterized by r-convergence with cost in training QNNs, and the second metric evaluates the required quantum resources to construct the quantum circuit. To facilitate the comparison of various ansätze under the first metrie, the number of shots for a single parameter update is set to be 8, so that the total number of measurements taken to complete one optimization step linearly scales with the number of parameters, i.e., M = LKs. As depicted in Figure g in the task of TFIM, compared with the initial over- parrammaettee asymmetric ansatz (labeled by 'SPO"), the re- quired number of measurements M for the pruned ansatz can be dramatically reduced by 14 times; meanwhile, the required circuit depth reduced by 3 times. In the task of Max- Cut, the hardware efficiency improvement is problem-dependent In particular, the required circuit depth is reduced by about 1.8 times and 2 times for the Erdos-Renyi graph and the 3- 3-regular graph, respectively. For the Renyi graph, compared to the ansatz returned by 'SP1', the required circuit depth of the ansatz returned by 'SP2' slightly increases from 100 to 130. This increase originates from the fact that the Erdos-Renyi graph with large number of edges requires a relatively deep circuit depth to construct the symmetric ansatz after SP1. Although the circuit depth is subtly increased, an evident benefit is a dramatic reduction of the number of measurements M, i.e, compared with the initial ansatz, the re- quired M for the pruned ansatz is reduced by 10 times than that of the initial ansatz. The achieved mumerical results confirm that the symmetric ansatz output by our proposal can offectively improve hardware efficiency. As such, it can simultancously reduce the required quantum resource for reaching the regime of pore-aaramtterzzaionn, enable an efficient im- plementation ion on NISQ devices, and more importantly, improve the convergence rate so as to reduce the number of access to the quantum devices.
10-5, Namely, the first metric concerns the runtime
Training dynamics analysis of symmetric ansatz. Here we numerically exhibit that EQNTK has the ability to capture the training dynamics of QNNs with symmetrical ansatz. The hyperparameter settings are as follows. In the task of TFIM, the number of qubits of the Hamiltonian is set n 6. We employ the QNN with symmetric ansätze processed by SP with the number of layers L = 80 to optimize the loss function defined in Eqn. ([. The learning rate 1) and the maximum number of iteration T is set 10-1 and 1000, respectively. Figure plots the theoretically predicted residual training error according to Theorem 2 the practical residual training error with 30 independent random initializations, and their average versus the gradient descent optimization steps. The numerical results show that the residual error e decays exponentially, which echos with the training dynamies derived in Theorem 2
24

---

Published as a conference paper at ICLR 2023
Single instance
Averaged value
Exact analytic
5
1
0
40
80
120
160
200
Figure 9: Residual training error versus the gradient descent steps The black dotted curve, black solid curve, and dotted curve correspond the training dynamics of s(t) 30 different initializations, the theoretical prediction for the average dynamics of a(t), and the numerical values for the averaged e(t), respectively.
25


Reviews:
[{"review_id": "xh303xzQ03", "reviewer": "Reviewer_feix", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a quantum NTK framework to improve the training convergence of QNNs for the GSP problem via a symmetric ansatz design with a small effective dimension. It also proposes a novel symmetric pruning algorithm to extract the symmetric ansatz from the overparameterized and assymetric ansatz. Empirical results confirm the effectiveness of this symmetric pruning algorithm and the quantum NTK framework.", "summary_of_the_review": "This paper appears sound and novel. Please see the weaknesses listed above. I am not an expert in this area, and I am giving a rating of 6 for now. Based on the authors' rebuttal and discussions with other reviewers, I can reconsider my score.\n\n----------\nReview Update\n\nI have changed my score to 8 based on the authors' response.", "strength_and_weaknesses": "Strengths\n+ The paper seems well-motivated and the problem statement is clearly explained.\n+ The convegence bound of QNNs with various symmetric ansatz is significantly improved.\n\nWeaknesses\n- I don't think the authors did a good job at positioning their paper with prior art. For example, I would have liked a thorough comparison with related works in Section 5. Instead of having blanket statements like \"Our results differ from the above literature in both theoretical and practical aspects\", it would be better if the authors can clarify how this work is better in terms of both the QNN training and symmetric ansatz.\n- Can the authors quantify the hardware efficiency improvement of their symmetric ansatz?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "b3dGvHCa4T", "reviewer": "Reviewer_1zgw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the trainability of quantum neural networks (QNNs) with symmetric ansatzes and how to exploit the symmetry to improve the trainability of QNNs. More precisely, it provides a theoretical understanding of the better trainability of symmetric ansatz over asymmetric ansatz by proposing the effective quantum neural tangent kernel (EQNTK) and connecting it to the over-parameterization theory. With the support of the theory, it proposes a symmetric pruning algorithm to extract a symmetric ansatz from an over-parameterized but asymmetric ansatz to improve the trainability of QNNs.", "summary_of_the_review": "This paper obtains important theoretical results showing that constructing symmetric ansatzes improve the trainability of QNNs and provides a practical algorithm to devise symmetric ansatzes.", "strength_and_weaknesses": "Given many recent negative results on the trainability of QNNs, such as the barren plateau and convergence, with the importance of trainability for variational quantum algorithms, results given here are useful for the researchers in this field to devise symmetric ansatz with better training performance to achieve the potential quantum advantage. The results themselves focus on the problem of ground state preparation but they are applicable to general quantum machine learning problems. Their main results of the analytical convergence rate depend on the effective quantum neural tangent kernel, which can be easily calculated by calculating the norm of parameter gradients. This facilitates the evaluation of the convergence of QNNs without any training procedure. Another contribution of this paper is proposing a novel paradigm of exploiting pruning techniques to devise symmetric ansatz. As the symmetry pattern of the problem Hamiltonian is sophisticated, they employ the automorphism algorithm from graph theory to recognize the spatial symmetry of the problem Hamiltonian and apply it to prune the ansatz.\n\nA small collection of numerical simulations is given which show the effectiveness of symmetric pruning and justify the important role of EQNTK in guiding the trainability of QNNs. However, the paper did not numerically show that the EQNTK can capture the training dynamics of QNNs. I would like to see a figure display like Figure 2 in [1] in the author’s response.\n\nTypos:\n- In the sentence “The above results indicate that when the number of trainable parameters scales with $LK ∼ O(d_{eff}^2/(\\eta Tr(H^2 )))$”, the $H$ should be $H^*$.\n- “Recall the considered the problem Hamiltonian is expressed …”.\n\n[1] Junyu Liu, Khadijeh Najafi, Kunal Sharma, Francesco Tacchino, Liang Jiang, and Antonio Mezzacapo. An analytic theory for the dynamics of wide quantum neural networks. arXiv preprint arXiv:2203.16711, 2022b\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "R67kHwbHQpU", "reviewer": "Reviewer_WF6w", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The article analyzes the convergence of quantum neural networks (QNNs) where the employed ansatz shares the same symmetry of the problem Hamiltonian, and gives an analytical convergence rate under the framework of the quantum neural tangent kernel. More precisely, they use the information of the problem Hamiltonian to shrink the solution space to an invariant space with dimension $d_{eff}$ (dubbed effective dimension). Furthermore, they exploit the effective dimension to propose the effective quantum neural tangent kernel (EQNTK) to capture the training dynamics symmetric ansatz. They show that a symmetric ansatz with a small effective dimension has a large EQNTK, leading to better trainability. Guided by EQNTK, they further devise a paradigm of ansatz design where a symmetric ansatz is extracted from an over-parameterized one by pruning redundant symmetry-breaking gates.", "summary_of_the_review": "This paper provides elegant and rigorous theoretical results towards understanding the trainability of QNNs with symmetric ansatzes. The proposed algorithm is effective but still has room for further improvement.", "strength_and_weaknesses": "Strength:\n1. The article is well-written and obtains some positive results for the training of QNNs, which is of prominent importance for researchers studying variational quantum algorithms.\n2. The achieved analytical results of convergence based on the EQNTK have practical guidance on trainability without any training procedure. \n3. The proposed symmetric algorithm provides a novel vision for devising a symmetric ansatz to reduce the quantum resource required for reaching the over-parameterization regime. \n\nWeakness:\nThe paper did not discuss the connection with existing studies about geometric quantum machine learning or equivariant quantum circuits. I’d like to see the authors’ response to this issue.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%