Improving QAOA to find approximate QUBO solutions in O(1) shots

• URL: http://arxiv.org/abs/2509.19035v1
• Date: Tue, 23 Sep 2025 14:07:55 GMT
• Title: Improving QAOA to find approximate QUBO solutions in O(1) shots
• Authors: A. Yu. Chernyavskiy, D. A. Kulikov, B. I. Bantysh, Yu. I. Bogdanov, A. K. Fedorov, E. O. Kiktenko,
• Abstract summary: We develop a modified fpQAOA scheme that considers the probability of achieving a target approximation ratio (AR) rather than requiring the exact optimum.<n>We demonstrate that this combination leads to a decreasing median number of shots required to obtain approximate solutions as the problem size increases.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) provides one of the most promising quantum frameworks for addressing discrete optimization problems with broad real-world applications, particularly quadratic unconstrained binary optimization (QUBO) problems. However, the widely used hybrid quantum--classical implementation faces significant challenges due to statistical noise and barren plateaus. A prominent approach to mitigate these issues is fixed-point QAOA (fpQAOA), where circuit parameters are trained on small problem instances and subsequently transferred to larger ones. In this work, we develop a modified fpQAOA scheme that combines (i) considering the probability of achieving a target approximation ratio (AR) rather than requiring the exact optimum, (ii) setting the number of layers equal to the problem size with the sine--cosine encoding of QAOA angles, and (iii) rescaling the problem coefficient matrices to unit Frobenius norm. We demonstrate that this combination leads to a decreasing median number of shots required to obtain approximate solutions as the problem size increases, with ARs being within a few percent from the optimum for the considered problem classes. Extrapolation of these results suggests an $O(1)$ shot complexity while retaining at most quadratic circuit depth, underscoring the potential of our approach to overcome key bottlenecks in QAOA implementations and scalability estimations. Remarkably, omitting even a single one of the modifications (i)--(iii) results in exponential growth of the number of shots required as the problem size increases.

Related papers

• Design and Analysis of an Improved Constrained Hypercube Mixer in Quantum Approximate Optimization Algorithm [0.0]
  In the Noisy Intermediate-Scale Quantum (NISQ) era, QAOA is not suited for constrained problems.<n>One way to incorporate certain types of constraints is to restrict the mixing operator to the feasible subspace.<n>We present a modification that generates circuits with fewer gates for a broad class of constrained problems.
  arXiv  Detail & Related papers  (2026-03-05T13:57:15Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz.<n>One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally.<n>Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources.
  arXiv  Detail & Related papers  (2025-06-03T17:46:53Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  We show that VarQITE achieves significantly lower mean optimality gaps compared to other conventional methods.<n>We demonstrate that scaling the Hamiltonian can further reduce optimization costs and accelerate convergence.
  arXiv  Detail & Related papers  (2025-04-17T03:09:37Z)
• Distributed Quantum Approximate Optimization Algorithm on a Quantum-Centric Supercomputing Architecture [1.953969470387522]
  Quantum approximate optimization algorithm (QAOA) has shown promise in solving optimization problems by providing quantum speedup on gate-based quantum computing systems.<n>However, QAOA faces challenges for high-dimensional problems due to the large number of qubits required and the complexity of deep circuits.<n>We present a distributed QAOA (DQAOA) which decomposes a large computational workload into smaller tasks that require fewer qubits and shallower circuits.
  arXiv  Detail & Related papers  (2024-07-29T17:42:25Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications [44.88678858860675]
  We investigate the application of the quantum approximate optimization algorithm (QAOA) and the quantum adiabatic algorithm (QAA) to the solution of a prototypical model in this field. We compare the performance of these two algorithms in terms of solution quality, using selected evaluation metrics.
  arXiv  Detail & Related papers  (2023-11-20T09:09:55Z)
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios [0.0]
  We provide some of the first lower coefficients for the number of rounds (the dominant component of QAOA runtimes) required for the QAOA.<n>For the conventional transverse-field mixer, (iv) our framework gives a trivial lower bound to all bounded-occurrence local cost problems.<n>For all strictly $k$-local cost Hamiltonians matching known results that constant approximation ratio is obtainable with a constant-round QAOA.
  arXiv  Detail & Related papers  (2023-08-29T17:10:20Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.