The selection of the right topology (ansatz) for a Variational Quantum Algorithm (VQA) is a complex task that usually involves deep knowledge of a particular problem. The importance of the selection is greater when we consider the current state of quantum hardware, particularly the noise associated with the complexity of Variational Quantum Circuits (VQCs) that implement VQAs. Here, a comparison is presented between two confronted approaches for solving the MaxCut problem: QAOA, which has a theoretical proof of convergence, and the automatic design proposal (QNAS), which relies on evolutionary algorithms (NSGA-II) to discover efficient circuits. The comparison was made across 490 graph instances from different graph topologies and sizes (n=4 to n=16), accounting for noise models such as depolarizing noise, gate errors, and readout noise. The results show that QAOA achieves an approximation ratio (rA) ≈1 on complete graphs at the cost of being almost 12 times more complex than QNAS in ideal conditions while approaching the random noise floor (rA≈0.5). QNAS was capable of finding circuits less complex while maintaining 69% of the fidelity at a cost of having an rA on the interval 0.7≤rA≤0.8. However, when the comparison is made across sparse graphs, performance is comparable, while QNAS is less complex.
The selection of the right topology (ansatz) for a Variational Quantum Algorithm (VQA) is a complex task that usually involves deep knowledge of a particular problem. The importance of the selection is greater when we consider the current state of quantum hardware, particularly the noise associated with the complexity of Variational Quantum Circuits (VQCs) that implement VQAs. Here, a comparison is presented between two confronted approaches for solving the MaxCut problem: QAOA, which has a theoretical proof of convergence, and the automatic design proposal (QNAS), which relies on evolutionary algorithms (NSGA-II) to discover efficient circuits. The comparison was made across 490 graph instances from different graph topologies and sizes (n=4 to n=16), accounting for noise models such as depolarizing noise, gate errors, and readout noise. The results show that QAOA achieves an approximation ratio (rA) ≈1 on complete graphs at the cost of being almost 12 times more complex than QNAS in ideal conditions while approaching the random noise floor (rA≈0.5). QNAS was capable of finding circuits less complex while maintaining 69% of the fidelity at a cost of having an rA on the interval 0.7≤rA≤0.8. However, when the comparison is made across sparse graphs, performance is comparable, while QNAS is less complex.
In recent years, Variational Quantum Algorithms (VQAs) have emerged as a promising approach for solving optimization problems on quantum computers in the NISQ era. However, one limitation of VQAs is their reliance on fixed-structure circuits, which may not be taylored for specific problems or hardware configurations. A leading strategy to address this issue are Adaptative VQAs, which dynamically modify the circuit structure by adding and removing gates, and optimize their parameters during the training. Several Adaptative VQAs, based on heuristics such as circuit shallowness, entanglement capability and hardware compatibility, have already been proposed in the literature, but there is still lack of a systematic comparison between the different methods. In this paper, we aim to fill this gap by analyzing three Adaptative VQAs: Evolutionary Variational Quantum Eigensolver (EVQE), Variable Ansatz (VAns), already proposed in the literature, and Random Adapt-VQE (RA-VQE), a random approach we introduce as a baseline. In order to compare these algorithms to traditional VQAs, we also include the Quantum Approximate Optimization Algorithm (QAOA) in our analysis. We apply these algorithms to QUBO problems and study their performance by examining the quality of the solutions found and the computational times required. Additionally, we investigate how the choice of the hyperparameters can impact the overall performance of the algorithms, highlighting the importance of selecting an appropriate methodology for hyperparameter tuning. Our analysis sets benchmarks for Adaptative VQAs designed for near-term quantum devices and provides valuable insights to guide future research in this area.
Abstract In the noisy intermediate-scale quantum (NISQ) era, quantum approximate optimisation algorithms are important tools for solving NP-hard problems such as combinatorial optimisation. However, most QAOA implementations ignore the inherent noise in quantum circuit environments. This study proposes a noisy quantum approximate optimisation algorithm (NQAOA) and analyses its performance under noisy conditions through numerical simulations. We compare the approximate ratios (AR) of various graphs under different optimisation strategies and noise conditions, and assess the impact of circuit depth, node count, edge count, and noise coefficient on the maximum cut (MaxCut). Experimental results show that noise leads to overfitting, and the approximate ratio ( AR ) exhibits fluctuating changes as the edge count e increases. The AR values under ideal conditions and the expected results are both superior to those under noisy conditions. This study is the first to systematically integrate multiple types of quantum noise into the QAOA framework, quantitatively analysing the synergistic effects of noise type, optimiser performance, and graph structure. Through theoretical derivations and numerical simulations, we established linear/exponential theoretical boundaries for AR decay related to noise coefficients, providing a critical reference for designing noise-resistant quantum optimisation algorithms on NISQ devices.
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.
Hybrid quantum-classical algorithms, such as variational quantum algorithms (VQA), are suitable for implementation on NISQ computers. In this Article we expand an implicit step of VQAs: the classical pre-computation subroutine which can non-trivially use classical algorithms to simplify, transform, or specify problem instance-specific variational quantum circuits. In VQA there is a trade-off between quality of solution and difficulty of circuit construction and optimization. In one extreme, we find VQA for MAXCUT which are exact, but circuit design or variational optimization is NP-HARD. At the other extreme are low depth VQA, such as QAOA, with tractable circuit construction and optimization but poor approximation ratios. Combining these two we define the Spanning Tree QAOA (ST-QAOA) to solve MAXCUT, which uses an ansatz whose structure is derived from an approximate classical solution and achieves the same performance guarantee as the classical algorithm and hence can outperform QAOA at low depth. In general, we propose integrating these classical pre-computation subroutines into VQA to improve heuristic or guaranteed performance.
The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.
We implement Quantum Approximate Optimization Algorithm (QAOA) on NP-Hard problem MaxCut (for 3-chain and 4-node chain graphs, and 4-node and 6node Mobius Ladder graphs) on a quantum simulator without noise, a simulator with experimentally bench-marked noise (fake back-end), and 5-qubit and 7-qubit processors. We use the following modes of operation: QAOA parameters updated through forward pass on the quantum circuit, modelled by the noiseless simulator as well as fake back-end, and the quantum circuit for final run with updated parameters implemented on the noiseless simulator, fake back-end, and real quantum processors. While QAOA yields higher approximation ratio compared to random guess for almost all graph instances, we also conclude that given the noise in existing quantum hardware, a quantum circuit with more than two stages is not suitable for experimental implementation of QAOA currently.