In recent years, several quantum algorithms have been proposed for addressing combinatorial optimization problems. Among them, the Quantum Approximate Optimization Algorithm (QAOA) has become a widely used approach. However, reported limitations of QAOA have motivated the development of multiple algorithmic variants, including recursive hybrid methods such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), as well as the Quantum-Informed Recursive Optimization (QIRO) framework. In this work, we integrate the Quantum Alternating Operator Ansatz within the QIRO framework in order to improve its quantum inference stage. Both the original and the enhanced versions of QIRO are applied to the Minimum Vertex Cover problem, an NP-complete problem of practical relevance. Performance is evaluated on a benchmark of Erdös-Rényi graph instances with varying sizes, densities, and random seeds. The results show that the proposed modification leads to a higher number of successfully solved instances across the considered benchmark, indicating that refinements of the variational layer can improve the effectiveness of the QIRO framework.
In recent years, several quantum algorithms have been proposed for addressing combinatorial optimization problems. Among them, the Quantum Approximate Optimization Algorithm (QAOA) has become a widely used approach. However, reported limitations of QAOA have motivated the development of multiple algorithmic variants, including recursive hybrid methods such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), as well as the Quantum-Informed Recursive Optimization (QIRO) framework. In this work, we integrate the Quantum Alternating Operator Ansatz within the QIRO framework in order to improve its quantum inference stage. Both the original and the enhanced versions of QIRO are applied to the Minimum Vertex Cover problem, an NP-complete problem of practical relevance. Performance is evaluated on a benchmark of Erdös-Rényi graph instances with varying sizes, densities, and random seeds. The results show that the proposed modification leads to a higher number of successfully solved instances across the considered benchmark, indicating that refinements of the variational layer can improve the effectiveness of the QIRO framework.
We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for combinatorial optimization problems. Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps that recursively simplify the problem. These reduction steps address the limitations of the quantum component (e.g., locality) and ensure solution feasibility in constrained optimization problems. Additionally, we use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware. We showcase the capabilities of our approach by informing QIRO with correlations from classical simulations of shallow circuits of the quantum approximate optimization algorithm, solving instances of maximum independent set and maximum satisfiability problems with hundreds of variables. We also demonstrate how QIRO can be deployed on a neutral atom quantum processor to find large independent sets of graphs. In summary, our scheme achieves results comparable to classical heuristics even with relatively weak quantum resources. Furthermore, enhancing the quality of these quantum resources improves the performance of the algorithms. Notably, the modular nature of QIRO offers various avenues for modifications, positioning our work as a template for a broader class of hybrid quantum-classical algorithms for combinatorial optimization. Published by the American Physical Society 2024
The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints. In this paper, we study Maximum k-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two XY-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially inp(the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.
ABSTRACT 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 on Erdős–Rényi random graphs and on 3‐regular graphs. Moreover, AMA‐QAOA+ significantly reduces the CNOT gate consumption, requiring only and of the CNOT gates used by QAOA+ on Erdős–Rényi 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.
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.
Graph-based combinatorial optimization problems are computationally challenging for classical optimization techniques due to their NP-hard nature. This paper proposes a novel Quantum-Assisted Hybrid Optimization Algorithm (QAHOA) that integrates the Quantum Approximate Optimization Algorithm (QAOA), spectral graph theory, and classical optimization strategies for graph-based combinatorial optimization. The developed framework uses spectral initialization via the graph Laplacian Fiedler vector to provide structurally informed starting variational parameters, aiming to stabilize the parameter search space and improve convergence trajectories under noisy conditions. The mathematical framework, alongside a convergence analysis to first-order stationary points, is provided to establish theoretical baseline properties. Evaluated on synthetic Erdős–Rényi random graph instances, the current study serves as a preliminary, small-to-medium-scale proof-of-concept. Controlled evaluations demonstrate that the proposed QAHOA achieves marginal yet stable and statistically significant improvements in mean cut values and approximation ratios over classical Greedy heuristics, Simulated Annealing, the standard QAOA, and Warm-Start QAOA. Formal paired hypothesis testing mathematically verifies the stability of the framework, while preliminary 4-qubit hardware executions demonstrate baseline architectural compatibility under physical NISQ noise channels.
The quantum approximate optimization algorithm (QAOA) promises to solve classically intractable computational problems in the area of combinatorial optimization. A growing amount of evidence suggests that the originally proposed form of the QAOA ansatz is not optimal, however. To address this problem, we propose an alternative ansatz, which we call QAOA+, that augments the traditional p=1 QAOA ansatz with an additional multiparameter problem-independent layer. The QAOA+ ansatz allows obtaining higher approximation ratios than p=1 QAOA while keeping the circuit depth below that of p = 2 QAOA, as benchmarked on the MaxCut problem for random regular graphs. We additionally show that the proposed QAOA+ ansatz, while using a larger number of trainable classical parameters than with the standard QAOA, in most cases outperforms alternative multiangle QAOA ansätze for fixed number of independent parameters.