The authors study the connection between the solution of the quantum approximate optimization algorithm (QAOA) and the generation of squeezed states. In doing so, they reveal a tight connection between the two seemingly unrelated fields of quantum metrology and computing. They also suggest the potential use of squeezing as a benchmark for assessing the quality of quantum algorithms.
The authors study the connection between the solution of the quantum approximate optimization algorithm (QAOA) and the generation of squeezed states. In doing so, they reveal a tight connection between the two seemingly unrelated fields of quantum metrology and computing. They also suggest the potential use of squeezing as a benchmark for assessing the quality of quantum algorithms.
Over the last five years, quantum computing has attracted the attention of a wide variety of research fields with the promise of tackling challenges that currently are infeasible for traditional computing techniques. While quantum computing encompasses many different disciplines, such as quantum machine learning and quantum chemistry, recent advances in the subfield of quantum combinatorial optimization are especially interesting for the risk management and reliability optimization community. However, most of the literature on the topic presents abstract case studies based on problems of low complexity, making it difficult to truly assess the technology's current level of maturity. Thus, this paper presents a condensed review and benchmark of quantum combinatorial optimization, focusing the discussion on the Quantum Approximate Optimization Algorithm (QAOA), arguably one of the most promising quantum optimization approaches in the current literature. A case study regarding the identification of important nodes within the context of critical infrastructure is presented to assess the current state and limitations that the QAOA presents for the field. The case study is showcased in a simulated environment, reflecting ideal conditions assuming a perfect (noise-free) quantum computer. The results obtained indicate that a series of practical limitations and challenges arise when using quantum-based combinatorial optimization approaches in a non-abstract case study. A discussion of these limitations and some feasible solutions to explore in the future are presented at the end of the paper.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum optimization technique used for solving combinatorial optimization problems. However, in constrained binary optimization, QAOA’s reliance on equal initial probabilities for all solutions can lead to suboptimal outcomes. To enhance the performance of QAOA in this context, we propose a novel approach that combines QAOA with genetic algorithms. In this hybrid approach, the results obtained from QAOA serve as the initial population for a genetic algorithm. We apply this methodology to address the k-heaviest subgraph problem, a critical challenge in quantum computing research. Our experiments, conducted on benchmark datasets, demonstrate a significant improvement in solution quality.
The Quantum Approximate Optimization Algorithm (QAOA) and its variants are leading algorithms to help solve challenging combinatorial optimization problems. QAOA maps these problems to Ising Hamiltonians such that their ground state is the desired solution. Candidate solutions are then drawn from a variational quantum circuit. The performance of QAOA hinges on a set of variational angles. However, finding good angles is an instance-specific and computationally expensive non-convex classical optimization task. Here, we learn the mapping from the problem instance to high-quality QAOA angles. Our learned models replace the per-instance optimization, that we call the solver, with a single forward pass that is several orders of magnitude faster than the solver with a near identical quality. Our models further generalize to unseen topologies such as Barabási-Albert and 2D grid graphs. Experiments on quantum hardware confirm that QAOA samples with angles produced by our open-source models are indistinguishable from solver angles. Crucially, models sensitive to the topology of the problem instance increase the quality of the QAOA angles. Our work amortizes a major bottleneck in QAOA by an up-front data generation and training cost. Importantly, this cost can be amortized over time in settings where many similar problems are optimized on a regular basis, as is often the case in applications for industry.
Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve NP-hard problems in near-term gate-based noisy quantum devices. In QAOA, the gate parameters of a parameterized quantum circuit (PQC) are varied by a classical optimizer to generate a quantum state with a significant support to the optimal solution. The existing analysis fails to consider nonidealities in the qubit quality i.e., short lifetime and imperfect gate operations in a realistic quantum hardware. In this article, we study the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analysis indicates that QAOA performance is noise-sensitive (especially higher-depth QAOA instances). Therefore, the optimal number of stages (p-value) for any QAOA instance is limited by the noise in the target hardware as opposed to the current perception that QAOA will provide monotonically better performance with higher-depth. We show that the two-qubit gate error has to be decreased by more than 75% of the current state-of-the-art levels to attain a performance within 10% of the maximum value for the lowest-depth QAOA.
Abstract Noisy intermediate-scale quantum (NISQ) devices are cutting-edge technology expected to demonstrate potential and advantages of quantum computing over classical computing. Its low number of qubits and imperfection from noises restrict running full-scale quantum algorithms on such devices; however, quantum advantages can still be obtained. To achieve quantum advantages from NISQ devices, the hybrid quantum-classical algorithms were introduced. Quantum approximate optimization algorithm (QAOA) is a variational hybrid algorithm, which utilizes a NISQ device as a sub-unit for specific tasks and performs most calculations on a classical computer. QAOA provides an approximate solution, with arbitrary precision as the number of operations increases, for optimization problems. In this work we investigate the possibility of applying QAOA to a clustering problem and compare its performance with the classical k-means algorithm. It turns out that the weights in graph connectivity can degrade the algorithm operation and make it more difficult to approximate the solution. We also benchmark the QAOA by comparing the approximated solutions with the exact one obtained from a classical clustering algorithm.