tsp2qubo

Convert traveling salesperson problem to QUBO (Quadratic Unconstrained Binary Optimization)

Since R2025b

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

Syntax

qprob = tsp2qubo(D)

qprob = tsp2qubo(G)

qprob = tsp2qubo(___,Penalty=val)

Description

qprob = tsp2qubo(D) converts a traveling salesperson problem given by a distance matrix to an equivalent QUBO formulation as a qubo object.

qprob = tsp2qubo(G) converts a traveling salesperson problem given by a fully connected graph to an equivalent QUBO formulation as a qubo object.

qprob = tsp2qubo(___,Penalty=val) also specifies a scalar penalty factor to penalize the constraints in the equivalent QUBO formulation for either of the previous syntaxes.

Examples

Convert Traveling Salesperson Problem Matrix to QUBO

Define a traveling salesperson problem by creating a matrix of distances in miles between five cities. Assign names to the cities. The (i,j)th element of the matrix represents the distance between city i and city j. For example, D(1,2) = 284 indicates that the distance between London and Paris is 284 miles.

D = [0 284 1071 681 1100;
     284 0 792 655 885;
     1071 792 0 1442 1344;
     681 655 1442 0 935;
     1100 885 1344 935 0];
names = ["London" "Paris" "Madrid" "Berlin" "Rome"];

Convert the distance matrix to a QUBO problem.

qprob = tsp2qubo(D)

qprob = 
  qubo with properties:

    QuadraticTerm: [25×25 double]
       LinearTerm: [25×1 double]
     ConstantTerm: 14420
     NumVariables: 25

Solve the QUBO problem.

result = solve(qprob)

result = 
  quboResult with properties:

                BestX: [25×1 double]
    BestFunctionValue: 4036
      AlgorithmResult: [1×1 tabuSearchResult]

Convert the result of the QUBO problem to the traveling salesperson formulation. The returned numeric index vector indicates the order the cities are visited.

order = quboResult2tsp(result)

order = 1×5

     3     2     1     4     5

names(order)

ans = 1×5 string
    "Madrid"    "Paris"    "London"    "Berlin"    "Rome"

Convert Traveling Salesperson Problem Graph to QUBO

Create and plot a fully connected graph of five connected cities with weighted edges corresponding to the distances in miles between the cities. Assign names to the cities.

D = [0 284 1071 681 1100;
    284 0 792 655 885;
    1071 792 0 1442 1344;
    681 655 1442 0 935;
    1100 885 1344 935 0];
names = ["London" "Paris" "Madrid" "Berlin" "Rome"];
G = graph(D,names,"omitselfloops");
plot(G,EdgeLabel=G.Edges.Weight);

Convert the graph to a QUBO problem and solve it.

qprob = tsp2qubo(G);
result = solve(qprob)

result = 
  quboResult with properties:

                BestX: [25×1 double]
    BestFunctionValue: 4036
      AlgorithmResult: [1×1 tabuSearchResult]

Convert the result of the QUBO problem to the traveling salesperson formulation.

[order,tourGraph] = quboResult2tsp(result,G)

order = 5×1 cell
    {'Madrid'}
    {'Paris' }
    {'London'}
    {'Berlin'}
    {'Rome'  }

tourGraph = 
  graph with properties:

    Edges: [5×2 table]
    Nodes: [5×1 table]

Plot the resulting tour over the fully connected graph by specifying greater line widths for edges in G.Edges that correspond to the edges in tourGraph.Edges.

idxTour = findedge(G,order,circshift(order,-1));
LWidths = 0.5*ones(1,numedges(G));
LWidths(idxTour) = 5;
plot(G,EdgeLabel=G.Edges.Weight,LineWidth=LWidths)

Input Arguments

D — Distance matrix

square matrix

Distance matrix, specified as a square matrix. The value of D(i,j) corresponds to the distance between city i and city j. The matrix must be symmetric or triangular, and the diagonal values must be 0.

Data Types: double

G — Cities graph

graph object

Cities graph, specified as a graph object. The graph must be fully connected and cannot contain self-loops. Each graph node represents a city. The weight of an edge between two nodes of the graph represents the distance between two cities.

val — Penalty factor

1 (default) | numeric scalar

Penalty factor, specified as a numeric scalar. The penalty factor dictates the importance of the problem constraints. If any of the following constraints is not satisfied in the traveling salesperson solution obtained using quboResult2tsp, try increasing the penalty factor:

• Each city must be visited.

• Each city must have two edges: one edge when arriving and one edge when departing.

• The tour must begin and end in the same city.

Data Types: double

Output Arguments

qprob — QUBO formulation

qubo object

QUBO formulation, returned as a qubo object.

More About

Traveling Salesperson Problem

The classic traveling salesperson problem involves a group of cities (locations) that a salesperson must visit. Given the distances between each city, the problem is to minimize the total distance the salesperson travels while visiting each city only once and returning to the starting city.

References

[1] Feld, Sebastian, Christopher Roch, Thomas Gabor, et al. "A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer." Frontiers in ICT 6 (June 2019): 1–13. https://doi.org/10.48550/arXiv.1811.07403.

Version History

Introduced in R2025b