This paper concerns quantum heuristics based on Mixer Hamiltonians that allow to restrict investigation on a specific subspace. Mixer Hamiltonian based approaches can be included in QAOA algorithm and we can state that Mixer Hamiltonians are mapping functions from the set of qubit-strings to the set of solutions. Mixer Hamiltonian offers an approach very similar to indirect representations commonly used in routing or in scheduling community for decades. After the initial publication of Cheng et al. in 1996 (Cheng et al., 1996), numerous propositions in OR lies on 1-to-n mapping functions, including the split algorithm that transform one TSP solution into a VRP solution. The objective is at first to give a compact and readable presentation of these Mixer Hamiltonians considering the functional analogies that exist between the OR community practices and the quantum field. Our experiments encompass numerical evaluations of circuit using the Qiskit library of IBM meeting the theoretical considerations.
This paper concerns quantum heuristics based on Mixer Hamiltonians that allow to restrict investigation on a specific subspace. Mixer Hamiltonian based approaches can be included in QAOA algorithm and we can state that Mixer Hamiltonians are mapping functions from the set of qubit-strings to the set of solutions. Mixer Hamiltonian offers an approach very similar to indirect representations commonly used in routing or in scheduling community for decades. After the initial publication of Cheng et al. in 1996 (Cheng et al., 1996), numerous propositions in OR lies on 1-to-n mapping functions, including the split algorithm that transform one TSP solution into a VRP solution. The objective is at first to give a compact and readable presentation of these Mixer Hamiltonians considering the functional analogies that exist between the OR community practices and the quantum field. Our experiments encompass numerical evaluations of circuit using the Qiskit library of IBM meeting the theoretical considerations.
This paper investigates quantum heuristics based on Mixer Hamiltonians, which allow the search to be restricted to a specific subspace and enable warm-start strategies for solving the Traveling Salesman Problem (TSP). Approaches involving Mixer Hamiltonians can be integrated into the Quantum Approximate Optimization Algorithm (QAOA), where the Mixer acts as a mapping function that transforms qubit strings into feasible solution sets. We first introduce a swap-based mixer tailored to the TSP, which ensures that only qubit strings representing valid TSP solutions are explored during the QAOA process. Second, we propose a warm-start technique that initializes QAOA with a solution generated by any classical heuristic, thereby promoting faster convergence. These two contributions are combined into a Warm-Start QAOA framework with a Swap-Based Mixer, leveraging both structural and initialization advantages. Experimental results on a custom TSP instance involving five customers demonstrate the effectiveness of this approach, providing, for the first time, a viable integration of warm-start and swap-based mixers for the TSP within a quantum optimization framework.
Constructing effective mixer Hamiltonians is essential for enhancing the performance of the Quantum Approximate Optimization Algorithm (QAOA) in solving combinatorial optimization problems. In this work, we develop a systematic methodology for designing QAOA mixers that align with the symmetries of the classical objective function, with the goal of achieving values (mean, median, and minimum over multiple runs) that are closer to the true optimum. Our main idea is to design QAOA operators that are explicitly adapted to the action of symmetry groups on the Hilbert space. We focus on subgroups of the symmetric group$ S_{d},where d = 2^\ell,toensurecompatibilitywithqudit−basedquantumarchitectures.Inparticular,weconstructQAOAmixersinvariantunderthefullsymmetricgroup S_{d}aswellasitscyclicsubgroup \mathbb {Z}_{d} \subset S_{d}.TheseconstructionsarenaturalinthattheyrespectthedecompositionoftheHilbertspaceintoisotypiccomponentsunderthesymmetrygroupaction.Notably,tothebestofourknowledge,theQAOAalgorithmbasedonthe \mathbb {Z}_{d}−invariantmixerprovidesthefirstexampleofaQAOAprotocolwhosedynamics(uptofinalmeasurement)areconfinedentirelywithinanontrivialirreduciblerepresentationofasymmetrygroupoftheobjectivefunction.Althoughourworkdoesnotinvestigatethebenefitsofexploitingsuchsubspacesascomputationalresources,wethinkthattheveryrealizationofavariationalalgorithmwhoseevolutionisrestrictedtoanontrivialsymmetry−adaptedsubspaceisoffundamentalconceptualinterest.Weprovideclosed−formexpressionsforthesemixers,togetherwithexplicitquantumcircuitimplementations.Toempiricallyevaluateourapproach,wecompareQAOAvariantsemployingthestandardmixerB = \sum X_{i}withthoseusingourproposedHamiltoniansH_{M}andH_\chi$on edge coloring and graph partitioning problems. Across multiple graph instances, our symmetry-adapted mixers consistently yield objective values closer to the optimum, demonstrating statistically significant improvements over classical baselines.
Quantum optimization algorithms, such as the Quantum Approximate Optimization Algorithm, are emerging as promising heuristics for solving complex combinatorial problems. To improve performance, several extensions to the standard QAOA framework have been proposed in recent years. Two notable directions include: warm-starting techniques, which incorporate classical approximate solutions to guide the quantum evolution, and custom mixer Hamiltonians, such as XY mixers, which constrain the search to feasible subspaces aligned with the structure of the problem. In this work, we propose an approach that integrates these two strategies: a warm-start initialization with an XY mixer ansatz, enabling constraint-preserving quantum evolution biased toward high-quality classical solutions. The method begins by reformulating the combinatorial problem as a MaxCut instance, solved approximately using the Goemans-Williamson algorithm. The resulting binary solution is relaxed and used to construct a biased superposition over valid one-hot quantum states, maintaining compatibility with the XY mixer's constraints. We evaluate the approach on 5-city instances of the Traveling Salesperson Problem, a canonical optimization problem frequently encountered as a subroutine in real-world Vehicle Routing Problems. Our method is benchmarked against both the standard XY-mixer QAOA and a warm-start-only variant based on MaxCut relaxation. Results show that the proposed combination consistently outperforms both baselines in terms of the percentage and rank of optimal solutions, demonstrating the effectiveness of combining structured initializations with constraint-aware quantum evolution for optimization problems.
Constructing an optimal mixer for Quantum Approximate Optimization Algorithm (QAOA) Hamiltonian is crucial for enhancing the performance of QAOA in solving combinatorial optimization problems. We present a systematic methodology for constructing the QAOA tailored mixer Hamiltonian, ensuring alignment with the inherent symmetries of classical optimization problem objectives. The key to our approach is to identify an operator that commutes with the action of the group of symmetries on the QAOA underlying Hilbert space and meets the essential technical criteria for effective mixer Hamiltonian functionality. We offer a construction method specifically tailored to the symmetric group Sd, prevalent in a variety of combinatorial optimization problems. By rigorously validating the required properties, providing a concrete formula and corresponding quantum circuit for implementation, we establish the viability of the proposed mixer Hamiltonian. Furthermore, we demonstrate that the classical mixer B commutes only with a subgroup of Sd of significantly smaller order than the group itself, enhancing the efficiency of the proposed approach. To evaluate the effectiveness of our methodology, we compare two QAOA variants utilizing different mixer Hamiltonians: conventional B=∑Xi and the newly proposed HM in edge coloring and graph partitioning problems across various graphs. We observe statistically significant differences in mean values, with the new variant consistently demonstrating superior performance across multiple independent simulations. Additionally, we analyze the phenomenon of poor performance in alternative warm-start QAOA variants, providing a conceptual explanation supported by recent literature findings.
The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems. It consists of interleaved unitary transformations induced by two operators labelled the mixing and problem Hamiltonians. To fit this framework, one needs to transform the original problem into a suitable form and embed it into these two Hamiltonians. In this paper, for the well-known NP-hard Traveling Salesman Problem (TSP), we encode its constraints into the mixing Hamiltonian rather than the conventional approach of adding penalty terms to the problem Hamiltonian. Moreover, we map edges (routes) connecting each pair of cities to qubits, which decreases the search space significantly in comparison to other approaches. As a result, our method can achieve a higher probability for the shortest round-trip route with only half the number of qubits consumed compared to IBM Q’s approach. We argue the formalization approach presented in this paper would lead to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to NP optimization problems.
Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA-QAOA+. Unlike QAOA+, AMA-QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA-QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA-QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by 5.30% on ER random graphs and 5.41% on 3-regular graphs. Moreover, AMA-QAOA+ significantly reduces the CNOT gate consumption, requiring only 15.30% and 25.18% of the CNOT gates used by QAOA+ on ER and 3-regular random graphs, respectively. These results demonstrate that AMA-QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource-efficient quantum circuits.