maxcut2qubo

Convert max-cut problem to QUBO (Quadratic Unconstrained Binary Optimization)

Since R2024b

Installation Required: This functionality requires MATLAB Support Package for Quantum Computing.

Syntax

qprob = maxcut2qubo(G)

Description

qprob = maxcut2qubo(G) converts a max-cut problem given by the graph G to an equivalent QUBO formulation as a qubo object.

Examples

Convert Graph to QUBO

Create and plot a graph that represents a max-cut problem.

s = [1 1 1 2 3 4];
t = [2 4 5 3 4 5];
G = graph(s,t);
plot(G)

Convert the graph to a QUBO problem.

qprob = maxcut2qubo(G)

qprob = 
  qubo with properties:

    QuadraticTerm: [5×5 double]
       LinearTerm: [5×1 double]
     ConstantTerm: 0
     NumVariables: 5

Solve the QUBO problem using QAOA.

result = solve(qprob,Algorithm=qaoa)

 
Exiting: Maximum number of function evaluations has been exceeded
         - increase MaxFunEvals option.
         Current function value: -3.600000 

result = 
  quboResult with properties:

                BestX: [5×1 double]
    BestFunctionValue: -5
      AlgorithmResult: [1×1 qaoaResult]

Examine the results. The solution to the max-cut problem for this graph is a cut across five edges that partitions the vertices into two groups, with vertices 1, 3, and 5 in one group and vertices 2 and 4 in another.

result.BestX

ans = 5×1

     0
     1
     0
     1
     0

Input Arguments

G — Max-cut graph

graph object

Max-cut graph, specified as a graph object. The graph must not contain self-loops.

References

[1] J., Abhijith, Adetokunbo Adedoyin, John Ambrosiano, Petr Anisimov, William Casper, Gopinath Chennupati, Carleton Coffrin, et al. “Quantum Algorithm Implementations for Beginners.” ACM Transactions on Quantum Computing 3, no. 4 (December 31, 2022): 1–92. https://doi.org/10.1145/3517340.

[2] Zhou, Leo, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices.” Physical Review X 10, no. 2 (June 24, 2020): 021067. https://doi.org/10.1103/PhysRevX.10.021067.

Version History

Introduced in R2024b