The Quantum Approximate Optimization Algorithm (QAOA) is a leading variational approach for combinatorial problems, yet its performance on NISQ hardware is limited depthbounds and challenging parameter landscapes. We propose Enhanced QAOA (EQAOA), a modified ansatz that appends a compact multi-parameter layer and uses a blockwise optimization scheme. This design preserves the QAOA evolution while broadening the candidate solution space and easing solution exploration. Applied to the MaxCut problem across diverse graph families, EQAOA achieves, with an order of magnitude smaller circuit depth, approximation ratios comparable to QAOA, using a single cost–mixer layer, thus reducing gate counts by up to fivefold, as supported by experiments. Moreover, ablation studies prove that blockwise fine-tuning is crucial to deliver higher-quality solutions at shallower depth, offering a practical, quantum hardware-efficient alternative for signal processing applications.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading variational approach for combinatorial problems, yet its performance on NISQ hardware is limited depthbounds and challenging parameter landscapes. We propose Enhanced QAOA (EQAOA), a modified ansatz that appends a compact multi-parameter layer and uses a blockwise optimization scheme. This design preserves the QAOA evolution while broadening the candidate solution space and easing solution exploration. Applied to the MaxCut problem across diverse graph families, EQAOA achieves, with an order of magnitude smaller circuit depth, approximation ratios comparable to QAOA, using a single cost–mixer layer, thus reducing gate counts by up to fivefold, as supported by experiments. Moreover, ablation studies prove that blockwise fine-tuning is crucial to deliver higher-quality solutions at shallower depth, offering a practical, quantum hardware-efficient alternative for signal processing applications.
The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.
In the Noisy Intermediate-Scale Quantum (NISQ) era, the Quantum Approximate Optimization Algorithm (QAOA) has attracted significant attention as an algorithm for solving combinatorial optimization problems that are classically intractable. Various modifications and training strategies have been proposed to enhance the performance of QAOA. However, as the circuit depth increases, existing methods encounter greater training difficulty and reach a barren plateau in performance improvements. In this paper, we propose the Smart Insert Layerwise QAOA (SIL QAOA) to overcome these challenges. In SIL QAOA, at each stage, a new layer is inserted into all possible positions; each circuit is independently optimized, and the parameter set from the circuit yielding the highest expectation value is adopted as the initial parameter for the next stage. Applying the proposed method to the MaxCut problem, we achieved up to approximately 11% higher approximation ratios compared to conventional Layerwise learning QAOA, while successfully mitigating early performance saturation observed at shallow depths. These results demonstrate the superior performance improvement capability of SIL QAOA. Furthermore, we also discuss its potential applicability to more complex optimization problems and deeper variational quantum circuits in future work.
Abstract The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum–classical algorithm used to approximately solve combinatorial optimisation problems. It involves multiple iterations of a parameterised ansatz that consists of a problem and mixer Hamiltonian, with the parameters being classically optimised. While QAOA can be implemented on near-term quantum hardware, physical limitations such as gate noise, restricted qubit connectivity, and state-preparation-and-measurement (SPAM) errors can limit circuit depth and decrease performance. To address these limitations, this work introduces the eXpressive QAOA (XQAOA), an overparameterised variant of QAOA that assigns more classical parameters to the ansatz to improve its performance at low depths. XQAOA also introduces an additional Pauli-Y component in the mixer Hamiltonian, allowing the mixer to implement arbitrary unitary transformations on each qubit. To benchmark the performance of XQAOA at unit depth, we derive its closed-form expression for the MaxCut problem and compare it to QAOA, Multi-Angle QAOA (MA-QAOA) (Herrman et al 2022 Sci. Rep. 12 6781), a classical-relaxed algorithm, and the state-of-the-art Goemans–Williamson algorithm on a set of unweighted regular graphs with 128 and 256 nodes for degrees ranging from 3 to 10. Our results indicate that at unit depth, XQAOA has benign loss landscapes with local minima concentrated near the global optimum, allowing it to consistently outperform QAOA, MA-QAOA, and the classical-relaxed algorithm on all graph instances and the Goemans–Williamson algorithm on graph instances with degrees greater than 4. Small-scale simulations also reveal that unit-depth XQAOA invariably surpasses both QAOA and MA-QAOA on all tested depths up to five. Additionally, we find an infinite family of graphs for which XQAOA solves MaxCut exactly and analytically show that for some graphs in this family, special cases of XQAOA are capable of achieving a much larger approximation ratio than QAOA. Overall, XQAOA is a more viable choice for variational quantum optimisation on near-term quantum devices, offering competitive performance at low depths.
The solution of large-scale combinatorial optimization problems, which are exorbitantly complex and resource-consuming, is one of the most significant challenges that computing systems face. Traditional algorithms often provide suboptimal results when confronted with bigger issues. This research aims to bring attention to these problems by introducing the Extending Quantum Approximate Optimization Algorithm (EQAOA) framework, which improves scalability, parameter optimization, and error resilience. Fundamental to the EQAOA methodology is repeatedly optimizing solution states via adaptive-depth, parameter-tuned quantum circuits. EQAOA also employs the method of converting combinatorial problems into cost Hamiltonians. Similar problems are shown in the Max-Cut and Graph Coloring programs. The experiments were conducted on several benchmark circumstances using real NISQ hardware and quantum simulators. The enhanced EQAOA outperforms baseline versions in terms of convergence time and solution quality. The efficient integration of dynamic circuit depth with hybrid classical-quantum parameter approaches applied to increasingly complicated problem scenarios and yielded good results. According to the study's findings, applying the proposed QAOA extension to practical combinatorial contexts yields a quantum advantage. The future of this field is bright, with researchers aiming to improve its interaction with traditional optimizers and extend its usage to other practical optimization areas.
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.
Combinatorial optimization lies at the heart of numerous real-world applications. For a broad category of optimization problems, quantum computing is expected to exhibit quantum speed-up over classic computing. Among various quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA), as one of variational quantum algorithms, shows promise on demonstrating quantum advantage on noisy intermediate-scale quantum (NISQ) hardware. However, with increasing problem size, the circuit depth demanded by original QAOA scales rapidly and quickly surpasses the threshold at which meaningful results can be obtained. To address this challenge, in this work, we propose a variant of QAOA (termed linear chain QAOA) and demonstrate its advantages over original QAOA on paradigmatic MaxCut problems. In original QAOA, each graph edge is encoded with one entangling gate. In our ansatz, we locate a linear chain from the original MaxCut graph and place entangling gates sequentially along this chain. This linear-chain ansatz is featured by shallow quantum circuits and with the low execution time that scales independently of the problem size. Leveraging this ansatz, we demonstrate an approximation ratio of 0.78 (without post-processing) on non-hardware-native random regular MaxCut instances with 100 vertices in a digital quantum processor using 100 qubits. Our findings offer new insights into the design of hardware-efficient ansatz and point toward a promising route for tackling large-scale combinatorial optimization problems on NISQ devices.