Rethinking Parity Check Enhanced Symmetry-Preserving Ansatz

Authors: ge  yan
mengfei  ran
ruocheng  wang
kaiseng  pan
junchi  yan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 12:07:28

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.

Main paper: 
 introduction: 
 Variational Quantum Algorithms (VQAs) [17, 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, 10] and the improved deployment capability [77] , the exploration of new VQAs has accelerated, as these algorithms have shown promise in delivering quantum advantage on near-term quantum devices [17] . 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 not be the most efficient approach. Addressing the natural incorporation of symmetries and hard constraints directly into VQAs remains an open and critical challenge for advancing the field.In this paper, we investigate Hamming Weight preserving (HWP) ansatz [78] and parity check [53] as a 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, 13] and surface code [29] have been widely widely adopted in quantum error correction through the use of stabilizers to detect and correct qubit errors. However, a significant challenge remains in identifying quantum ansatze that naturally facilitate error correction mechanisms. In response, we propose a 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 measurements, quantum states can be 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 is 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-zero 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] , XYmixer [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, 70] .3) We propose a novel hard-constraint VQA with parity check as further constraints for HWP. We map the permutation matrix in 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.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. 1Guidelines:• 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
parity check as error mitigation for hwp: 
 We first illustrate how to use 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.The ground state energy estimation problem, which is the very first step in computing the energetic properties of molecules and materials, has received intensive attention with various VQE approaches [73] . The ground state of a 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 H m , and a trial wave function |ψ⟩, the ground state energy E 0 is bounded by [28] :EQUATIONwhere the equality holds if and only if the parameterized wavefunction |ψ⟩ is the ground state. To solve this problem on a quantum computer, we need to design the ansatz wavefunction, which is 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⟩ n (abbreviated as |0⟩) with n as the number of orbitals under the Jordan-Wigner transformation [45] . Notice that any quantum state is necessarily a normalized wavefunction, so the cost function of the VQE problem is [73] :EQUATIONThe 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 an error mitigation method.We first introduce two basic models, namely the Fermi-Hubbard model [44] and Unitary Coupled Cluster model (UCC) [64] , to show how HWP ansatz can be linked to quantum chemistry. Recall the hopping term on adjacent sites i and j in the Fermi-Hubbard model is defined as:EQUATIONwhere a and a † 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 † i a j . For the state transformation for UCC model, we follow the form |ψ⟩ = e T -T † |ψ 0 ⟩ [5] , where T -T † 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 isEQUATIONBoth of the above Hamiltonian fits the definition of HWP (see Eq. 21 in Apx.B for the introduction of the preliminaries of HWP), so they are both HWP operators. Lemma 2.2. The hopping terms in UCC and Fermi-Hubbard are not universal in the HWP subspace.According to Theorem B.1 [66] (see details in Apx. B), an HWP operator with a given connectivity is universal if and only if the dimension of the corresponding dynamical lie algebra (DLA) isd 2 k with d k = n k ,where n and k 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:dim nn (g U CC ) = 1 2 n(n -1), dim nn (g F H ) =    (n + 1)(n -1) n is odd 1 2 n(n -1) n is even (5)For fully connected (FC) connectivity, the dimensions of DLA for the two operators are:EQUATIONAll of the dimensions do not meet the requirement of d 2 k , so both Eq. 5 and Eq. 6 are not universal in the HWP subspace, which aligns with the fact that Eq. 3 and Eq. 4 are truncated hopping terms.Theorem 2.3. An ansatz U(θ) can solve the ground state energy estimation problem without truncation if the ansatz is universal under the d k -dimensional HWP subspace.The detailed proof is provided in Apx. C. In contrast to 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 to 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:EQUATION)NBS gate is very close to universal under NN connectivity and simpler than the one proposed in [78] . Thus, we can use the NBS gate to construct an NN connected ansatz without any truncation (UCCSD [67] ) or prior knowledge about quantum chemistry (adaptVQE [36] ).A common error mitigation technique in VQE for the UCC and Hubbard model is SV [70, 38] , 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 propose utilizing parity checks, a 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 it directly into the circuit, as illustrated in Fig. 1 . The molecular Hamiltonian is obtained from the Python package OpenFermion [58] . The computational basis for all the molecules is STO-3G with Jordan-Wigner transformation. To simulate the circuit with noise on Qiskit, we utilize the Aer-simulator from Qiskit based on the density matrix which is time-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. 1Baselines: 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 as 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 3 Parity Check as Further Constraints for QAP Apart from the quantum chemistry problems, the HWP ansatz is 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.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. 4.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
quadratic assignment problem: 
 The Quadratic Assignment Problem (QAP) is a well-studied NP-hard problem dated back to [52] .A typical QAP instance of size m is given by two matrices F ∈ R m×m , D ∈ R m×m , defining the flows between facilities and the distances between locations [55] . Its objective with constraints is:EQUATIONwhere X ∈ {0, 1} m×m 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 ∈ R m 2 ×m 2 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:EQUATIONwhere vec(X) ∈ {0, 1} m 2 ×1 denotes a vector by concatenating the columns of matrix X [79] . We can further derive the Hamiltonian of the Ising form of QAP: 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 m = 3, we select n = m 2 working qubits denoted as q ij and m ancilla qubits denoted as a i with the structure shown on the right. Each qubit q ij maps to the element X ij in the permutation matrix and suffice the constraints that each row and column has only one |1⟩.EQUATION)𝑞 !! 𝑞 !" 𝑞 !# 𝑞 "! 𝑞 "" 𝑞 "# 𝑞 #! 𝑞 #" 𝑞 ## 𝑎 ! 𝑎 " 𝑎 # B S(c) The overall circuit for QAP with all the working and ancilla qubits is named the same as in (b).whereH QAP ∈ R 2 n ×2 n, and σ z is the pauli-z matrix. Thus, we need n = m 2 qubits to solve QAP.The QAP can be seen as optimizing a matrix X ∈ {0, 1} m×m with each row and each column having only one non-zero element. We can easily map the permutation matrix to the topology of the superconducting qubits as illustrated in Fig. 2(b ). The coupler denoted as c i between two qubits stands for the allowance of two-qubit gates between the corresponding two qubits. It shows a commonly used topology [3, 34] 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 a qubit, we can easily adopt the HWP ansatz to meet the constraints of QAP. Each row and column of the qubits have exactly one |1⟩ with the rest as |0⟩, which can be converted to an HWP problem with dimension as d k = m 1 . Without loss of generality, we apply m independent HWP ansatz on the row and we utilize a projective measurement on the column to ensure the post-measurement states are 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⟩, a sufficient and necessary condition for QAP is that the parity check results for all m columns are all odd.A detailed circuit for parity check is illustrated in Fig. 2(c ). HWP ansatz is applied on 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 a parity check on 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 we 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 q ii as |1⟩ and the rest as |0⟩. The overall parameterized evolution can be written in the following unitary transformation:EQUATIONwhere U HW P is the unitary of the HWP layer with θ t,l as the parameters in block t layer l, 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 on the ancilla qubits will not destroy 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 |ψ i ⟩ with i ∈ [0, m) on each row. The quantum state can be written as:EQUATIONwhere δ 1 is a density matrix for block 1 before parity check. After the first parity check, the states on the working qubits are transformed from m independent quantum states on the rows to feasible states in the QAP subspace and other entangled states outside the subspace.EQUATIONwhere ρ 1 is the density matrix for block 1 after parity check, and |i⟩ denotes the quantum states on the ancilla qubits. We can see that the measurement changes the basis of δ 1 and ρ 1 , resulting feasible states for QAP in ρ 1 . Similarly, we denote the quantum state after the final parity check asEQUATION)Since the quantum states on the working qubits are in QAP subspace if and only if the ancilla qubits are all measured as |1⟩, the feasible final state on the working qubits is ρ T (2 m -1). The loss is:EQUATIONwhere H QAP is the Hamiltonian of QAP with definition in Eq. 10. We only update the parameters based on those in-constraint states so that we are able to further find the optimal answer in the QAP subspace. The expectation value of obtaining ρEQUATIONwhere p ρ T (2 m -1) denotes the probability of obtaining ρ T (2 m -1) from all the possible states. We can further derive the equation using the Stirling's formula and we haveEQUATION)The expectation of obtaining feasible states decreases exponentially with m. However, this order of the expectation value is acceptable as the Ising model for QAP requires n = m 2 qubits. We will further show in the experiments that we generally have a better probability of obtaining feasible states and this is much better than using soft constraints.Dataset: We generated a dataset comprising random instances of QAPs, with 100 instances for each size m = {3, 4, 5, 6}. Each instance includes a m × m distance matrix D and a flow matrix F,with elements D ij = D ji and F ij = F ji , drawn from a uniform distribution [0, 1]. D ij = D ji ∼ U (0, 1), F ij = F ji ∼ U (0, 1), i ̸ = j.Baselines. HEA [46] : 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 [39] : hard constraints and is proved to be an HWP gate with the Hamiltonian asH XY = σ x ⊗ σ x + σ y ⊗ σ y .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:EQUATIONEQUATION)where |ψ⟩ is the final state and α 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:EQUATIONwhere L max and L min denote the maximum and minimum loss for in-constraint states. For an infeasible state, the loss L QAP is equal to L max , so the approximation ratio η = 0. For an inconstraint state, η 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 as p optimal . We utilize both metrics to avoid the situation that we converge to a second-best solution which yields high η and low p optimal .Hyperparameter Setting: In this section, we will discuss two crucial hyperparameters namely the penalty weight α for soft constraints and the number of parity checks T for hard constraints. We first analyze the number of parity checks required in our model. This experiment is conducted with L × T remains to be a constant so that adding parity checks will not increase the number of parameters. From Fig. 5 , we can 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 to other feasible states. Thus, we set the number of parity checks T = 4 to balance the circuit depth and the quality of results. (Details analysis for penalty weight α for soft constraints are in Apx. F.2)Results on simulators: 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 n to n m . However, when we use hard constraints, the dimension before the parity check is m 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 m = 5 (25 qubits) and m = 6 (36 qubits).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 α = 1 for all the soft constrained baselines based on 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-constrained states, which indicates lower η when α is set the same as NN. 2 n m 2 n 2 -1 n is odd 1 2 n(n -1) n is even n m 2 -1While soft constraints often face difficulties in identifying optimal solutions at larger scales, hard constraints consistently demonstrate notable effectiveness and robustness.For the hard constrained methods, we show results with NN connectivity only since our method is qubit topology The upper one is results on noiseless simulator as a standard, the lower one is on superconducting quantum processor, under the same parameter setting. oriented. XYmixer can obtain a relatively high approximation ratio but with a rapid decrease in the probability of obtaining the optimal solution as m increases. The results verify the capability and efficiency of our hard constrained method as well as the expressivity of the proposed NBS gate.We further conduct the experiment with a superconducting quantum processor. The 12 qubits (see Fig. 4 ) are chosen from a 66-qubit superconducting quantum processor. The processor has qubits lying on a 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 error mitigation methods to post-process data. Considering the qubit quality and coupling strength, here we only conduct experiments for the case of m = 3 for QAP, as a primary verification of the feasibility of executing the algorithm on quantum processors. Detailed hyperparameter setting see Apx. F.1Evaluation Metric: Apart from the approximation ratio η and the probability of obtaining the optimal solution p optimal used for the simulator, we introduce two more metrics to analyze the performance on the quantum processor. The first one is the approximation ratio for the in-constraint solution denoted as η in . Since all the infeasible solutions are counted as 0 in η, η in can be seen as the true approximation ratio. Thus, it is very important to include the probability p in 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, η in can enlarge the difference when conducting experiments on the quantum processor.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 on the quantum processor, except for HEA on p in 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [Yes] Justification: We will make our code available after the publication. Guidelines: • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or 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 a 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 error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
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 a perfect testbed for parity check. Results on simulator with noise verify that parity check is a powerful error mitigation method for HWP ansatz. We then propose a 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 on soft constraints. To conclude, we provide detailed evidence in this paper to show that the combination of HWP ansatz and parity check is among the most promising candidates to demonstrate quantum advantages in 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, we believe this paper still break through the upper limit of existing constrained quantum 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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 the positive and negative societal impacts in Sec. 4.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer:[NA] Justification: Our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: 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 [27] as the most famous one. However, this paradigm is not 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 a 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 a 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, as 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-flow 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 are enforced by classical Sinkhorn layer.Finally we also briefly mention the develop in classic machine learning for solving combinatorial optimization [8] , especially those with hard constraints, whereby the constrained are mostly incorporated by penalty term [47] . While some exceptions [74, 75] design specific neural layers to accommodate the permutation constraint or others. By contrast, in this paper, we focus on the quantum realm.Classical LDPC codes, first proposed by Gallager in 1962 [31] , are binary linear codes defined by a paritycheck matrix H. These codes have seen 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 ρ ones. 2) Each column contains γ ones.3) The number of ones in common between any 2 columns, denoted λ, is at most 1. 4) Both ρ and γ are small relative to 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 correction. MacKay et al. [56] pioneered sparse graph-based QLDPC codes, enhancing error correction efficiency. Hagiwara and Imai [40] developed quantum quasi-cyclic 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 et al. [37] 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] .Constrained Optimization is one of the most focused applications in the quantum computing domain.For unconstrained optimization problems, quantum processors have established methods, typically involving the transformation of optimization problems into QUBO problems, subsequently reformulated as Ising models, and ultimately solved using Variational Quantum Algorithms. Thus, the key to 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.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 solutions, with penalty terms ensuring a higher probability of feasible solutions appearing in the outcome. This approach requires the algorithm to explore the entire B n space, where B n represents the binary string typically equivalent to the number of qubits. Compared to the feasible space of solutions, this represents a significantly larger search domain, leading to a 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-Wave [23] incorporates a series of linear constraints and inequality 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, it does not guarantee a feasible solution. [11] primarily addresses the constraints of quantum annealing hardware and proposes new algorithms for mapping Boolean constraint satisfaction problems onto quantum annealing hardware.Hard constraints involve restricting quantum evolution within a in-constraint subspace, ensuring that all obtained solutions are feasible.Hard 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 Alternating Operator Ansatz(QAOA-c) proposed by [39] . This method is an extension of QAOA and allows for alternation between families of unitary operators with general parameterizations. The challenge with QAOA-c lies in the complexity of implementing constraint-preserving mixers and the necessity to introduce a large number of auxiliary qubits, leading to a lack of universality. Under current hardware conditions, preparing a uniform superposition of constrained states also presents a significant challenge. [30] Additionally, this approach suffers from limited flexibility in its application.There has been much research related to QAOA-c. For instance, [61] executed the Quantum Alternating Operator Ansatz algorithm on a trapped-ion quantum computer, utilizing Hamming-weight-preserving XYmixer 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.In addition to QAOA-c and its derivative algorithms, there are also works on other hard constraint methods. For example, [78] analyzed the capability, expressivity, and trainability of Hamiltonian-weight preserving ansatz and verified these theoretical results on the unitary approximation 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 is particularly sensitive to the number of measurements.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 distance-flow products. The QAP is one of the most significant combinatorial optimization problems, and it has been proven to be NP-hard [68] .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 branch-and-bound, cutting planes, or combinations of these methods. The branch-and-bound algorithm [57, 2] commences with a heuristic-derived initial feasible solution, setting the upper bound, and then segments the problem into lower-bounded sub-problems. [1] The cutting planes method [7] 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 convergence.Additionally, dynamic programming [55] is another method [19] 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 frame.Numerous 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 [15] .Metaheuristics represent a more universal paradigm, essential to which are a priori strategies adapted to the problem structure. Metaheuristics can be categorized into single-based solutions and populationbased solutions. [1] For instance, Simulated Annealing [51] is a type of single-based solution, while Genetic Algorithms [43] fall under population-based solutions. Other methods include Scatter Search [33] and Ant Colony Optimization [25] .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 quantum devices using the VQE and Quantum QAOA solvers, respectively. [54] 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 in the form of Quadratic Unconstrained Binary Optimization (QUBO), without altering the original soft constraints. [71, 21] employ quantum annealing to solve problems, similarly incorporating constraints as penalty terms. [9] proposes an approach of updating cycles as a substitute for constraints in QAP. However, the energy calculation for cycles is only feasible for certain specialized versions of QAP, such as the three-dimensional shape correspondence problems highlighted in the paper.We will first introduce one of the most common type of symmetry-preserving 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.Now we give a brief review of the Hamming Weight Preserving ansatz. The HWP ansatz aims to solve a fundamental physical symmetry which is the number of spin-ups in the quantum states. For a n-qubit quantum system with the number of |1⟩s in the quantum states is k, we say that this problem is in an HWP subspace with the dimension of the subspace as d k = n k . The work [78] provides a detailed definition of the HWP ansatz as well as a thorough analysis of the expressivity, capability, and trainability of the ansatz.For two-qubit HWP situation, all four basis states {|00⟩ , |01⟩ , |10⟩ , |11⟩} have three Hamming weights: 0, 1, and 2. Thus, a two-qubit HWP gate should only operate on basis states |01⟩ and |10⟩. The general form of the two-qubit HWP gates is:EQUATIONwhere a, c ∈ R, b ∈ C, and b denotes the conjugate of b. H HW is a Hermitian matrix that satisfies H † HW = H HW . Taking the Hermitian matrices of the allowed gates as generators, we have a set of generators G = {H p } P p=1 , we can define the Dynamical Lie Algebra (DLA):EQUATIONwhere ⟨•⟩ Lie denotes the Lie closure. We then repeatedly take the commutators of the elements in the generator set. For a N -dimensional quantum system, we have the following important theorem [66] . Theorem B.1.[66] A necessary and sufficient condition for complete controllability of a Ndimensional quantum system Ĥ is that the dimension of the DLA g is N 2 where N is the dimension of quantum system.We provide the definition of annihilation operator and creation operator in second quantization. Definition B.2.EQUATION)where a j denotes the annihilation operator on qubit j and a † i denotes the creation operator on qubit i.In quantum computing, 'qubit' (abbreviation of 'quantum bit') is a key concept which is similar to a classical bit with a binary state. The two possible states for a qubit are the state |0⟩ and |1⟩, which correspond to the state 0 and 1 for a classical bit respectively. We refer the readers to the textbook [60] for comprehension of quantum information and quantum computing. Here we give a brief introduction to the background.A quantum state is commonly denoted in bracket notation. It is also common to form a linear combination of states, which we call a superposition: |ψ⟩ = α|0⟩ + β|1⟩. Formally, a quantum system on n qubits is an n-fold tensor product Hilbert space H = (C 2 ) ⊗d with dimension 2 d . For any |ψ⟩ ∈ H, the conjugate transpose ⟨ψ| = |ψ⟩ † . The inner product ⟨ψ|ψ⟩ = ||ψ|| 2 2 denotes the square of the 2-norm of ψ. The outer product |ψ⟩⟨ψ| is a rank 2 tensor. Computational basis states are given by |0⟩ = (1, 0), and |1⟩ = (0, 1). The composite basis states are defined by e.g. |01⟩ = |0⟩ ⊗ |1⟩ = (0, 1, 0, 0).[17] proposed the concept of Variational Quantum Algorithms (VQA), which leverages quantum advantages to solve machine learning problems on a 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 θ (radias) around the x-axis. A PQC is mainly composed of Rx(θ), Ry(θ) and Rz(θ) with θ as the parameters. The parameters θ are updated by a classical optimizer to minimize the loss function L(θ) which evaluates the dissimilarity between the output of PQC and the target result. The derivative of the i-th parameter θ(i) can be computed by using the shifting technique proposed by [59] . It requires running the whole circuit twice but with shifting θ(i) to θ(i) + π/2 and θ(iEQUATIONC Proof of Theorem 2.3We 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 d k -dimensional 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 |1⟩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 asd k = n k .𝑞 EQUATIONwhere {U(θ)} θ denotes the reachable unitary matrices from arbitrary parameters θ and SU(d k ) denotes the super unitary group with dimension as d k . 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 a state preparation problem. If we have a 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 k -dimensional HWP subspace.All the numerical simulations are performed on a machine with 190GB memory, one physical CPU with 32 cores AMD Ryzen Threadripper 3970X CPU, and 5 GPUs (Nvidia GeForce RTX 3090). We implement a Python quantum simulator so that we are able to simulate a quantum system for our method with up to 42 qubits (m = 6 with ancilla qubits). Implementation details are shown in Appendix D.1. The results on the quantum processor are conducted on a superconducting quantum processor with detailed information shown in Appendix D.2.self-built simulator Since the quantum circuit of the proposed hard constrained method is executed in the m m dimensional subspace, we utilize a implementation trick to reduce the dimension of the simulation. For a traditional quantum simulator based on quantum states, the space we need to store a quantum state is 2 m×m . However, we can utilize a mapping function to map the corresponding state to the m m dimensional vector. For each two-qubit gates on the row, the gate is operating on a m * 1 dimensional quantum state, which indicates the gate is a m × m unitary operator. Therefore, the time complexity of applying a quantum gate on the state is O(m m-1 m 2 ), which is much faster than O(2 m×m ). Moreover, to simulate the projective measurement, we simulate the results on the shot basis, enabling us to simulate the in-circuit measurement.In the experiment, we utilized a 12-qubit Superconducting Quantum Processor with an intercoupled topology as shown in the Fig. 4 .Tab. 5 presents the performance information regarding Single-Qubit Operations, while Tab. 6 presents the fidelity of the controlled-Z gate between two qubits. QAP on Superconducting Quantum Processors: Due to limited coherence time and noise, the parameter setting is a bit different from that on the simulator. We are only able to apply one layer of NBS-FC considering the number of CNOTs, so the rest of the methods are set with the same amount of parameters as one layer of NBS-FC. As QAOA has a parameter-sharing strategy, we set its number of layers as 2. For NBS-Hard, we set T = 2. Each circuit is measured with 20K shots.The penalty weight is very sensitive and may vary significantly with different models and different problem sizes. We set α = 1 as a constant based on the sensitivity results on XYmixer since it is impossible to fine-tune α for each instance. As illustrated in Fig. 5 , the approximation ratio η achieves a peak at α = 1 (figures for other scenarios are listed in Fig. 6 ). We provide η as the approximation ratio for all states, η in as the approximation ratio for feasible states, and p in as the probability of obtaining feasible states. We observe that smaller α leads to a better in-constraint approximation ratio but a relatively small in-constraint probability. A large α leads to a high p in , yet it results in convergence to a random in-constrain state due to the dominance of the penalty term.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 simplified to a singular relationship, the problem evolves from a complex assignment decision to a singular sequence or path problem, which is the quest for a Hamiltonian cycle with minimal cost, degenerating QAP into the Traveling Salesman Problem (TSP) formulated as:EQUATIONwhere i ⊕ 1 = (i + 1) mod m. Therefore, TSP can be considered as a special case of QAP under specific simplified assumptions, enabling us to utilize QAP solvers directly for deriving solutions to TSP problems.Dataset: Similar to the QAP dataset, we generate a dataset of random TSP instances, with 100 instances for each size m = {3, 4, 5, 6}. For each TSP instance, we included a m × m distance matrix D, which was constructed using randomly generated real points [72] .The results in Tab. 9 demonstrate a similar pattern as those of QAP. Notice that the TSP problem can be solved by dynamic programming with the algorithm complexity as O(n 2 2 n ) [22] , it is theoretically a 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.NeurIPS Paper ChecklistJustification: 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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 ?
2. 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? 
3. 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: limitations: no potential negative societal impact of their work.
paper_summary: paper_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.
strength_weakness: strength_weakness: A potential weakness may be less background information included in main text of paper, especially for the target audience (ML/neurips).
questions: questions: Would quantum chemistry ground-state experiment be possible to perform on superconducting processor, and how would methods perform relatively with the quantum noise? 

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?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: The discussion of the scalability of the proposed algorithm is not sufficient.
questions: questions: See the comments.
limitations: limitations: yes.

Comments: comment: Thanks.
We are sincerely grateful for your careful reading and thoughtful comments on our manuscript, which have been invaluable in enhancing the clarity and rigor of our work. Thank you again for your time and effort in reviewing our paper.

Best regards
Thank you for the response, most of my question are solved. I would happy to raise my score.
Dear AC:

Thanks for your efforts and the profound suggestions from the reviewers. Since half of the discussion time has passed, we wonder whether the reviewers' concerns have been resolved by our reply and whether they have further questions.
Dear reviewer K5Kf,

We really appreciate your valuable comments. In our rebuttal, we have highlighted the contributions and answered the questions accordingly. Since the discussion period is approaching its end, we are looking forward to your feedback.

Best regards,

Authors