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.
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.
Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the depth of the variational ansatz used - the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant ε > 0, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor N^(1-ε), for N denoting the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists in the even "simpler" QAOA-type settings. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems.
Hybrid Quantum–Classical Optimization combines the advantages of quantum computing and classical optimization to address complex combinatorial optimization problems. The Quantum Approximate Optimization Algorithm (QAOA), as an outstanding Variational Quantum Algorithm (VQA), shows great potential in solving combinatorial optimization problems. Classical optimization methods play a crucial role in tuning the parameters of quantum circuits, affecting the algorithm’s convergence speed and solution quality. This paper designs and simulates QAOA circuits based on the Qiskit framework, focusing on comparing the performance of three classical optimizers— Adaptive Moment Estimation (Adam), Constrained Optimization BY Linear Approximations (COBYLA), and Simultaneous Perturbation Stochastic Approximation (SPSA)—in parameter optimization. Adam and SPSA perform more stably in deeper circuits, making them suitable for high-dimensional parameter spaces, whereas COBYLA tends to get trapped in local optima and exhibits greater fluctuations under limited iterations. The results further highlight the importance of classical optimizer selection and hyperparameter tuning in enhancing the performance of hybrid quantum–classical optimization algorithms.
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.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimization Algorithm (QAOA) of [Farhi, Goldstone, Gutmann, 2014], have seen intense study towards near-term applications on quantum hardware. A crucial parameter for VQAs is the \emph{depth} of the variational ``ansatz'' used -- the smaller the depth, the more amenable the ansatz is to near-term quantum hardware in that it gives the circuit a chance to be fully executed before the system decoheres. In this work, we show that approximating the optimal depth for a given VQA ansatz is intractable. Formally, we show that for any constant ε>0, it is QCMA-hard to approximate the optimal depth of a VQA ansatz within multiplicative factor N1−ε, for N denoting the encoding size of the VQA instance. (Here, Quantum Classical Merlin-Arthur (QCMA) is a quantum generalization of NP.) We then show that this hardness persists in the even ``simpler'' QAOA-type settings. To our knowledge, this yields the first natural QCMA-hard-to-approximate problems.