The Quantum Approximate Optimization Algorithm

Kevin Thompson

Soumyadip Paul, Sarit Chakraborty

Quantum technology offers a transformative approach to solving complex computational challenges in decentralized systems, particularly in blockchain transaction scheduling. Efficient transaction scheduling is critical in distributed ledger systems, which often face challenges like dynamic transaction loads. This work proposes a novel approach namely Hybrid Quantum Approximate Optimization Algorithm (HQAOA) which combines Multi-Agent QAOA (MA-QAOA) and Adaptive Layer QAOA (AL-QAOA) to provide a robust solution to such issues. HQAOA leverages a decentralized optimization framework where multiple agents, each representing a node in the network, optimize local transaction scheduling while considering global constraints. Additionally, HQAOA adapts to varying transaction loads by dynamically adjusting the number of quantum layers for each agent, ensuring computational efficiency under different conditions. Such dynamic layer adjustment mechanisms mitigate the adverse effects of quantum noise and ensures optimal performance in scenarios with fluctuating transaction loads. In contrast to traditional QAOA, which struggles with noise and scaling issues, HQAOA provides improved performance by balancing the complexity of the problem with available quantum resources. Experimental results signify the future potential of HQAOA to outperform QAOA, particularly in noisy environments and irregular transaction conditions. This work demonstrates the potential of HQAOA to optimize blockchain transaction scheduling in decentralized systems.

Ansh Bansal

Takuya Yoshioka, Keita Sasada, Yuichiro Nakano +1 more

Quantum computers are expected to accelerate solving combinatorial optimization problems, including algorithms such as Grover adaptive search and quantum approximate optimization algorithm (QAOA). However, many combinatorial optimization problems involve constraints which, when imposed as soft constraints in the cost function, can negatively impact the performance of the optimization algorithm. In this paper, we propose fermionic quantum approximate optimization algorithm (FQAOA) for solving combinatorial optimization problems with constraints. Specifically, FQAOA tackles the constrains issue by using fermion particle number preservation to intrinsically impose them throughout QAOA. We provide a systematic guideline for designing the driver Hamiltonian for a given problem Hamiltonian with constraints. The initial state can be chosen to be a superposition of states satisfying the constraint and the ground state of the driver Hamiltonian. This property is important since FQAOA reduced to quantum adiabatic computation in the large limit of circuit depth $p$ and improved performance, even for shallow circuits with optimizing the parameters starting from the fixed-angle determined by Trotterized quantum adiabatic evolution. We perform an extensive numerical simulation and demonstrate that proposed FQAOA provides substantial performance advantages against existing approaches in portfolio optimization problems. Furthermore, the Hamiltonian design guideline is useful not only for QAOA but also Grover adaptive search and quantum phase estimation to solve combinatorial optimization problems with constraints. Since software tools for fermionic systems have been developed in quantum computational chemistry both for noisy intermediate-scale quantum computers and fault-tolerant quantum computers, FQAOA allows us to apply these tools for constrained combinatorial optimization problems.

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

Ali Al-Bayaty, Marek A. Perkowski

This article investigates the performance impact of five classical optimization approximation algorithms on our previously introduced quantum search algorithm, termed the Boolean–Hamiltonians Transform for Quantum Approximate Optimization Algorithm (BHT-QAOA), to effectively search for all best-approximated solutions for Boolean-based problems. These optimization approximation algorithms are BFGS, L-BFGS-B, SLSQP, COBYLA, and COBYQA. Their performance impact is evaluated and compared using two proposed performance metrics—(i) the final number of function evaluations (the lower numbers denote the best optimization approximation algorithms) and (ii) the final quality of qubit measurements (the higher values indicate all best-approximated solutions were found for a problem). Arbitrary classical Boolean problems in various logical structures were examined and evaluated using the BHT-QAOA, these five optimization approximation algorithms, and a simulated noisy model of an IBM quantum computer. Broadly, the BHT-QAOA, with these five algorithms, successfully finds all optimized approximated solutions for these problems. Specifically, both the BFGS and SLSQP algorithms successfully find all best-approximated solutions for these problems, in the context of fewer function evaluations and higher quality of qubit measurements.