Related Experiment Video
Updated: Jan 3, 2026
05:30
Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
1.0K
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.
Scientific Reports
|November 22, 2019
Summary
This study introduces quantum annealing for the theory of cuts, formulating the Minimum Multicut Problem into QUBO. Researchers explored technical challenges and tradeoffs for D-Wave quantum annealers.
Area of Science:
- Theoretical Computer Science
- Quantum Computing
Background:
- Quantum annealing offers a novel approach to solving complex combinatorial optimization problems.
- NP-hard problems, characterized by complex energy landscapes, benefit from quantum fluctuations to escape local minima.
Purpose of the Study:
- To propose and evaluate the application of quantum annealing for the theory of cuts.
- To formulate the Minimum Multicut Problem (MMP) into a Quadratic Unconstrained Binary Optimization (QUBO) representation.
Main Methods:
- Developed two distinct constructions for QUBO functions tailored to the Minimum Multicut Problem.
- Investigated technical difficulties in embedding and submitting problems to quantum annealer processors.
- Performed numerical scaling analysis comparing classical approaches.
Main Results:
- Presented two QUBO formulations for the Minimum Multicut Problem.
- Analyzed tradeoffs between the different QUBO mappings.
- Provided numerical scaling analysis results.
Conclusions:
- Quantum annealing presents a viable, albeit challenging, approach for the theory of cuts.
- Identified key challenges and tradeoffs for implementing MMP QUBO formulations on current D-Wave quantum annealers.
Related Concept Videos
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
247
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
247
01:17Ampere-Maxwell's Law: Problem-Solving
1.0K
A parallel-plate capacitor with capacitance C, whose plates have area A and separation distance d, is connected to a resistor R and a battery of voltage V. The current starts to flow at t = 0. What is the displacement current between the capacitor plates at time t? From the properties of the capacitor, what is the corresponding real current?
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...
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...
1.0K
01:28Synthetic Disvision of Polynomials
110
Synthetic division is an efficient algorithmic approach for dividing a polynomial by a linear binomial of the form x - c, where c is a real number. This method is helpful due to its streamlined process, which avoids the more cumbersome steps involved in the traditional long division of polynomials. It simplifies computation and serves as a practical tool for evaluating polynomials and identifying their factors.To perform synthetic division, one begins by listing the coefficients of the...
110
01:22Block Diagram Reduction
475
The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
475
01:34Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.7K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.7K
01:26Cartesian Form for Vector Formulation
1.0K
The Cartesian form for vector formulation is a process to calculate the moment of force using the position and force vectors. The moment of force is defined as the cross-product of these vectors, making it a vector quantity. The Cartesian form of the position and force vectors involves unit vectors, which can be used to express the cross-product in determinant form.
1.0K