Analysis and Experimental Demonstration of Amplitude Amplification for Combinatorial Optimization

• URL: http://arxiv.org/abs/2601.10473v1
• Date: Thu, 15 Jan 2026 14:58:26 GMT
• Title: Analysis and Experimental Demonstration of Amplitude Amplification for Combinatorial Optimization
• Authors: Daniel Koch, Brian Pardo, Kip Nieman,
• Abstract summary: Quantum Amplitude Amplification (QAA) is capable of yielding optimal solutions to optimization problems with high probabilities.<n>We show that linear cost functions are a special case whereby an exact formula exists for determining optimal oracle parameter settings.
• Score: 1.8479558716666362
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum Amplitude Amplification (QAA), the generalization of Grover's algorithm, is capable of yielding optimal solutions to combinatorial optimization problems with high probabilities. In this work we extend the conventional 2-dimensional representation of Grover's (orthogonal collective states) to oracles which encode cost functions such as QUBO, and show that linear cost functions are a special case whereby an exact formula exists for determining optimal oracle parameter settings. Using simulations of problem sizes up to 40 qubits we demonstrate QAA's algorithmic performance across all possible solutions, with an emphasis on the closeness in Grover-like performance for solutions near the global optimum. We conclude with experimental demonstrations of generalized QAA on both IBMQ (superconducting) and IonQ (trapped ion) qubits, showing that the observed probabilities of each basis state match our equations as a function of varying the free parameters in the oracle and diffusion operators.

Related papers

• Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization [1.3824488054100907]
  We study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces.<n>We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions.<n>Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum optimization.
  arXiv  Detail & Related papers  (2026-02-07T04:37:32Z)
• 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)
• One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems [0.0]
  We present a unified quantum-classical framework for solving NP-complete constrained optimization problems. We show that QCP's parameterized ansatz class always captures the optimum within its generated subcone.
  arXiv  Detail & Related papers  (2024-11-01T08:00:30Z)
• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  This paper introduces in detail a non-variational quantum algorithm designed to solve a wide range of optimisation problems. The algorithm returns optimal and near-optimal solutions from repeated preparation and measurement of an amplified state.
  arXiv  Detail & Related papers  (2024-07-29T13:54:28Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  We introduce an efficient single-loop primal-dual block-coordinate algorithm called ALEXR.<n>We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions.<n> Experimental results on GDRO and partial Area Under the ROC Curve for cFCCO demonstrate the promising performance of our algorithm.
  arXiv  Detail & Related papers  (2023-12-04T19:00:07Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Variational Amplitude Amplification for Solving QUBO Problems [0.0]
  This study focuses on QUBO (quadratic unconstrained binary optimization) problems, which are well-suited for qubit superposition states. We demonstrate circuit designs which encode QUBOs as cost oracle' operations $U_textrmC$, which when combined with the standard Grover diffusion operator $U_textrms$ lead to high probabilities of measurement for states corresponding to the optimal and near optimal solutions.
  arXiv  Detail & Related papers  (2023-01-31T14:33:40Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm [0.0]
  We show that the calculation of the expectation of a problem Hamiltonian under a Grover-driven, QAOA-prepared state can be performed independently of system size. Such calculations can help deliver insights into the performance of and predictability of angles in QAOA in the limit of large problem sizes.
  arXiv  Detail & Related papers  (2022-08-22T17:18:25Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.