Related Experiment Video
Updated: Jan 3, 2026

Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
A QUBO Formulation of Minimum Multicut Problem Instances in Trees for D-Wave Quantum Annealers
William Cruz-Santos1, Salvador E Venegas-Andraca2, Marco Lanzagorta3
1CU-UAEM Valle de Chalco, Hermenegildo Galeana 3, Valle de Chalco, Estado de México, 56615, Mexico.
Abstract:
Quantum annealing algorithms were introduced to solve combinatorial optimization problems by taking advantage of quantum fluctuations to escape local minima in complex energy landscapes typical of NP - hard problems. In this work, we propose using quantum annealing for the theory of cuts, a field of paramount importance in theoretical computer science. We have proposed a method to formulate the Minimum Multicut Problem into the QUBO representation, and the technical difficulties faced when embedding and submitting a problem to the quantum annealer processor. We show two constructions of the quadratic unconstrained binary optimization functions for the Minimum Multicut Problem and we review several tradeoffs between the two mappings and provide numerical scaling analysis results from several classical approaches. Furthermore, we discuss some of the expected challenges and tradeoffs in the implementation of our mapping in the current generation of D-Wave machines.
Related Concept Videos
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Ampere-Maxwell's Law: Problem-Solving
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of the...
Synthetic Disvision of Polynomials
Block Diagram Reduction
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
Cartesian Form for Vector Formulation

