Quantum Approaches to the Minimum Edge Multiway Cut Problem

• URL: http://arxiv.org/abs/2601.00720v1
• Date: Fri, 02 Jan 2026 15:26:36 GMT
• Title: Quantum Approaches to the Minimum Edge Multiway Cut Problem
• Authors: Ali Abbassi, Yann Dujardin, Eric Gourdin, Philippe Lacomme, Caroline Prodhon,
• Abstract summary: We investigate the minimum edge multiway cut problem, a fundamental task in evaluating the resilience of telecommunication networks.<n>We benchmark the problem across three quantum computing paradigms: quantum annealing on a D-Wave quantum processing unit, photonic variational quantum circuits simulated on Quandela s Perceval platform, and IBM s gate-based Quantum Approximate Optimization Algorithm (QAOA)
• Score: 1.3701366534590498
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We investigate the minimum edge multiway cut problem, a fundamental task in evaluating the resilience of telecommunication networks. This study benchmarks the problem across three quantum computing paradigms: quantum annealing on a D-Wave quantum processing unit, photonic variational quantum circuits simulated on Quandela s Perceval platform, and IBM s gate-based Quantum Approximate Optimization Algorithm (QAOA). We assess the comparative feasibility of these approaches for early-stage quantum optimization, highlighting trade-offs in circuit constraints, encoding overhead, and scalability. Our findings suggest that quantum annealing currently offers the most scalable performance for this class of problems, while photonic and gate-based approaches remain limited by hardware and simulation depth. These results provide actionable insights for designing quantum workflows targeting combinatorial optimization in telecom security and resilience analysis.

Related papers

• Assessing Quantum Annealing to Solve the Minimum Vertex Multicut [1.3701366534590498]
  Cybersecurity in telecommunication networks often leads to hard optimization problems that are challenging to solve with classical methods.<n>This work investigates the practical feasibility of using quantum annealing to address the Restricted Vertex Minimum Multicut Problem.<n>We analyze key aspects of the quantum workflow including minor embedding techniques, chain length, topology constraints, chain strength selection, unembedding procedures, and postprocessing.
  arXiv  Detail & Related papers  (2026-01-02T15:09:30Z)
• VQC-MLPNet: An Unconventional Hybrid Quantum-Classical Architecture for Scalable and Robust Quantum Machine Learning [50.95799256262098]
  Variational quantum circuits (VQCs) hold promise for quantum machine learning but face challenges in expressivity, trainability, and noise resilience.<n>We propose VQC-MLPNet, a hybrid architecture where a VQC generates the first-layer weights of a classical multilayer perceptron during training, while inference is performed entirely classically.
  arXiv  Detail & Related papers  (2025-06-12T01:38:15Z)
• Provably Robust Training of Quantum Circuit Classifiers Against Parameter Noise [49.97673761305336]
  Noise remains a major obstacle to achieving reliable quantum algorithms.<n>We present a provably noise-resilient training theory and algorithm to enhance the robustness of parameterized quantum circuit classifiers.
  arXiv  Detail & Related papers  (2025-05-24T02:51:34Z)
• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  We introduce a comprehensive benchmarking framework designed to evaluate quantum optimization techniques against well-established NP-hard problems.<n>Our framework focuses on key problem classes, including the Multi-Dimensional Knapsack Problem (MDKP), Maximum Independent Set (MIS), Quadratic Assignment Problem (QAP), and Market Share Problem (MSP)
  arXiv  Detail & Related papers  (2025-03-15T13:02:22Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Quantum Neural Architecture Search with Quantum Circuits Metric and Bayesian Optimization [2.20200533591633]
  We propose a new quantum gates distance that characterizes the gates' action over every quantum state. Our approach significantly outperforms the benchmark on three empirical quantum machine learning problems.
  arXiv  Detail & Related papers  (2022-06-28T16:23:24Z)
• Squeezing and quantum approximate optimization [0.6562256987706128]
  Variational quantum algorithms offer fascinating prospects for the solution of optimization problems using digital quantum computers. However, the achievable performance in such algorithms and the role of quantum correlations therein remain unclear. We show numerically as well as on an IBM quantum chip how highly squeezed states are generated in a systematic procedure.
  arXiv  Detail & Related papers  (2022-05-20T18:00:06Z)
• Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
  We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most. We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
  arXiv  Detail & Related papers  (2022-04-12T19:39:31Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)

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.