The variational quantum power method (VQPM), which adapts the classical power iteration algorithm for quantum settings, has shown promise for eigenvector estimation and optimization on quantum hardware. In this work, we provide a comprehensive theoretical and numerical analysis of VQPM by investigating its convergence, robustness, and qubit locking mechanisms. We present detailed strategies for applying VQPM to QUBO problems by leveraging these locking mechanisms, establishing systematic guidelines for their practical applications. Furthermore, we provide a comparative study against the Quantum Approximate Optimization Algorithm (QAOA). Our analysis evaluates classical optimization behaviors and evaluates performance using localized Hamming distance (bit difference of the combinatorial solution). Scaling simulations up to $n=18$ qubits demonstrate that the success probability in VQPM exhibits notable resilience. Finally, we evaluate VQPM under realistic quantum noise using the IBM Qiskit Aer framework. Our results indicate that VQPM serves as an effective quantum optimization algorithm for combinatorial problems, and this work can serve as an initial guideline for such applications.
The variational quantum power method (VQPM), which adapts the classical power iteration algorithm for quantum settings, has shown promise for eigenvector estimation and optimization on quantum hardware. In this work, we provide a comprehensive theoretical and numerical analysis of VQPM by investigating its convergence, robustness, and qubit locking mechanisms. We present detailed strategies for applying VQPM to QUBO problems by leveraging these locking mechanisms, establishing systematic guidelines for their practical applications. Furthermore, we provide a comparative study against the Quantum Approximate Optimization Algorithm (QAOA). Our analysis evaluates classical optimization behaviors and evaluates performance using localized Hamming distance (bit difference of the combinatorial solution). Scaling simulations up to n=18 qubits demonstrate that the success probability in VQPM exhibits notable resilience. Finally, we evaluate VQPM under realistic quantum noise using the IBM Qiskit Aer framework. Our results indicate that VQPM serves as an effective quantum optimization algorithm for combinatorial problems, and this work can serve as an initial guideline for such applications.
Combinatorial optimization on near-term quantum devices is a promising path to demonstrating quantum advantage. However, the capabilities of these devices are constrained by high noise or error rates. In this article, inspired by the variational quantum eigensolver (VQE), we propose an iterative layer VQE (L-VQE) approach. We present a large-scale numerical study, simulating circuits with up to 40 qubits and 352 parameters, that demonstrates the potential of the proposed approach. We evaluate quantum optimization heuristics on the problem of detecting multiple communities in networks, for which we introduce a novel qubit-frugal formulation. We numerically compare L-VQE with the quantum approximate optimization algorithm (QAOA) and demonstrate that QAOA achieves lower approximation ratios while requiring significantly deeper circuits. We show that L-VQE is more robust to finite sampling errors and has a higher chance of finding the solution as compared with standard VQE approaches. Our simulation results show that L-VQE performs well under realistic hardware noise.
Variational Quantum Algorithms (VQAs) are promising methods for solving combinatorial optimization problems on noisy intermediate-scale quantum (NISQ) devices. However, benchmarking VQAs is difficult due to their stochastic behavior and the lack of standardized performance criteria. This work introduces a general framework for evaluating VQAs applied to Quadratic Unconstrained Binary Optimization (QUBO) problems. The framework uses three complementary metrics: feasibility, quality, and reproducibility. It also introduces a quality diagram that visualizes trade-offs between success probability and computational resources. Reproducibility is formalized using Shannon entropy, and a decision rule is defined for selecting algorithms under resource constraints. As a demonstration, the framework is applied to several VQAs using Conditional Value at Risk (CVaR) cost functions and different shot counts on a 16-qubit QUBO instance. The results show how the framework supports systematic benchmarking and provides a foundation for adaptive algorithm selection in hybrid quantum-classical workflows.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
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.
The Quantum Approximate Optimization Algorithm (QAOA) has emerged as one of the most extensively studied variational approaches for tackling combinatorial optimization problems on near-term quantum devices. An extensive body of literature has examined the algorithm from multiple perspectives, including ansatz design, parameter optimization, computational resource requirements, solution quality, and noise effects.This paper adopts these principal analytical dimensions as a structured framework and revisits them from a performance-assessment perspective. By synthesizing representative theoretical, numerical, and experimental contributions, the discussion highlights recurring tendencies in reported results, particularly regarding approximation behavior, depth–noise trade-offs, optimization stability, and resource accounting.The analysis indicates that QAOA performance must be interpreted through a multidimensional lens that jointly considers solution quality, classical and quantum resource costs, optimization dynamics, and hardware constraints. By organizing existing results along common evaluation axes, this work provides a coherent basis for interpreting benchmarking outcomes and for guiding future assessment methodologies in realistic computational settings.