MG-Net: Learn to Customize QAOA with Circuit Depth Awareness
Authors: Yang Qian
Xinbiao Wang
Yuxuan Du
Yong Luo
Dacheng Tao
Venue: NeurIPS 2024 poster (2024)
Keywords: Quantum approximation optimization algorithm
quantum machine learning
Primary area: machine_learning_for_physical_sciences
TL;DR: Our work analyzes the convergence behavior of QAOA and introduces the Mixer Generator Network (MG-Net) to dynamically formulate optimal mixer Hamiltonians tailored to distinct tasks and circuit depths.

Abstract: Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling combinatorial optimization challenges. However, their practical realization confronts a dilemma: the requisite circuit depth for satisfactory performance is problem-specific and often exceeds the maximum capability of current quantum devices. To address this dilemma, here we first analyze the convergence behavior of QAOA, uncovering the origins of this dilemma and elucidating the intricate relationship between the employed mixer Hamiltonian, the specific problem at hand, and the permissible maximum circuit depth. Harnessing this understanding, we introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians tailored to distinct tasks and circuit depths. Systematic simulations, encompassing Ising models and weighted Max-Cut instances with up to 64 qubits, substantiate our theoretical findings, highlighting MG-Net's superior performance in terms of both approximation ratio and efficiency.

MG-Net: Learn to Customize QAOA with Circuit Depth Awareness
Yang Qian li School of Computer Science, Faculty of Engineering, University of Sydney New South Wales 2008, Australia
Xinbiao Wang2. 2.1
Yuxuan Du Yong Luo
Dacheng T
Institute of Artificial Intelligence, School of Computer Science, Wuhan University
Wuhan, China
*College of Computing and Data Science, Nanyang Technological University
Singapore 639798, Singapore
"qiinyaanggg 12 217 70gmail com
*cyriewang@gmail. com #duyuxuua1120gmail.ccm
1luoyongOthu.
www.nn/osuuuuuuuu..ooooo edu. cn
dacheng. tww.ntu. edu.sg
Abstract
Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling combinatorial optimization challenges. However, their practical realization confronts a dilemma: the requisite circuit depth for satis- factory performance is problem-specifie and often exceeds the maximum capability of current quantum devices. To address this dilemma, here we first analyze the convergence behavior of QAOA, uncovering the origins of this dilemma and elu- cidating the intricate relationship between the employed mixer Hamiltonian, the specific problem at hand, and the permissible maximum circuit depth. Harness- ing this understanding, we introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians tailored to distinct tasks and circuit depths. Systematic simulations, encompassing Ising models and weighted Max-Cut instances with up 64 qubits, substantiate our theoretical findings, highlighting MG-Net's superior performance in terms of both approximation ratio and efficiency.
Introduction
Combinatorial optimization problems (COPs) 1. central numerous seientific and engineering disciplines 3 often defy efficient classical solutions due to their computational complexity [5)6]. A promising strategy overcome these computational challenges involves harnessing the power of quantum computing, as these COPs can be mapped to Ising Hamiltonians whose ground states denote optimal solutions 7 8. Leveraging this quantum representation, the Quantum Approximate Optimization Algorithm (QAOA)
9 has emerged to address these COPs. In particular, theoretical 3 underscore the potential of QAOA, suggesting its superiority over classical counterparts in certain contexts, particularly with unlimited infinite circuit depth. Mcantime, empirical studies [14 15 [6] affirm its applicability across a diverse spectrum of problems and devices.
analyses [10
Despite these advancements, QAOA's practical efficacy is challenged by the quantum coherence limits of modern quantum devices, there is ceiling the allowable maximum circuit depth p. As a result, standard QAOA often underperforms classical counterparts [8] 19. This motivates research shift towards redesigning the mixer Hamiltonian HM, key component of QAOA. As
illustrated in Fig. Ta), supported by the results of quantum adiabatic evolution 20 21), alternative
"Corresponinng authors
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

HM may exist that guide the system along more direct and efficient trajectory a shortcut- to the solution state, leading to better performance compared the standard QAOA. Besides, as shown in Fig. [b), empirical evidence indicates that the form of Ha promising good performance is varied with the allowable p. As such, diverse alternatives Har are proposed in past years, drawing upon concepts from quantum annealing [22], incorporating additional trainable parameters [17] or exploiting permutation symmetry [23]. However, these approaches require deep domain expertise and often lack generalizability across different tasks and circuit configurations p.
In response to these challenges, here we first analyze the convergence of QAOA on various mixer Hamiltonian con- figurations and circuit depths with the tool of representa- tion theory [24]. Our finding reveals that (i) the conver- gence of QAOA can be enhanced through parameter group- ing in the mixer Hamiltonian; (ii) the specific strategy for parameter grouping is dependent on the particular problem and the value of p. These two findings are instrumental in understanding the interplay between p, parameter group- ing, and the overall efficiency of the QAOA, providing valuable insights for the design of the mixer Hamiltonian,
L
Ug
Initial
Solution
Ve
00
(b)
Ayproodimat atioo ratin ower
Envisioned by the achieved theoretical results, we pro- pose an end-to-end learning framework, termed Mixer Generator Network (MG-Net), to dynamically design the mixer Hamiltonian H for a class of problems and distinct circuit depth constraints. Conceptually, MG-Net takes the problem's 's description and the available circuit depth p as input and directly outputs the optimal mixer Hamiltonian for a p-QAOA. There are three distinguished features of our proposal: (i) The ability to dynamically adjust HM according to p. enhancing its compatibility with practi- cal quantum devices; (ii) Fast customization of HM for unseen problems and circuit depth p, attributed to the multi-condition controlled generative network architec- ture; (iii) Circumvent the need for the expensive collection of vast training dataset of optimal HM by employing estimator-generta structure alongside two-stage train- ing approach. Note that the developed techniques can be flexibly extended to other variational quantum algorithms which may be independent of interests.
200
411
QADA
110
Figure I: Mixer Hamiltonian affects the performance QAOA. (a) The optimiza- tion trajectories of QAOA with varied mixer Hamiltonians Has- Given a fixed circuit depth p. tailored Has (highlighted in pink) can more effectively steer the quantum state towards the exact solution compared to the original HM used in QAOA. (b) Transition of the effective dimension defs required in QAOA with increasing p. 'ma-QAOA maa-QAAA' de- notes case with independent parameters [7]. contrasted with 'QAOA' where param- eters are fully correlated. 'he orange line denotes the average effective dimension over all samples.
(VQAs)
25 26]
The contributions of this paper are:
We provide rigorous theoretical analysis on the conver- gence of QAOA with sufficient circuit depth, elucidating the link between the performance and the parameter
grouping in QAOA circuits. This analysis offers guidance on the design of mixer Hamiltonian to achieve high approximation ratio for specified circuit depth.
We propose MG-Net, which dynamically tailors its predicted mixer Hamiltonian Ha to suit the given problem and circuit depth. Our model greatly reduces the cost of collecting labeled training data, attributed to an estimator-generant framework and a two-stage training strategy.
The proposed MG-Net demonstrates remarkable generalization ability from a limited dataset to a broad spectrum of combinatorial problems, which facilitates rapid and efficient creation of HM for unseen problems, advancing the practical utility of QAOAs.
Extensive experiments on the Transverse-fiel Ising model and Max-Cut up to 64 qubits verify our theoretical discoveries and demonstrate the advantage of MG-Net in achieving higher approximation ratios at various circuit depths compared to other quantum and traditional methods. The code is released at wittt::///// ://g tigthb...... com/ QQQYang/MG- Net

---

2 Background
2.1 Quantum approximation optimization algorithm
Considering a COP defined on a set of N binary variables 2 = 21 ...... EN, where 2; E {+1}, our objective is to identify bit string that maximizes specific objective function C(z) {+1 J R2o. Intuitively, the solution space grows exponentially with N, rendering the exact solution to many COPs intractable [ In practice, an alternative approximation algorithm is selected to seek an approximate solution z to achieve high approximation ratio r = C(z))/Cman where Ciaxx max, C(z).
In response to this inherent complexity, Quantum Approximate Optimization Algorithm (QAOA) 9 is proposed. In this framework, the bit string x is encoded into quantum state (x) [1 ENv with dy (1 24) /2, and the objective function ((x) is encoded into the problem Hamiltonian Hc E C² X2" so that He (z)) C(x) (æ)). Refer to Appendix A for the omitted details.
QAOA is hybrid quantum- classical algorithm that combines a parameterized quantum eircuit (PQC) for state evolution and a classical optimizer for parameter updates. For p-layer QAOA circuit shown in Fig. Ia), the quantum state (1pp) is prepared by alterntely applying the problem Hamiltonian Hc
and the mixer Hamiltonian HM >i= X; on the initial state (vo)), formulated as
2
(a (3)
II
B3p His iop He Wo)
where a = ap) and 3 = (31,.., Bp) are 2p trainable parameters. These parameters are optimized maximize the expectation value of the problem Hamiltonian He:
(a", ,/)) = arg max Pp(a. a
where F, 3) = (a, Hy can be estimated by multiple measurements on the quantum system. As Fp(a", , approaches the optimal value Caax of the objective function, obtain the approximate solution to the combinatorial optimization problem with high probability by
measuring the state [a, ,38)) }} in the computational basis. A metric for assessing the performance of QAOA is the approximation ratio r = Fa (,""",))),, ,3)) /Cmax.
2.2 Symmetry in QAOA
Symmetry, ansatz design, and effective dimension. A symmetry S refers to the unitary operator leaving the operator H invariant such that St = H (or (s, H] = 0). All symmetries form group S where given any two symmetries S1, S2 E S, the compositions S,S₂ and S2S, are also symmetries in S. Among various symmetries, the most relevant one to our work is the permutation symmetry Sx, with the subscript being the qubit count N and Sy being the symmetric group. For example, a permutation ı with (1) 3. (2) = 1, (3) = 2 acting on the state (u)] (122) (Wa) yields (41) (122) (&a) (&aa) (4)) l222.. Throughout the whole study, we denote the group of permutation symmetries of the problem Hamiltonian He as Per(Hc) = { E SN I HoT Hc).
Consider an N-qubit PQC U(0) = -II II e 0H with O E θ and d = 2 We call (()) symmetric PQC with respect to the problem Hamiltonian He if there exists a symmetry group of He such that SU) = for any O E and S. This symmetry determined by the generators of PQCs A = [HI ... Hx) which is also called ansatz design. as (U)),, S] = 0 holds for any 0 E if and only if H (0) = 0 for any E [K). Such symmetry can be quantified by the effective dimension [27 28
Definition 2.1 (Effective dimension). Consider an N-qubit QAOA instance ((v6) (8), Hc) where (()) acts on the vector space V. If there exists a direct sum decomposition V = # L and V* E (V,), 1=1 such that (0) |vo) E V* for any 0 and the ground state of the problem Hamiltonian (1**) satisfies (xb*) E V*. then the effective dimension detf N is defined as the dimension of V*.
Experimental and theoretical analysis has shown that symmetric ansatz design with a small effective dimension contributes to better trainability 29 28 30)
3

---

Symmetry and ansatz designs in QAOA. The PQC in Eqn. ① adopted in the original QAOA, fully groups (FG) the trainable parameters and has the ansatz design AFG a Hc), which is symmetric with respect to Hc under the permulation symmetry. This is because its mixer Hamiltonian HM = - X; is invariant under arbitrary permutation operator.
However, AFG fails to employ the specific symmetry group of Hc. This issue can be addressed by partially grouping (PG) trainable parameters in QAOA. For example, denote Hc = E(i..i)) Zi, Zin with Zj. being the Pauli-Z. operator acting on the jı-th qubit. An alternative symmetric ansatz design is ApG = { ... oo Hor,".. .., where Ho, = Eieo, X; and Ho; = Ea 7:7, refer to the generators respecting the permutation symmetry of Hc satisfying HM
Σ Ho, and Hc Dド=1 Ho; [23] The ansatz design ArG enables more free parameters than the ansatz design AFG in each layer, and has been empirically shown with faster convergence rate than AFG given the same number of layers.
When Hc is asymmetric, another typical ansatz design in QAOA is ANG (Z Z:,,.". 7:p 7 X1,'.. ,x), where the parameters of all parameterized gates are independent and non-grouping (NG). Notably, the PQCs related to various ansatz design AFG ANG,ANG employ the same parameterized gates but with different parameter grouping strategies, where (3,x) each layer can be fully grouped, partially grouped, and non-grouped
23
3 Convergence theory of QAOA
In this section, we theoretically illustrate how employing appropriate parameter grouping corresponds to better convergence performance. Similar to Refs. (27) and (28), our derivations are based on the observation that the exploited PQC with highly-symmetee ansatz structure generally enables a faster convergence rate.
Theorem 3.1 (Convergence), Consider a QAOA instance denoted as (Woo) U()), Hc) with (0)
determined by the related ansatz design. Let ArG, APG,ANG be the ansatz designs of the circuits with parameters fully grouped, partially grouped, and no-grouped. Their effective dimension yields den (AFG)
den((Apo S den((AN),
(3)
where the equality in the inequality holds if there is no spatial symmetry in Hc. Besides, there exists des-deeendent threshold C so that circuit depth p C, the iterations T required achieve the same approximation ratio yield
TPG TFG S TNG-
The proof of Theorem 3.1 and more elaborations are presented in Appendix B The achieved results, combined with the over-parameterization theory of PQCs (30], deliver the following two implications. First, when the circuit depth p > C' is sufficiently large such that all PQCs with various ansatz designs reach the parumetrriitioonnnnnnnn regime, performing the parameter grouping can effectively decrease the effective dimension detf compared with the PQCs with no-parameter grouping, leading a faster convergence rate. Second, the aerrparrametrizzatoon of QAOA occurs when the number of trainable parameters exceeds a critical point that proportionally related deff-
The above two implications indicate the selection of AFG. or ANG is complicated and is both depth- and problem-dependert dependent. In particular, given a specified p. adopting parameter grouping strategy can simultaneously reduce the number of parameters and the effective dimension, making it difficult to determine whether the QAOA reaches the parameterrizztioonn regime. For instance, in scenario such that the parameter grouping strategy drastically reduces the number of parameters but only slightly reduces the effective dimension, an warr-tarameterized QAOA could transform to an under-parameterda stuck in bad local minimal 31 32
QAOA, leading to a degraded convergence as the optimization can be easily
4 MG-Net
The implication of Theorem 3.1
inspires us to devise a method for dynamically generating an appropriate mixer Hamiltonian H tailored to both the problem G at hand and the specified circuit depth p. For this purpose, we harness the power of deep learning and devise an end-to-end learning framework, dubbed Mixer Generator Network (MG-Net).

---

Problen cnosder
Probicm encoder
Stage
Problem G
Mixer
Mixer encoder
Cost estimator
11.
Dipth rmbadting
Degth umbeedting
(b) Inference
Problem praph caceder
G
Miser ganerator
QADA walver
Degth umbedding
Figure 2: Framework of MG-Net. (a) Training Phase. Initially (left), the estimator is trained precisely predict QAOA performance specific problem instances, circuit depths, and mixer Hamiltonians. subsequent stage (right). with the cost estimator fixed, the mixer generator is trained through unsupervised learning to derive the optimal mixer Hamiltomian that minimizes the cost estimator's 's output. (b) Inference Phase. Given problem G and circuit depth p. the mixer generator produces mixer Hamiltonian, subsequently utilized a QAOA solver to find the solution.
4.1 Framework of MG-Net
Before presenting the proposed MG-Net, let us first formalize the learning problem towards design- ing the mixer Hamiltonian Hx. To incorporate different Pauli operators and parameter grouping strategies, we extend the definition of an N-qubit mixer Hamiltonian Нм in Eqn. (I) to a more generalized form, supporting flexible operators and parameter correlations by substituting the Pauli-X operator with selection of general Pauli operator and stratifying the N operators into K groups. Mathematically, the refined mixer Hamiltonian yields
HM
Σ P. LEG
(5)
j=1
where B5 refers to the trainable parameter controlling the j-th group of operators, 9j contains the indices of operators belonging to the j-th group such that u , 9j [N] and G; ng, 0 for Vi A and P. refers to Pauli operator. This work focuses on P. E X, as the types of candidate operators, rather than using only the single Pauli-X operator. Previous studies have demonstrated the effectiveness of using Pauli-Y operators in mixer Hamiltonians 33 K as summarized in Tab, [ In this sense, operators in the same group are correlated with each other, sharing the same parameter. In this way, the design of HM is decoupled into two distinct tasks: determine the parameter groups " identify the appropriate operator types P.. With the reformulation above, the decoupled tasks can be accomplished by learning a mapping rule f (G, p) - (g.P) with {9, 1 and P E (X,) Y) referring to the parameter correlation and mixer Hamiltonian.
Table Previous works that have introduced the Pauli-Y operator as a candidate mixer Hamiltonian.
Works
Mixer Hamiltonian
DC-QAOA 33
YY,, Use(N) (X,, YJ u (EEeN YJ u (E X,) ULJeINIiNN) (B,C,IB,.C, (X,Y))
QAOA
Designing model to learn f faces two main challenges:
(C-1) The variety of combinatorial optimization tasks leads to uncertain input formats for the model, which necessitates universal representation method and retains essential properties of the original
5

---

data, such as permutation invariance:
(C-2) The exponential growth of the search space for both parameter correlation and operator types. (i.e., scaling at O(N*) ) and O(2*), ), respectively), hurdles the design of an effective learning method. For instance, directing training learning model in the supervised learning paradigm may require computationally unaffordable training examples to ensure good prediction accuracy.
We next present an end-to-end learning framework-Miix Generator Network (MG-Net), as depicted in Fig. 2 to address the above challenges. Particularly, to address C-1, we devise a problem encoder which transforms each problem G into a unified directed acyclic graph Gc, ensuring a consistent and effective input format. Coupled with the mixer encoder, it maps both the problem and mixer Hamiltonian to a shared hidden space. To address C-2, MG-Net features unique estimator estimator-generatoor framework, supplemented by hvo-stage training strategy. The role of these techniques is summarized below and their implementation details are demonstrated in the subsequent subsections.
Role of estimator. Rather than directly seeking the optimal parameter correlation strategy 9" and operator type p for given (G,p), we devise cost estimator to map the relationship between (G, P) and the achievable minimal cost F' of the corresponding QAOA in Eqn. (
Role of generator. We devise a generator to predict (G, P) that minimizes the cost estimator's s output. This design requires only the cost of any mixer Hamiltonian as a label, thus avoiding the exhaustive search of optimal pairs (G", P*).
Two-stage training. The pipeline is visualized in Fig. Za).
Stage 1 (Cost Estimator Training). This stage, marked in purple, focuses on training the cost estimator using supervised learning. Inputs include the problem graph G, potential mixer Hamiltonians HM- and the chosen circuit depth p. with the corresponding cost y as the target label. Stage 2 (Mixer Generator Training). This stage, marked in orange, freezes the cost estimator and only updates the mixer generator to minimize the ouiput of the cost estimator under the unsupervised learning paradigm.
For inference unknown problem instances (in Fig. (()). MG-Net employs only the mixer generator to predict the optimal mixer Hamiltonian. which then fed into QAOA solver to derive the final solution. Distinguished by its ability to generalize effectively across a class of problems from a limited learning set, MG-Net sets itself apart from previous studies. Refer to Appendix. C for discussion.
4.2 Implementation of MG-Net
Data encoder in MG-Net. MG-Net exploits three types of data encoder, i.e., the problem encoder, mixer encoder, and depth encoder, which maps the given problem G. the candidate mixer Hamiltonian HM, and the specified depth p the same hidden feature space. The construction of these encoders is introduced below and the omitted details are deferred to Appendix D.2
Cost estimator in MG-Net (Stage 1). Recall Stage 1 in Sec. 4.1 the cost estimator takes the encoded problem graph Gg. the encoded mixer Hamiltonian GM. and the encoded circuit depth T. as inputs, and outputs the prediction of the achievable minimum loss of the corresponding QAOA. Each input is processed by an independent branch respectively: the problem graph branch, the mixer Hamiltonian branch, and the circuit depth branch, shown in Fig. B The concatenation of three types of features is subsequently utilized by a multi-layer perceptron (MLP) to output the minimum loss 9 that the QAOA ansatz can achieve. Refer Appendix. D.3 for details.
Mixer generator in MG-Net (Stage 2). The mixer generator in MG-Net takes Ge and up as input and outputs targeted mixer Hamiltonian H Specifically, the mixer generation is composed of two separate sub-generators: the operator type generator and the parameter grouping generator defined in Eqn. (5), shown in Fig. (b). The operator type generator is responsible for generating operator types P. which is conceptualized as a graph node classification task. The parameter grouping generator is responsible for predicting the sets of index groups (G, } with an unspecified K, which is modeled as a link prediction task. Refer to Appendix. D.3 for details.
4.3 Training strategy
The training process of MG-Net is varied for the first and second stages, under supervised and unsupervised learning paradigms, respectively.

---

Figure Structure of cost estimator and mixer generator. (a) Cost estimator. The cost estimator comprised of three distinct branches, each dedicated to processing different types of data: the original problem. the candidate mixer Hamiltonian, and the circuit depth. Their outputs are then integrated to predict the cost value achievable by the QAOA circuit. (b) Mixer generator. The mixer generation is divided into two distinct parts: operator type generation and parameter grouping generation. The former executed node classification lask, while latter approached link prediction task.
First-stage training. This stage involves constructing labeled dataset D ((G)) G() Dp ()),, y where the i-th sample consists tuple of features (i.e., the problem description G the mixer G(), and the circuit depth feature ) and the label (( representing the minimum cost value achievable by this QAOA instance (i.e., determined by repeatedly executing such QAOA with varying initial parameters). Once D ready, the cost estimator is optimized by minimizing the loss function
Lee = AeCe ArCr,
(6)
where de E [0, 1] and A E J0, 1] are two hyyper-parameten of each loss, fe EE (y (/ the mean square error, and E, is the ranking loss
L. 52
Σ max(0. sign(y (0))) g(H))).
Second-stage training. This stage involves the training of the mixer generator via unsupervised learning. The loss function of this stage is
s E 1=1
Ling
(7)
S
where C(-) and (-) represent the output of the cost estimator and mixer generator, respectively. Note that only the parameters of the mixer generator are updated; the cost estimator parameters remain fixed ensure consistent evaluation criteria throughout the whole learning process.
5 Experiments
We evaluate the performance of MG-Net by two typical applications of QAOA: weighted Max- Bux-Cut and Transverse-fiele Ising model (TFIM), each of which is elucidated below.
Weighted Max-Cut. Denote weighted graph as = (V, F,, W), where V is the set of vertices of graph, E is the set of graph edges, W {wey (i,))E is the set of weights assigned each edge. The problem Hamiltonian for the weighted Max- Mux problem H MaxCut 0.5 E(i W.y Z.Zj
where Z, is a Pauli-Z. operator acting on the i-th qubit.
E TFIM. Our focus is a class of inhomogeneous TFIMs: - Jr ZZ N,
where Jıj is the interaction strength between neighboring spins (or qubits) (i,j), and h signifies the strength of global transverse field applied to each spin. In this model, the interaction strengths Jıj can vary between different pairs of spins, adding layer of complexity to the system.
7

---

5.1 Experiment configuration
Dataset construction. The Max-Cut problem focuses weighted 3 3-degree regular (w3r) graphs, where the edge weights {wsy} are uniformly sampled from [0, 1]. The TFIM focuses on 1D instances where a qubit i E [N 1] has neighbors i + (mod N). The strength J.g and h are uniformly sampled from [0.5, 1.5] and [0.1, 2] respectively. The training dataset D in Sec. 4.3 contains $ = 100 instances for both two tasks with size up to N = 64 qubits, while The test dataset DT contains another 100 problem instances which are different from that of D Refer to Appendix D.1 for details.
on
Optimization and training of MG-Net. The cost estimator and mixer generator trained using an Adam optimizer with a learning rate of 10-1, and hyper-parameters X = and X, = 1 in Eqn. (6
Optimization of QAOA. After predicting the problem- problem-hardware- hardware-tailoree mixer Hamiltonian HM by the trained mixer generator, QAOA circuit with the initial state + and HM is optimized by an Adam optimizer with a learning rate of O. 15. Each setting undergoes 10 independent runs with
varied random seeds and initial parameters obtain the statistical results. Refer to Appendix D.4 detailed discussion about the selection of initial state.
5.2 Results
Cost estimator acts as an accurate performance indication for QAOA. The behavior of the cost estimator on the test dataset with varying circuit depths p and two distinct parameter grouping strategies NG and FG (defined in Theorem 3.1) is recorded in Fig. 4 In Fig. 4a). we observed strong correlation between the estimated and minimum cost values, and the correlation strength changes with p and parameter grouping strategy. Particularly, the cost estimator predicts a high likelihood of finding the most accurate solution for QAOA circuits with FG parameters and depth of p = 92. This prediction aligns with the actual performance of QAOA under these specific conditions. To further investigate the cost estimator's 's behavior with more complex mixer operator types, con- ducted additional experiments using an extended set candidate operators (X, Y, X XX,, }. which includes two-qubit operators. As shown in Fig. 4 (b), the cost estimator continues to demonstrate its efficiency and high performance, even as the complexity of the mixer Hamiltonian design increases.
00
Treaent oud
C-0-0
O-O-0
200
Figure 4: Behavior of cost estimator. (a) The correlation hetween the estimated cost and the minimum oost for Max-Cut (left) and TFIM (right). Each point represents the result of problem instance. The dashed line represents that QAOA can find the exact solution y = x. (b) Behavior of cost estimator with extended mixer operator pool {X, Y, XX, YY). 'label' represents the actual achieved approximation ratio, while 'pred' represents the result predicted by the cost estimator. (c) The achievable cost under various circuit depth for Max-Cut (left) and TFIM (right). The label 'CE' is the abbreviation of cost estimator. The dashed lines represent the cost achieved by QAOA, while the solid lines represent the cost estimated by model.
We next focus on the behavior of the cost estimator concerning p as shown in Fig. ((c. We note that for FG (standard QAOA), the estimated loss decreased monotonically with increasing p. aligning with standard QAOA's behavior. Under the NG scenario (multi-angle QAOA), a transition that QAOA performance begins to decline is observed when the circuit becomes excessively long (p > 42). These results indicate the reliability of the cost estimator as a performance indicator for QAOA and reveal the complexities in QAOA performance under conditions of increased circuit length.
Mixer generator. We next evaluate the performance the customized mixer Hamiltonian generated by MG-Net. As shown in Fig. 5 a). the number of trainable parameters # P of the generated quantum circuits aligns with the maximum scenarios where all parameters are non-correlated (labeled as 'NG') for smaller circuit depths 20. This alignment indicates that MG-Net effectively enhances
8

---

the expressibility of the QAOA ansatz for limited- circuits without significantly increasing the number of parameters, thereby avoiding potential trainability issues. As p increases, transition occurs. The growth rate of # starts to decelerate, reaching notable transition point at p 62 for Max-Cur (p = 52 for TFIM). Beyond this threshold, the generated mixer Hamiltonians gradually converge towards the configuration seen in standard QAOA, with fully grouped parameters.
(b)
0.966
(0)
MGGOe Dieokai!
Nec (TEIN))
300
2IFIC
16
Ouer (EM54)
12"0
-20
000
12-4
Ecretion
Figure 5: The trainability of the quantum circuits generated by MG-Net for Max-Cut and TFIM. (a) The number # of trainable parameters of the quantum circuits with mixer Hamiltonian predicted MG-Net. (b) Comparison
effective dimension detf quantum circuits standard QAOA and MG-Net driven QAOA (labeled as 'Ours'). The green and grey solid lines denote the average effective dimension dess of the predicted circuits that can achieve an approximation ratio over 0.995 for Max- Cut and TFIM, respectively. It assesses circuits achieving an approximation ratio of least 0.995. (c) The convergence of QAOA with FG, NG and mixer Hamiltonian predieted by MG-Net for Max-Cut 64-node weighted graphs.
Fig. b)b) compares the effective dimension dest of quantum circuits achieving high approximation ratio 0.995 in standard QAOA and MG-Net driven QAOA. The results show that circuits generated by MG-Net achieve 2 0.995 across all values of p. even as low as = 2, outperforming standard QAOA, which only reaches this level for p > 50 for Max-Cut > 20 for TFIM). Besides, the effective dimension of these high-quality quantum circuits gradually decreases with growing p. in line with the convergence analysis in Theorem 3.1 These findings suggest that MG-Net dynamically adjusts quantum circuits in response to changes in circuit depth thereby consistently ensuring high performance.
Fig. 5)c) explicitly demonstrates the optimization behavior of 64-qubit QAOA with FG, NG and the mixer Hamiltonian predicted by MG-Net. The left panel displays the loss curves during the optimization quantum circuits with = revealing that our method achieves the most rapid convergence. The right panel further explores the gradients of the three methods during optimization. Notably, the parameter gradient norm of our method maintains a trainable level of 1, whereas the gradient for FG and NG falls to 10-1 and 10-4 respectively, compromising their trainability.
Performance comparison. In evaluating the effectiveness of our proposed method for solving Max- Cut problems, we conducted a comparative analysis against both classical and quantum algorithms. The benchmarks included the greedy algorithm, Goemaan-Williamson (GW) algorithm (35), alongside various quantum approaches such QAOA, ADAPT-QAOA, and multi-angle QAOA (ma-QAOA). Our analysis, based on the average results from 100 graphs in our test dataset, is summarized in Tab. 2 The findings reveal that method consistently outperforms other techniques in achieving a higher approximation ratio, particularly in larger-scale problems. Refer to Appendix E. for comparison results TFIM.
More numerical results. We have conducted additional analysis on the behavior of MG-Net and additional experiments on more tasks. Refer to E for more details.
6 Conclusion
In this study, we analyze QAOA's convergence on varied mixer Hamiltonians, focusing on parameter grouping strategies. We introduce MG-Net for dynamically generating optimal mixer Hamiltonians for various problems and circuit depths. Numerical experiments on Max-Cui and TFIM confirm MG-Net's efficacy in enhancing QAOA's approximation ratio, particularly for large-scale problems,

---

Table 2: Comparison of approximation ratio among different methods for Max-Cut.
Method
6 qubits
16 qubits
64 qubits
Greedy
0.89 + 0.104
0.91 + 0.047
0.79
GW
0.94 + 0.074
0.93 + 0.052
0.91
QAOA
0.93 + 0.027
0.35 = 0.119
0.19
ADAPT-QAOA
0.75 + 0.129
0.58 + 0.154
ma- ma-QAOA
0.98 + 0.004
0.84 + 0.129
0.0
Ours
0.99 + 0.0004
0.95 + 0.152
0.96
while ensuring low circuit complexity. This research advances the understanding and application of QAOA across various circuit depths.
Despite these promising outcomes, our work has several limitations that need to be addressed in future research. Firstly, training the cost estimator of MG-Net involves the construction of labeled dataset DTY, which introduces additional resource consumption. Future work can focus on more efficient training algorithms. Additionally, on early fault-tolerant devices, which limits the exploration of extending MG-Net to other quantum algorithms and noisy devices. Addressing these limitations will further enhance the robustness and scalability of MG-Net, offering potential for broader use in VQAs.
current approach is specifically designed for QAOA
Acknowledgments and Disclosure of Funding
The proposed research is partially supported by Dr Tao's NTU RSR and Start Up Grants.
References
[1] Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti- Spaccamela, and Marco Protasi. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012.
[2] Clayton W Commander. Maximum cut problem, max-cut. Encyclopedia of Optimization, 2009.
[3] Tommy R Jensen and Bjarne Toft. Graph coloring problems. John Wiley & Sons, 2011.
[4] Karla L. Hoffman, Manfred Padberg, Giovanni Rinaldi, et al. Traveling salesman problem. Encyclopedia of operations research and management science, 1:1573-1578, 2013.
[5] Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
[6] Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
[7] Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, 2:5, 2014.
[8] Young-Hyun Oh, Hamed Mohammadbagherpoor Patrick Dreher, Anand Singh, Xianqing Yu, and Andy Rindos. Solving multi-coloring combinatorial optimization problems using hybrid quantum algorithms. arXiv preprint arXiv: 19/1000555, 2019.
[9] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint /411:::4111400 2014.
[10] Farhi and AW Harrow. Quantum supremacy through the quantum approximate optimization algorithm (2016). arXiv preprint arXiv: 1602.07674.
[11] Seth Lloyd. Quantum approximate optimization is computationally universal. arXiv preprint 1:Xiv:112.11107, 2018. 2018.
10

---

[12] Mauro ES Morales, Jacob D Biamonte, and Zoltán Zimborás. On the universality of the quantum approximate optimization algorithm. Quantum Information Processing. 19:1-26, 2020.
[13] Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. A review quantum approximate optimization algorithm and its variants. Physics Reports, 1068:1-60 2024.
[14] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for maxcut: fermionic view. Physical Review A, 97(2):022304, 2018.
[15] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S Collins, Arinjoy De, Paul W Hess, Harvey B Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, et al. Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator. Proceedings of the National Acudemy of Sciences, 117(41)25396-25400 2020.
[16] Leo Zhou, Sheng-Tar Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near- term devices. Physical Review X, 10(2):21067,, 2020.
[17] Rebekah Herrman, Phillip C Lotshaw, James Ostrowski, Travis S Humble, and George Siopsis. Multi-angle quantum approximate optimization algorithm. Scientific Reports, 12(1):6781, 2022.
[18] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp. Andreas Fuhrer, Jay M Gambetta, Marc Ganzhor, et al. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3(3):030503, 2018.
[19] Gian Giacomo Guerreschi and Anne Y Matsuura. Qaoa for max-cut requires hundreds of qubits for quantum speed-up. Scientific reports, 9(1):6903, 2019.
[20] Michael Victor Berry. Transitionless quantum driving. Journal of Physics A: Mathematical and Theoretical, 42(36))365303, 2009.
[21] David Guéry-Odelin, Andreas Ruschhaupt, Anthony Kiely, Erik Torrontegui, Sofia Martínez- Garaot, and Juan Gonzalo Muga. Shortcuts to adiabaticity: Concepts, methods, and applications. Reviews of Modern Physics, 91(4):045001, 2019
[22] Yunlong Yu, Chenfeng Cao, Carter Dewey, Xiang-Bin Wang, Nic Shannon, and Robert Joynt. Quantum approximate optimization algorithm with adaptive bias fields. Physical Review Research, 4(2):223249, 2022.
[23] Frederic Sauvage, Martin Larocca, Patrick J Coles, and Marco Cerezo. Building spatial symmetries into parameterized quantum circuits for faster training. Quantum Science and Technology, 2022.
[24] Edwin Williams. Representation theory, MIT Press, 2002.
[25] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physies, 3()):22--64 2021.
[26] Yang Qian, Xinbiao Wang, Yuxuan Du, Xingyao Wu, and Dacheng Tao. The dilemma of quantum neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[27] Xuchen You, Shouvanik Chakrabarti, and Xiaodi Wu. A convergence theory for over- parameterized variational quantum eigensolvers. arXiv preprint vrxXiv2205.124883 2022.
[28] Xinbiao Wang, Junyu Liu, Tongliang Liu, Yong Luo, Yuxuan Du, and Dacheng Tao. Symmetric pruning in quantum neural networks, 2023.
[29] Martin Larocca, Piotr Czarnik, Kunal Sharma, Gopikrishnan Muraleedharan, Patrick J Coles, and M Cerezo. Diagnosing barren plateaus with tools from quantum optimal control. Quantum, 6:824, 2022.

---

[30] Martin Larocca, Nathan Ju, Diego overparameetrization quantum neural networks, Nature Computational Science, 3(6):542-551, 2023.
Patrick J Coles, and Marco Cerezo. Theory of
[31] Xuchen You and Xiaodi Wu. Exponentially many local minima in quantum neural networks. In International Conference on Machine Learning, pages 12144-12155. PMLR, 2021.
[32] Eric Ricardo Anschuetz. Critical points in quantum generative models, 2022.
[33] Pranav Chandarana, Narendra N Hegade, Koushik Paul, Francisco Albarrán- Arriiaan,,, Enrique Solano, Adolfo Del Campo, and Xi Chen. Digtiized-counterdiaatti quantum approximate optimization algorithm. Physical Review Research, 4(1):013141, 2022.
[34] Linghua Zhu, Ho Lun Tang, George S Barron, FA Calderon-Vargas, Vargas, Nicholas J Mayhall, Edwin Barnes, and Sophia E Economou. Adaptive quantum approximate optimization algo- rithm for solving combinatorial problems on quantum computer. Physical Review Research, 4(3):033029, 2022.
[35] Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), (116):115--1155 1995.
[36] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. Quantum circuit learning. Physical Review A, 98(3):032309, 2018.
[37] Louis Schatzki, Martin Larocca, Quynh T Nguyen, Frederic Sauvage, and Marco Cerezo. Theoretical guarantees for Information, 10(1):12, 2024.
quantum neural networks. npi Quantum
[38] Barry Simon. Representations of finite and compact groups. Number 10. American Mathemati- cal Soc., 1996.
[39] Ruslan Shaydulin and Stefan M Wild. Exploiting symmetry reduces the cost of training qaoa. IEEE Transactions on Quantum Engineering, 2:1-9, 2021.
[40] Kaiyan Shi, Rebekah Herrman, Ruslan Shaydulin, Shouvanik Chakrabarti, Marco Pistoia, and Jeffrey Larson. Multiangle qaoa does not always need all its angles. In 2022 JEEF/ACM 7th Symposium Edge Computing (SEC), pages 414-419. IEEE, 2022.
[41] Michelle Chalupnik, Hans Melo, Yuri Alexeev, and Alexey Galda. Augmenting qaoa ansatz with multiparameter -iblee--nddeendeent layer. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 97- IEEE, 2022.
[42] Stuart Hadfield, Zhihui Wang, Bryan O' G'Gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to quantum alternating operator ansatz. Algorithms, 12(2):34, 2019.
[43] Takuya Yoshioka, Keita Sasada, Yuichiro Nakano. and Keisuke Fujii. Fermionic quantum approximate optimization algorithm. Physical Review Research, 5(2):023071, 2023.
[44] Jonathan Wurtz and Peter J Love. Counterdiabaticity and the quantum approximate optimization algorithm. Quantum, 6:635, 2022.
[45] Andreas Bärtschi and Stephan Fidenhenz. Grover mixers for qaoa: Shifting complexity from mixer design state preparation. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 72-82. IEEE, 2020.
[46] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Physical review letters, 125(26))260005, 2020.
[47] Javier Villalba- Diez, Ana González-Marcos, and Joaquín B Ordieres-Meré. Improvement of quantum approximate optimization algorithm for max-cut problems. Sensors, 22(1):244, 2021.
12

---

[48] Shi-Xin Zhang, Chang- Yu Hsieh, Shengyu Zhang, and Hong Yao. Neural predictor based quantum architecture search. Machine Learning: Science and Technology. 2(4):045027, 2021.
[49] Esther Ye and Samuel Yen-Chi Chen. Quantum architecture search via continual reinforcement learning. arXiv preprint arXiv:21 2021.
[50] Mateusz Ostaszewski. Lea M Trenkwalder, Wojciech Masarczyk, Eleanor Scerri, and Vedran Dunjko. Reinforcement learning for optimization of variational quantum circuit architectures. 2021.
Advances in Neural Information Processing Systems,
[51] En-Jui Kuo, Yao-Lung L. Fang, and Samuel Yen-Chi Chen. Quantum architecture search via deep reinforcement learning, arXiv preprint urXiv:2104.077 2021.
[52] Fan-Xu Meng, Ze-Tong Li, Xu-Tao Yu, and Zai-Chen Zhang. Quantum circuit architecture optimization for variational quantum eigensolver via monto carlo tree search. IEFE Transactions on Quantum Engineering, 2:1-10, 2021.
[53] 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):62, 2022.
[54] Kehuan Linghu, Yang Qian, Ruixia Wang, Meng-Jun Hu, Zhiyuan Li, Xuegang Li, Huikai Xu, Jingning Zhang, Teng Ma, Peng Zhao, et al. Quantum circuit architecture search superconducting processor. arXiv preprint 2tti::20/.0003::00 2022.
[55] Zhimin He, Chuangtao Chen, Lvzhou Li, Shenggen Zheng, and Haozhen Situ. Quantum architecture search with meta-learning. Advanced Quantum Nechnologies, 5(8):2100134, 2022.
[56] Shi-Xin Zhang, Chang- Yu Hsieh, Shengyu Zhang, and Hong Yao. Differentiable quantum architecture search. Quantum Science and Technology, 7(4):045023, 2022.
[57] Wenjie Wu, Ge Yan, Xudong Lu, Kaisen Pan, and Junchi Yan. Quantumdarts: differentiable quantum architecture search for variational quantum algorithms. In International Conference on Machine Learning, pages
PMLR, 2023.
[58] Cong Lei, Yuxuan Du, Peng Mi, Jun Yu, and Tongliang Liu. Neural auto-designer for enhanced quantum kernels. In The Twelfth International Conference Learning Representations, 2024.
(59] Xudong Lu, Kaisen Pan, Ge Yan, Jiaming Shan, Wenjie Wu, and Junchi Yan. Qas-bench: rethinking quantum architecture search and benchmark. In International Conference on Machine Learning, pages 22880-22898, PMLR, 2023.
[60] Linghua Zhu, Ho Lun Tang, George S Barron, FA Calderon- Nicholas Mayhall, Edwin Barnes, and Sophia E Economou. An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. arXiv preprint arXiv:2005. 2020.
[61] Zeqiao Zhou, Yuxuan Du, Xinmei Tian, and Dacheng Tao. Quoa-in-qaoa: solving large-scale maxcut problems on small quantum machines. Physical Review Applied, 19(2):024027. 2023.
[62] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[63] Yang Qian, Yuxuan Du, Zhenliang He, Min-Hsiu Hsieh, and Dacheng Tao. Multimodal deep representation learning for quantum cross-platform verification. Physical Review Letters, (33(13)13060)) 2024.
[64] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M Sohaib Alam, Guillermo Alonso-Linaje, B AkashNarayanan, Ali Asadi, et al. Pen- nylane: Automatic differentiation of hybrid quantum-classical computations. arXiv preprint PrXiv:1811.04990 2018
13

---

[65] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga. et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
A Optimization of QAOA
In this section, we separately elaborate on the elementary notations in quantum computing, the preliminary of Hamiltonian, and the optimization strategy of QAOA.
Basics of quantum computation. The elementary unit of quamtum computation is qubit (or quantum bit), which is the quantum mechanical analog of classical bit. A qubit is two-level quantum- mechanical system described by a unit vector in the Hilbert space C?, In Dirac notation, a qubit state is defined as (6) = co 0)) + [1} C where (0) [1. 0] T and [1) = [0. 1]" specify two unit bases and the coefficients Co. C1 E C yield lcol 2 + |c1 2 = 1. Similarly, the quantum state of n qubits is
defined unit vector in C²" i..., (v) Σj= c le,), where le,) E R² is the computational
basis whose j-th entry is 1 and other entries are O, and Σ lc,/ 1 with Cj 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 (v)) is p = 115) (1bl E C²" where (v²l ww) refers to the complex conjugate transpose of (w). For a set of qubit states (pj, k with Pj > 0. 2==110 Pj = 1, and (1bz) E C for E [m)) its density matrix p Σラ= PjPj with Pj (wg) (4by) and Tr(p) 1.
quantum gate is unitary operator that can evolve a quantum state p to another quantum state p' Namely, an n--ubi gate U E EM(2) obeys UU = U = 12n, where (2") refers to the unitary group in dimension 2n. Typical single-qubit quantum gates include the Pauli gates, which can be written as Pauli matrices:
0 1 0
1
0
1
0
x
Y
(8)
0
0
-1
The more general quantum gates are their corresponding rotation gates Rx
(0) - ( Ry
e and Rz (f) = c with tunable parameter 0, which can be written in the matrix form as
Rx = cos e
2
-i sin 8 2 cos 2
(r) = cos
sin
R2(() = E
0
- sin
sin
cos
(9) They are equivalent to rotating tunable angle 0 around x, y. and 2 axes of the Bloch sphere, and recovering the Pauli gates X, Y, and Z when 0 = æ. Moreover, a multi-qubit gate can be either an individual gate (e.g., CNOT gate) tensor product of multiple single-qubit gates.
The quantum measurement refers to the procedure of extracting classical information from the quantum state. It is mathematically specified by a Hermitian matrix H called the observable. Applying the observable H to the quantum state (b)) yields a random variable whose expectation value is (16l H (x)).
Hamiltonian and ground state. In quantum computation, a Hamiltonian a Hermitian matrix that is used to characterize the evolution of quantum system or as an observable to extract the classical information from the quantum system. Specifically, under the Schrödinger equation, quantum gate S has the mathematical form of U = e-itH where H is Hermitian matrix, called the Hamiltonian of the quantum system, and t refers to the evolution time of the Hamiltonian. Typical single-qubit Hamiltonians include the Pauli matrices defined in Eqn. (8. As result, the evolution time refers to the tunable parameter 0 in Eqn. D. Any single-qubit Hamiltonian can be decomposed as the linear combination of Pauli matrices, i.e., H = a + a2 agY + Z with aj E C. In the same way, multi-qubit Hamiltonian is denoted by /l = Σ j=1 a, where P, E X1, ZJ is the tensor product of Pauli matrices. In quantum chemistry and quantum many-body physies, the Hermitian matrix that describes the quantum system to be solved is denoted the problem Hamiltonian Hc- Within the context of QAOA, the information of the graph is encoded in the problem Hamiltonian, which is also called cost Hamiltonian. Another essential Hamiltonian in QAOA refers to the mixer
14

---

Hamiltonian Ниs which is designed to facilitate transitions between different states (solutions), allowing the algorithm to explore the solution space.
When taking the problem Hamiltonian as the observable, the quantum state (1/)) ) is said to be the ground state of problem Hamiltonian H if the expectation value (v/ H (al)) takes the minimum eigenvalue of H, which is called the ground energy. The solution of the optimization problem is encoded in the ground state of the problem Hamiltonian.
Optimization of QAOA. The loss function for QAOA with problem Hamiltonian He generally defined as
L( = (o, 3)) = (O) HcU())
(10)
where (0) refers to the parameterized unitary implemented on a quantum computer and (tb)) is an easily prepared state, which generally set the computational basis state (00"). The optimization of the loss function L(0) can be completed by gradient- methods. A plethora of optimizers have been designed estimate the optimal parameters 0" ming C(0). Here we introduce the implementation of the first-order gradient-based optimizer for self-consistency. Refer to 225 for comprehensive review.
Based on Eqn. (1. the trainable parameters of QAOA are denoted by 0 (ØT .... 0 with 0, = [fg..... fexx )T, where the subscript 'ék' refers to the k-th parameter the f-th layer Ue for vk E [K] and vy E []]. The corresponding update rule at the t-th iteration Vt E [T] is
(
(() OC(((()
00
( n ((vo) ((00)) (oU() (b) - Eo) 0 ((vol (OU())) (W0) Eo)
00
where y refers to the learning rate. The derivative in the last equality can be calculated via the parameter shift rule [36]- Mathematically, the derivative with respect to the parameter Oek for VE E [4] and vk E [K] is
a (woll U(O) HCU(O) (wb) FFo)
00ck
2sin ((vol
(Wo) Eo)
(bb) Eo) )
where 0+ 0 + aeek, 0- = 0 - aeek, ezk is the unit vector along the On axis and can be any
real number but the multiple of x because the diverging denominator.
B Proof
The theoretical analysis of the convergence for symmetric QAOA based on representation the- ory. In this regard, we first introduce the foundation of representation theory related to QAOA in Appendix B.1 The proof of Theorem elaborated in Appendix B.2
B.1 Representation theory in QAOA
In general, an instance of QAOA is specified by triplet (Ioo) (O). H), where (vbo and H refer to the initial state and problem Hamlitonian, and U(O) refers to the parameterized quantum circuit (ansatz) with the form of
P II
U = 1=1 ==k
H
(11)
where 0 = (011.... 00 0p.. Ppk) O PK is trainable parameters, j is the index of layer, and {H& is set of Hermitian traceless operators called an ansatz design. The difference of ansatz originates from the varied @ and A. Given O and A. set of ansatz forms subgroup of SU()") with 4AA = (U()) (O):
)). which can be characterized by dynamical
Lie group with dynamical Lie algebra 29
15

---

Definition B.1 (Dynamical Lie algebra and dynamical Lie group, 22)). Given an ansatz design A = (H,,.... H the dynamical Lie algebra (DLA) g generated by the repeated nested commutators of elements in A, i.e.
= span (iHI, iHk) Lie
(12)
where (S) Lie denotes the Lie closure, i.e., the set obtained by repeatedly taking the nested commuta- tors of the elements in S. The set of unitaries MA that can be generated by the ansatz design A is determined by its DLA through
= H E
(13)
Furthermore, the algebra structures of the ansatz design A can be characterized through the represen- tation and the subrepresentation of Lie algebra specific vector space.
Definition B.2 (Representation of Lie algebra). Let g be a Lie algebra on a finit-dimenniionll vector space V. A representation r' of acting on V is a Lie algebra bomomorphism r i + g((V), i.e., linear map satisfying
((X, = [-()), for all X, E g.
(14)
The dimension of the representation r is defined by dim(r) - (V). If there exists a direct sum decomposition of V into subspaces V = V11 + 1/2 ... @ V2 such that rg))u, V, for any 1 E Vj and any g E g. then ry = rlv, is called the subrepresentation of r on the vector space Vy. Moreover, ry is irreducible if there is non-trivial invariant subspace of Vj. Then the representation of g on the vector space V = V1 @ V/2 @ ... @ Va can be written as
(())()) = (r1 @ ... (g) vx) (ri(g)v1,"- (x(g) for all g E g. e V. (15)
The dimension of the representation with irreducible representation in Equ. 15 is dim(r) =
Σ dim
The representation of DLA refers to the natural representation r - g. In this regard, the dimension of DLA refers to dim(g) dim(r). While the dimension of DLA is employed to characterize the threshold of over-parameterization [30] and the barren plateau [29]. it does not
take into account the symmetry structure of the ansatz and the initial state concerning the problem Hamiltonian. In particular, the symmetry operators of the DLA g refer to unitary operators S satisfying SgSt g for any g. which is a subset of the commutant of g.
Definition B.3 (Commutant). Let g be a matrix algebra. Its commutant is defined as C(g) = {A: [A,g] = 0, Vg g).
We recall that the ansatz being symmetric with respect to the problem Hamiltonian means that there exists symmetry group of the problem Hamiltonian S- (S St H = Hc} such that S is also the symmetry group of the related DLA i.e., S C C(a). This indicates that the problem Hamiltonian and the ansatz design have the same block diagonalization structure [37], namely the acting vector space V Φ Vg. Moreover, when there exists a subspace V* E {ViJ such that the initial state lives in this space, then the optimization the variational quantum state could be constrained into this subspace V whose dimension refers to the effective dimension defined in Definition 2.1 In this regard, the trainability of QAOA could be instead characterized by the effective dimension deff= dlim(V (28 27). The relation between the effective dimension and the dimension of DLA is encapsulated in the following lemma.
Lemma B.4 (The relation between effective dimension and the dimension of DLA). Consider
QAOA instance (190). (0), Hr) with DLA g. If there exists an invariant subspace Vg covering the initial state (bb) and the solution state (ab²) U((")) (1))). then the effective dimension des of this ansatz design A and the dimension of the corresponding DLA g yields dest S dim(g).
Proof of Lemma B.4 The derivation of detf Σ dim (g) could be directly obtained from the observa- tion of deet maxjej dim(V) (V,) Σ V, dim(g).
16

---

B.2 Proof of Theorem 3.1
The proof of Theorem 3.1 employs the following lemmas, whose proofs are deferred Appendix B..3
Lemma B.5 (Convergence, adapted from Corollary 5.4 in (7)). Consider QAOA instance denoted as (1/0)) U(), He) with the effective dimension dett- The unitary operator U follows the Haar distribution over special unitary matrices. Let (ab)) denote the solution state for problem Hamiltonin He and l1)(t) be the state at the 1-th iteration. There exists an deft deeendenndnnt over- parameter threshold Cddet) and PK dependent learning rate (PP)) so that if the number of the ansatz parameters PK 2 C, then with high probability, under gradient flow with learning rate J, the output state (1) converges to the solution state with error e 11 (16 (6")) after T. = O(lo Aul)) iterations.
Lemma B.6. Let AFG, ApG, ANG be the ansatz designs of the circuits with parameters fully grouping, partially grouping, no- oo-grouping. then the effective dimension related to AFG, ANG yields
(An() = denl (ArG) S dent (ANG), where the equality in the inequality holds if there is permutation symmetry in the problem Hamiltonian.
(16)
Proof of Theorem 3.1 To obtain the ordering relation of the convergence rate of various ansatz designs, we first clucidate the relation between the convergence rate of the approximation ratio and the effective dimension. Consider the problem Hamiltonian Hc [(1)) Z;Z, Cdxd with
= 2 and eigenvalues X S >..... < Xa and its corresponding eigenvector {1x:) ) 1-=1- Preparing a quantum state w) with overlap with the target ground state }=>"): (w>lv>*) of the expectation value of (xb) Hl))) is
e, the lower bound
(HHc))) = (vb) Σ
A (1x) (1:l
(17)
= =A1 - -)² + Σ A1 (111)))
(18)
< A1 +)2 +fal (1-
(19)
where the first inequality works by scaling each eigenvalue A to da and following the fact ( (1 c)? Then approximation ratio is
r (wbHHWl (V)
Ad
Aa A (1 - ) 2 (1-8)²
A1
A1
A1
651 VT
(20)
where the first inequality the first equation holds because A 0. Employing Lemma B.5 we have that the output state (z)()) converges to the solution state with approximation ratio ( ())
(
dett )) iteration steps. These achieved results indicate that a small effective after T, Olog( 1- dimension leads to a faster convergence rate. In this regard, combining with Lemma B.6 the convergence rate T related to various ansatz ANG, Ara, ArG for achieving the same approximation ratio yields TFG = TPG < TNG.
B.3 Proof of Lemma B.6
The proof of Lemma B.6 employs the following lemmas, where the proofs of Lemma Lemma B.9 are deferred to Appendix B.44and and Appendix [B.]
B.7 and
Lemma B.7. Let g be dynamical Lie algebra and be the natural representation the vector space V satisfying r(g) = g for any g E g. If there exists irreducible subrepresentations of r on V such that r(g) [g( @ ... @ @x(g) acting on the space V = V1 @ ... Vor any g E g. then the dimension of Lie algebra yields
k
dim(g) dim(r)
dim(r;)
dim(V,)
(21)
17

---

where the dimension of subrepresentation r, refers to dim(ry) = (Vm
Lemma B.8 (Commutant structure [8)). Let r be representation of a Lie algebra g on the Hilbert space H and its decomposition into irreducible representation be
r(g) = rr(g):
(22)
where mj is known as the multiplicity of the irreducible representation rj. Then the elements of its commutant are of the following form
C(g) - dimm(m,))>
(23)
where Cj(g) denotes bounded operators in a my-diimensional Hilbert space. Then the dimension of representation and subrepresentattinn T3 yields
dim(r) dim(C(g)), and dim(r;) dim((C(a))
(24)
Lemma B.9. Let GFG, 8PG, BNG be the Lie algebra related to the ansatz designs of the circuits with parameters fully grouping AFG. partially grouping ApG, no- po-grouping ANG. Then the related commutants of the three Lie algebras yield
C(DNc) C C(DrG) C(ppc):
(25)
where the equality in the subset holds if there is no spatial symmetry in the problem Hamiltonian.
We now begin present the proof of Lemma B.6
Proof of Theorem B.6 Following Lemma B.7 with denoting r be the natural representation of vector space V. the dimension of DLA is equal the sum of dimensions of irreducible subrepresentations, i.c.,
di) dim (r)
dim(ry)
dim(V)),
(26)
where Vj is the irreducible invariant subspace related to the subrepresentation ry. For the symmetric ansatz design A, there exsits an invariant space V. E (V,), such that the effective dimension
(A4) = dV.).
To obtain Eqn. (6). we first show that the effective dimension of DLA g is inversely proportional to the size of commutant of the DIAA g. and then show that the commutant sizes related to ansatz design AFG.APG. ANG are monotonically non-increasing. In particular, the commutant of Lie algebra g. denoted as C(g) = (V E (U [V.g] = 0}, includes all the symmetry operator of the corresponding ansatz design. For any two Lie algebras g B2 with C(gi) C C(g2), then any block diagonalization of the elements in C(gi) is also the block diagonalization of the elements C(g)). This indicates that any invariant subspace of C(ga is also the invariant subspace of C(gz), leading to dim(C, (g2)) I dim(C, (g1)) Following Lemma B.8. we have
dest (g2) = dim(r, (r. (gz)) = dim(C. (g2)) I dim(C, = dim(r, (g1)) = dea (g1),
(27)
where E [k] refers to the index of invariant space the optimization performs on and dim (g:)) with j 1. refers to the effective dimension related to the DLA gj. In conjunction with Lemma B.9 and Eqn. (27). we have C(gNG) C C(gra) = C(gra) and hence dear (grG) = (ef(gr)) S des (gvG).
This completes the proof.
B.4 Proof of Lemma B.7
Proof of Lemma B.7 The first equality in Eqn. (2T) follows the fact that natural representation is bijective and does not change the dimension of pre-image space. the second equality follows the definition of the dimension representation in Definition B.2 such that
(r) = (V) (Vi .... Vi.)= = Σ dim = Σ dim(r,),
(28)
where the last equality follows that ry is representation of g on the space V,. This completes the proof.
D
18

---

B.5 Proof of Lemmal B.9
Proof of Lemma B.9 We begin this proof by showing that the commutant A = (H1 @ I H2)
is a subset of B 1 @ I++I @ H2), where H1, H2 are arbitrary Hermitian operators and B refers the set with imposing parameter grouping on A. In particular, for any matrix which commutes with the elements in A, we have
S &I H2) = S(H, + = (H
(H1 @I+I@ H2)S. (29)
This indicates that C(A) C C(B). With this fact, we now derive the Eqn. (5 We first recall that the generators of the Lie algebras BNG, BPG, BFG yield non-discreasingly restrictive parameters grouping strategy, and are identity when there is no spatial symmetry in the problem Hamiltonian, ic.. 9FG gPG BNG- Moreover, the definition of BFG- 9PG indicates that the related ansatzes follow the same symmetry, namely, any unitary U commutes with the elements in gFG and only if U commutes with the elements in 9PC- Hence we have C(gra) C(pra) as the commutant consists of the symmetry operator of the ansatz design.
On the other hand, the relation C(grc) S C(gNc) in Eqn. (25) directly following the analog between the set A and B and the generators related to the Lie algebra gPG and gNg, where the generators related to 9PG refers to the set with imposing parameters grouping on gvg- This completes the proof.
C Related work
In this section, embark concise literature review, focusing conventional algorithms for the Max-Cut problem, some variants of QAOA, and quantum circuit architecture search algorithms. This examination sets the stage for comparative analysis between these established methods and our proposed model. In summary, our discussion underscores the distinctive strength of our model: its exceptional ability to generalize.
C.1 Conventional algorithms
Greedy algorithm for Max-Cut problem. The greedy algorithm for solving the Max-Cut problem operates simple principle: iteratively makes local, myopic decisions to construct a solution that attempts to maximize the sum of weights of edges between two disjoint subsets of vertices. This algorithm does not assure optimal solution due its greedy nature nature-making making decisions based only on immediate benefits without considering future consequences. The detailed procedure is introduced in Alg. 1
Goemans-Wiill Williamson (GW) algorithm for Max-Cut problem. The GW algorithm utilizes semidef- inite programming to relax the original combinatorial problem into a continuous one that can be solved efficiently. After solving the semidefinite program, the algorithm uses a random hyperplane to split the vertices into two subsets, which form the cut. The GW algorithm achieves approximation ratio of at least 0.878 for the Max-Cut problem. The simplified pseudocode of GW algorithm is described in Alg. 2
C.2 Variants of QAOA
The studies variants of QAOA aim to improve the convergence rate or reduce the computational time by changing the PQCs or the problem Hamiltonian. Current progress has revealed that the per- formance of QAOA could be improved by employing multi-angle QAOA [17] where the parameters no-grouped or partially grouped according to the permutation symmetry of problem Hamiltonian
39 40 23], utilizing different mixer Hamiltonian obtained by searching from a given Hamiltonian 4 43 and other quantum algorithms [33 44 45
pool 34 inspired by specific problem 41
22
Another type of the variant of QAOA focuses on modifying the problem Hamiltonian, either through eliminating redundant qubits [66 to obtain reduced problem Hamiltonian, imposing conditional rotations [47] to the Hamiltonian. In the following, we delve into the most relevant variants of QAOA
our study and compare them with our model.
Multi-Angle QAOA (ma-QAOA) [77. The ma-QAOA innovates on the traditional QAOA frame- work by incorporating larger set of parameters. It allows each operator within both the cost and
19

---

Algorithm Greedy Algorithm for weighted Max-Cut
Input: A graph G EV) with weights wij on edges (i,j) E
2: Output: A partition of V into subsets S and S maximizing the cut weight
3: Initialize S = 0, =
4: Initialize BudWeight.
5: for each vertex v E V do
6: deltaWeisg eight- =
7: for each edge (u, u) E E connected to e do
8: if u E S and & S $ S and S then deltaWeight
9:
deltaWeight w(r,u)
else
11:
deltaW eight deltaWeight w(v,u) u) end if end for
13:
if delta Wegght > then
15:
if v E S then
Move S and update cutWeight- deltaWeight eight else
17:
18:
Move u to and update cut wighh++ = deltaWes eight
19: end if
20: end if
21:
end for
22: return S, S, SutWeight
Algorithm 2 GGemans-Williamsee Algorithm for Max-Cut
1: Input: A graph G = EV) with weights Wiy edges (i.j) E E
2: Output: A partition of V into subsets S and 5
3: Formulate the Max-Cut problem as semidefinite programming (SDP) problem.
4: Solve the SDP problem to find a vector representation ē; for each vertex
5: Choose a random hyperplane by selecting random unit vector f.
6: for each vertex i E do
7: if ū; F> 100 then
8: Assign vertex to subset S
9: else
10: Assign vertex to subset S
end if
12:
end for
return S, S
mixer Hamiltonians be governed by its own unique parameter, diverging from the conventional approach where a single parameter is shared among all operators. In our experiment, attention is focused exclusively on the modifications within the mixer Hamiltonian for fair comparison. The new mixer Hamiltonian is expressed as
N HM = Σ 3xX,
(30)
where X; denotes the Pauli-X operation applied the i-th qubit and 3; represents the corresponding individual parameter. This adjustment significantly expands the parameter space in ma-QAOA, scaling the total count from 2p in the standard QAOA to (N 1)p. Despite empirical evidence suggesting that ma- ma-QAOA surpasses the original QAOA in achieving higher approximation ratios for configurations with fewer layers, the complexity introduced by the augmented parameter space could potentially impede its effectiveness in scenarios involving deeper circuits.
ADAPT-QAOA [34]. In ADAPT-QAOA, the mixer Hamiltonian is selected from pre-defined operator pool {A,} step by step. For the k-step, the operators A, is guided by maximizing the following gradient:
-i (vi--iia,)))) B))e He Ao.e Ne lo 1(xx
(31)
20

---

where [ 8)) (TT k== e e - (im)te)) (6)). Following the selection of A,, all parameters undergo subsequent optimization phase. This procedure iterated until the gradient's norm falls below set threshold, or the circuit reaches its predefined maximum depth. ADAPT-QAOA's dynamic mixer Hamiltonian selection aims to potentially discover more direct path to adiabaticity, thereby enabling accelerated convergence. However, its practicality for large-scale problems is hampered by the increased measurement costs required for gradient evaluation, a factor contingent on the size of the operator pool.
Contrasting with these QAOA variants, MG-Net uniquely offers dynamic offline adaptation of the mixer Hamiltonian, tailoring it to the specific problem and circuit depth without incurring extra computational costs. Additionally. MG-Net demonstrates remarkable generalization capabilities, effectively learning from a limited dataset to address a broad spectrum of problems. This facilitates the rapid development of mixer Hamiltonians for new problems.
C.3
Quantum circuit architecture search
In the design of quantum circuits, quantum circuit architecture search methodologies have been developed to autonomously identify optimal quantum circuit architectures [48, 49 50 51 52 53 54]
55
58 [5]. In the following, we delve into several notable approaches and contrast them with our MG-Net model.
56
57
Quantum architecture search (QAS) [53]. The QAS approach automatically seeks an optimal quantum circuit architecture to balance the benefits and side effects of adding more quantum gates, considering the noise in quantum systems. This method involves several steps: initializing super- structure (supernet) that defines the pool of potential architectures, optimizing parameters across these architectures, ranking them based on performance, and finally refining the chosen architecture.
Differentiable Quantum Architecture Search (DQAS) (56). DQAS introduces a novel approach by employing differentiable programming techniques. This method enables the concurrent optimization of both the structure and parameters of quantum circuits through gradient descent, streamlining the search process.
QuantunDARTS [57). The QuantumDARTS algorithm, which leverages the Gumbel-Softmait technique for differential optimization of quantum circuit structure and parameters, aims to reduce the search cost by following search strategies: macro search for entire cireuit optimization and micro search for sub-circuit structures, improving its adaptability to large-scale problems.
Despite their advancements, these QAS methodologies share fundamental limitation: they inherently designed to address singular, specific problems. Consequently, adapting these methods to new problems necessitates repeating the resource-intensive architecture search process from scratch. In contrast, MG-Net exhibits an unparalleled ability to generalize across a spectrum of problems based minimal set of training examples. This capability enables MG-Net to rapidly design optimal circuits for novel problems through a single feedforward computation, bypassing the need for repeated, exhaustive searches. This unique advantage positions MG-Net highly efficient and versatile tool in the quantum computing landscape, offering significant savings in computational resources and time.
D Implementation details of MG-Net
In this section, we initially outline the methodology for constructing datasets used train MG-Net across various problem scales. Subsequently, we detail the implementation of the data encoder, illustrated with specific example.
D.1 Dataset construction
Operator types. The set of operator types for the mixer Hamiltonian is defined as {X, o in our experiments. Note that the operator type pool can flexibly adjusted according to specific problems and hardware. For example, we can introduce two-qubit operators into the operator type pool to further enhance the performance of QAOA, as done [60] Considering the exponential growth of the search space in relation to the system size N, we have sampled only a subset from this pool in all
21

---

our experiments. This approach is adopted to construct the training dataset while minimizing data collection costs.
Construction of parameter group pool. A straightforward idea to construct the pool of parameter group is to assume each X; can be assigned index j ranging from 1 N, leading to pool P P= (ūi E jN E [ with size N* However, there exist multiple duplicate candidates in the pool due the disorder of the initial parameter pool. For example, for two-qubit QAOA ansatz, parameter index vectors (1, 2) and (2, 1) make no difference in the optimization of QAOA. Based on these observations, we propose a recursive algorithm Alg. to build compact pool of parameter groups.
Algorithm 3 Construction of parameter group pool
1: Input: The qubit number N, pool P = -
2: Oufput: Pool P
3: Function crouping_pool((mng _indeer,,drr,, inder_list, N)
4: if length(inder. list) == N
5: Add inder _ist to P
6: return
7: end if
8: for i = 1, maa__ndde
9:
Append i to index_list
10:
grouping pool(max((mar index, index index_list[1]] + 2), index _ist, 11: Delete the last element of index list
12: end for
13: End Function
14:
pooplnng_poo((,eoom empty_lisst N)
In practice, we randomly selected candidates from the parameter grouping pool for each operator type. Although the training dataset only partially covers the entire space of operator types and parameter groupings, our model is still capable of learning the intrinsic relationship between the mixer Hamiltonian and its corresponding achievable cost.
To find the minimal cost that can be achieved by QAOA circuit during the construction of the training dataset in stage I, we run the same QAOA circuit 10 times and record their cost values. For each run, the QAOA circuit is initialized with different random parameters and optimized for 40 epochs. Finally, the minimum of these cost values is selected as the label that represents the minimal achievable cost.
Large-scale dataset. To assess our method's efficacy on large-scale problems, we concentrated on the Max-Cut problem using weighted graphs with 64 nodes. Simulating larger-scale quantum circuits on classical devices poses significant challenges. To overcome this, our approach employs a wwvide-and-conquer strategy, simulating large-scale circuit through multiple smaller-scale circuits. We then integrate the results of these smaller circuits to estimate the performance of the original large-scale circuit. For a detailed explanation of this methodology, refer to QAOA-in-QAOA [6]]
In constructing the training dataset Tr for 64-node graphs, we divide each 64-node graph into co
sub-graphs, each containing nodes. The max-cut of each sub-graph is computed using 8-qubit QAOA. To gather a comprehensive range of samples, we vary the operator types and parameter groupings in the 8-qubit circuits, which in simulates the variation in mixer Hamiltonians for 64-qubit circuits. It is important to note that these 8-qubit circuits operate independently, with no shared parameters, resulting in at least 8 independent parameters for each 64-qubit circuit in training dataset. For testing on the unknown graphs, we employ tensor network simulations to accurately estimate the performance of the original 64-qubit QAOA.
D.2 Data encoder
Problem encoder. Our problem encoder rooted on the problem Hamiltonian He Eqn. T More precisely, to facilitate a consistent and unified representation for diverse combinatorial problems (G). we initiate by converting the original problem into the corresponding unitary Uc = exp(-ias ion Hc). which is subsequently transformed into directed acyclic graph (DAG) Gc.
22

---

ZA
93
Problem graph
Figure 6: Encoding of problem. The problem graph is first transformed into quantum circuit, which subsequently encoded by a DAG.
Fig. illustrates the problem encoding process a regular graph with 6 nodes. Each node of the problem graph corresponds to qubit in the quantum system and each edge (i,j) is represented as two-qubit gate Z.Zj, which is exactly the problem Hamiltonian of QAOA for the Max-Cut problem. Based on this problem unitary, we construct the final graph representation Gc. with each two-qubit gate depicted as node in the graph. In addition to these gate-induced nodes, two unique node types, the input and output nodes which correspond to qubits, are introduced to denote the start and end of Gc, respectively. The edges of Ge signify the temporal order of quantum gate execution, linking consecutive gates and thereby dictating the flow of the quantum computation. The weights of edges are encoded into the node feature.
Paraniter sharing
Use
Car
Figure 7: Encoding of mixer Hamiltonian. Each qubit in the mixer Hamiltonian is represented node in encoded graph. The type of operator associated with each qubit encoded in the node feature, while parameter grouping strategy is encapsulated in the edge features.
Mixer encoder. We define a one-to-one mapping to encode the candidate mixer Hamiltonian Har as graph GM. Recall Eqn. ( two types of information about HM should be encoded in GM are operators }Pt} and the parameter grouping strategy G. MG-Net, each operator is modeled as node of Gas, and the operator type is encoded as part of the node feature vector. Concretely, MG-Net initially constructs Ga as a fully connected graph, where the edge weight is a binary variable, representing whether the two operators connected by the edge share the same control parameter.
The process of encoding a mixer Hamiltonian into graph representation illustrated in Fig. 7 Here, we take the example of 6-qubit mixer Hamiltonian encoded as graph GM. In this graph, each qubit's corresponding operator depicted
node, with the operator acting on the i-th qubit represented by the i-th node in GM. The graph's 's edges signify the parameter correlations among these operators. Specifically, let Wij E (0, 1} be the weight of edge connecting node and j. the operator and j share the same parameter, then Wij = O; otherwise, Wij = 1.
Depth embedding. The eircuit depth p is encoded as vector w, through position embedding 662 Mathematically, Ep is constructed as
[2k] sin
100002k/d, Tp 2k: 1]
cos
20000
P
where d, is dimension of x, and k 0,... [d,/2jj.
D.3
Network structure
D.3.1
Cost estimator
In our experimental setup, the intricate architecture of cost estimator detailed Fig. Both the problem and mixer Hamiltonian branches incorporate two layers of graph convolutions, utilizing
23

---

ReLU activation functions to transform the initial node features from dimensions de and d to unified 228-dimensional space. Subsequently, the three extracted features =c, M. and Fp z are concatenated to facilitate the prediction of the attainable minimum cost for a given QAOA instance through an MI.P layer.
Gc
GraphConv
ReLU
GraphConv
GAP
XC
4g x 64
64 128
G
GraphConv
ReLU
GraphConv
GAP
XM
MLP
du 64
64 128
Xy
Figure 8: Implementation of cost estimator. The term 'GraphConv' represents the graph convolution module. 'ReLU' a commonly used activation function in neural networks. de and dy represent the dimension of node feature in graph Ge and Car respectively. P. represents the operator type for the i-qubit and eiy represents the weight for edge (i,
D.3.2 Mixer generator
which encodes a quantum circuit as a graph, the mixer generation is composed of two separate sub-generators: the operator type generator and the parameter grouping generator, which are respectively responsible for graph node and link prediction.
Inspired by 3
Operator type generator. The task of generating operator types P is conceptualized as graph node classification task. Specifically, we employ a GNN to process Gc, identifying output nodes to represent the operators corresponding to each qubit, while disregarding irrelevant nodes. To incorporate the circuit depth p into the prediction, we enhance the feature set of each output node by appending feature vector Fp. This enriched node feature set is then fed into MLP to predict the specific category of each operator.
Parameter grouping generator. Recall that the grouping strategy is traditionally represented by sets 1K of index groups { with an unspecified K, posing challenge for neural network processing. To address this, we extend the parameter grouping problem as follows: if edge indicator eij 1, then the mixer operators P; and Pj are correlated and share the same parameter, otherwise, they controlled by independent parameters. Furthermore, if eij = 1 and eik, 1, then P.. Py and Pş are correlated regardless of the value of Ejk- In this way, the parameter grouping task is translated into the prediction of the binary variable eij E {0, 1). link prediction task. This modeling bypasses the need to predetermine the number of parameter groups and offers flexibility in incorporating constraints related to qubit connections.
Analogous to the operator type generator, the parameter grouping generator employs another GNN to process Go to extract features of output nodes, which are then extended with circuit depth feature Tp. For node and j. their extended features æ; and æj are used to determine the existence of an edge (i,j) by evaluating eij- (MLP((x; æ,)), where B(-) signifies binarization function. In trick, ensuring the differentiability.
MG-Net, this function is realized using the
In our experiment, the detailed structure of the mixer generator is depicted in Fig. 19) The mixer generator integrates two specialized branches to analyze the input problem graph Gc. with each branch deploying two graph convolution layers to distill the feature vector ze with a dimensionality of 128.. This feature vector is then augmented with the circuit depth feature T.p to enrich the predictive capability of the model. For the precise prediction of operator types {P.) applicable to each qubit, the terminal nodes of Gc are chosen for input into a Multi-Layer Perceptron (MLP) layer. This step calculates the likelihood of each potential operator type. Concurrently, separate MLP layer is employed to ascertain the parameter sharing between operators P; and P,. This is achieved through the equation eij = M2;,(a;; o my)), where denotes the element- wise multiplication, and æ; symbolizes the enriched feature of the i-th node.
24

---

GraphConv
GraphConv
MLP
P
Ge
64
GraphConv
ReLU
GraphConv
MLP
eij
dy 64
64
Xp
Figure Implementation mixer generator. The term 'GraphConv' represents the graph convolution module. 'ReLU' is a commonly used activation function in neural networks. de and dar represent the dimension of node feature in graph Ge and GM respectively.
D.4 Experiment settings
Hardware platform. All QAOA circuits are implemented by PennyLane (64 and run on classical device with Intel(R) Xeon(R) Gold 6267C CPU @ 2.60GHz and 128 GB memory. MG-Net is implemented by Pytorch [65] and trained on a single NVIDIA GeForce RT 2080Ti with 12G graphics memory.
Hypper-arrmeeers. The hyper-parametees of optimizing MG-Net and QAOA circuit are listed in Tab. 3
Initial state. The initial quantum state of the QAOA circuit is consistently set to [+) 8N irrespective of the mixer Hamiltonian chosen. Although this approach does not ensure that the initial state is always the ground state of the predicted mixer Hamiltonian, it does compromise the QAOA's performance and has the potential to outperform the traditional state initialization technique, which can be partially explained by the physical intuition of counterdiabatic (CD) driving 33 34).
Table 3: The hyper-paramette of optimizing MG-Net and QAOA circuit.
QAOA
MG-Net
optimizer
Adam
Adam
learning rate
0.15
* 10-4
epoch
40
250
1.0
d
1.0
E More numerical results
In this section, initially show the results of comparing the approximation ratio achieved by different methods for TFIM. Then we examine how the approximation ratio achieved by various methods varies with different circuit depths p. Subsequently, explore the convergence behavior of the QAOA when enhanced by our approach.
E.1 Performance comparison among different methods for TFIM
In evaluating the effectivenesss of our proposed method for solving TFIM, conducted comparative analysis against QAOA, ADAAT-QAAA, and multi multi-angle QAOA (ma-QAOA). Our analysis, based on the average results from 100 graphs in test dataset, is summarized in Tab, 4 The findings reveal that our method consistently outperforms other techniques in achieving a higher approximation ratio for TFIM, particularly in larger-scale problems.
E.2 Experiments asymmetric graphs and 2D-TFIM
We conducted additional experiments on the asymmetric graphs of 6 nodes and 2D lattice models of 6 spins. Their topological structure is shown in Fig. 10
25

---

Table 4: Comparison of approximation ratio r among different methods for TFIM.
Method
6 qubits
16 qubits
QAOA
0.990 + 0.005
0.523 + 0.083
ADAPT-QAOA
0.857 = 0.245
0.742 + 0.356
ma-QAOA
0.994 + 0.001
0.921 + 0.040
Ours
0.996 + 0.001
0.963 + 0.031
Asymmetric graph
TFIM
Figure 10: Topological structure of asymmetric graphs and 2D TFIM.
The comparison of the achieved approximation ratio at = 42 over 100 random test samples is summarized in the Tab. E2
The result affirms that model consistently outperforms both standard QAOA and ma- QAOA in terms of approximation ratio on more general cases.
Tasks
Max-Cut for asymmetric graphs
2D TFIM
QAOA
0.952 0.026 0.987 + 0.008
0.977 0.008
ma- ma-QAOA
0.980 + 0.019
Ours
0.988 + 0.005
0.988 0.006
E.3 Approximation ratio with respect to p
In small-scale quantum systems, achieving the criteria set in Theorem 3.1 is more straightforward by increasing circuit depth p beyond the threshold C. We analyze the approximation ratios achieved by 6-qubit QAOA circuits for Max-Cut and TFIM within the range of 2 to 82. Figure IT illustrates that lower p values, our method consistently records the highest approximation ratio r, clearly outperforming both standard QAOA and ma- na-QQAA. As increases from 2 to 62, standard QAOA and ma- -A-QAA exhibit rise r. eventually matching our method's 's performance. However, further increase in leads to performance decline in ma-QAOA, where the detrimental impact of its numerous trainable parameters on convergence outweighs the benefits of enhanced expressibility. In contrast, our method maintains stable performance, continually achieving the highest r. These findings confirm our method's superiority in optimizing approximation ratios across various circuit depths compared to other approaches.
We further explore the specific configurations of mixer Hamiltonians generated by MG-Net. Table presents examples of predicted mixer Hamiltonians for values of 12, 52, 82. At smaller circuit depth of p 12, the optimal parameter grouping strategy maximizes the number of parameters, assigning each operator its independent parameter. This approach enhances the expressivity of QAOA circuit and, alongside the introduction of novel mixer operators, contributes to superior approximation performance. For p 52, which verges on the threshold of over-parameetriizatoo. a trend towards grouping some operators is observed. a higher circuit depth, such as p = 82, the majority of operators are assigned the parameter, aligning closer to the configuration of
26

---

Max-Cut
TFIM
1.0
1.00
0.95
0.8
0.90
0.6
0.85
QAOA
QAOA
ma-QAOA
0.80
ma-QAOA
0.4
Ours
Ours
20
40
80
20
60
Figure 11: Comparison the approximation ratio achieved by 6-qubit QAOA, ma ma-QAOA and our model for Max-Cut and TFIM with varying p-
a standard QAOA circuit. The evolution of the mixer Hamiltonian configuration with varying partially reveals the underlying design principle of mixer Hamiltonian across different problems and circuit depths.
Table 5: Operator type and parameter group generated by MG-Net. 'X' and 'Y' represent Pauli-X and Pauli- Y, respectively. Parameter groups are formatted d1 02 ax. with a, E {0, I,,., 1} indicating the parameter index for the i-th operator. Identical indices (a, = a,) imply shared parameters between operators.
Task
Max-Cut
TFIM
Operator type Parameter Group
YYYYXX
XXXXXX
p 12
0-1-2-3-4-5
0-1-2-3-4-5
Operator type
XXXXXX
XXXXXX
52
Parameter Group
0-1-2-0-4-4
0-1-1-3-4-5
Operator type
XXXXXX
XXXXXX
82
Parameter Group
0-1-0-0-0-1
0-0-0-0-0-0
E,4 Convergence of QAOA with various mixer Hamiltonian
In our investigation, we conducted an analysis on randomly selected 16 16-qubit Max-Cut and TFIM problem from our test dataset, scrutinizing the convergence patterns of QAOA, ma- na-QAAA, and our method across various configurations (p 4, 6, 8, 10). Illustrated in Fig. [2] our methodology not only achieves a notably lower loss value within reduced number of iterations in comparison both QAOA and ma-QAOA but also consistently outperforms in terms of the final loss value attained by end of the optimization. Specifically, at p = 10, our approach necessitates merely 28 iterations for Max-Cui and 22 iterations for TFIM to diminish the loss value to -8 and 15, respectively. In contrast, ma-QAOA demands 40 iterations for both challenges, whereas QAOA fails to achieve this loss value. This evidence underscores the superior efficiency and effectiveness of our method in navigating the solution landscape for these quantum optimization tasks.
E.5 Experiments extended candidate operator type set
In this section, we investigate the performance of our model when applied to more complex set of candidate operator types. Specifically, we expand the pool of mixer operator types from X, Y to X, X,X, YY by incorporating additional two-qubit operators, thereby increasing the search space operator types to 0(4 All other experimental conditions remain consistent with those described in the main text. The behavior of the cost estimator under these conditions is illustrated in Fig. [3] Our results indicate that the cost estimator continues serve as reliable performance indicator for QAOA, even with the increased complexity of the mixer Hamiltonian design.
27

---

QAOA
ma-QAOA
Ours
Loss (Max-Cha Chat))
p=1
P-8
p=10
30
10
Loss (TFIM)
-00-
10
Iteration
Iteration
Iteration
Figure 12: Comparison of the convergence of 16-qubit QAOA, ma-QAOA and our model for Max-Cut and TFIM with varying
-2.
2.5
-30
pred
-3.5
-.0
4.5
-5.0
5
4
-3
2
label
Figure 13: Behavior of cost estimator with extended mixer operator pool (X, Y, XX, YY). 'lahel' represents the actual achieved approximation ratio, while 'pred" represents the result predicted by the cost estimator.
28

---

E.6 Ablation study on the circuit depth embedding
MG-Net acts as initial protocol and provides flexible bircuit-generatiin framework where model components can be conveniently replaced by advanced techniques. Besides the position embedding of circuit depth in the main text, have also considered another two embedding strategies: integer embedding and one-hot embedding. There are two key differences between the implementation of position encoding and one-hot integer encoding:
1. Feature vector length. The length of the one-hot-encoded vector X, depends the predefined maximum value p. while the length of the integer-encoded vector Xp is In contrast, adjust the length of position-encoded vector X according to the dimension of X and XM-
2. Feature integration strategy. When using one-hot or integer encoding, we employ con- catenation as the integration strategy for the three features Xc, XM and Xp rather than summation.
The achieved approximation ratios for 6-qubit MaxCut problems using different depth encoding methods are shown below:
Table 6: Comparison of approximation ratio r among different circuit depth embedding strategies.
Depth embedding method
Approximation ratio r
Integer
0.981 + 0.004
One-hot
0.984 + 0.003 0.99 + 0.0004
Position
29

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Sec.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Sec.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

Justification: Sec.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Ys)
Justification: Sec. Dec Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer: [Yes]
Justification: Sec.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipp/.ccppulic/guuii. http:p/bbl...giiiiee/d//deeeaaaa CoodeSubeeiieeeeeeeeee ssi asionnolle onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ye]]
Justification: Sec.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: Sec. 5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
32

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix.
D
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:::///nuriieee httppp//sccppp..t.tttttcicceeeee
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
Sec.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
33

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Appendix. D
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppaipptheeee throdee.wteceee..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
34

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "hpjS711gMo", "reviewer": "Reviewer_aG1x", "summary": "This paper studies the convergence behavior of QAOA, a variational quantum algorithm for combinatorial optimization. The authors prove a convergence result showing how the use of parameter grouping affects the expressibility (i.e. effective dimension) and training time. Furthermore, they design a deep learning model known as MG-Net to generate an appropriate mixer Hamiltonian for a given input problem. Experiments are conducted to evaluate the performance of their model on prototypical problems (Max-Cut and TFIM). The numerical results suggest that their method achieves a higher approximation ratio than all other tested methods, including a simple greedy algorithm, Goemans-Williamson, and standard QAOA.", "questions": "- Throughout this paper, $p$ is referred to as the circuit depth. Shouldn't it be the number of layers, which is not quite the same as the usually defined circuit depth (although they are proportional)?\n- For a given $H_C$, is the ansatz with partial grouping unique? I suppose not since there may be different generators of $\\mathrm{Per}(H_C)$. If this is correct and the ansatz is not unique, then does Theorem 3.1 hold regardless of the choice of generators?\n- It is stated that this approach is designed for early fault-tolerant algorithms, while many existing works on variational quantum algorithms suggest they may be suitable for NISQ devices. Aside from the high monetary cost of training parameterized circuits, are the quantum resources (i.e. circuit depths) required for this approach low enough to be practical without fault-tolerance? If not, what are the main limitations of QAOA that need to be overcome?", "limitations": "There are no major societal impacts of this work. However, as mentioned in the paper, this work is limited to QAOA and it is of interest whether this approach may be applied to more general variational quantum algorithms.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper tries to resolve an important question relevant to the performance of QAOA, which has implications for the practicality of quantum optimization algorithms.\n- The use of parameter grouping, while not a very novel idea, appears to be the \"right\" choice to take advantage of problem symmetries and improve the performance of QAOA.\n- The presentation of this paper is clear and everything is fairly straightforward to understand.\n- The code availability is nice to have.", "weaknesses": "- In Section 3, there are several references mentioned that also study the convergence of VQAs, but the theoretical contributions of this work are somewhat unclear. This paper would benefit from a clear statement of how this work relates to the results of those existing papers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the potential of the proposed method to enhance QAOA with practical utility. Your feedback is invaluable, and we address each of your concerns as follows:\n\n\n**Q1: In Section 3, there are several references mentioned that also study the convergence of VQAs, but the theoretical contributions of this work are somewhat unclear. This paper would benefit from a clear statement of how this work relates to the results of those existing papers.**\n\n**A1:** We have followed the reviewer's suggestions to state the theoretical contributions of our study in the main text and highlight the relation with existing papers in Appendix C. In the following, we will separately address these two concerns raised by the reviewer.\n    \n\n**The relation with existing literature.**\nAs stated in the theoretical contribution of our Global Response, while the convergence of VQAs with symmetric ansatz has been established from various aspects, they did not consider how concrete strategies for ansatz design, specifically the parameter grouping, affect the symmetry degree or equivalently the effective dimension, and hence fail to apply to the problem setting in our manuscript. \n    \n\n**Theoretical contributions.** We **qualitatively analyze the relation between the effective dimension and convergence rate of QNNs equipped with various parameters grouping strategies** in the context of QAOA. The techniques used in our theoretical results are mainly the effective dimension and the tools of representation theory [Ragone et al., 2023], which have been widely used in existing literature to perform theoretical analysis for QNNs with symmetric ansatz. Please refer to the contributions discussed in Global Response for details.\n\n**Q2: Throughout this paper, $p$ is referred to as the circuit depth. Shouldn't it be the number of layers, which is not quite the same as the usually defined circuit depth (although they are proportional)?**\n\n**A2:** We agree that the terms \"circuit depth\" and \"number of layers\" are often used interchangeably but can have distinct meanings in different contexts. Circuit depth typically measures how many \"layers\" of quantum gates are executed in parallel, whereas the number of layers can either share this meaning or refer to the number of blocks with the same structure. In QAOA, $p$ specifically denotes the number of blocks, each consisting of a cost Hamiltonian and a mixer Hamiltonian, as defined in Eqn.~(1) of the manuscript. Following the reviewer's advice, we have revised the manuscript to ensure consistent and precise terminology.\n\n**Q3: For a given $H_C$, is the ansatz with partial grouping unique? I suppose not since there may be different generators of Per${H_C}$. If this is correct and the ansatz is not unique, then does Theorem 3.1 hold regardless of the choice of generators?**\n\n**A3:** For the reviewer's supposition, the answer is right. Namely, the ansatz with partial grouping for given $H_C$ is not unique. For the second concern, Theorem 3.1 indeed holds regardless of the choice of generators. In particular, Theorem 3.1 is established to **perform the qualitative analysis** about the effects of parameter grouping strategies on convergence. **Multiple partial grouping strategies could exist to achieve the same effective dimension, which depends on the specific problem Hamiltonian.** However, it is difficult to **quantitatively determine the effective dimension and explicitly adopt the correct parameter grouping strategy** for better convergence, as achieving this **requires analyzing the complicated graph structure of the problem Hamiltonian case-by-case**. In this regard, we delve into exploiting the power of deep learning and propose the MG-Net for automatically generating the ansatz design with optimal parameter grouping strategy.\n\n**Q4: It is stated that ... If not, what are the main limitations of QAOA that need to be overcome?**\n\n**A4:** As explained in the Section \"Motivation\" of our Global Response, we consider **the allowable circuit depth as the primary hardware constraint, a common issue for both early fault-tolerant and NISQ devices. To further address your concerns, we provide a detailed explanation of the rationale behind researching noiseless cases and discuss the suitability of our approach for noisy devices. Finally, we clarify the resource requirements of our approach.\n\n- **Importance of Fault-Tolerant Quantum Research:** Conducting research within a fault-tolerant framework is crucial for unlocking the full potential of quantum computing and achieving quantum advantages over classical methods, such as works on quantum learning theory and optimization acceleration [Larocca et al., 2023; Liu et al., 2024]. Our theoretical analysis of QAOA is situated in the same fault-tolerant context to provide practical insights for improving QAOA's performance to achieve quantum advantage within limited circuit depths in idealized settings.\n\n- **Suitability for Noisy Devices:** Although our theoretical analysis is based on noiseless settings, our algorithm implementation, MG-Net, does not impose limitations on device noise. Refer to the discussion on impact in our Global Response for details.\n\n- **Resource Efficiency:** By dynamically generating mixer Hamiltonians tailored to specific problems and allowable circuit depths in practical hardware, MG-Net can improve the achievable approximation ratio of QAOA with small number of layers, making it more feasible for NISQ devices. As shown in Table 1 of our manuscript, our method achieves an approximation ratio of 0.96 for 64-qubit Max-Cut problems, which is much higher than other QAOAs with the same number of circuit layers.\n\nWe hope that this clarification will address the reviewer's concerns. We are prepared to offer more comprehensive responses if there are any further questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JPYjZnYgHM", "reviewer": "Reviewer_xXN5", "summary": "In this paper, the authors propose a model named MG-Net to automatically generate QAOA ansatz. It is able to generate the mixer layer in QAOA and decide which gates to share parameters. By sharing parameters, the ansatz generated by the proposed model can potentially achieve better trainability as well as expressivity. Experimental results on Max-cut and TFIM for up to 64 qubits are provided showing the proposed method can improve the accuracy under the proposed setting.", "questions": "No questions.", "limitations": "Shaky experiments with naive essence disguised in the fancy presentation.", "rating": 2, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Well-structured paper with numerous experiments verifying the theoretical claims.", "weaknesses": "1. It is too simple to design the mixer Hamiltonian since it only involves choosing one of the three Pauli operators to fill in the blanks. I don't see evidence that the proposed model (especially the training step) can still work if it encounters a more complex candidate gate set. \n2. The theoretical findings are not surprising to me since they mainly come from the quantum optimal control theory and overparameterization.\n3. The experimental results are shaky. 1) The comparison against ma-QAOA actually shows that these two methods have extremely close performance, which makes sense since the proposed grouping method is similar to ma-QAOA; 2) Missing the number of parameters (especially the number of different parameters) for each method in all the experiments, which is crucial since the expressivity of the ansatz is closely related to the number of tunable parameters; 3) The fatal problem is that the authors seem not fully understand the QAOA. The RZZ gates provide two-qubit phase transitions, and the original mixer, which is made of Pauli-X gates, finds the minimum eigenvector. Therefore, the ansatz should not consist of any single-qubit Pauli-z gate to introduce an illegal phase to the final state. This can also be verified in Tab.4 in the appendix. A Pauli-Y gate can be decomposed by Pauli-Z and Pauli-X gates, and since it's illegal to have a single-qubit phase in the final state, involving Pauli-Y gates **will not** benefit the results. It is clear that there is no single-qubit phase in the Hamiltonian of either Max-Cut or TFIM; I'm confused about how the authors got the results. So with all the efforts in training and selecting from {X, Y, Z, I}, it is actually deciding X or Y, which have identical effects on the final state (Y might be even weaker). I suspect that randomly choosing from X and Y can produce identical results **with precisely the same number of tunable parameters**. \n4. The whole paper is wrapped in an exquisite box with the essence of only choosing Pauli-X or Pauli-Y for the QAOA mixer.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our manuscript. We value your insights and address your concerns as follows:\n\n**Q1: It is too simple ... candidate gate set.**\n\n**A1:** We respectfully disagree with the reviewer's perspective that designing the mixer Hamiltonian is too simple. As mentioned in the Section \"Motivation\" of our Global Response, We release all freedom of the mixer Hamiltonian, including operator type and parameter grouping. Directly designing the mixer Hamiltonian based on Pauli operators remains computationally challenging and our proposed method tries to overcome this challenge efficiently. \n\n1. **Structure of Mixer Hamiltonian:** As described in Lines 176-189 and Eqn. (5) of our manuscript, designing a mixer Hamiltonian involves not only choosing appropriate operator types but also determining the parameter groups. This dual requirement adds complexity to the design process beyond simply selecting Pauli operators.\n\n2. **Challenges in Mixer Hamiltonian Design:** As discussed in Lines 194-197 of our manuscript, the search space for both parameter correlation and operator types grows exponentially with the system size $N$ (i.e., scaling at $O(N^N)$ and $O(2^N)$, respectively). This exponential growth makes designing an effective learning method difficult, as directly training a model in a supervised learning paradigm may require an infeasible amount of training data to achieve high accuracy. MG-Net addresses these challenges by bypassing the need to directly seek the optimal parameter correlation strategy and operator type.\n\n3. **Additional Experiments on Extended Candidate Operator Type Set:** To further support our claims, we have conducted additional experiments with an extended set of candidate operator types $\\{X,Y,XX,YY\\}$, achieving an approximation ratio $0.985\\pm 0.003$. As demonstrated in Figure 1 of the uploaded pdf, MG-Net maintains its efficiency and high performance even when the complexity of the mixer Hamiltonian design is increased.\n\n**Q2: The ... overparameterization.**\n\n**A2:** We would like to emphasize that our primary contribution lies in the development of novel algorithms designed to tailor optimal ansatz. While our study includes theoretical results, they are not the central focus but rather provide the theoretical foundation for MG-Net. Please refer to the Global Response for details. Notably, the theoretical results presented are non-trivial in terms of both contributions and techniques.\n\n**Theoretical Contribution.** Existing work on QNN convergence with symmetric ansatz does not address how specific ansatz design strategies affect symmetry or effective dimension. Our study qualitatively analyzes the relationship between the effective dimension and QNN convergence with various parameter grouping strategies in the context of QAOA.\n\n**Technical Aspect.**\nOur theoretical techniques involve the novel concept of effective dimension and tools from representation theory, widely used in analyzing QNNs with symmetric ansatz in quantum optimal control and over-parameterization. While the notion of effective dimension is inspired by these fields, our techniques for analyzing its relationship with ansatz design are unique. We use representation theory to compare the effective dimension of QNNs with different parameter grouping strategies by examining their algebraic structures.\n\n\n**Q3: The experimental results are shaky ... parameters.**\n\n**A3:** We respectfully disagree with the reviewer's perspective that the experimental results are shaky. We address the reviewer's concerns one by one as follows:\n\n1. **Comparison with ma-QAOA:** As demonstrated in Section 5 of our manuscript, our proposed MG-Net **performs significantly better than ma-QAOA** regarding convergence and approximation ratio. As the system scale grows from 6 to 64, the approximation ratio gap between our method and ma-QAOA increases from 1% to 96%. Besides, the mechanism for designing the parameter grouping strategy for MG-Net and ma-QAOA differs. MG-Net **dynamically generates** the optimal parameter grouping based on the given problem instance and allowable circuit depth, while ma-QAOA adopts a **static non-grouping strategy** to maximize the number of trainable parameters.\n\n2. **Number of Parameters:** We kindly remind the reviewer to refer to Lines 295-303 and Figure 5(a) of our manuscript for a detailed discussion about the number of parameters of different methods.\n\n3. **Mixer Hamiltonian Design:** We agree that the mixer Hamiltonian usually cannot be purely Pauli-Z due to the requirement of noncommutativity with the cost Hamiltonian. Therefore, we do not include Pauli-Z in the pool of operator types. However, the Pauli-Y operator is acceptable and can drive the quantum state toward the solution along a different and possibly more efficient path than the Pauli-X operator, as indicated in Figure 1(a) of our manuscript. This choice aligns with principles of counterdiabatic (CD) driving or shortcuts to adiabaticity (STA). Numerous works [Chandarana et al., 2022; Zhu et al., 2022] have verified the effectiveness of using Pauli-Y as a mixer Hamiltonian, as listed in Table 1 of the uploaded pdf. **Additional experiments** investigating the impact of randomly choosing mixer operator types from Pauli-X and Pauli-Y while maintaining the same number of tunable parameters indicate that mixer Hamiltonians with different operators and the same number of parameters behave differently, shown in Figure 2 of the uploaded pdf.\n\n**Q4: The whole ... mixer**\n\n**A4:** Our disagreement stems from the motivation and design of the mixer Hamiltonian in QAOA. Based on the elaboration in our Global Response and our response **A1-3**, we believe the review provides a clear understanding of our work. We are prepared to provide further explanations if necessary.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q4hvMa4XhR", "reviewer": "Reviewer_6Eat", "summary": "This paper provides a theoretical analysis on parameter grouping strategy in QAOA circuits. And the authors proposed MG-Net to design the mixer Hamiltonian, leading to the advantage over conventional methods and other QAOA classes.", "questions": "1. Have the author considered and compared with other mixer Hamiltonian design, e.g. Grover-Mixer? \n2. Can MG-Net be adapted to other VQA problems?", "limitations": "There does not seem to be negative social impact of this theoretical research.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. MG-Net reduces the cost of labelling and training by utilizing two-stage training strategy. \n2. Extensive numerical results strongly support the advantage of MG-Net, advancing the practicality of QAOAs. \n3. The method of this paper is certainly effective and the results are well presented.", "weaknesses": "1. The parameter grouping strategy does not guarantee a significant reduction in the effective dimension, which undermines the theoretical analysis's assurance of better convergence when employing MG-Net in subsequent sections. \n2. The details regarding the training of the mixer generator with hardware information are not clearly presented, raising concerns about the authors' claims of a \"problem-hardware-tailored mixer\" and \"Customize QAOA with Quantum Hardware Constraints.\" \n3. The numerical results comparison should include the Grover-Mixer method, as it also involves a unique design of the mixer Hamiltonian.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your thorough evaluation and thoughtful feedback on our manuscript. We are pleased that you recognized the strengths of MG-Net, including its cost-effective two-stage training strategy and the extensive numerical results that highlight its advantages, enhancing the practicality of QAOAs. In the following, we separately address your concerns:\n\n**Q1: The parameter grouping ... sections.**\n\n**A1:** To address the reviewer's concern, we would like to emphasize that the **theoretical results are not established to completely guarantee the performance of MG-Net**. Instead, **the proposed MG-Net in our work is theory-inspired to improve the convergence by tailoring ansatz design with optimal parameter grouping strategy**. To explain this point, we elaborate on the relationship between the theoretical results and proposed MG-Net algorithms. \n    \nWe first recall our theoretical contributions stated in Global Response that the Theorem 3.1 only establishes the qualitative analysis for the effect of parameter grouping strategy on the convergence in the overparameterization regime, showing that parameter grouping strategy could potentially reduce the effective dimension with the reduction amount determined by the specific Hamiltonian. Moreover, it is difficult to quantitatively analyze the reduction of effective dimension enabled by the parameter grouping strategy for various problem Hamiltonians, as this reduction depends on the detailed graph structure of problem Hamiltonians which is hard to analyze and is case-by-case. In this regard, there is no explicit optimal grouping strategy for significant reduction of the effective dimension for general problem Hamiltonians. To address this problem, we propose MG-Net to exploite the power of deep learning to automatically tailor the ansatz design with optimal parameter grouping strategy to achieve better convergence. \n\n\n**Q2: The details regarding ... Constraints.\"**\n\n**A2:** We acknowledge that further clarification is needed regarding the integration of hardware constraints in the training of MG-Net in our manuscript. As explained in the Section \"Motivation\" of our Global Response, we consider **the allowable circuit depth as the primary hardware constraint**, a common issue for both early fault-tolerant and NISQ devices. In the following, we address your concerns by providing a detailed explanation of the hardware constraints referred to in our manuscript and the implementation of the training of the mixer generator with hardware information. \n    \n- **Quantum hardware constraints.** There are many properties of a quantum device that affect its capacity, such as qubit connectivity, noise level, and maximum coherence time. In our manuscript, the term \"hardware constraint\" refers to the allowable circuit depth of a quantum device, which is closely related to the metric of maximum coherence time.\n\n- **Hardware-information-aware training.** When constructing the labeled training dataset, we collect the achieved approximation ratio of a mixer Hamiltonian with varying circuit depths. After the first-stage training, the cost estimator can precisely capture the intrinsic correlation between the circuit depth and the achievable cost, as verified in Lines 282-288 of our manuscript. In the second-stage training, this circuit depth information is incorporated by encoding it into the input features of the mixer generator. Guided by the circuit-depth-oriented cost estimator, the mixer generator can be trained to predict the optimal mixer generator according to the given hardware constraints, i.e., circuit depth.\n\n- **Extension to other hardware constraints.** Although we only consider the allowable circuit depth as the hardware constraint in applying MG-Net to QAOA in our manuscript, our proposed method is a general framework to learn a hardware-oriented circuit generator. It can be flexibly extended to other hardware constraints. Refer to the discussion on impact in our global response for details.\n\nTo clarify, we have followed the reviewer's advice to clarify the hardware-constraint-aware training in the revised manuscript.\n\n**Q3: The numerical results comparison should include the Grover-Mixer method, as it also involves a unique design of the mixer Hamiltonian.**\n\n**A3:** The Grover-Mixer (GM) method uses Grover-like selective phase shift mixing operators based on the prepared equal superposition of all feasible states. GM is designed to perform particularly well for constraint optimization problems. However, in our manuscript, we utilize QAOA to solve Max-Cut and TFIM problems, which are both unconstrained optimization problems. When applying GM to these tasks, it is equivalent to the original QAOA. Therefore, we did not consider GM in our original manuscript.\n    \nTo effectively compare our method with GM, we shifted our focus to a new constrained optimization problem. Due to the limited rebuttal period, we will update the results as soon as they become available.\n\n\n**Q4: Have the author considered and compared with other mixer Hamiltonian design, e.g. Grover-Mixer?**\n\n**A4:** Please refer to A3 for details.\n\n**Q5: Can MG-Net be adapted to other VQA problems?**\n\n**A5:** Yes, MG-Net can be flexibly adapted to handle other VQA problems. While the primary focus of our manuscript is on improving the QAOA, the proposed method provides a general framework for automatically learning a hardware-oriented circuit generator that can balance performance and hardware resources, based on the interdisciplinary collaboration of quantum science and artificial intelligence (AI). Many works that utilize deep learning techniques to assist the research of quantum algorithms have been successfully applied to tackle multiple VQA problems [Zhang et al, 2022; Wu et al, 2023; Fürrutter et al, 2024]. We kindly refer the reviewer to the discussion about extending our work to other problems in our Global Response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W3aP4AkCmf", "reviewer": "Reviewer_DGPC", "summary": "The paper proposes a deep learning approach called Mixer Generator Network (MG-Net) to enhance the performance of Quantum Approximate Optimization Algorithm (QAOA) by dynamically designing optimal mixer Hamiltonians for a given class of problem and a circuit depth constraint. This is done by parameter grouping that is analyzed theoretically by the authors. The authors demonstrate the effectiveness of MG-Net enhances QAOA performance in terms of approximation ratio for QAOA problem instances like Ising models and weighted Max-Cut instances up to 64 qubits.", "questions": "- It is not clear why position embedding is needed to represent the depth, why not give the number or use simple one-hot encoding?\n- Why $J_{ij}$ is chosen to be only positive between $[0.5, 1.5]$ and not include also negative value or even 0? To avoid frustration?\n- Can this approach be extended to other problems in quantum computing that use PQC such as unitary synthesis or state preparation?", "limitations": "Limitations are addressed in the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The main contribution of the paper (MG-Net) as a dynamic solution to customize mixer Hamiltonians is novel, innovative, and sound, backed by theoretical analysis of the convergence theory of QAOA. The performance evaluation of the method is also comprehensive, covering a range of QAOA problem instances and validating the proposed framework's effectiveness. The presentation of the paper is clear and well-structured. The paper detailed the explanations of methodologies supported by diagrams that aid comprehension.", "weaknesses": "- The “Quantum Hardware Constraints” in the title seems not appropriate. When talking about quantum hardware constraints, practically one would talk about the qubit connectivity, available gate set, noise model, etc. However, in this paper, it seems that it only talks about the circuit depth.    \n- The paper is reasonably sound and well-presented. However, I am not sure if the broader NeurIPS community will be interested in this work since it is a specific improvement for the QAOA algorithm. This will attract the quantum machine learning community. However, some of the quantum computing communities might also be skeptical because, as mentioned in the conclusion, this does not take into account the noise in the device. \n- The paper does not address the efficiency issue. This can be done by adding the training and inference time for each method in Table 1.\n\nMinor comments:\n- “Intial” in Figure 1. \n- Add $d_{eff}$ after “effective dimension” to make it clearer in Figure 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your detailed evaluation and thoughtful feedback on our manuscript. We are pleased to hear that you found MG-Net to be a novel, innovative, and sound contribution, with strong theoretical backing and comprehensive performance evaluation. In the following, we separately address your concerns:\n\n**Q1: The “Quantum ... about the circuit depth.**\n\n**A1:** As explained in the Section \"Motivation\" of our Global Response, we consider **the allowable circuit depth as the primary hardware constraint**, a common issue for both early fault-tolerant and NISQ devices. The allowable circuit depth of a quantum device is closely related to the metric of maximum coherence time. To make our title clearer, we have followed your suggestion and rewritten the title as \"MG-Net: Learn to Customize QAOA with Circuit Depth Awareness\" and clarified the hardware constraints in the main text of the revised manuscript.\n\nAdditionally, MG-Net can be flexibly extended to other hardware constraints. Refer to the Section \"Impact\" of our global response for further details.\n\n\n**Q2: The paper ... the noise in the device.**\n\n**A2:** We appreciate your recognition of the soundness and presentation of our work. We address your concerns regarding the broader interest to the NeurIPS community and the consideration of device noise as follows:\n\n1. **Broader Interest to the NeurIPS Community.** While the primary focus of our manuscript is on improving the QAOA to tackle complicated combinatorial optimization problems, the proposed method provides a general framework for automatically learning a hardware-oriented circuit generator that can balance performance and hardware resources. The methodologies and insights derived from this work have broader implications for the field of machine learning for physical sciences, which aligns with NeurIPS's emphasis on interdisciplinary collaboration. The principles of dynamically optimizing quantum circuits using deep learning can be applied to other quantum algorithms and hybrid quantum-classical approaches, making this work relevant to a wide audience interested in quantum technologies and their integration with machine learning.  There is a growing number of papers related to quantum computing have been published at top AI conferences like NeurIPS, ICML and ICLR [Gao et al., 2023; Sidford et al., 2023; Wu et al., 2023; Tang et al., 2024; Patel et al., 2024; Lei et al., 2024]. Among these, QAOA is particularly appealing for solving combinatorial optimization problems.\n\n2. **Noise Settings.** We acknowledge that our current manuscript does not explicitly consider noise constraints in quantum devices, as discussed in the conclusion of our manuscript. We address your concerns from two dimensions: the importance of fault-tolerant quantum research and the extension to noisy devices.\n\n    - **Importance of fault-tolerant quantum research.** Conducting research within a fault-tolerant, noiseless framework is crucial for unlocking the full potential of quantum computing and achieving quantum advantages over classical methods, such as works on quantum learning theory and optimization acceleration [Larocca et al., 2023; Liu et al., 2024]. Our theoretical analysis on QAOA is situated at the same fault-tolerant context to provide practical insights for improving QAOA's performance to achieve quantum advantage within limited circuit depths in idealized settings.\n\n    - **Suitability for noisy devices.** Our algorithm implementation MG-Net can adapt to device noise. Refer to the Section \"Impact\" of our Global Response for further details. The success of our approach within this framework sets the stage for future exploration of our model's applicability to noisy systems and real-device experimentation.\n\n\n**Q3: The paper does not ... in Table 1.**\n\n**A3:** Since only MG-Net includes a training phase, we have followed your advice to add inference time for each method shown in Table 2 of the newly uploaded pdf.\n\n**Q4: “Intial” in Figure 1.**\n\n**A4:** We have corrected this typo in the revised manuscript.\n\n**Q5: Add $d_{eff}$ after \"effective dimension\" to make it clearer in Figure 1.**\n\n**A5:** We have followed your advice to add $d_{eff}$ after \"effective dimension\" in the caption of Figure 1 of the revised manuscript.\n\n**Q6: It is not clear ... one-hot encoding?**\n\n**A6:** Thank you for your insightful question. It is indeed an interesting idea to replace position embedding with integer encoding or one-hot encoding. As mentioned in the \"Contribution\" section of our Global Response, MG-Net acts as an initial protocol and provides a flexible circuit-generation framework where model components can be conveniently replaced by advanced techniques. To address your concerns, we are conducting additional experiments to replace position embedding with one-hot encoding or integer encoding. Due to the limited rebuttal period, we will update the results as soon as they become available.\n\n**Q7: Why $J_{ij}$ is ... frustration?**\n\n**A7:** The choice of $J_{ij}$ values in our study is influenced by several considerations related to TFIM.\nThe TFIM undergoes a quantum phase transition at the critical point $h/J=1$. To more comprehensively study the behavior of the system in different phases, we set $J\\in [0.5, 1.5]$ and $h\\in [0.1, 2]$. This range ensures that the value of $h/J$ can be smaller than, equal to and greater than 1, covering the critical point and both phases of the transition. We do not consider the case where $J$ is negative because we mainly focus on ferromagnetic interactions to avoid frustration.\n\n**Q8: Can this approach be extended ... preparation?**\n\n**A8:** Yes, our approach can be flexibly extended to other problems in quantum computing that use parameterized quantum circuits. Please refer to the Section \"Impact\" of our global response for further details.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

We thank all reviewers for their efforts, insightful comments and constructive suggestions. We appreciate the opportunity to clarify the main motivation, contributions and impact of our work.

**Motivation.** A promising approach to tackle combinatorial optimization problems (COPs) is QAOA, which can potentially outperform classical methods when unlimited circuit depth is assumed. However, this requirement is impractical. Considering the practical utility of QAOA, where quantum resources are constrained by limited circuit depth, noise, and qubit connectivity, many variants of QAOA have been proposed to enhance its performance within these hardware constraints [Chandarana et al., 2022; Zhu et al., 2022; Yu et al., 2022; Herrman et al., 2022; Bartschi et al., 2020; Sauvage et al., 2022]. However, these alternatives often require deep domain expertise and lack generalizability across different tasks and circuit depths.

Our work considers **the allowable circuit depth as the primary hardware constraint, a common issue for both early fault-tolerant and NISQ devices.** We release all freedom on the mixer Hamiltonian, including operator type and parameter grouping. Our goal is to dynamically adjust the mixer Hamiltonian according to the given problem and the allowable circuit depth of a quantum device, thereby **enhancing the performance of QAOA while ensuring compatibility with the available quantum resources**.

**Contributions.** To fully exploit the potential of a QAOA circuit with arbitrarily limited circuit depth, we first theoretically analyze the convergence of QAOA:
- **Theoretical contributions.** Existing literature studied the convergence of VQAs from two aspects, namely the quantum neural tangent kernel [Liu et al., 2022; Liu et al., 2023] and gradient flow [You et al., 2022; You et al., 2023]. In particular, when analyzing the convergence rate of QNNs with symmetric ansatz, both of these two techniques involve utilizing the tools of effective dimension for quantifying the effect of symmetry degree of ansatz design on the convergence rate. While existing literature has explored the convergence theory of VQAs with symmetric ansatz well, **how concrete strategies for ansatz design affect the symmetry degree remains an open question**. In this study, we **initiate the first attempt to qualitatively analyze the effects of various parameter grouping strategies on the convergence of QAOA**.
- **Technical contributions.** We rigorously show that **fully or partially grouping the parameters according to the spatial symmetry of problem Hamiltonians could reduce the effective dimension** (Refer to Lemma B.6 in Appendix B), where the concrete reduction amount depends on the symmetric degree of problem Hamiltonians. Moreover, combined with the existing results on the effective dimension-based convergence analysis [You et al., 2022], we reach our main theoretical results (Theorem 3.1) regarding the convergence rate of QAOA with various symmetric structures in the overparameterization regime.
- **Implications.** Qualitatively, when $p$ is large enough to reach the overparameterization regime, a suitable parameters grouping strategy should be adopted to reduce the effective dimension for better convergence. Conversely, for a small $p$, the parameters should not be grouped to obtain as large a representation space as possible for better convergence. However, **it is difficult to quantitatively determine the effective dimension, the critical point for the overparameterization regime for general problem Hamiltonians**, as they are determined by the specific graph structure of the problem Hamiltonian which is case-by-case and hard to analyze. This inspires us to utilize the power of deep learning to automatically tailor the circuit depth-aware ansatz design with the optimal parameter grouping strategy for better convergence.

Guided by the established theoretical results, we propose MG-Net for automatical circuit design：
- The QAOA circuit generated by the proposed MG-Net achieves **higher approximation ratios at various circuit depths** compared to other quantum and traditional methods,  advancing the **practical utility** of QAOAs.
- MG-Net **greatly reduces the cost of collecting labeled training data**, making it possible to handle **larger-scale problems and more complicated mixer Hamiltonians**.
- MG-Net provides a flexible circuit-generation framework where the data encoder can introduce more hardware constraints, and the model components can be conveniently replaced by advanced techniques. Although our theoretical analysis is based on noiseless settings, our implementation does not impose limitations on device configuration. **MG-Net can be flexibly extended to other hardware constraints**, such as **qubit connectivity** and **hardware noise**. 

**Impact.** While our work enhances the ability to employ quantum algorithms to tackle combinatorial optimization problems, the methodologies and insights derived from this work have a broader impact on the field of **machine learning for physical sciences**. The principles of **dynamically optimizing quantum circuits using deep learning** can be applied to other quantum algorithms and hybrid quantum-classical approaches.

Concretely, **MG-Net can be flexibly adapted to handle other VQA problems.** The feature encoding used in MG-Net, which includes problem-specific and hardware-specific information, can be modified to accommodate the requirements of different VQA problems. This modularity ensures that the model can process diverse types of input data relevant to other quantum algorithms, such as unitary synthesis, state preparation and quantum machine learning.

We hope these explanations can provide a more comprehensive understanding of our work and partially address your concerns. Below, we provide a point-by-point response to the reviewers’ comments and concerns.

Best regards,

Authors

Meta-review: This paper proposed Mixer Generator Network (MG-Net), a unified deep learning framework for dynamically formulating optimal mixer Hamiltonians tailored to distinct tasks and circuit depths. Theoretical results proved bounds on the effective dimension of ansatzes and connected those to convergence guarantee from theoretical results by You et al. (2022). Experimental results compared the proposed mixer with previous QAOA methods and achieved better performance throughout.

There were adequate discussions during the rebuttal. Three of the reviewers (aG1x, 6Eat, DGPC) found the paper favorable because the results are solid (having both theory and experimental results), and the performance evaluation is also comprehensive. The presentation is also clear and the codes are publicly available. On the other hand, one reviewer (xXN5) was concerned about the design of the mixer Hamiltonian (too simple chosen only from Pauli X and Y) as well as the experimental results. The authors responded in detail with clarification of experimental details, and also added experiments with Pauli X, Y, XX, YY ansatz design.

Given the very distinct scores from the reviewers, the area chair carefully checked the paper as well as all discussions between the authors and reviewers. The decision is to accept the paper. Regarding the main concern raised by xXN5 that choosing between Pauli X and Pauli Y make the task of designing the mixer Hamiltonian relatively naive, the mixer Hamiltonian in the original QAOA algorithm is simply sum of Pauli X’s. As QAOA is quite motivated from quantum adiabatic algorithms, it needs to transit from a simple Hamiltonian with an easy-to-prepare ground state to the target Hamiltonian. Being simple in the mixer Hamiltonian is not an issue, but the paper shows how to enlarge the search space of the mixer Hamiltonian with better performance.

Nevertheless, towards the final version of the paper, the authors should also improve on various perspectives to clarify the details:

1. Clarify the mixer choices. Table 1 of “Supplementary Material for Tables and Figures” added during rebuttal is very helpful; the author should add the table to the main body, with an extra line covering what are the mixer Hamiltonians considered in this paper (by adding a line beginning with “this work”).

2. Merge the experimental results, especially those with ansatz design from {X, Y, XX, YY} (i,e., including two-qubit Pauli XX and YY), into the main body.

3. The choice of the initial state |psi_0>. This was not a point raised by reviewers and hence was not discussed during the discussion period, but the area chair got confused and feel that this is a point that is worth clarification in detail. After all, QAOA-type algorithms are motivated from quantum adiabatic theorems, and the initial state should probably the ground state of the mixer Hamiltonian that is also easy to be prepared. Is this also the case for the mixers studied by the paper? I guess if the mixer is composed of only single-gate Pauli X and Y’s this shouldn’t be a problem (but this is still worth clarifying); but as the discussion period suggested and the author had done, ansatz design now covers XX and YY, I feel that the preparation of the initial state should be carefully discussed.
Decision: Accept (poster)