Main Content

maxcut2qubo

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

Since R2024b

collapse all in page

    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.

    example

    Examples

    collapse all

    This example uses:

    Open Live Script

    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)

    Figure contains an axes object. The axes object contains an object of type graphplot.

    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

    collapse all

    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

    See Also

    Functions

    Objects

    Topics