A quantum feasibility preserving modeling for the min cut problem

• URL: http://arxiv.org/abs/2602.22943v1
• Date: Thu, 26 Feb 2026 12:34:59 GMT
• Title: A quantum feasibility preserving modeling for the min cut problem
• Authors: Ali Abbassi, Yann Dujardin, Eric Gourdin, Philippe Lacomme, Caroline Prodhon,
• Abstract summary: We study the minimum cut problem in weighted undirected graphs using variational quantum algorithms.<n>We employ a ring structured XY mixer that restricts the quantum evolution to the subspace of valid cut configurations.
• Score: 1.3701366534590498
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the minimum cut problem in weighted undirected graphs using variational quantum algorithms in which only feasible cut configurations are explored. Although minimum cut admits efficient classical solutions, it is a fundamental component of more complex network optimization problems such as multicut and network interdiction. Our objective is to examine quantum models in which feasibility is preserved by the mixer dynamics, without introducing penalty terms in the cost Hamiltonian. We employ a ring structured XY mixer that restricts the quantum evolution to the subspace of valid cut configurations, ensuring that all sampled states correspond to feasible solutions. To address scalability limitations, we suggest an iterative metaheuristic strategy that decomposes large instances into smaller subproblems solved sequentially using the same quantum model. The results obtained using the mixer indicate that the initial probability distribution can be systematically controlled, thereby enabling the development of warm start techniques within variational quantum based algorithms.

Related papers

• Tensor Network Assisted Distributed Variational Quantum Algorithm for Large Scale Combinatorial Optimization Problem [19.046113542182436]
  We propose the Distributed Variational Quantum Algorithm (DVQA) for solving Combinatorial Optimization Problems (COPs)<n>A key innovation of DVQA is its use of the truncated higher-order singular value decomposition to preserve inter-variable dependencies without relying on complex long-range entanglement.<n> Empirically, DVQA achieves state-of-the-art performance in simulations and has been experimentally validated on the Wu Kong quantum computer for portfolio optimization.
  arXiv  Detail & Related papers  (2026-01-20T13:31:02Z)
• Quantum remeshing and efficient encoding for fracture mechanics [0.5541644538483946]
  We present a variational quantum algorithm for structural mechanical problems, specifically addressing crack opening simulations.<n>Our approach provides an alternative solution for a relevant 2D case by implementing a parametrized quantum circuit.<n>Our method has been experimentally validated on Quandela's photonic quantum processor Ascella.
  arXiv  Detail & Related papers  (2025-10-16T14:50:59Z)
• Quantum Random Feature Method for Solving Partial Differential Equations [36.58357595906332]
  Quantum computing holds promise for scientific computing due to its potential for exponential speedups over classical methods.<n>In this work, we introduce a quantum random method (QRFM) that leverages advantages from both numerical analysis and neural analysis.
  arXiv  Detail & Related papers  (2025-10-09T08:42:09Z)
• RhoDARTS: Differentiable Quantum Architecture Search with Density Matrix Simulations [44.13836547616739]
  Variational Quantum Algorithms (VQAs) are a promising approach to leverage Noisy Intermediate-Scale Quantum (NISQ) computers.<n> choosing optimal quantum circuits that efficiently solve a given VQA problem is a non-trivial task.<n>Quantum Architecture Search (QAS) algorithms enable automatic generation of quantum circuits tailored to the provided problem.
  arXiv  Detail & Related papers  (2025-06-04T08:30:35Z)
• Qubit-efficient quantum local search for combinatorial optimization [0.0]
  We present a qubit-efficient variational quantum algorithm that implements a quantum version of local search with only $lceil log l rceil$ qubits.<n>This achievement highlights the algorithm's potential for solving large-scale optimization problems on near-term quantum devices.
  arXiv  Detail & Related papers  (2025-02-04T11:44:34Z)
• Designing Minimalistic Variational Quantum Ansatz Inspired by Algorithmic Cooling [0.0]
  This study introduces a novel minimalistic variational quantum ansatz inspired by algorithmic cooling principles.<n>The proposed Heat Exchange algorithmic cooling ansatz (HE ansatz) facilitates efficient population redistribution without requiring bath resets.<n>We also proposed a new variational algorithm that utilize HE ansatz to compute the ground state of impure dissipative-system variational quantum eigensolver.
  arXiv  Detail & Related papers  (2025-01-28T07:59:33Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• A Neural-Network Variational Quantum Algorithm for Many-Body Dynamics [15.435967947933404]
  We propose a neural-network variational quantum algorithm to simulate the time evolution of quantum many-body systems. The proposed algorithm can be efficiently implemented in near-term quantum computers with low measurement cost.
  arXiv  Detail & Related papers  (2020-08-31T02:54:09Z)

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.