Rethinking Parity Check Enhanced Symmetry-Preserving Ansatz
Authors: Ge Yan
Mengfei Ran
Ruocheng Wang
Kaisen Pan
Junchi Yan
Venue: NeurIPS 2024 poster (2024)
Keywords: symmetry-preserving quantum computing
parity check
error mitigation
Primary area: machine_learning_for_physical_sciences

Abstract: With the arrival of the Noisy Intermediate-Scale Quantum (NISQ) era, Variational Quantum Algorithms (VQAs) have emerged to obtain possible quantum advantage. In particular, how to effectively incorporate hard constraints in VQAs remains a critical and open question. In this paper, we manage to combine the Hamming Weight Preserving ansatz with a topological-aware parity check on physical qubits to enforce error mitigation and further hard constraints. We demonstrate the combination significantly outperforms peer VQA methods on both quantum chemistry problems and constrained combinatorial optimization problems e.g. Quadratic Assignment Problem. Intensive experimental results on both simulators and superconducting quantum processors are provided to verify that the combination of HWP ansatz with parity check is among the most promising candidates to demonstrate quantum advantages in the NISQ era to solve more realistic problems.

Rethinking Parity Check Enhanced Symmetry-Preserving Ansatz
Ge Yan, Mengfei Ran, Ruocheng Wang, Kaiseng Pan, Junchi Yan" Dept. of CSE & School of AI & Zhiyuan College, Shanghai Jiao Tong University Srange98,Imf202 Ignite, passsiteepss811,,.. pks0813, yanjunchi)00jjtu yaaneeee wts.anccchc.jj.uuuu....... edu.cc
Abstract
With the arrival of the Noisy Intermediate-Scale Quantum (NISQ) era, Variational Quantum Algorithms (VQAs) have emerged to obtain possible quantum advantage. In particular, how to effectively incorporate hard constraints in VQAs remains a critical and open question. In this paper, we manage to seamlessly combine the Hamming Weight Preserving ansatz with topological-awe physical qubits to enforce error mitigation and further hard constraints. We demon- strate such combination significantly outperforms peer VQA methods both quantum chemistry problems and constrained combinatorial optimization problems e.g. Quadratic Assignment Problem. Our extensive experimental results both simulators and superconducting quantum processors verify that the combination HWP ansatz with parity check is among the most promising candidates to show quantum advantages in the NISQ era to solve more realistic problems.
parity check on
Introduction
Variational Quantum Algorithms (VQAs) [7 73 and their derivatives [80] have garnered increasing attention as numerous studies investigate their potential to achieve quantum supremacy. With the advent of the NISQ era [65] [0] and the improved deployment capability (77), the exploration of new these algorithms have shown promise in delivering quantum advantage on near-term quantum devices [1]. However, despite their potential, commonly used VQAs such as the QAOA [27] for Quadratic Unconstrained Binary Optimization (QUBO) and UCCSD [67] for ground state energy estimation are not inherently designed to handle hard constraints. Typically, these constraints are modeled as soft penalty terms within the objective function, which may be the most efficient approach. Addressing the natural incorporation of symmetries and hard constraints directly into VQAs remains an open and eritical challenge for advancing the field.
VQAs has accelerated,
In this paper, we investigate Hamming Weight preserving (HWP) ansatz 78 and parity check (53 novel approach for error mitigation and the imposition of hard constraints in quantum circuits, rather than modeling these constraints as penalty terms in the Hamiltonian, as is common in the literature [18 48 The HWP ansatz, operating in a constrained subspace, utilizes parameterized gates that maintain the number of non-zero elements in the quantum state. Recent work [78] has thoroughly analyzed the expressivity and trainability of the HWP ansatz, demonstrating its outstanding performance in capturing fundamental symmetries, such as total spin conservation. Meanwhile, quantum LDPC code [53] [3] and surface code [2 have been widely widely adopted in quantum error correction through the use of stabilizers to detect and correct qubit errors. However, significant challenge remains identifying quantum ansatze that naturally facilitate error correction mechanisms. In response, we propose combined framework that integrates the HWP ansatz with parity check operations. Since the HWP ansatz. inherently preserves the number of non-zero elements in quantum states, it offers a promising foundation for enhancing parity check performance in mitigating errors. By employing parity checks as projective mcasurements, quantum states can be
"Correspondence author. This work was partly supported by NSFC (92370201, 62222607) and Shanghai Municipal Science and Technology Major Project under Grant 2021SHZDZX0102.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

constrained directly to the problem subspace, thereby introducing a robust mechanism for error mitigation while expanding the utility of parity checks beyond their conventional role. This approach allows for more effective error correction and constraint enforcement within quantum circuits.
In this paper, we first analyze the effect of utilizing parity check as an error mitigation method for HWP ansatz on popular quantum chemistry problems, whose (symmetry) constraints can be effectively addressed by HWP. The parity check block is constructed by a cascade of CNOT gates which only requires nearest neighbor connectivity of physical qubits. By repeatedly inserting parity check blocks in the quantum circuit we can mitigate the influence of unexpected bit-flip errors. The results on noiseless simulator demonstrate that the proposed universal HWP ansatz is able to exceed UCC ansatz with single, double, and even triple excitation. We also test the performance of parity checks with HWP ansatz against other symmetry verification (SV) methods [38, (70 with UCC ansatze. Under the simulated noise, we observe that only verifying the number of non-zero elements at the end of the circuit is not enough to determine whether there is an occurrence of error, so constantly parity checks in the circuit are essential for detecting bit-flip errors.
We then combine HWP ansatz and parity check to develop an efficient paradigm to incorporate additional hard constraints beyond the capability of HWP, to enable solving other constrained problems in classic computing, specifically Quadratic Assignment Problem (QAP) [55]. This problem known an NP-hard combinatorial optimization (CO) problem. as widely studied in literature in both classic machine learning (ML) [79] and quantum ML [80]. It aims to find an optimal permutation matrix with each column and row having only one non-zer element. Specifically, we map the permutation matrix to the physical qubit lattice topology with each qubit connected to its four nearest neighbors. We then apply HWP layers on the rows to ensure a smaller subspace with parity checks on the columns appearing at intervals to further restrict the states to QAP subspace. The final loss is calculated with in-constraint states so that we can find the optimal solution within the constraints.
To further illustrate the capability and efficiency of the proposed approach, we conduct experiments on both simulators and superconducting quantum processors. We compare a wide range of baseline methods with soft constraints, e.g., HEA [46]. QAOA [27]. X Xmmxer [39]. and we also add hard constraints to some of them with the proposed paradigm. The numerical results on the simulator demonstrate the outstanding performance of the proposed hard constraint paradigm. We also test our methods on the Traveling Salesman Problem (TSP) to illustrate the capability of our methods on other CO problems by reducing it into QAP. For the hardware experiments on a superconducting quantum processor, the proposed method also show promising performance, especially with the physical qubit topology (no SWAP gates required in the compilation). We move the related works and preliminaries to the Appendix. The contributions of this paper are:
1) We illustrate how to utilize parity check to mitigate quantum errors and incorporate further constraints for HWP ansatz. The combination of these two is among the most promising candidates to demonstrate quantum advantages in the NISQ era (for VQA) to solve more realistic problems.
2) We discuss the connection between HWP and UCC ansatze on quantum chemistry problems and further examine the efficiency of parity check as error mitigation on the simulator with noise. Results illustrate that universal two-qubit HWP gates exceed UCC with high-order excitation terms and parity check in between HWP gates can mitigate errors better than SV [38 (7)..
3) We propose a novel hard-constraint VQA with parity check as further constraints for HWP. We map the permutation matrix QAP to the physical qubit topology and enable the maximum utility of qubit connectivity. The superior performance over peer VQAs on both simulator and quantum processor shows the capability and efficiency of our method on constrained CO, e.g. QAP and TSP.
2 Parity Check as Error Mitigation for HWP
We first illustrate how to parity check as error mitigation for HWP ansatz. The HWP ansatz maintains the number of non-zero elements in the whole unitary transformation, which makes it easy to detect any unexpected bit-flip. By constantly applying parity checks we can correct these errors.
2.1 Ground State Energy Estimation
The ground state energy estimation problem, which is the very first step in computing the ener- getic properties of molecules and materials, has received intensive attention with various VQE approaches 73.. The ground state of molecule is the stationary state with the lowest allowed energy, which can be estimated given the types and relative coordinates of the atoms in the molecule and the

---

number of orbitals and electrons. Providing a molecular Hamiltonian Hm, and a trial wave function (1)), the ground state energy Eg is bounded by (28)
S (bb) Hm 11b)
Eg
(I)
(161))
where the equality holds if and only the parameterized wavefunction (e) is the ground state. To solve this problem bound to be unitary operations since we are operating on a quantum computer and all the quantum gates are unitary transformations. We then describe the unitary parameterized ansatz as U()). The qubits are initialized as [0)" (abbreviated as (0)) with n as the number of orbitals under the Jordan- Wigner transformation [45]. Notice that any quantum state is necessarily normalized wavefunction,
quantum computer, need to design the ansatz wavefunction, which is
so the cost function of the VQE problem is 773
EVQE min (0) ((0) (0)
The molecular Hamiltonians often come with symmetry constraints, and we can utilize HWP ansatz to reduce the evolving space and draw support from parity check as error mitigation method.
2.2 HWP ansatz for Quantum Chemistry
We first introduce two basic models, namely the Cluster model (UCC) [64), show how HWP ansatz be linked quantum chemistry. Both models describe the hopping of electrons on orbitals (UCC model) or sites (Hubbard model) by creation and annihilation operators (see definition in Apx. B..2. We have the following observation: Remark 2.1. Both hopping terms in the UCC and Fermi-Hubbard model are HWP operators.
model 44 and Unitary Coupled
Recall the hopping term on adjacent sites i and in the Fermi-Hubbard model is defined as:
0
0
0
HFH = a,a, afa:
0
xx 3
oz + Og & 0y
0
0 0
where a and at are the annihilation and creation operators, respectively (see detailed definition in Apx. B.2). Similarly, the cluster operator in the coupled cluster theory is T a,a,. For the state transformation for UCC model, we follow the form (e) -- (b6) [3]. where T 7 is an anti-Hermitian operator which makes it suitable for quantum computers since the exponential of an anti-Hermitian operator is a unitary operator. The Hamiltonian for the single excitation term is
-0000
0
0
Hucc (T- (T-
0
0
0
0
1
0
0
0
0
-1
0
0
0
(4)
0
0
0
0
0
Both of the above Hamiltonian fits the definition of HWP (see Eq. 21 Apx for the introduction of the preliminaries of HWP), so they are both HWP operators.
B
Lemma 2.2. The hopping terms in UCC and Fermi-Hubbuu are not universal in the HWP subspace.
According Theorem B.1 (66 (see details in Apx. Bp. an HWP operator with a given connectivity is universal if and only it the dimension of the corresponding dynamical lie algebra (DLA) is de with
dy = (f). where n and & is the number of orbitals and electrons, respectively. For nearest neighbor (NN) connectivity, we can derive the dimensions of DLA for operators in Eq. 3 and Eq. 4 as follows:
(n ()
odd
1 dirnn((urc)) nnnn - 1), dimmn (DFH)
(5)
n(n 1)
is even
For fully connected (FC) connectivity, the dimensions of DLA for the operators are:
(de + 1) 1)
n + 2k
diCcc( di. (dk 1), dimfe(gru)
1 (d+ + +22 - 2) n = 2k
(6)
2
All of the dimensions do not meet the requirement of de, so both Eq. and Eqq. are not universal in the HWP subspace, which aligns with the fact that Eq. 3 and Eq. 4 are truncated hopping terms.
3

---

Theorem 2.3, An ansatz U()) can solve the ground state energy estimation problem without truncation if the ansatz is universal under the dg dimensional HWP subspace.
The detailed proof is provided in Apx. C In contrast the Fermi-Hubbard model that does not have higher-order hopping terms, the UCC model has double and triple excitation operators [41] able to improve the accuracy of the final ground states. However, the double and triple excitation operators require 4-qubit and 6-qubit gates respectively, which makes it unaffordable when decomposing them into basic gates. Thus, we seek two-qubit HWP gates (much easier implement than double and triple excitation operators) that are universal under the HWP subspace with no truncation at all.
Definition 2.4. We propose an HWP gate namely NBS with the Hamiltonian and dimension of DLA:
0
0
0
0
ch
#
2k,
HNBS-
dim(p) (0)
(7)
0
-
0
d2
2k.
0
0
NBS gate is very close to universal under NN connectivity and simpler than the one proposed in 778.. Thus, we can use the NBS gate to construct an NN connected ansatz without any truncation (UCCSD (67)) prior knowledge about quantum chemistry (adapt (36)).
common error mitigation technique in VQE for the UCC and Hubbard model is SV which discards runs where the final and initial occupations do not match. This method leverages the fact that these VQE ansatze exhibit symmetries such as number conservation per spin sector and time-reversal symmetry. Specifically, when verifying the symmetry of total spins, one counts the number of non-zero elements in the final state to detect any unexpected bit-flip or readout errors that may alter the total spin count. However, SV only reflects symmetries in the final state and requires readout of all qubits (or at least an equal number of measurements), adding complexity. To simplify both the verification of final states and the intermediate states during computation, we pro- pose utilizing parity checks, technique commonly employed in classical and quantum error correction. Unlike SV, which counts the number of non-zero elements in the quantum state, parity checks only evaluate the parity of these non-zero elements. While a single parity check extracts less information than SV, applying parity checks continuously throughout the quantum circuit ensures that the final state retains the same Hamming Weight as the initial state (as long as the probability of multiple bit-flips occurring between two parity checks is sufficiently low). The HWP ansatz is an ideal complement to parity checks because it guarantees a constant HW for the intermediate states, allowing for the seamless integration of parity checks at any point in the ansatz. This approach not only mitigates errors but also simplifies the error detection process by embedding directly into the circuit, as illustrated in Fig.
Parily Check
9:
HWP layer
XX
Z
|/2 [30
Repest times
Figure I: The overall circuit structure for par- ity checks and HWP ansatz.
Table 1:
Statistics of molecules. k, da is the number of orbitals, electrons, and HWP subspace dimension respectively.
2.3 Simulated Experiments on State Preparation
Dataset: We select three well-studied molecules, i.e. Hy- drogen (H2), Lithium Hydride (LiH), and Water (H2O). The molecular Hamiltonian is obtained from the Python package OpenFermion (58). The computational basis for all the molecules is STO-3G with Jordan Winnerr transfor- mation. To simulate the circuit with noise on Qiskit, we d₃
Molecules
H2
LiH
H₂O
4
8
8
k
2
2
4
28
70
utilize the Acr-simulator from Qiskit based on the density matrix which is time-come consuming. Therefore, we freeze some of the inactive orbitals to reduce the problem size of the above molecules. The detailed molecular information is listed in Tab.[]
To show the efficiency of the HWP ansatz and the superiority of combining HWP ansatz with parity check, we select the well-studied UCC ansatz our baselines. To better illustrate that universal HWP ansatz is able to solve the state preparation problem without any truncation, we include single excitation (UCCS), double excitation (UCCSD), and triple excitation (UCCSDT), All
Baselines:

---

Table 2: Numerical results for state preparation. "Error" stands for the energy with respect to
FCI energy, "prob" represents the success rate in SV and PC, "SE" stands for value less than 10 10
Scting
Esngs (Ha)
Evor
Poob
Enegge (Hi)
1alt
Eroo
Poob
Energe (Hi)
1g0
Everr
Pob
1.83x21013
DCTS
4.9776263500
2. 2195220" 1
770094709444
1.65x10-11
24.446601122
5055300
5V
4.9110997814
106-:10"
0.365
F10264 T06?
1.8
0.751
7215 12469
0.49
misccos
7.17619937044 1.0 10
3.0
2.82x10m1
-2472559385001
10-
8.94361 NAWS
561734
9-98x10-1
788 10"1
SV
4.70427/9212
4.32K10-1
0.716
6.3376200127
1.08
-738500427310
9.87-10-1
0,501
milseles
87x
UCCSDT
mise
-72 2218445285537
8.0 8.1
SV
-77 8637764770
8 10
0,500
1.1781886977
56118162000
56
-242119244415-
77
SV
777554740003
3 3.0001
0.747
1512560064
7:53x10
908855555257
8.36-10
0.505
SV-PC
4.76078771177
3.66-100-
0.64
-7 27222 2012/0
6.01-11--1
0.833
-24048636800
6.88x10-1
0.022
the ansatze are implemented with Qiskit-Nature 24 and initialized with Hartree-Food state. The optimizer SLSQP.
Results on Simulators The sensitivity analysis on the number of parity checks and hyperparameter settings are listed in Apx. E We provide the results on the simulator with noise in Tab. 2 We first focus on the results of UCC ansatze with different excitation and the proposed HWP ansatz without noise. Notice that H2 and LiH only have 2 active electrons so it is impossible to apply triple excitation in the ansatz. It is shown that adding high-order excitation terms in the UCC ansatz can improve the results, and the proposed universal HWP ansatz is able solve the problem with no truncation at all which leads to energy with error less than 1 x 10-10 The circuit depth of HWP ansatz is also much less than UCCSD and UCCSDT. Detailed comparisons of the eircuit statistics are listed in Tab. g
We make several important observations on the results with noise and error mitigation methods. I) UCCS outperforms other methods with noise since it is extremely shallow. 2) SV with deep circuit is useless since the parity of the output state is approximate to 0.5, indicating the results for each qubit close uniform superposition state. 3) More shots per Pauli string would be beneficial to better illustrate the performance of error mitigation methods. 4) Parity check can improve the results on deep ansatz. By combining other error mitigation approaches (such as readout error mitigation), we may further improve the accuracy. Therefore, we can conclude that parity check is an efficient error mitigation method for HWP ansatz, which can improve the result quality.
Parity Check as Further Constraints for QAP
Apart from the quantum chemistry problems, the HWP ansatz proved to be able to serve as a hard constraint for combinatorial optimization problems (78). In this section, we will demonstrate how to utilize parity check to enforce additional hard constraints for HWP ansatz so that we are capable of solving more complicated constraints.
3.1 Quadratic Assignment Problem
The Quadratic Assignment Problem (QAP) is a well-studied NP-hard problem dated back to 152
typical QAP instance of size m is given by two matrices E Rm D E Rm defining the
flows between facilities and the distances between locations (55). Its objective with constraints is:
min E. k0=1k,p=1
S.t.
X 1=1
-1
Σ
- 1 m, (8)
where X E {0, 1m is the permutation matrix illustrated in Fig. 2(a). The essence of QAP is to find the best permutation matrix which minimizes the objective function. Further, we define
W E Rmm xmx as the energy matrix with W = F & D, corresponding to the vector product form of the flow and distance matrices. The QUBO form of QAP is:
min vXc T W vec(X)
s.t.
X
= Σ
= 1,
m,
(9)
j=1
where XXe E {0, 10.1mm²x denotes a vector by concatenating the columns of matrix X 79 We can further derive the Hamiltonian of the Ising form of QAP:
1 Σ
HQAP
D F (oll-o-((C o1) (1- -jj),
(10)
4
k,p=1
5

---

(a)
[c]
3
HRR Tayer
Party Chock
0
911
0
012
1
011
812
(9)
923
811
922
Repeal STA3
(5)
109
10)
Repast
Figure (a) The QAP instance with four facilities (A, B,C, mapped to four locations (0, 2,3). The permutation matrix encodes the mapping and satisfies the constraint that each facility is mapped to only one location and vice versa. (b) The topology of the physical qubits of superconducting quantum processor. For QAP with ancilla qubits denoted as a, with the structure shown on the right. Each qubit şij maps to the element X.y in the permutationn matrix and suffice the constraints that each row and column has only one [1). (c) The overall circuit for QAP with all the working and ancilla qubits is named the same as (b).
3, we select n m working qubits denoted as qij and m
where HQAP& E R x2", and o² is the pauli-z matrix. Thus, we need n = m2 qubits to solve QAP.
3.2 HWP ansatz for Combinatorial Optimization
The QAP be seen as optimizing matrix X 10 with each row and each column having only one non-zero element. We can easily map the permutation matrix to the topology of the supereonducting qubits as illustrated in Fig. (b). The coupler denoted c; between two qubits stands for the allowance of two-qubit gates between the corresponding two qubits. It shows a commonly used topology [ B4 for superconducting quantum processors with each qubit connected to its four nearest neighbors through couplers. This kind of topology on the NISQ device can produce better connectivity than the nearest neighbor connectivity for logical qubits where each logical qubit is connected to only two nearest neighbors. Therefore, we aim to make full use of the qubit topology to provide an algorithm that is suitable for those existing superconducting quantum processors.
Notice that if we map each element in matrix X to qubit, we can easily adopt the HWP ansatz meet the constraints of QAP Each row and column of the qubits have exactly one [1) with the rest 10), which can be converted loss of generality, we apply m independent HWP ansatz on the row and we utilize a projective measurement the column ensure the most-measurement states feasible states for QAP. Here we will introduce how to use parity check circuit to implement the projective measurement with only one ancilla qubit for each column. Since each column has exactly one [1), sufficient and necessary condition for QAP is that the parity check results for all m columns are all odd.
HWP problem with dimension dg (T) Without
A detailed circuit for parity check is illustrated in Fig. (c.. HWP ansatz is applied each row of physical qubits and parity check is applied on each column. We repeat the NN connected HWP layers for L times and then apply parity check each ancilla qubit. After measuring the ancilla qubits, we flip the working qubits back and reset the ancilla qubits as (0). The whole block is repeated T times before measure all the working qubits and calculate the loss. For the working qubits, the initial state should be a trivial state in the QAP subspace that can be easily prepared such as the identity permutation with qubit qa [1) and the rest as (0). The overall parameterized evolution can be written in the following unitary transformation:
UQ
P [umwrr(0.)). ==1
II
(11)
where U UP is the unitary of the HWP layer with O., as the parameters in block / layer and P denotes the projective measurement by parity check. We utilize a cascade of CNOT gates to transfer the parity information from working qubits to the ancilla qubits, which will not further include SWAP gates in execution. Note that the parity check measurement the ancilla gubits will not destroy

---

Table 3: Results QAP simulation with the best in bold and the best in soft constraints underlined.
CONSTRAINT
METHOD
dém
3
4
5
me
3
Popeciml m
HEA 46
2"
0.7000
0.0000
0.1746
0,0000
QAOA 27
2"
0,4715
0.5491
0.2497
0,0000
XYMIXER-NN
39
0.5672
0.6927
0.1998
0.0999
SOPT
XYMIXER-FC
39
[W]
0.9957
0.4707
0.8738
0.1196
m
NBS-NN
0.7969
0.6046
0.5495
0,0500
NBS-FC
Lm/ 0.9975
0.4517
0.8765
0.0788
XYMIXER-HAME HARD
39
m!! 1,0000
0.9931
0.9837
0.9474
1.0000
0.8498
0.7500
0,3500
NBS HARD
md!
1,0000
0.9991
0.9919
0.9826
1.0000
0.9448
0.8500
0.5000
the in-constraint quantum states on the working qubits, so we are able to restrict the states without collapsing the whole quantum system. After measuring the ancilla qubits, we flip back all the working qubits and reset the ancilla qubits as [0).
The parity checks can provide certain entanglement on the topological columns of qubits. The quantum states on the working qubits before the first parity check is m independent pure states denoted as (1%)) with i E [0, m) on each row. The quantum state can be written as:
51 = =0) &0m
X ==
(ita) )
X 1=0
(0) 60m
(12)
where 5N is density matrix for block 1 before parity check. After the first parity check, the states on the working qubits are transformed from independent quantum states the rows to feasible states in the QAP subspace and other entangled states outside the subspace.
2
Σ 1=0
(1)
(13)
where P1 is the density matrix for block 1 after parity check, and (t) denotes the quantum states on the ancilla qubits. We can see that the measurement changes the basis ô, and Pt, resulting feasible states for QAP in Pl. Similarly, we denote the quantum state after the final parity check as
2
PT
Σ I=0
11) pr(
(14)
Since the quantum states on the working qubits are QAP subspace if and only if the ancilla qubits all measured as [1), the feasible final state the working qubits is pr (2 1). The loss is:
CQAP Tr HQAP (2 - -1)}
(15)
where HQAP is the Hamiltonian of QAP with definition in Eq. 10 We only update the parameters based on those in-constraint states that are able further find the optimal answer in the QAP subspace. The expectation value of obtaining pr(2m - -1) is
m!
(2
(16)
m
where (2m denotes the probability of obtaining Pr (2 1) from all the possible states. We can further derive the equation using the Stirling's formula and we have
V V2rm( m
V2rm
((P))(2"-1)) R2
(17)
m
e
The expectation of obtaining feasible states decreases exponentially with However, this order of the expectation value is acceptable as the Ising model for QAP requires n m2 qubits. We will further show in the experiments that generally have better probability of obtaining feasible states and this is much better than using soft constraints.
3.3 Simulated Experiments on Quadratic Assignment Problem
Dataset: We generated dataset comprising random instances of QAPs, with 100 instances for each size m {3, 4, 5, 6}. Each instance includes a X distance matrix D and flow matrix F.
7

---

with elements Dij D ja and F. Fii, drawn from a uniform distribution [0,1]. Diy = Ds (O, 1). Fúj F (0, 1),iz..
Baselines. HEA 146/: the most commonly used quantum machine learning model with a simple structure and only nearest neighbor connectivity is required; QAOA [27]: the originator of utilizing VQA to solve QUBO problem; XYmixer
139]: hard constraints and is proved to be an HWP gate with the Hamiltonian as Hxy o² @ at o & σ²
We apply soft constraints to the above baselines by adding a penalty term in the Hamiltonian with X as the permutation matrix from the final state:
m-- XX 1)
Crenalty Σ
Σ
Ex
Σ X. 1)
(18)
LQAP-soft (b) HQAP (1b) + x Cranelty:
(19)
where (15) is the final state and a is the penalty coefficient. Moreover, we adopt XYmixer as a HWP gate in the proposed hard constraint paradigm to see the performance between different HWP gates.
Evaluation Metric: To better illustrate the performance difference across methods, we utilize the approximation ratio as the evaluation metric, defined as:
Lmax LQAP
(20)
Lmaz Lmin
where Lmaz and Lmin denote the maximum and minimum loss for in-constraint states. For an infeasible state, the loss LQAP is equal to Lmaz, so the approximation ratio 7 = 0. For an in- constraint state, 17 is a value between 0 and 1, and it evaluates the overall performance. Apart from the approximation ratio, we also evaluate the methods based on the probability of obtaining the optimal solution denoted Poptimal. We utilize both metries to avoid the situation that we converge second-best solution which yields high ry and low Poptimal-
Hyperparameter Setting: In this section, we will discuss two crucial hyperparameters namely the penalty weight a for soft constraints and the number of parity checks T for hard constraints. We first analyze the number of parity checks required in model. This experiment is conducted with L x T remains to be a constant so that adding parity checks will not increase the number of parameters. From Fig. 5 we see that the probability of obtaining feasible states from the last parity check declines slowly, but the probability of obtaining an optimal solution requires a specific number of parity checks. Moreover, parity checks with excessively small intervals might cause the in-constraint states to be trapped at the initial state as the HWP layers in between two parity checks are not able to transfer the initial state other feasible states. Thus, set the number of parity checks T = 4 to balance the circuit depth and the quality of results. (Details analysis for penalty weight a for soft constraints are in Apx. F.2
The results are shown in Tab. 3 We provide the dimension of the space in which these approaches operate. When utilizing the soft constraints, HWP ansatz can reduce the dimension from 2 to (.)) However, when we use hard constraints, the dimension before the parity check is m and it further decreases to m! which is exactly the problem complexity of QAP. Considering the space of those methods, we are unable to provide results for baselines with soft constraints for 5 (25 qubits) and m (36 qubits).
Results on simulators:
All the results for soft constraints are conducted regardless of the physical qubit topology. HEA, XYmixer-NN, and NBS-NN satisfy the nearest neighbor topology while QAOA, XYmixer-FC, and NBS-FC require full connectivity of the qubits. We set the penalty a = 1 for all the soft constrained baselines based the analysis in Fig. 5 The results show that: (1) HWP ansatz with soft-constraints are generally better than QAOA and HEA; (2) the dimension of DLA of HWP ansatz matters to the results see Tab. 4 (3) FC leads to better exploration of the subspace and will lead to more out-of-constrainee states, which indicates lower 1) when a is set the same as NN.
While soft constraints often face difficulties in identifying optimal solutions at larger scales, hard constraints consis- tently demonstrate notable effectiveness and robustness. For the hard constrained methods, we show results with NN connectivity only since our method is qubit topology
Table 4: DLA dimension when n = m².
NBS
XYmixer
NN
FC
NN
FC
n add
(1)
4u(n
1) v is even
8

---

1.0 N6S-FC
1.0
0.5
0.4
0.2
Pn
On
Postimal
Pr.
Postinal
Metrics
Metrics
Figure 3: Results for QAP on quantum processor. The upper one is results on noiseless simulator as standard, the lower one is superconducting quantum processor, under the same parameter setting.
oriented. XYmixer can obtain a relatively high approximation ratio but with a rapid decrease the probability of obtaining the optimal solution as increases. The results verify the capability and efficiency of our hard constrained method as well as the expressivity of the proposed NBS gate.
3.4 QAP on Superconducting quantum processors
We further conduct the experiment with a superconducting quantum processor. The 12 qubits (see Fig. are chosen from a 66-qubit superconducting quantum processor. The processor has qubits lying on 2D lattice, and the qubits are capacitively coupled to their four nearest neighbors. Detailed information about this processor is listed in Sec D.2 None of the experiments on the quantum processor involve quantum eтror mitigation methods to post-process data. Considering the qubit quality and coupling strength, here we only conduct experiments for the case of 3 for QAP, as primary verification of the feasibility of executing the algorithm on quantum processors. Detailed hyperparameter setting see Apx. F.
Evaluation Metric: Apart from the approximation ratio and the probability of obtaining the optimal solution Poptimal used for the simulator, on the quantum processor. The first one is the approximation ratio for the in-constraint solution denoted as 7/n- Since all the infeasible solutions are counted approximation ratio. Thus, is very important to include the probability Pin of obtaining feasible solutions from all the output solutions as the second metric. Since the circuit error will greatly infect the solutions and will become very small, Tin can enlarge the difference when conducting experiments on the quantum processor.
introduce two more metries to analyze the performance
in y). 7ha can be seen the true
The numerical results on the quantum processor are illustrated in Fig. 3 Quantum noise greatly affects the results, although we only utilize twelve qubits. QAOA and HEA demonstrate better performance with very few parameters and shallow circuits. All the methods requiring full connectivity will include SWAP gates during compilation, which leads to worse performance on the quantum processor. Our method consistently outperforms other soft constrained methods over all the metrics and further enlarges the overhead when executed the quantum processor, except for HEA on Pin since HEA is extremely shallow and it may perform better on quantum processor some time. We believe the results will be much better if deeper circuits and more two-qubit gates are allowed. Notice that the parity checks on the columns are also able to correct the bit flip errors on the column. This may be another reason why we can achieve better performance with noise.
Results:
4 Conclusion and Limitations
In this paper, we first demonstrate the efficiency of HWP ansatz on ground state energy estimation problem and explain why HWP ansatz is perfect testbed for parity check. Results simulator with noise verify that parity check is a powerful error mitigation method for HWP ansatz. We then propose novel method to utilize parity check as projective measurement to enforce further hard constraints for HWP ansatz. Intensive experimental results on QAP on both simulator and superconducting quantum processor illustrate the superior performance against peer VQA methods relying soft constraints. To conclude, we provide detailed evidence this paper to show that the combination of HWP ansatz and parity check is among the most promising candidates to demonstrate quantum advantages the NISQ era to solve realistic problems.
Limitation and Future Work: We are aware that quantum algorithms might not exhibit any advantage (at least currently) under inevitable quantum noise and the extremely small problem size. However, believe this paper still break through the upper limit of existing constrained quantum

---

algorithms for CO. We will further study the performance of our methods on inequality constraints in future. At the moment, our work does not have any negative societal impacts.
5
Acknowledgement
The authors would like to express their gratitude to Zhiyuan College, Shanghai Jiao Tong University and Zhiyuan Future Scholar Program (Grants No. ZIRC2024-07).
References
[1] Mohamed Abdel-Basset, Gunasekaran Manogaran, Heba Rashad, and Abdel Nasser H Zaied. comprehensive review of quadratic assignment problem: variants, hybrids and applications. Journal of Ambient Intelligence and Humanized Computing, pages 1-24, 2018.
[2] Warren P Adams, Monique Guignard, Peter M Hahn, and William L Hightower. A level-2 reformulation- -iniulaattoo--nnezzzatttooo technique bound for the quadratic assignment problem. European Journal of Operational Research, (003))983--90 2007.
[3] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using programmable superconducting processor. Nature, 574(7779):505-53) 510, 2019.
[4] Mayowa Ayodele, Richard Allmendinger, Manuel López-lháñez, and Matthieu Parizy. Multi- objective qubo solver: Bi-objective quadratic assignment problem. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 467-475 2022.
[5] Rodney Bartlett, Stanislaw A Kucharski, and Jozef Noga. Alternative coupled-cluster ansätze ii the unitary coupled-cluster method. Chemical physics letters, 155(1):133-140, 1989.
[6] Nouédyn Baspin and Anirudh Krishna. Connectivity constrains quantum codes. Quantum, 6:711, 2022.
[7] Mokhtar S Bazaraa and Hanif D Sherali. On the of exact and heuristic cutting plane methods for the quadratic assignment problem. Journal of the Operational Research Society, 33(11):911-1003, 1982.
[8] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon. 290(2):405-421, 2021.
[9] Marcel Seelbach Benkner, Zorah Lähner, Vladislav Golyanik, Christof Wunderlich, Christian Theobalt, and Michael Moeller. Q-match: Iterative shape matching via quantum annealing. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7586-7596. 2021.
[10] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug. Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kottmann, Tim Menke, et al. Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics, 94(1):015004, 2022.
[11] Zhengbing Bian, Fabian Chudak, Robert Brian Israel, Brad Lackey, William Macready, and Aidan Roy. Mapping constrained optimization problems to quantum annealing with application fault diagnosis. Frontiers in ICT. page 14, 2016.
[12] Sergey Bravyi, Andrew W Cross, Jay M Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Na- ture, 67788005) 2024.
[13] Nikolas Breuckmann and Jens Niklas Eberhardt. Quantum low-density parity-check codes. PRX Quantum, 2(4):040101, 2021.
[14] Rainer E Burkard and Tilman Bönniger. A heuristic for quadratic boolean programs with applications to quadratic assignment problems. European Journal of Operational Research, 13(4):374-386, 1983.
10

---

[15] Rainer E Burkard and Eranda Çela. Heuristics for biquadratic assignment problems and their computational comparison. European Journal of Operational Research, 83(2):283-300, 1995.
[16] Robert Calderbank and Peter W Shor. Good quantum error-correcting codes exist. Physical Review A, 54(2):1098, 1996.
[17] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3(9):625 644, 2021.
[18) HA Chieza, MT Khumalo, K Prag, and M Woolway. On the computational performance of ibm quantum devices applied to combinatorial optimisation problems. In International Conference on Soft Computing & Machine Intelligence (ISCMI), pages 260-264. IEEE, 2020.
[19] Nicos Christofides and Enrique Benavent. exact algorithm for the quadratic assignment problem on tree. Operations Research, 37(5):760-768, 1989.
[20] Philippe Codognet. Encoding the at-most-one constraint for qubo and quantum annealing: Experiments with the n-queens problem. Proceedings of the Companion Conference on Genetic and Evolutionary Compulation, pages 2195-2202, 2023.
[21] Philippe Codognet, Daniel Diaz, and Salvador Abreu, Quantum and digital annealing for the quadratic assignment problem. In 2022 IEEE International Conference on Quantum Software (QSW), pages 1-8. IEEE, 2022.
[22] Sanjoy Dasgupta and Christos H Papadimitriou. Algorithms. 2006.
[23] D-Wave Developers, Measuring performance of the leap constrained quadratic model solver. Technical report, Tech. Rep. 14-1065A-A, D-Wave Systems Inc, 2022.
[24] The Qiskit Nature developers and contributors. Qiskit nature 0.7.2, 2023.
[25] Marco Dorigo. Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, 1992.
[26] Sara El Gaily and Sándor Imre. Constrained quantum optimization algorithm. In 2021 20th International Symposium INFOTEH-JAHIRINA (INFOTEH), pages 1-6. IEEE, 2021.
[27] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv: / 1.4028, 2014.
[28] Richard Phillips Feynman. Forces in molecules. Physical review, 56(4):340, 1939.
[29] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A AAtoomic, Molecular, and Optical Physics, 86(3):032324, 2012.
[30] Franz. G Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander J Stasik, and Giorgio Sartor. Constrained mixers for qaoa. arXiv preprint arXiv:2203.0609) 2022.
[31] Robert Gallager. Low-density parity-check codes. IRE Transactions on information theory. 8(1):21-28, 1962.
[32] Paul C Gilmore. Optimal and suboptimal algorithms for the quadratic assignment problem. Journal of the society for industrial and applied mathematics, 10(2)330-3333, 1962.
[33] Fred Glover. Heuristics for integer programming using surrogate constraints. Decision sciences, 8(1):156-166, 1977.
[34] Ming Gong, Shiyu Wang, Chen Zha, Ming-Cheng Chen, He-Liang Huang, Yulin Wu. Qingling Zhu, Youwei Zhao, Shaowei Li, Shaojun Guo, et al. Quantum walks on programmable two-dimensional 62-qubit superconducting processor. Science, 372(6545):948 952, 2021.
[35] Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. arXiv preprint
arXiv:1310.2984, 2013.

---

[36] Harper R Grimsley, Sophia E Economou, Edwin Barnes, and Nicholas J Mayball. An adap- tive variational algorithm for exact molecular simulations on a quantum computer. Nature communications, 10(1):3007, 2019.
[37] Shouzhen Gu, Eugene Tang, Libor Caha, Shin Ho Choe, Zhiyang He, and Aleksander Kubica. Single-shot decoding of good quantum ldpe codes. Communications in Mathematical Physics, 405 2024.
[38] Shaojun Guo, Jinzhao Sun, Haoran Qian, Ming Gong, Yukun Zhang, Fusheng Chen, Yangsen Ye, Yulin Wu, Sirui Cao, Kun Liu, al. Experimental quantum computational chemistry with optimised unitary coupled cluster ansatz. arXiv preprint arXiv: 2022.
[39] Stuart Hadfield, Zhihui Wang, Bryan O' O'gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2):34, 2019.
[40] Manabu Hagiwara and Hideki Imai. Quantum quasi-cyclic ldpe codes. In 2007 IEEE Interna- tional Symposium on Information Theory, pages 806-810. IEEE, 2007.
[41] Mohammad Haidar, Marko Rancic, Yvon Maday, and Jean- Piquemal. Extension of the trotterized unitary coupled cluster to triple excitations. The Journal of Physical Chemistry A, 127(15):3543-3555 2023.
[42] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky, and Marco Pistoia. Constrained optimization via quantum zeno dynamies. Communications Physics, 6(1):219, 2023.
[43] John H Holland. Genetic algorithms. Scientific american, 267(():6 1992.
[44] John Hubbard. Electron correlations in narrow energy bands. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 276(1365):238-257) 1963.
[45] Pascual Jordan and Eugene Paul Wigner. Über das paulische äquivalenzverbot. Springer, 1993.
[46] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Hardware- variational quantum eigensolver for small molecules and quantum magnets. nature, 549(7671):242 246. 2017.
[47] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. 2020.
[48] Maxine T Khumalo, Hazel A Chieza, Krupa Prag, and Matthew Woolway. An investigation of ibm quantum computing deviceperformance on combinatorial optimisation problems. arXiv preprins arXiv:2107.03663: 2021.
[49] Maxine T Khumalo, Hazel Chieza, Krupa Prag, and Matthew Woolway. An investigation of ibm quantum computing device performance on combinatorial optimisation problems. Neural Computing and Applications, pages 1-16, 2022.
[50] MT Khumalo, K Prag, and KJ Nixon. Evaluating the performance of the quantum approximate optimisation algorithm to solve the quadratic assignment problem. In 2022 9th International Conference on Soft Computing & Machine Intelligence (ISCMT), pages 86-90. IEEE, 2022.
[51] Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. Optimization by simulated annealing. science, 220(4598);671 16600 1983.
[52] Tjalling C Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, pages 53-76, 1957.
[53] Alexey Kovalev and Leonid P Pryadko. Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Physical Review A, 87(2):203044 2013." 2013.
12

---

[54] Michiya Kuramata, Ryota Katsuki, and Kazuhide Nakata. Larger sparse quadratic assignment problem optimization using quantum annealing and bit-flip heuristic algorithm. In 2021 IFEE 8th International Conference Industrial Engineering and Applications (ICIEA), pages 556-565. IEEE, 2021.
[55] Eliane Maria Loiola, Nair Maria Maia De Abreu, Paulo Oswaldo Boaventura- Peter Hahn, and Tania Querido. A survey for the quadratic assignment problem. European journal of operational research, 176(2):657-690 2007.
[56] David JC MacKay, Graeme Mitchison, and Paul L McFadden. Sparse-graph codes for quantum error correction. IEEE Transactions on Information Theory, 50(10):3315-2330, 2004.
[57] Bernard Mans, Thierry Mautor, and Catherine Roucairol. A parallel depth first search branch and bound algorithm for the quadratic assignment problem. European Journal of Operational Research, 117))617-628, 1995.
[58] Jarrod R McClean, Nicholas C Rubin, Kevin Sung, Ian D Kivlichan, Xavier Bonet-Monroig. Yudong Cao, Chengyu Dai, E Schuyler Fried, Craig Gidney, Brendan Gimby, al. Openfermion: the electronic structure package for quantum computers. Quantum Science and Technology. 5(3):034014, 2020.
[59] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. Quantum circuit learning. Phys. Rev. A, 98:032309, Sep 2018.
[60] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
[61] Pradeep Niroula, Ruslan Shaydulin, Romina Yalovetzky, Pierre Minssen, Dylan Herman, Shaohan Hu, and Marco Pistoia. Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer. Scientific Reports, 12(1):17171, 2022.
[62] Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM review, 33(1):60-100, 1991.
[63] Pavel Panteleev and Gleb Kalachev, Asymptotically good quantum and locally testable clas- sical ldpe codes. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 375-388, 2022.
[64] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O'brien. variational eigenvalue solver on a photonic quantum processor. Nature communications, 5(1):4213, 2014.
[65] John Preskill. Quantum computing in the nisq and beyond. Quantum, 2:79, 2018.
[66]
Viswanath Ramakrishna, Murti V Salapaka, Mohammed Dahleh, Herschel Rabitz, and Anthony Peirce Controllability of molecular systems. Physical Review A, (1():96,, 1995.
[67] Jonathan Romero, Ryan Babbush, Jarrod R McClean, Cornelius Hempel, Peter Love, and Alán Hapuru-Guzik, Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Science and Technology, 4(1):014008, 2018.
[68] Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM (JACM), 23(3)5555-555, 1976.
[69] Zain Saleem, Teague Tomesh, Bilal Tariq, and Martin Suchara. Approaches to constrained quantum approximate optimization. SN Computer Science, 1(2):183, 2023.
[70] Stasja Stanisic, Jan Lukas Bosse, Filippo Maria Gambetta, Raul A Santos, Wojciech Mruczkiewicz, Thomas E O'Brreen, Eric Ostby, and Ashley Montanaro. Observing ground-state properties of the Rerni-hubbard model using a scalable algorithm on quantum computer. Nature communications, 13(1):5743, 2022.
[71] Veit StooB, Martin Ulmke, and Felix Govaers. Adiabatic quantum computing for solving the weapon target assignment problem. In 202/ IEEE 24th International Conference on Information Fusion (FUSION), pages 1-6. IEEE, 2021.
13

---

[72] Eric Taillard. Robust taboo search for the quadratic assignment problem. Parallel computing. 47(4-5):443-455 1991.
[73] Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H Booth, al. The variational quantum eigensolver: a review methods and best practices. Physics Reports, 986:1-128, 2022.
[74] R. Wang, Yan, and X. Yang. Learning combinatorial embedding networks for deep graph matching. pages 3056-3065 2019.
[75] R. Wang, Zhang. Z. Guo, Chen, X. Yang, and J. Yan. insatnet: The positive linear satisfiability neural networks. 2013.
[76] Zhihui Wang. Nicholas C Rubin, Jason M Dominy, and Eleanor G Rieffel. X y mixers: Analytical and numerical results for the quantum alternating operator ansatz. Physical Review
A, 101(1):013300, 2020.
[77] Wenjie Wu, Yiquan Wang. Ge Yan, Yuming Zhao, Bo Zhang, and Junchi Yan. On reducing the execution latency of superconducting quantum processors via quantum program scheduling. In IEEE/ACM International Conference Computer-Aided Design, 2024.
[78] Ge Yan, Hongxu Chen, Kaisen Pan, and Junchi Yan. Rethinking the symmetry--reserrvng circuits for constrained variational quantum algorithms. In The Twelfth International Conference on Learning Representations, 2024.
[79] Junchi Yan, Shuang Yang, and Edwin Hancock. Learning graph matching and related combina- torial optimization problems. In IJCAI, 2020.
[80] Xinyu Ye, Ge Yan, and Junchi Yan. Towards quantum machine learning for constrained combinatorial optimization: a quantum qap solver. International Conference on Machine Learning, pages 39903-39912, 2023.
14

---

A Related Work
In this section, we first briefly review the related works of this paper. A typical way for quantum computers to solve the optimization problem is to transform the optimization problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem and then model the QUBO problem using the Ising model. The Ising model can be solved with variational quantum algorithms (VQAs) with QAOA 227 as the most famous one. However, this paradigm is natively designed to deal with constraints. Thus, we need to develop special strategies for constrained optimization problems to be solved on quantum computers.
Existing approaches tackle constraints either by adding soft constraints to the Hamiltonian 76 23 20) or hard constraints to the quantum circuit 39 30, 61]. Soft constraints are easy to realize but are hindered by the problem of balancing the objective and constraints [80]. which makes hard constraints better choice in general. However, hard constraints are quite hard to enforce on the quantum circuit since it is impossible to restrict the quantum state to a smaller subspace only by unitary transformations. Different from designing hard constrained ansatz from mining in all the gates, the very recent work (78) proposed pipeline to analyzing an HWP ansatz. However, they have not yet figured out a proper way to estimate the dimension of the Dynamic Lie Algebra (DLA) of different HWP gates.
QAP, one of the most significant NP-hard CO problems (68] is defined as finding a minimum cost allocation of facilities to locations, with the costs being the sum of all possible distance-flor products.
There have been only very few quantum algorithms for QAP due to the constraints. [71 49 4 21
focus on using soft constraints to solve QAP and [80] utilize QNN to learn from data oriented QAP with constraints enforced by classical Sinkhorn layer.
Finally we also briefly mention the develop in classic machine learning for solving combinatorial opti- mization X especially those with hard constraints, whereby the constrained are mostly incorporated by penalty term 47.. While some exceptions 77 75 design specific neural layers to accommodate the permutation constraint others. By contrast, in this paper, we focus on the quantum realm.
A.1 LDPC
Classical LDPC codes, first proposed by Gallager in 1962 31, are binary linear codes defined by a paritycheck matrix H. These codes have renewed interest due to their low bit error rates under fixed signal-to-noise ratios, particularly with the development of turbo codes and iterative decoding techniques. The defining properties of LDPC codes are: 1) Each row contains P ones. 2) Each column contains y ones. 3) The number of ones in common between any 2 columns, denoted X, is at most 1. 4) Both p and y are small relative the code length.
Quantum LDPC codes extend the principles of classical LDPC codes into the quantum domain, functioning as stabilizer codes where the stabilizer generators are low-weight operators, thus ensuring efficient error correction in quantum systems. Significant advancements in QLDPC codes began with the introduction of CSS codes [16), which utilized classical codes for quantum error correc- tion. MacKay et al. [56] pioneered sparse graph-based QLDPC codes, enhancing error correction efficiency. Hagiwara and Imai [40] developed quantum quasi-cyclie LDPC codes, which simplified encoding and decoding processes. Camera et al. Gottesman [35] demonstrated that QLDPC codes could significantly reduce the overhead required for fault-tolerant quantum computing. Recent advancements include work by Baspin and Krishna (6. who explored connectivity constraints and provided bounds on code distance and dimension. Panteleev and Kalachev (63) demonstrated the
existence of asymptotically good QLDPC codes by leveraging the lifted product construction over non-abelian groups. Additionally, Gu al. showed that quantum Tanner codes enable single-shot error correction, crucial for practical fault-tolerant quantum computing. LDPC codes are widely regarded as the most promising approach for realizing quantum error correction. However, there is currently no clear evidence of their application on real-world quantum ansatz [12
A.2 Constrained Quantum Optimization
Constrained Optimization is one of the most focused applications the quantum computing domain. For unconstrained optimization problems, quantum processors have established methods, typically involving the transformation of optimization problems into QUBO problems, subsequently reformu- lated as Ising models, and ultimately solved using Variational Quantum Algorithms. Thus, the key to
15

---

solving Constrained Optimization lies in handling constraints, which are divided into soft constraints that encode penalty terms into the Hamiltonian, and hard constraints that restrict the evolutionary space using quantum circuits.
Soft Constraints
The soft constraint method, currently the most commonly employed, incorporates penalty terms into the objective function, offering adaptability to a wide range of constraints and high versatility. However, the quality of the solution is highly sensitive to the balance between the objective and constraints [76). Under soft constraints, quantum circuits may return all infeasible and feasible solu- tions, with penalty terms ensuring a higher probability of feasible solutions appearing in the outcome. This approach requires the algorithm explore the entire B space, where 3" represents the binary string typically equivalent to the number of qubits. Compared to the feasible space of solutions, this represents significantly larger search domain, leading to decrease in the feasibility rate and search efficiency of solutions. There is extensive research on methods employing soft constraints. For instance, the Constrained Binary Model solver (CQM) developed by D- D-Wave[233] incorporates series of linear constraints and incquality constraints. [20) discusses various approaches to encoding constrained optimization and constraint satisfaction problems into QUBO issues, specifically targeting problems that involve at most one constraint, (26) utilizes the quantum phase estimation method, which enables the search for an item in a sorted or unsorted database. However, does not guarantee feasible solution. [1I] primarily addresses the constraints of quantum annealing hardware and proposes new algorithms for mapping Boolean constraint satisfaction problems onto quantum annealing hardware.
Hard Constraints
Hard constraints involve restricting quantum evolution within a in-constraint subspace, ensuring that all obtained solutions are feasible. constraints involve restricting quantum evolution within an in-constraint subspace, ensuring that all obtained solutions are feasible. However, most hard constraint methods are still only capable of solving specific and relatively simpler forms of problems. An example of this approach is the Quantum Alternting Operator Ansatz(QAOA-cc) proposed by [39]. This method is an extension of QAOA and allows for alternation between families of unitary operators with general parameteriizations. The challenge with QAOA-c lies in the complexity of implementing mixers and the necessity to introduce a large number of auxiliary qubits, leading to lack of universality. Under current hardware conditions, preparing uniform superposition of constrained states also presents a significant challenge. [300 Additionnal,, this approach suffers from limited flexibility in its application. Theree has been much research related QAOA-c. For instance, [6]] executed the Quantum Alternating Operator Ansatz algorithm on a trapped-ion quantum computer, utilizing Hamming-weighh wewpiingwwwiggh-peeeeeeeeeeee presehii-eeeeeiingggg Ximixer circuits to restrict quantum evolution to the in-constraint subspace. (69] proposed the dynamic quantum variational ansatz, which dynamically adapts to ensure maximum utilization of a fixed allocation of quantum resources.
constraint-presevvie
In addition to QAOA-c and its derivative algorithms, there are also works on other hard con- straint methods. For example, [78) analyzed the capability, expressivity, and trainability of Hamiltonian- weight preserving ansatz and verified these theoretical results on the unitary approxima- tion problem. 42 restricts quantum evolution to the constrained subspace through repeated projective measurements. However, this method has not been effectively validated on many quantum gates and particularly sensitive to the number of measurements.
A.3 Quadratic Assignment Problem
The Quadratic Assignment Problem (QAP) is defined as finding a minimum cost allocation of facilities to locations, with the costs being the sum of all possible fistance-flow products. The QAP one of the most significant combinatorial optimization problems, and has been proven to be Na-hard [68].
Classic Algorithms
The predominant methodologies for solving this encompass the exact, heuristic, and metaheuristic approaches. In the following sections, we will discuss these methodologies and present typical techniques within each category.
Obtaining exact solutions for QAP is extremely challenging, and current methodologies are only capable of achieving global optimal solutions for small-scale QAP instances. Existing approaches include cranch-and-bount cutting planes, combinations of these methods. The branch-and-
16

---

bound algorithm 57 2 commences with a cuuristic-derived initial feasible solution, setting the upper bound, and then segments the problem into ower-bounded sub-problems. The cutting planes m employs Mixed Integer Linear Programming formulations but is characterized by extended computational times. The branch-and-cut algorithm [62 amalgamates the aforementioned methodologies, offering an advantage over cutting planes as the cuts are associated with the polytope's facets, enabling swifter AenagennceA.diiioonnllyyy dynamic programming (55) is another method [9] for obtaining exact solutions, yet it is incapable of running in polynomial time.
Heuristic methods, although unable to guarantee optimal solutions, can yield reasonable solutions within a shorter time
heuristic methods have been proposed for addressing QAP. For instance, [32] introduced the constructive method. [14] applied enumerative methods, and improvement methods were utilized by [T5].
Metaheuristics represent a more universal paradigm, essential which are priori strategies adapted to the problem structure, Metaheuristics can be categorized into single-based solutions and population- based solutions. [ For instance, Simulated Annealing [51] is a type of single-based solution, while Genetic Algorithms [3 fall under population-based solutions. Other methods include Scatter
Search 3
and Ant Colony Optimization 25
Quantum Algorithms
Due to the complexity of QAP, there are currently few quantum solvers specifically designed for QAP. Most of the existing solvers predominantly employ the method of soft constraints. [49 50 utilize traditional soft constraint encoding, experiments were conducted on IBM's s quantum devices using the VQE and Quantum QAOA solvers, respectively, focuses on solving sparse Quadratic Assignment Problems (QAP), the approach involves transforming quadratic terms generated by penalty items into linear terms, followed by a post-processing step to derive feasible solutions. [80]presents the construction of a novel quantum neural network, whereby feasible solutions are obtained through classical post-processing. 4 focuses on extending the method to bi-objective QAP expressed the form of Quadratic Unconstrained Binary Optimization (QUBO), without altering the original soft constraints. [1 emmply quantum annealing to solve problems, similarly incorporating constraints as penalty terms. proposes approach of updating cycles substitute for constraints in QAP. However, the energy calculation for cycles is only feasible for certain specialized versions of QAP, such the three-dimensional shape correspondence problems highlighted in the paper.
B Preliminaries
We will first introduce one of the most common type of symmetry-pressrving ansatz, namely the HWP ansatz, and basic ideas of parity check in the quantum circuits. Then we will provide details about quantum computing and machine learning.
B.1 Hamming Weight Preserving Ansatz
Now we give brief review of the Hamming Weight Preserving ansatz. The HWP ansatz aims to solve fundamental physical symmetry which is the number of spin-ups in the quantum states. For n-qubit quantum system with the number of [1)s in the quantum states is k; we say that this problem
in an HWP subspace with the dimension of the subspace as de = (i). The work (78) provides detailed definition of the HWP ansatz as well as thorough analysis of the expressivity, capability, and trainability of the ansatz.
For two-qubit HWP situation, all four basis states {/00) 101), , [10), [1)} have three Hamming weights: 1, and 2. Thus, two-qubit HWP gate should only operate basis states (01) and (10).
The general form of the two-qubit HWP gates is:
0
0
0
0
H HW
(21)
0
0
where a, c E R, be E C, and b denotes the conjugate of H is a Hermitian matrix that satisfies
H'w How Taking the Hermitian matrices of the allowed gates as generators, we have a set of generators g {H p= we can define the Dynamical Lie Algebra (DLA):
g spon (iH, iH
.iHP) Lie
(22)
17

---

where Lie denotes the Lie closure. We then repeatedly take the commutators of the elements in the generator set. For N -ddimensional quantum system, we have the following important theorem [66].
Theorem B.1. [66] A necessary and sufficient condition for complete controllability of N-
dimensional quantum system H is that the dimension of the DLA is N where N is the dimension of quantum system.
B.2 Quantum Chemistry
We provide the definition of annihilation operator and creation operator in second quantization. Definition B.2.
aj - :
af =
(23)
where aj denotes the annihilation operator on qubit j and a! denotes the creation operator on qubit i.
B.3 Quantum Computing
In quantum computing, "qubit' (abbreviation of "quantum bit') is key concept which is similar to a classical bit with binary state. The two possible states for qubit are the state (0) and {1), which correspond to the state 0 and for classical bit respectively. We refer the readers to the textbook [60] for comprehension of quantum information and quantum computing. Here we give brief introduction to the background.
quantum state is commonly denoted in bracket notation. is also common to form a linear combination of states, which call superposition: (ल) = a/0) 3]1). Formally, quantum system on qubits is an n-fold tensor product Hilbert space 7 = (C2)ed with dimension 24, For any (Φ)) E H. the conjugate transpose (1-l = | The inner product (ell)) = || denotes the square of the 2-norm of v. The outer product (&) (vil rank tensor. Computational basis states are given by 10) (1,0), and [1} = (0, 1). The composite basis states are defined by e.g.
(01) = (0) @ 11 (0, 0).
B.4 Quantum Machine Learning
17 proposed the concept of Variational Quantum Algorithms (VQA), which leverages quantum advantages solve machine learning problems near-term quantum device. Then, Parameterized Quantum Circuits (PQC) are the concrete implementation of certain VQA. For each qubit we have rotation operator Rx ()) which rotate through angle O (radias) around the r-axis. A PQC is mainly composed of (o) Ry(@) and R2(0) with A as the parameters. The parameters O are updated by a classical optimizer minimize the loss function L(0) which evaluates the dissimilarity between the output of PQC and the target result. The derivative of the i-th parameter ( can be computed by using the shifting technique proposed by (59]. It requires running the whole circuit twice but with shifting (1) to ((t) + π T/2 and O(i) x/2
ac(0)
1 x (R(((1)).. ,(() T "C. +.
O0(1) 2
=((0)) ,()) -
(24)
C Proof of Theorem 2.3
We first restate the theorem:
Theorem. An ansatz U()) can solve the ground state energy estimation problem without truncation if the ansatz is universal under the dg di-ddimesional HWP subspace.
Proof. Firstly, the ground state energy estimation problem has the physical symmetry that the number of total spins and total particles will not change during the evolution. So the final state will have exactly the same number of [])s as the initial state (usually the Hatree-Fock state). Thus, the ground state energy estimation problem can be solved within a HWP subspace with the dimension as dy (.).
18

---

902
C12
412
613
422
G14
a2
401
411
421
11
400
C8
410
Q20
62
ag
Figure Selected qubits on the superconducting quantum processor
Secondly, an ansatz U(0) is universal if and only if the reachable unitary matrices from arbitrary parameters satisfies:
{U(O)} SU((k),
(25)
where {U())}e denotes the reachable unitary matrices from arbitrary parameters 0 and (dx) denotes the super unitary group with dimension as dg. Thus, we can approximate any unitary matrix within the HWP subspace with arbitrary precision by optimizing the parameters in the universal ansatz.
Back to the ground state energy estimation problem. Since we are finding the optimal eigenstate with the smallest eigenvalue, we can take this problem as state preparation problem. If have universal ansatz in HWP subspace, then we can reach arbitrary state in the HWP subspace with any legit initial state. Therefore, we conclude that the ansatz U() can solve the ground state energy estimation problem without truncation if the ansatz is universal under the d: di-dimensional HWP subspace.
L
D Implementation Detail
All the numerical simulations are performed on a machine with 190GB memory, one physical CPU with 32 cores AMD Ryzen Threadripper 3970X CPU, and GPUs (Nvidia GeForce RTX 3090). We implement a Python quantum simulator so that we are able to simulate quantum system for our method with up to 42 qubits (m with ancilla qubits). Implementation details are shown in Appendix D. The results on the quantum processor are conducted on superconducting quantum processor with detailed information shown Appendix D.2
D.1 Implementation Detail for the Classical Simulator
self-built simulator Since the quantum circuit of the proposed hard constrained method is executed in the m dimensional subspace, we utilize a implementation trick to reduce the dimension of the simulation. For traditional quantum simulator based quantum states, the space need to store a quantum state is 2mxm, However, we can utilize a mapping function to map the corresponding state the n dimensional vector. For each two-qubit gates the row, the gate is operating m dimensional quantum state, which indicates the gate is a m x m unitary operator. Therefore. the time complexity of applying quantum gate on the state is O(m 11-1pp -mm)). which is much faster than (2 Moreover, to simulate the projective measurement, we simulate the results on the shot basis, enabling us simulate the in-circuit measurement.
D.2 Implementation Detail for Superconducting Quantum Processor
In the experiment, we utilized 12-qubit Superconducting Quantum Processor with an intercoupled topology as shown the Fig. 4 Tab. presents the performance information regarding Single-Qubit Operations, while Tab, presents the fidelity of the controlled-Z gate between two qubits.
19

---

Qubit
900
Q01
Q02
910
Q11
Q12
Q20
921
q22
00
41
02
w/2T(GHz)
4.8661
4.6814
4.6302
4.9031
4.7910
4.7097
4.8504
4.9323
4.8387
4.709
4.5704
4.7247
T((s))
26.298
33.374
28.819
28.239
20.626
36,092
21.695
24.781
28.757
31.169
37.170
31.313
T2 (us)
2.8271
2.6789
2.2952
5.8565
2.9713
3.1998
3.8482
4.8506
1.873
4,459
1.6298
1.1544
Fo
0.9414
0.9222
0,9168
0.9242
0.9268
0,9478
0.9400
0.9206
0,9592
0.9364
0,9604
0,9240
Fi
0.8732
0.8022
0.8690
0.8062
0.7378
0.8686
0.8430
0.8166
0.8484
0.703
0.8404
0.8276
Fo
0.9990
0.9993
0,9992
0.9993
0.9992
0.9994
0.9991
0.9993
0.9989
0.9993
0.9987
0,9989
Table 5: Performance of Single-Qubll Operations. w is the working frequency. Coherence times T1 and 72" representing the energy relaxation time and dephasing time. The term Fo (Fi) represents the readout fidelity, specifically denoting the probability of accurately measuring the qubit state in (0) (11)) after it has been successfully initialized in the (0) ((1)) state. Fg denotes the gate fidelity of native gates.
Qubit
40o
901
402
9110
911
912
Q/20
921
422
g00
0.9839
0.9827
0.9798
0.9806
0.9778
402
0.9806
0.9798
Q10
0.9827
0.9868
0,9867
0.9778
0.9868
0.9852
0.9840
Q12
0.9798
0.9852
0,9873
Q20
0.9867
0.9880
0,9822
421
0.9840
0,9880
0.9783
Q22
0.9873
0.9791
0,9822
0.9783
0g
0.9791
Table 6: The controlled-7 gate fidelity between qubit pairs, which is symmetric along the main diagonal due to the undirected nature qubit coupling.
E Further Experimental Results for Parity Check as Error Mitigation
E.1 Hyperparameter Setting
Here we provide the noise levels we used in the experiments. We set the depolarizing error for single qubit 1.6 10 and for two-qubit gates 6.4 x 10-3 3, The bit-flip and phase- flise-flip error for each gate are set as 5 x 10-3, 33 We also set a x 10-2 readout error for obtaining [1] given (0), and x 10-2 vise versa. To simulate the computing way on quantum computers, we set the number of shots per Pauli string in the measurement stage at 5000, which makes at least 500,000 shots in total for LiH and H2O since they all have more than 100 Pauli strings.
E.2 Sensitivity Analysis the Number of Parity Checks
Now we discuss the impact of the number of parity check layers. It is clear that more parity checks can reduce the probability of errors but it also brings more CNOT gates which can also hinder the results. Thus, it is crucial to seek equilibrium in the number of parity checks in the NISQ era. From the results in Tab. 7 we conclude that applying parity check for every HWP gates can achieve the best performance. Thus, we insert 2 parity check blocks for H2 and 10 blocks for LiH and H2O. We omit the analysis on H2 since the ansatz is very shallow for Hg. Consider that we have 63 HWP gates in the 8-qubit ansatz, we set the number of parity checks 6, 8, 10, 12, 15, which is parity check per 10, 6, 5, gates respectively. The results illustrate that parity check for every 6 HWP gates can have the best performance considering the additional CNOT gates brought in by parity checks.
E.3 Ansatz statistics
Detailed statistical information for both UCC ansatze and the proposed HWP ansatz in Tab. g We provide the number of gates, number of CNOT gates and the number of parameters to show the
20

---

energy
PC=6
PC= 8
PC=10
PC=12
PC=15
LiH
0.657022752 0.748342082
0.661989975 0.72675715
16609112113
0.65741316 0.743041427
0.675546743
H₂O
0.688285861
0.745211306
Table 7: Sensitivity analysis on the number of parity checks for the proposed HWP ansatz. The best results are bold.
H2 UCCSD
LiH UCCSD
H₂O
UCCS
ours
UCCS
ours
UCCS
UCCSD
UCCSDT
ours
num_gates
32
107
108
1067
441
144
2002
5871
441
num CNTT
8
48
732
189
1376
4304
189
num_ hamp_arams
2
12
6
15
63
15
26
34
63
Table Statistics for UCC and proposed HWP ansatze.
10
08-
5.3
0.6
0.6
0.6
0.4
0.2
0.2
0.
0.0
32 0.0
0.0
10
10"
6
10
12
14
2
8
10
12
Figure 5: From left to Right. (a) and (b) Sensitivity study penalty weight a: (a) XYmixe--NN
with m 3: (b) XYmixer-FC with m 4. (c) and (d) Sensitivity study on the number parity
checks T. (c) NBS-NN with m 5; (d) NBS-NN with = 6.
difference between the baseline methods and ours. It is shown that the proposed HWP ansatz can achieve precise energy results with much shallower circuit than UCCSD and UCCSDT.
F Further Experimental Results for Parity Check as Further Constraints
F1 Hyperparameter Setting
QAP simulator:
The layer of XYmixer-FC. NBS-FC, HEA, and QAOA XYmixer-NN, NBS-NN, Xymixer-hard, and NBS-hard have the same number of parameters as NBS-FC. Learning rate is set to 0.05 and the number of iterations is 1000.
2 x and
QAP on Superconducting Quantum Processors: Due to limited coherence time and noise, the parameter setting is a bit different from that the simulator. We only able to apply one layer of NBS-FC considering the number CNOTs, so rest of the methods are set with the same amount of parameters one layer of NBS-FC. As QAOA has parameter-sharinn strategy, set its number we set T = 2. Each circuit is measured with 20K shots.
of layers as 2. For
F.2 Sensitivity Analysis for QAP
The penalty weight is very sensitive and may vary significantly with different models and different problem sizes. We set = as a constant based on the sensitivity results on XYmixer since impossible to fine-tune a for each instance. As illustrated in Fig. the approximation ratio y achieves a peak at a = 1 (figures for other scenarios are listed in Fig. 6p. We provide as the approximation ratio for all states, 7)x the approximation ratio for feasible states, and Pin. the probability of obtaining feasible states. We observe that smaller a leads to a better in-constraint approximation ratio but relatively small in-constraint probability. large a leads to high Pin- yet it results in convergence to a random in-constrain state due to the dominance of the penalty term.
F.3 Simulated Experiments on TSP
Reduction to QAP: The complexity of QAP lies in its inclusion of dual relationships, namely the interrelations between locations and the interactions between facilities. When the dual relationship is
21

---

3.0
08
3.
2.
22
12
Figure 6: Sensitivity study on penalty weight a. From left to right. (a) XYmixer-FC with m 3. (b) XYmixer-FC with m 4. (c) XYmixer-NN with m 3. (d) QAOA with = 3.
Table 9: Results on the simulator for TSP with the best in bold and the best results by soft constraints underlined.
CONSTRAINT
METHOD
172
771
m
5
710
3
772 =
Poptinal
m
HEA
0.7885
0.0009
0.6500
0.0000
QAOA
2
0.7242
0.6686
0.4996
0.1996
XYMIXER-NN
19
0.6857
0.7355
0.5497
0.3995
SOFT
XYMIXER-FC
39
1.0000
0.7096
1.0000
0.4531
NBS-NN
0. 0.9975
0.8042
0.9492
0.3495
NBS-FC
1.0000
0.5834
1.0000
0.1815
YYMIXER
1.0000
0.9991
0.9920
0.9670
0.9500
0.8500
0.6500
HARD
NBS-NN
1.0000
1.0000
0.9933
0.9698
1.0000
1,0000
0.9000
0.7500
simplified singular relationship, the problem evolves from a complex assignment decision singular sequence or path problem, which the quest for Hamiltonian cycle with minimal cost, degenerating QAP into the Traveling Salesman Problem (TSP) formulated as:
min E Σ
(26)
R.P
where @ 1 () mod m. Therefore, TSP can be considered as special case QAP under specific simplified assumptions, enabling to utilize QAP solvers directly for deriving solutions to TSP problems.
Similar to the QAP dataset, we generate dataset of random TSP instances, with 100 instances for each size m (3, 4, 5, 6). For each TSP instance, we included a m x m distance matrix D, which was constructed using randomly generated real points (72).
Dataset:
Results on Simulator: The results in Tab. demonstrate similar pattern those of QAP. Notice that the TSP problem can be solved by dynamic programming with the algorithm complexity as (n2222) 22 it is theoretically simpler problem than QAP. This explains why all the methods perform better on TSP. The results further verify the capability and efficiency of the proposed hard constrained method.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We have elaborated on the main claims in Sec. 1
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 be expected to generalize other settings.
much the results
is fine to 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:
We mentioned limitations of our work in 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]
23

---

The paper provides a thorough presentation of theoretical results in section 2.2 including the full set of assumptions and complete proofs for each result.
Justification:
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 or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
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 of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We mentioned our hyperparameter settings in section and section 3
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 NeurIPS 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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to 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?
24

---

reproducible, they Answer: [Yes]
Justification:
We will make our code available after the publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
public/guidess http///ooaaamaiiiiooooooo.ooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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 for more details.
/ //nip. http::ccpplllligguiieeee wttp/uddee//Coeubmmi seriissssonpoiiiio
The authors should provide instructions on data access and preparation, including how to 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 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 as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is 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: [Yes]
The paper provides comprehensive details about the experimental setup, including the training and test data splits, the choice of hyperparameters. Additionally, full details are provided in the Appendix
Justification:
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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the standard deviation in Table. For each noiseless case, We run 10 times with different seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
25

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
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 errors 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 of range (e.g. negative emrr 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 reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We mentioned the compute resources in 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
Answer: [Yes]
Justification: Yes, our research conforms to the NeurIPS Code of Ethics.
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 circumstances 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:
We discuss positive and negative societal impacts in Sec.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
26

---

The conference expects that many papers will be foundational research and not tied 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 an improvement in the quality of generative models could be used to 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 to 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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:
Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses 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 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 not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or 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?
Answer: [NA]
Justification:
We do not use the existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thcode. com 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 it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We introduce the assets about QAP problem, and the corresponding details are demonstrated in Sec.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll 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: Our paper does not involve crowdsourcing nor research with human subjects.
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 as much detail as possible should be included in 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: Our paper does not involve crowdsourcing nor research with human subjects.
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.
28


Reviews:
[{"review_id": "zBbJY4MeiR", "reviewer": "Reviewer_K5Kf", "summary": "The paper investigates combining the HW-preserving ansatz with qubit topology-aware parity checks to impose hard constraints on quantum circuits for the quantum chemistry and Quadratic Assignment Problem. It includes numerical simulations and experiments on a real quantum device.", "questions": "1. as definition of NBS is kind of constant gate, how to train the HWP anstaz constructed by such fixed gates shown in Fig 1.  ? and what is the R in Figure 1 ?\n2. comparing to the proposed HWP, the UCCS not only requires shallow circuit but also have out-performance. What is the advantages of the proposed over it? \n3. it may be poor scalable of such ansatz used for combinatorial optimization problem, especially in NISQ era. and in line 252, the probability of finding the feasible state will exponentially small with the problem size $m$, how to extract such feasible state without performing exponentially measurement?", "limitations": "no potential negative societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "sufficient numerical and real device experiments.", "weaknesses": "comparing to previous work \"Rethinking the symmetry-preserving circuits for constrained variational quantum algorithms\",  it is difficult to gauge its novelty and impact as the main contribution is incremental with respect to previous results no matter in theoretical or numerical aspects.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and valuable feedback, including the comparison of previous work [1]. We would like to highlight the differences between these two papers and promise to add a remark in the related work section to distinguish them.\n\nIn [1], the authors proposed methods to analyze the expressivity and trainability of the HWP ansatz. They also proposed BS gate to conduct experiments with the Hamiltonian as:\n$$\nH_{BS}=\\left(\\begin{array}{cccc}\n        0 & 0 & 0 & 0\\\\\\\\\n        0 & \\frac{1}{2} & \\frac{1+\\text{i}}{2\\sqrt{2}} & 0\\\\\\\\\n        0 & \\frac{1-\\text{i}}{2\\sqrt{2}} & \\frac{1}{2}& 0\\\\\\\\\n        0 & 0 & 0 & 0\n    \\end{array}\\right),\\quad H_{NBS}=\\left(\\begin{array}{cccc}\n        0 & 0 & 0 & 0\\\\\\\\\n        0 & \\frac{1}{2} & \\frac{\\text{i}}{2} & 0\\\\\\\\\n        0 & \\frac{-\\text{i}}{2} & \\frac{1}{2}& 0\\\\\\\\\n        0 & 0 & 0 & 0\n    \\end{array}\\right).\n$$\nIn this paper, we integrate parity checks and the HWP ansatz to enforce additional constraints and mitigate hardware errors. **We focus on the practical usage of parity checks in near-term quantum computing**, which involves utilizing some good qualities of the HWP ansatz. We have the following distinguishing contributions:\n1. We proposed a simpler gate, namely the NBS gate, with compatible expressivity as the BS gate.\n2. We developed a viable method to incorporate parity checks for error mitigation in the HWP ansatz, conducting experiments on both superconducting quantum processors and simulators.\n3. We proposed a novel approach to use parity checks as projective measurements, thereby restricting the evolving subspace of quantum states. We demonstrated the effectiveness of our method on an NP-hard combinatorial optimization problem. This paradigm holds significant potential for constrained VQE, offering a straightforward means to incorporate hard constraints using simple parity checks.\n\nTherefore, we disagree that \"the main contribution is incremental to previous results\". According to your review, we think that our work is something more than \"For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.\" We also strongly believe that good incremental work (if you insist) is also within the scope of NeurIPS. \n\n[1] Rethinking the symmetry-preserving circuits for constrained variational quantum algorithms\n\nWe will then respond to your questions:\n> Q1: as definition of NBS is kind of constant gate, how to train the HWP anstaz constructed by such fixed gates shown in Fig 1. ? and what is the R in Figure 1 ?\n\nAns: Thanks for your kind reminder, and we apologize for the misunderstanding caused by our negligence. The matrix provided in the paper is the Hermitian matrix of the NBS gate. The unitary operator of the NBS gate should take exponential of the Hermitian matrix:\n$$U_{NBS}=e^{\\text{i}\\theta H_{NBS}}=\\left(\\begin{array}{cccc}\n        1 & 0 & 0 & 0\\\\\\\\\n        0 & \\frac{\\cos\\theta+\\text{i}\\sin\\theta+1}{2} & \\text{i}\\frac{\\cos\\theta+\\text{i}\\sin\\theta-1}{2} & 0\\\\\\\\\n        0 & -\\text{i}\\frac{\\cos\\theta+\\text{i}\\sin\\theta-1}{2} & \\frac{\\cos\\theta+\\text{i}\\sin\\theta+1}{2} & 0\\\\\\\\\n        0 & 0 & 0 & 1\n    \\end{array}\\right)=\\left(\\begin{array}{cccc}\n        1 & 0 & 0 & 0\\\\\\\\\n        0 & \\frac{e^{\\text{i}\\theta}+1}{2} & \\text{i}\\frac{e^{\\text{i}\\theta}-1}{2} & 0\\\\\\\\\n        0 & -\\text{i}\\frac{e^{\\text{i}\\theta}-1}{2} & \\frac{e^{\\text{i}\\theta}+1}{2} & 0\\\\\\\\\n        0 & 0 & 0 & 1\n    \\end{array}\\right),$$\n    \nwhich contains trainable parameters. The rotations at the end of the ansatz in Fig.1 are for measuring different decomposed Pauli strings of the problem Hamiltonian. They can be omitted from the ansatz for simplicity. \n\n> Q2: comparing to the proposed HWP, the UCCS not only requires shallow circuit but also have out-performance. What is the advantages of the proposed over it?\n\nAns: The UCCS ansatz is indeed very shallow, which leads to the \"out-performance\" on NISQ devices. However, it exhibits relatively weak performance compared to other methods, failing to achieve results within chemical accuracy ($1.6\\times 10^{-3}$Ha) for any of the molecules tested. It is essential to consider performance not only during the NISQ era but also beyond. Additionally, other methods can also achieve superior results if similar numbers of layers or parameters are utilized.\n\n> Q3: it may be poor scalable of such ansatz used for combinatorial optimization problem, especially in NISQ era. and in line 252, the probability of finding the feasible state will exponentially small with the problem size, how to extract such feasible state without performing exponentially measurement?\n\nAns: This one is actually a very good question and we do acknowledge that this might be a potential limitation of the proposed method (as stated in the paper). However, we would like to point out that for an $n$-qubit system, the number of shots we need to obtain the final distribution is $\\mathcal{O}(2^n)$, which is why the order of the expectation value remains acceptable. Despite this, the proposed method potentially stands as the best constrained-VQE currently available.", "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": "LxNUzpUfwC", "reviewer": "Reviewer_6BLB", "summary": "Paper introduces a Hamming Weight Preserving ansatz with parity check. The proposed method is tested on quantum chemistry problems and constrained combinatorial optimization problems (eg. quadratic assignment problem). The HWP ansatz can satisfy the hard constraints in QAP. Experiments show that proposed methods outperforms some existing methods for the simulation and superconducting quantum processor.", "questions": "Would quantum chemistry ground-state experiment be possible to perform on superconducting processor, and how would methods perform relatively with the quantum noise? \n\nNBS-NN and NBS-FC (if nearest neighbor vs fully connected qubits), these are also commonly abbreviations for Neural network and fully connected (layers). Could authors further describe difference between NBS-NN and NBS-FC? and their difference with NBS-hard?", "limitations": "A stated limitation is different results on superconducting processor vs. simulator, based on noise of superconducting processor. Additional stated limitations are related to state of quantum computing such as small problem size and quantum noise.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Paper addresses a significant problem of simulation on quantum circuits and applications to quantum chemistry and combinatorial problems. Originality: Paper proposes a novel ansatz using HWP and parity checks, although I am not too familiar with previous work. The quality and clarity of presentation is good, and experiment results are clear.", "weaknesses": "A potential weakness may be less background information included in main text of paper, especially for the target audience (ML/neurips).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the time and effort you have invested in evaluating our paper, and we hope we can clarify your concerns.\n\n> W1: A potential weakness may be less background information included in main text of paper, especially for the target audience (ML/neurips).\n\nAns: Thanks for your kind advice. We do realize this paper may not be familiar to the general NeurIPS community. We promise to provide a detailed background intro in the revision appendix.\n\n> Q1: Would quantum chemistry ground-state experiment be possible to perform on superconducting processor, and how would methods perform relatively with the quantum noise?\n\nAns: Ground state preparation is considered one of the most promising problems to demonstrate experimental advantages on recent superconducting processors [1], as evidenced by various preliminary attempts [2, 3, 4]. However, inevitable noise severely affects the performance of current ansätze, prompting the search for new ansätze that are better suited for error mitigation and error correction methods.\n\n> Q2: NBS-NN and NBS-FC (if nearest neighbor vs fully connected qubits), these are also commonly abbreviations for Neural network and fully connected (layers). Could authors further describe difference between NBS-NN and NBS-FC? and their difference with NBS-hard?\n\nAns: We apologize for any confusion caused by the abbreviations. The terms NBS-NN and NBS-FC refer to nearest-neighbor and fully connected physical qubit connectivity, respectively. On a superconducting quantum processor, physical qubits rely on couplers to achieve entanglement, meaning two-qubit gates can only be applied to qubits directly connected by a coupler. Given the impracticality of connecting each pair of qubits with a coupler, it is not feasible to apply two-qubit gates freely to any pair. Therefore, fully connected (FC) connectivity represents an idealized scenario, whereas studying nearest-neighbor (NN) connectivity is crucial in the Noisy Intermediate-Scale Quantum (NISQ) era, given the current hardware limitations.\n\nIn Table 3, NBS-hard denotes the use of parity checks as additional constraints. The simple HWP ansatz can only maintain symmetry along either rows or columns, necessitating extra methods to impose constraints in the other direction. Consequently, NBS-NN and NBS-FC in the soft section of Table 3 represent NBS with corresponding connectivity, where penalties in the Hamiltonian act as constraints. NBS-hard refers to NBS-NN with parity checks as a hard constraint for the other direction.\n\n\n\n[1] The Variational Quantum Eigensolver: A review of methods and best practices. Physics Reports\n\n[2] Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature\n\n[3] Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer. Nature Communications\n\n[4] Experimental quantum computational chemistry with optimized unitary coupled cluster ansatz. Nature Physics", "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": "TJ9UXrraEA", "reviewer": "Reviewer_kL3u", "summary": "This paper designs a novel quantum algorithm that eliminates the need for penalty terms when solving constrained problems. Instead, it constructs a subspace where the states satisfy the constraints, allowing the final solution to be constructed within this subspace. Additionally, the authors use parity check to replace system validation, ensuring that qubits remain unflipped at every step, not just in the final state, thereby enhancing error correction capabilities. The authors demonstrate how this algorithm works on a class of NP-complete combinatorial optimization problems and achieve better results than previous quantum algorithms.", "questions": "See the comments.", "limitations": "yes.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "**Originality:** The authors propose a quantum machine learning algorithm capable of solving constrained optimization problems without relying on penalty terms.\n\n**Clarity:** The paper clearly defines quantum computing concepts, provides detailed derivations of the main equations involved, and offers a very clear explanation of the quantum system's architecture. The discussion of experimental results is also very thorough.\n\n**Significance:** The quantum algorithm presented in this paper naturally incorporates constraint conditions into the optimization process. Compared to soft constraints, this approach yields more accurate results. This has significant implications for integrating machine learning into quantum computing, offering valuable insights.\n\n**Quality:** The language of the paper is rigorous and clear, with appropriate citations of previous work. The overall approach is straightforward and easy to understand. The paper provides a multi-faceted analysis of the experimental results, validating the algorithm's correctness on simulators and conducting experiments on real quantum computers, further demonstrating feasibility. The theoretical section is also excellent, with detailed derivations of the main equations. The paper excels in both theory and experiment.", "weaknesses": "The discussion of the scalability of the proposed algorithm is not sufficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review and valuable feedback. We greatly appreciate the time and effort you have invested in evaluating our manuscript. Your insights and suggestions have been instrumental in improving the quality of our work. We are aware that the scalability of the quantum algorithm has attracted considerable interest, and we will provide more detailed derivation and discussion as an extension to Equation 17 in the revision.", "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:

Meta-review: The submission proposes combining the HW-preserving ansatz with qubit topology-aware parity checks to impose hard constraints directly on quantum circuits, which was difficult for implementing important applications in quantum chemistry and optimization (e.g., the Quadratic Assignment problem).  It includes both numerical simulations and experiments on a real quantum device, which further validates the proposed approach. All reviewers acknowledged the authors’ contributions. However, it is suggested that authors should articulate their contributions, especially compared with a few existing references with similar titles.
Decision: Accept (poster)