A quantum feasibility preserving modeling for the min cut problem

Ali Abbassi, Yann Dujardin, Eric Gourdin, Philippe Lacomme, Caroline Prodhon

arXivarxiv/2602.22943Feb 26, 2026quant-phscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.22943
curl -X POST /api/v1/records/arxiv/2602.22943/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.22943/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'