Quadratic unconstrained binary optimization (QUBO) tasks are very important in chemistry, finance, job scheduling, and so on, which can be represented using graph structures, with the variables as nodes and the interaction between them as edges. Variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) and its variants, present a promising way, potentially exceeding the capabilities of classical algorithms, for addressing QUBO tasks. However, the possibility of using message-passing machines, inspired by classical graph neural networks, to enhance the power and performance of these quantum algorithms for QUBO tasks was not investigated. This study introduces a novel variational quantum graph optimization algorithm that integrates the message-passing mechanism, which demonstrates significant improvements in performance for solving QUBO problems in terms of resource efficiency and solution precision, compared to QAOA, its variants, and other quantum graph neural networks. Furthermore, in terms of scalability on QUBO tasks, our algorithm shows superior performance compared to QAOA, presenting a substantial advancement in the field of quantum approximate optimization.Quadratic unconstrained binary optimization (QUBO) tasks are very important in chemistry, finance, job scheduling, and so on, which can be represented using graph structures, with the variables as nodes and the interaction between them as edges. Variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) and its variants, present a promising way, potentially exceeding the capabilities of classical algorithms, for addressing QUBO tasks. However, the possibility of using message-passing machines, inspired by classical graph neural networks, to enhance the power and performance of these quantum algorithms for QUBO tasks was not investigated. This study introduces a novel variational quantum graph optimization algorithm that integrates the message-passing mechanism, which demonstrates significant improvements in performance for solving QUBO problems in terms of resource efficiency and solution precision, compared to QAOA, its variants, and other quantum graph neural networks. Furthermore, in terms of scalability on QUBO tasks, our algorithm shows superior performance compared to QAOA, presenting a substantial advancement in the field of quantum approximate optimization.

arXiv:2404.06434Apr 9, 20240 citations

Amplitude amplification-inspired QAOA: improving the success probability for solving 3SAT

Alexander Mandl, Johanna Barzen, Marvin Bechtold +2 more

Abstract The Boolean satisfiability problem (SAT), in particular 3SAT with its bounded clause size, is a well-studied problem since a wide range of decision problems can be reduced to it. The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices in the near future due to its simple quantum ansatz. However, although QAOA generally exhibits a high approximation ratio, there are 3SAT problem instances where the algorithm’s success probability when obtaining a satisfying variable assignment from the approximated solution drops sharply compared to the approximation ratio. To address this problem, in this paper, we present variants of the algorithm that are inspired by the amplitude amplification algorithm to improve the success probability for 3SAT. For this, (i) three amplitude amplification-inspired QAOA variants are introduced and implemented, (ii) the variants are experimentally compared with a standard QAOA implementation, and (iii) the impact on the success probability and ansatz complexity is analyzed. The experiment results show that an improvement in the success probability can be achieved with only a moderate increase in circuit complexity.Abstract The Boolean satisfiability problem (SAT), in particular 3SAT with its bounded clause size, is a well-studied problem since a wide range of decision problems can be reduced to it. The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices in the near future due to its simple quantum ansatz. However, although QAOA generally exhibits a high approximation ratio, there are 3SAT problem instances where the algorithm’s success probability when obtaining a satisfying variable assignment from the approximated solution drops sharply compared to the approximation ratio. To address this problem, in this paper, we present variants of the algorithm that are inspired by the amplitude amplification algorithm to improve the success probability for 3SAT. For this, (i) three amplitude amplification-inspired QAOA variants are introduced and implemented, (ii) the variants are experimentally compared with a standard QAOA implementation, and (iii) the impact on the success probability and ansatz complexity is analyzed. The experiment results show that an improvement in the success probability can be achieved with only a moderate increase in circuit complexity.

arXiv:2303.01183Quantum Science and TechnologyDec 11, 20238 citations

Quantum Approximate Optimization Algorithm: Applications, Limitations and Enhancement

Pablo Herrero Gómez, Marcos Alemany Manzanaro, David Gil +1 more

Communications in computer and information scienceJan 1, 20260 citations

The Quantum Approximate Optimization Algorithm

Stefan Isermann

Jul 3, 20260 citations

Warm-start adaptive-bias quantum approximate optimization algorithm

Yunlong Yu, Xiang‐Bin Wang, Nic Shannon +1 more

In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with $40$ to $180$ qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to $1000$ qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the $1000$ -qubit case even in level 1 can only be matched by the GW algorithm after about $10^{5.5}$ random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with $40$ to $180$ qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to $1000$ qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the $1000$-qubit case even in level 1 can only be matched by the GW algorithm after about $10^{5.5}$ random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.

arXiv:2503.20048Physical Review AJul 14, 20254 citations

40

180

qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to

1000

qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the

1000

-qubit case even in level 1 can only be matched by the GW algorithm after about

10^{5.5}

random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.