Heuristic Quantum Amplitude Amplification: A Traffic QUBO Case Study

• URL: http://arxiv.org/abs/2609.13505v1
• Date: Fri, 11 Sep 2026 20:11:46 GMT
• Title: Heuristic Quantum Amplitude Amplification: A Traffic QUBO Case Study
• Abstract summary: Quantum Amplitude Amplification (QAA) is a generalization of Grover's algorithm.<n> QAA is appealing due to its ability to drive the quantum system to a target state.<n>However, realizing QAA for application-scale optimization currently exceeds quantum hardware capacity.
• Score: 2.076917207095107
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Amplitude Amplification (QAA), the generalization of Grover's algorithm, is well-positioned for combinatorial optimization and is particularly promising for Quadratic Unconstrained Binary Optimization (QUBO) problems. QAA is appealing due to its ability to drive the quantum system to a target state, yielding the globally optimal solution with probability over $90$+%. However, realizing QAA for application-scale optimization currently exceeds quantum hardware capacity, which is further compounded by unresolved algorithmic challenges regarding the choice of free parameters. In this study, we address these issues by utilizing a realistic traffic flow QUBO problem to investigate the implementation of QAA as a heuristic solver. Specifically, allowing the diffusion operator parameter to take non-$π$ values expands the capabilities of QAA. This unlocks a new multiple-shot, low-iteration strategy that aims for a high cumulative probability rather than maximizing the probability of a single basis state. Using $25$-qubit simulations, our results demonstrate that heuristic QAA addresses two of the main challenges cited in previous studies. Firstly, heuristic QAA works even at a single iteration, reducing circuit depth by orders of magnitude compared to standard QAA. And secondly, we show that the problem-dependent parameters necessary for reaching optimal algorithmic performance can be reliably approximated with minimal upfront classical computing overhead.

Related papers

• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  Existing techniques rely on qubit reduction at the cost of information loss, leading to degraded computational performance.<n>We propose the Equivalence-preserving Qubit Efficient QAOA, which significantly reduces the required number of qubits without degrading performance.<n>We show that it is broadly applicable to large-scale optimization problems, excluding only unconstrained problems with completely independent variables.
  arXiv  Detail & Related papers  (2026-04-20T13:57:49Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Quantum molecular docking with quantum-inspired algorithm [4.959284967789063]
  We propose a novel quantum molecular docking (QMD) approach based on QA-inspired algorithm. We construct two binary encoding methods to efficiently discretize the degrees of freedom with exponentially reduced number of bits. We show that QMD has shown advantages over the search-based Auto Vina and the deep-learning DIFFDOCK in both re-docking and self-docking scenarios.
  arXiv  Detail & Related papers  (2024-04-12T06:24:45Z)
• Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem [3.3682090109106446]
  We propose the Variational Quantum Algorithm-Preserving Feasible Space (VQA-PFS) ansatz. This ansatz applies mixed operators on constrained variables while employing Hardware-Efficient Ansatz (HEA) on unconstrained variables. The numerical results demonstrate that VQA-PFS significantly enhances the success probability and exhibits faster convergence.
  arXiv  Detail & Related papers  (2023-12-12T01:36:49Z)
• 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)
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem [8.738180371389097]
  The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem. We observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers.
  arXiv  Detail & Related papers  (2023-08-04T14:17:21Z)
• Challenges of variational quantum optimization with measurement shot noise [0.0]
  We study the scaling of the quantum resources to reach a fixed success probability as the problem size increases. Our results suggest that hybrid quantum-classical algorithms should possibly avoid a brute force classical outer loop.
  arXiv  Detail & Related papers  (2023-07-31T18:01:15Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• 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)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
  arXiv  Detail & Related papers  (2021-05-14T11:31:14Z)

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.