The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for solving NP hard combinatorial optimization problems on noisy intermediate-scale quantum (NISQ) hardware. However, its performance is critically dependent on the selection of the circuit depth a parameter that must be specified a priori without clear guidance. In this paper, we introduce a variant of QAOA called dynamic depth Quantum Approximate Optimization Algorithm (DDQAOA) that resolves the challenge of pre selecting a fixed circuit depth. Our method adaptively expands circuit depth, starting from p = 1 and progressing up to p = 10, by transferring learned parameters to deeper circuits based on convergence criteria. We tested this approach on 100 instances of the Constrained Shortest Path Problem (CSPP) at 10 qubit and 16 qubit scales. Our DDQAOA achieved superior approximation ratios and success probabilities with fewer CNOT gate evaluations than the standard QAOA for p = 3, 5, 10, and 15. In particular, while standard QAOA at p = 15 achieved results close to our approach, it used 217% and 159.3% more CNOT gates for 10 qubit and 16 qubit instances, respectively. This demonstrates the performance and practical applicability of DDQAOA to solve combinatorial optimization problems on near term devices.
The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for solving NP hard combinatorial optimization problems on noisy intermediate-scale quantum (NISQ) hardware. However, its performance is critically dependent on the selection of the circuit depth a parameter that must be specified a priori without clear guidance. In this paper, we introduce a variant of QAOA called dynamic depth Quantum Approximate Optimization Algorithm (DDQAOA) that resolves the challenge of pre selecting a fixed circuit depth. Our method adaptively expands circuit depth, starting from p = 1 and progressing up to p = 10, by transferring learned parameters to deeper circuits based on convergence criteria. We tested this approach on 100 instances of the Constrained Shortest Path Problem (CSPP) at 10 qubit and 16 qubit scales. Our DDQAOA achieved superior approximation ratios and success probabilities with fewer CNOT gate evaluations than the standard QAOA for p = 3, 5, 10, and 15. In particular, while standard QAOA at p = 15 achieved results close to our approach, it used 217% and 159.3% more CNOT gates for 10 qubit and 16 qubit instances, respectively. This demonstrates the performance and practical applicability of DDQAOA to solve combinatorial optimization problems on near term devices.
Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era. Quantifying the performance of QAOA in the near-term regime is of utmost importance. We perform a large-scale numerical study of the approximation ratios attainable by QAOA is the low-to medium-depth regime. To find good QAOA parameters we perform 990 million 10-qubit QAOA circuit evaluations. We find that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. We observe a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. We observe that the difference in approximation ratios between problem instances increases as the similarity between instances decreases. We find that optimal QAOA parameters concentrate for instances in out benchmark, confirming the previous findings for a different class of problems.
The Quantum Approximate Optimization Algorithm (QAOA) is a well-known hybrid quantum-classical algorithm for combinatorial optimization problems. Improving QAOA involves enhancing its approximation ratio while addressing practical constraints of Noisy Intermediate Scale Quantum (NISQ) devices, such as minimizing the number of two-qubit gates and reducing circuit depth. Although existing research has optimized designs for phase and mixer operators to improve performance, challenges remain, particularly concerning the excessive use of two-qubit gates in the construction of phase operators. To address these issues, we introduce a Dynamic Adaptive Phase Operator (DAPO) algorithm, which dynamically constructs phase operators based on the output of previous layers and neighborhood search approach, optimizing the problem Hamiltonian more efficiently. By using solutions generated by QAOA itself to simplify the problem Hamiltonian at each layer, the algorithm captures the problem's structural properties more effectively, progressively steering the solution closer to the optimal target. Experimental results on MaxCut and NAE3SAT problems show that DAPO achieves higher approximation ratios and significantly reduces two-qubit RZZ gates, especially in dense graphs. Compared to vanilla QAOA, DAPO uses only 66% of RZZ gates at the same depth while delivering better results, demonstrating its potential for efficient combinatorial optimization in the NISQ era.
The quantum approximate optimization algorithm (QAOA) is an appealing proposal to solve NP problems on noisy intermediate-scale quantum (NISQ) hardware. Making NISQ implementations of the QAOA resilient to noise requires short ansatz circuits with as few controlled- () gates as possible. Here we present the dynamic adaptive quantum approximate optimization algorithm (Dynamic-ADAPT-QAOA). Our algorithm significantly reduces the circuit depth and the count of standard ADAPT-QAOA, a leading proposal for near-term implementations of the QAOA. Throughout our algorithm, the decision to apply -intensive operations is made dynamically, based on algorithmic benefits. Using density-matrix simulations, we benchmark the noise resilience of ADAPT-QAOA and Dynamic-ADAPT-QAOA. We compute the gate-error probability p gate ★ below which these algorithms provide, on average, more accurate solutions than the classical, polynomial-time approximation algorithm by Goemans and Williamson. For small systems with six to ten qubits, we show that p gate ★ > 10 − 3 for Dynamic-ADAPT-QAOA. Compared to standard ADAPT-QAOA, this constitutes an order-of-magnitude improvement in noise resilience. This improvement should make Dynamic-ADAPT-QAOA viable for implementations on superconducting NISQ hardware, even in the absence of error mitigation. Published by the American Physical Society 2024
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.
Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parametrized quantum circuits using a classical coprocessor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on current quantum hardware, is the quantum approximate optimization algorithm (QAOA). Despite efforts to realize deeper circuits, experimental state-of-the-art implementations are limited to a fixed depth. However, it is known that problem density---a problem constraint to a variable ratio---induces underparametrization in fixed depth QAOA. Density-dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a $3\ensuremath{\sigma}$ confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect to problem size is recovered for the range of 5--15 qubits.