QED driven QAOA for network-flow optimization

• URL: http://arxiv.org/abs/2006.09418v3
• Date: Thu, 22 Jul 2021 19:10:13 GMT
• Title: QED driven QAOA for network-flow optimization
• Authors: Yuxuan Zhang, Ruizhe Zhang and Andrew C. Potter
• Abstract summary: We present a framework for modifying quantum approximate optimization algorithms (QAOA) to solve constrained network flow problems. By exploiting an analogy between flow constraints and Gauss's law for electromagnetism, we design lattice quantum electrodynamics inspired mixing Hamiltonians that preserve flow constraints throughout the QAOA process.
• Score: 17.745108999585867
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We present a general framework for modifying quantum approximate optimization algorithms (QAOA) to solve constrained network flow problems. By exploiting an analogy between flow constraints and Gauss's law for electromagnetism, we design lattice quantum electrodynamics (QED) inspired mixing Hamiltonians that preserve flow constraints throughout the QAOA process. This results in an exponential reduction in the size of the configuration space that needs to be explored, which we show through numerical simulations, yields higher quality approximate solutions compared to the original QAOA routine. We outline a specific implementation for edge-disjoint path (EDP) problems related to traffic congestion minimization, numerically analyze the effect of initial state choice, and explore trade-offs between circuit complexity and qubit resources via a particle-vortex duality mapping. Comparing the effect of initial states reveals that starting with an ergodic (unbiased) superposition of solutions yields better performance than beginning with the mixer ground-state, suggesting a departure from the "short-cut to adiabaticity" mechanism often used to motivate QAOA.

Related papers

• MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
  Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling optimization challenges. The requisite circuit depth for satisfactory performance is problem-specific and often exceeds the maximum capability of current quantum devices. We introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians.
  arXiv  Detail & Related papers  (2024-09-27T12:28:18Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Quantum Alternating Operator Ansatz (QAOA) beyond low depth with gradually changing unitaries [0.0]
  We study the underlying mechanisms governing the behavior of Quantum Alternating Operator Ansatz circuits. We use the discrete adiabatic theorem, which complements and generalizes the insights obtained from the continuous-time adiabatic theorem. Our analysis explains some general properties that are conspicuously depicted in the recently introduced QAOA performance diagrams.
  arXiv  Detail & Related papers  (2023-05-08T04:21:42Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  We propose a novel neural algorithm for the fundamental problem of computing the entropic optimal transport (EOT) plan between continuous probability distributions. Our algorithm is based on the saddle point reformulation of the dynamic version of EOT which is known as the Schr"odinger Bridge problem. In contrast to the prior methods for large-scale EOT, our algorithm is end-to-end and consists of a single learning step.
  arXiv  Detail & Related papers  (2022-11-02T14:35:13Z)
• Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions [0.0]
  We study how the accuracy of approximate solutions affect the performance of the warm-start QAOA (WS-QAOA) We find that WS-QAOA tends to outperform QAOA as approximate solutions become closer to the exact solutions in terms of the Hamming distance. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having a better result than QAOA especially when the circuit is relatively shallow.
  arXiv  Detail & Related papers  (2022-09-07T05:26:48Z)
• An entanglement perspective on the quantum approximate optimization algorithm [0.0]
  We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits. We also investigate the entanglement spectrum in connection with random matrix theory.
  arXiv  Detail & Related papers  (2022-06-14T17:37:44Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices. We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
  arXiv  Detail & Related papers  (2022-04-11T14:11:24Z)
• 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)
• Quantum Approximate Optimization Algorithm applied to the binary perceptron [0.46664938579243564]
  We apply digitized Quantum Annealing (QA) and Quantum Approximate Optimization Algorithm (QAOA) to a paradigmatic task of supervised learning in artificial neural networks. We provide evidence for the existence of optimal smooth solutions for the QAOA parameters, which are transferable among typical instances of the same problem. We prove numerically an enhanced performance of QAOA over traditional QA.
  arXiv  Detail & Related papers  (2021-12-19T18:33:22Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)
• 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.