Quantum computing for a profusion of postman problem variants

Quantum annealing exploits the quantum-mechanical effects of superposition, entanglement, and tunneling to explore the energy landscape in an efficient manner Lanting et al (2014); Santoro and Tosatti (2006) when sampling from energy-based models. NP-hard combinatorial optimization problems are formulated as either an Ising model or quadratic unconstrained binary optimization (QUBO) problem that can be run on a D-Wave quantum annealer (QA). QUBO as well as Ising model are formulations that both belong to the class of binary quadratic models (BQM). A BQM is a problem consisting of a collection of binary-valued variables (variables that can be assigned two values, for example -1, 1) with associated linear and quadratic biases. The Ising model objective function is

where \(s_{i} \in \) \(\{-1,+1\}\) are the spin variables, while \(h_{i}\) and \(J_{ij}\) are, respectively, biases on, and strengths between spins.

Quantum computers use qubits to encode information. Their behavior is governed by the laws of quantum mechanics. This allows a qubit to be in a “superposition” state which means it can be both a “\(-1\)” and a “\(+1\)” at the same time. An outside event causes it to collapse into either. The annealing process results in a low-energy ground state, g, which consists of an Ising spin for each qubit.

While solving a combinatorial optimization problem, QAs are typically limited by the number of variables which can be represented and embedded in the hardware graph topology. During the embedding process each logical variable maps to a chain of qubits. The D-Wave 2000Q QA uses a Chimera topology with more than 2000 qubits and more than 6000 couplers. In the Chimera topology the qubits per unit cell are 8. Each qubit is connected to 4 orthogonal qubits through internal couplers and each qubit is coupled to 6 different qubits. This allows a fully connected graph (or clique) of 64 nodes (or variables) to be embedded in the sparse Chimera graph. The newer D-Wave Advantage uses a Pegasus topology with over 5000 qubits and more than 35, 000 couplers. In the Pegasus topology the qubits per unit cell are 24. Each qubit is coupled to 15 different qubits. The largest embeddable clique size is 177 McGeoch and Farré (2021).

QAs proved to be useful for solving NP-hard optimization problems such as those involved in graph theory Mniszewski et al (2021); Negre et al (2020); Ushijima-Mwesigwa et al (2017) and machine learning Dixit et al (2021); O’Malley et al (2018) among others. The QUBO formulation is most commonly used for optimization problems. The objective function is

where \(x_{i} \in \) \(\{0,1\}\) encodes the inputs and results. The symmetric matrix, Q, is formulated such that the weights on the diagonal correspond to the linear terms, while the off-diagonal weights are the quadratic terms. Ising model to a QUBO model transformation is related through \(s = 2x - 1\).

Constraints on current D-Wave architectures include limited precision and range on weights and strengths, sparse connectivity, and number of available qubits. These constraints impact both the size of the problems that can be run and the solver performance. A QUBO matrix is mapped onto the hardware using an embedding algorithm such as minorminer D-Wave Systems Inc. (2021). A hybrid quantum-classical approach is required when the number of problem variables is too large to run directly on the D-Wave hardware. In that case, the quantum-classical qbsolv sampler is used Booth et al 2017. Other efforts have also explored relevant work on experimental classical, quantum, and hybrid methods using QA Asproni et al (2020); Bass et al (2021).

This paper presents a routing problem known as the Chinese Postman Problem (CPP) as well as many of its variants in the context of finding solutions with a QA. The details for what the CPP is and how this will relate to QA is discussed in detail in Sect. 3, but let us provide a brief explanation now. Given a graph, the type of graph with vertices and edges, the most classic version of the CPP problem is the one which asks for the most efficient walk in the graph which traverses every edge. The careful reader may note this problem is quite similar to the more famous Traveling Salesman Problem. The solutions to the CPP have many real-world applications, some of which are discussed in Sect. 3.1. The applicability of the CPP to real world problems is increased when one allows for more flexibility, such as requiring only a subset of edges be traversed, or more constraints, such as a partial order on edge traversals. The variants of the problem relevant to the paper are defined in more detail in Sect. 3.1. Once one begins to include some of these variants to the CPP, solving the CPP can become computationally difficult classically. The primary aim of this paper is to explore ways to solve the CPP problem on a QA and test if such methods are effective.

The following is an outline for how the paper has been organized. In Sect. 2, we provide some graph theory definitions necessary to understand the problem, followed by an overview of the history of the CPP. In Sect. 3.1, we define many variants of the Postman Problem along with potential applications. Next, in Sect. 3.2, we introduce the Quantum Annealing Workflow for solving the CPP as a QUBO on a QA. In Sect. 3.3, a CPP QA algorithm first put forth by Siloi et al 2021 for solving the Closed Undirected CPP is discussed with potential modifications. Then, we introduce a novel algorithm for using a QA to solve a large class of CPP variants in Sects. 3.4 and 3.5. Finally, we show results from our implementations and discuss observations from our experiments in Sects. 4 and 5 respectively.

2.1 Graph algorithm terminology

The following are definitions about graphs and objects used in the graph algorithms discussed throughout this paper Bondy and Murty (2008).

Definition 1

(Graph) A graph, G, is a triple (V, U, D) where \(V\subset \mathbb {N}\) is a non-empty finite subset, \(U\subset \{([a,b],c) \vert a,b\in V, a\ne b, c\in (\mathbb {R}^+)^2\}\) with \(c = [W_{a,b}, W_{b,a}]\), and \(D\subset \{((a,b),W_{a,b}) \vert a,b\in V, W_{a,b}\in \mathbb {R}^+\}.\) We shall refer to V as vertices, U as undirected edges, and D as directed edges. Undirected edges and directed edges are labeled as [a, b], (a, b), respectively, while \(W_{a,b}\) is the weight of the edge from vertex a to vertex b. We refer to \(E = U\bigcup D\) as the edges. Note \((*,...,*)\) is used to denote an ordered tuple and \([*,...,*]\) is used to denoted an unordered tuple.

Definition 2

(Vertex Adjacency) In a graph, G, vertex \(a\in V\) is said to be adjacent to vertex \(b\in V\) if there exists some \(W_{a,b}, W_{b,a}\in \mathbb {R}^+\) so that \(([a,b],[W_{a,b},W_{b,a}])\in U\) or there exists some \(W_{a,b}\in \mathbb {R}^+\) so that \({((a,b),W_{a,b})\in D}\).

Definition 3

(Edge Adjacency) In a graph, G, the edge labeled [a, b] or (a, b) is adjacent to the edge labeled [c, d] or (c, d) if the edges may be written, up to reordering of unordered tuples, so that \(b = c\).

Definition 4

(Walk) A walk of length n in a graph, G, is a tuple of length \(n+1\), \((v_0,...,v_n)\), where \(v_i\) is a vertex adjacent to \(v_{i+1}\) for all i.

Definition 5

(Open/Closed Walk) A walk in a graph is a closed walk if the first and last vertex in the walk are the same. Otherwise the walk is called an open walk.

Definition 6

(Walk Weight) The walk weight of a walk is the sum of all the weights of the edges traversed in the walk. Given a walk \((v_0,...,v_n)\), the walk weight is \(\sum \limits _{i=0}^{n-1}W_{v_i,v_{i+1}}\).

Definition 7

(Trail) A trail is a walk for which no edge is repeated within the walk.

Definition 8

(Circuit) A circuit is a closed trail.

Definition 9

(Eulerian Circuit) An Eulerian circuit is a circuit which includes every edge in the graph.

Definition 10

(In/Out-Degree) A vertex, v, in a graph, G, has in-degree equal to the number of vertices adjacent to v, and out-degree equal to the number of vertices v is adjacent to. In other words, the in-degree of the vertex v is the number of edges which end in v, up to reordering of unordered tuples. The out-degree is similar in reverse.

Definition 11

(Degree) A vertex, v, in an undirected graph, G, has degree equal to its in-degree and out-degree.

Definition 12

(Strongly Connected) A graph G is said to be strongly connected if for every pair of vertices, \(a,b\in V\), there exists a walk in G from vertex a to vertex b.

Definition 13

(Partially Ordered Set) A pair (X,\(\le \)) such that X is a set, \(S\subset X\times X\) (Cartesian product), and \(x\le y\) for \(x,y\in X\) if and only if \((x,y)\in S\), is called a partially ordered set if the following hold for all \(x,y,z\in X\):

1. 1.

   \(x\le x\)

2. 2.

   \(x\le y\) and \(y\le x \implies x = y\)

3. 3.

   \(x\le y\) and \(y\le z \implies x\le z\)

Definition 14

(Perfect Pairing) Let S be a finite set with an even number of elements. Then a perfect pairing of S is a collection of subsets of S, \(A_i\), such that:

1. 1.

   \(\vert A_i\vert \) = 2 for all i

2. 2.

   \(A_i\cap A_j = \emptyset \) for all \(i\ne j\)

3. 3.

   \(\bigcup A_i = S\)

Note our definition of graph precludes multi-graphs and loops. Although if one is very careful with notation, all the concepts in the paper should extend to multi-graphs. One could include loops by adding an additional vertex to the loop edges to eliminate the loops. We shall assume henceforth that all our graphs are strongly connected. Note that in an undirected graph the property connected implies strongly connected and so one may just assume the weaker property, connected, in the undirected case. This strongly connected assumption is used to guarantee the existence of a solution to the CPP. It is worthy of note that some not strongly connected graphs may also have solutions to the CPP and the methods described in this paper would apply in those situations as well. Though our method may have trouble determining if such a solution exists.

2.2 History

The CPP was first posed as a combinatorial optimization problem by the then lecturer at Shandong Normal University, Mei-Gu Guan, in 1960. At that time China was trying to modernize itself as a country and mathematicians were encouraged to work on real-world applications. The original phrasing of the CPP is as follows:

“A postman has to deliver letters to a given neighborhood. He needs to walk through all the streets in the neighborhood and back to the post-office. How can he design his route so that he walks the shortest distance? Grotschel and Yuan (2010)"

This problem is usually modeled as a graph. One does this by considering road intersections as vertices and roads as graphs. Also one should consider the post office itself as a vertex. One then adds weights to the edges based on how long it takes to deliver the mail on that street. The historical version of the CPP was then converted into a question about the least weight walk in the graph which uses every edge. As we will see in Sect. 3 there are many ways to modify this question to enhance its range of uses in real-world problems.

3.1 Variants and applications

The CPP is a general term for a wide variety of routing problems. Each variant of the CPP is often created to optimize a specific application or technical consideration in mind Comaklisokmen et al (2019); Thimbleby (2003). In Table 1, we present the list of CPP variants covered organized by the general category that they belong to and provide the associated specifics of the variant within the category. This is followed by details of each variant from a graph perspective, as well as an example application.

Variant 1

(Undirected CPP) Given an undirected graph, G, find a walk in G which traverses every edge in G with the minimal walk weight.

Application 1

(Neighborhood Pothole Inspection) Imagine one wished to survey the road conditions in a large neighborhood with bidirectional roads. One could represent the neighborhood as an undirected graph with intersections as vertices and the roads as edges and solve the Undirected CPP.

Variant 2

(Directed CPP) Given a directed graph, G, find a walk in G which traverses every edge in G with the minimal walk weight.

Application 2

(Downtown Pothole Inspection) Imagine one wished to survey the road conditions of a city’s downtown containing only one-way streets. One could represent the downtown area as a directed graph with the intersections as vertices and the roads as edges and solve the Directed CPP.

Variant 3

(Mixed CPP) Given a mixed graph, G, find a walk in G which traverses every edge in G with the minimal walk weight.

Application 3

(Town Pothole Inspection) Imagine one wished to survey the road conditions of an entire town which contained one-way streets, two-way streets (e.g. a highway with lanes), and bidirectional streets (e.g. a residential street with no lanes). One could represent the town as a mixed graph with the intersections as vertices, the one/two-way streets as one/two directed edges, and the bidirectional streets as undirected edges, and solve the Mixed CPP.

The above variants determine what types of graphs need to be considered for the problem, which can drastically effect the computational complexity of the problem. Both the undirected and the directed variants are solvable classically in polynomial time, while the mixed variant is NP-Hard Comaklisokmen et al (2019). For any CPP one will need to choose a type of graph to work over as well as where the postman will need to start and/or stop their route. When solving the CPP classically, the start/stop choice will change what algorithm is needed Thimbleby (2003).

Variant 4

(Closed CPP) Given a graph, G, find a walk in G which traverses every edge in G such that the start and stop are on the same vertex, with a minimal walk weight for such a walk.

Application 4

(Tunnel Inspections) Imagine a mine operator wishes to inspect the integrity of the tunnels in her mining operation. The mine has only one entry/exit for its vast and extensive network of tunnels. One could represent the tunnels as edges and the tunnel junctions as vertices and solve the Closed CPP.

Variant 5

(Open CPP) Given a graph, G, find a walk in G which traverses every edge in G with the minimal walk weight.

Application 5

(Museum Cleaning Robot) Imagine a museum wishes to clean their floors using a robot and has two docking stations for the robot start and stop at. The museum wishes to know where to place these docking stations as well as what walk the robot should take so as to clean the museum efficiently. One could represent the rooms as vertices and the hallways between them as edges and solve the Open CPP.

Variant 6

(Open with Endpoints CPP) Given a graph, G, and a starting vertex, \(v_1\), and/or a stopping vertex, \(v_2\), find a walk in G which traverses every edge in G with the minimal walk weight for such walks. This walk starts at \(v_1\) if given and ends at \(v_2\) if given.

Application 6

(Botanical Garden Picnic) Imagine you wish to see every part of the Botanical Garden as efficiently as possible. You may wish to just start at the beginning and finish at the exit or you may wish to start at the beginning and finish somewhere in the garden (you don’t care where) so as to enjoy a picnic. One could represent the paths as edges and the path junctions as vertices and solve the Open with Endpoints CPP.

Now that all of the required variant choices have been laid out, we will introduce some optional variants to modify the CPP. Inclusion of these variants allow the CPP to be applied in a much wider array of applications. Many of the variants can be applied in conjunction with one another so as to be applicable in an even broader set of use cases.

Variant 7

(Rural Postman Problem) Given a graph, G, and a subset, R, of the edges of G, find a walk in G which traverses every edge in R with the minimal walk weight.

Application 7

(Traveling Salesmen) Imagine you were a traveling salesmen who wished to sell your wares in every capital city in every state of the United States of America. One could consider the graph defined with every capital city as a vertex and with an edge (weighted by cost to travel) between every pair of capital cities. Then one could modify this graph by replacing each vertex with two vertices (each with all the original vertices edges) with an edge of weight zero connecting them. Considering only the added edges of weight 0 as our R, one could solve the Rural Postman Problem.

Variant 8

(Windy Postman Problem) Given a graph, G, where \(W_{a,b}\) may not equal \(W_{b,a}\) for undirected edges, as in definition 1, find a walk in G which traverses every edge of G with minimal walk weight.

Application 8

(Injured Hiker) Imagine a rescue team is trying to find an injured hiker on the trails in a mountain range. One could represent the trails as undirected edges and the trail junctions as vertices. One could then account for the differences in difficulties of going uphill versus downhill by assigning different directional weights to the undirected edges and solve the Windy Postman Problem.

Variant 9

(k-Postman Problem With Capacity) Given a graph, G, \(k\in \mathbb {N}\), and \(\{c_1,...,c_k\}\subset (\mathbb {R}\cup \{\infty \})^k\), find k walks in G such that each edge in G is covered by at least one of the k walks, the i^th walk weight is less than or equal to \(c_i\) for \(i\in \{1,...,k\}\), and the sum of walk weights are minimized.

Application 9

(Postal Service) Imagine you were in charge of your local area postal service and had 10 postal agents/ vehicles in your employ. You need to deliver mail to every street in your region in an efficient way, but no postal worker may work more than an 8 h workday by law. One could represent every street as an edge and every street intersection as a vertex and solve the k-Postman Problem With Capacity.

Variant 10

(Service-Based Traversal Postman Problem) Given a graph, G, modify the graph so as to create a duplicate of each edge, without duplicating any vertices. The duplicated edges may have a different weight. Note that each pair of vertices which had only one edge now has two edges between them. All the original edges will be called servicing edges, while all the added edges will be called traversal edges. One should then solve the Rural Postman Problem on all the servicing edges.

Application 10

(Pipe Repairman) Imagine your were a pipe repairman and you had an extensive network of pipes to repair. It takes you 1 h to repair 10 meters of pipe and 10 minutes to pull your pipe fixing supplies that same distance. One could represent the pipes as edges and the pipe-splitting junctions as vertices and solve the Service-Based Traversal Postman Problem.

Variant 11

(Turning Challenge Postman Problem) Given a graph, G, and a collection of \(3-\)tuples in the form (edge-in, edge-out, bonus weight), we shall, with regard to the collection of \(3-\)tuples, sum the corresponding bonus weights for each instance where edge-in is followed by edge-out in the walk. We will call this sum, extra weight. Find a walk which traverses every edge in G where the sum of the walk weight and extra weight is minimized.

Application 11

(Street Cleaner) Imagine your job was to clean the streets in a North American city where there are lights and stop-signs. In general, it is faster to go right or straight than it is to make a left turn or a u-turn. One could form a collection of \(3-\)tuples by, for each road, r, making \(3-\)tuples of the form (r, s, w) for each road, s, which could follow r, with w being the added time it takes to make such a turn. Then one could represent each road as an edge and each intersection as a vertex and solve the Turning Challenge Postman Problem.

Variant 12

(Hierarchical Postman Problem) Given a graph, G, for which the edges, E, have a partial ordering, find a Service/Traversal Postman Problem solution constrained by the edges needing to be serviced in an order congruous to the partial order.

Application 12

(Forgotten Packages) Imagine you were a delivery person in a town and yesterday several packages were delivered to the wrong address. Now you must deliver today’s packages as well as pick-up and redeliver the misdelivered packages. One could represent roads as edges and the intersections as nodes. Then one could place a partial ordering on the edges so that a street with a package which was misdelivered yesterday must come before the street with the intended destination of the package. One could then solve the Hierachical Postman Problem.

Quantum Annealing Workflow

Full size image

3.2 Foundations for solving a problem on a quantum annealing device

At its core, QAs are machines which are meant to solve one kind of problem extremely well. Fortunately, that problem is NP-Complete Lewis Glover (2017) and many useful problems may efficiently be converted into an instance of this problem. Ising model and QUBO formulations of the aforementioned problems can be solved on a QA. We will frame the CPP problem as a Polynomial Version QUBO (see Definition 16 below).

Definition 15

(Matrix Version: QUBO Problem) Given \(Q\in M_n(\mathbb {R})\), find

constrained by

Definition 16

(Polynomial Version: QUBO Problem) Given \(q_{ij}\in \mathbb {R}\) for \(i,j\in \{1,...,n\}\), find

constrained by \(x_i\in \{0,1\}\text { for all }i\).

Once one realizes that any binary variable \(x\in \{0,1\}\) has the property \(x^2 = x\) Glover et al (2022), the equivalence of the two versions becomes clear upon inspection. Now that we have defined what a QUBO is, we outline the individual steps involved in solving a problem with a QUBO formulation on a QA (see Fig. 1).

3.3 Closed undirected CPP

According to a literature review completed by the authors, the first and only previous work done on the subject of using a QA to solve the CPP in any form was done by Siloi et al. in “Investigating the Chinese Postman Problem on a Quantum Annealer” Siloi et al (2021) which solved the Closed Undirected CPP.

Below we outline our implementation for solving the Closed Undirected CPP (variants 1, 4) in Algorithm 1. Note the Closed Undirected CPP is the Closed CPP on an Undirected graph. The reason why this algorithm works is a consequence of the following two theorems.

Solving the Closed Undirected CPP on a QA.

Theorem 1

(Euler Circuit Criterion) Given an undirected graph, G, G contains an Eulerian circuit if and only if every vertex in G is of even degree.

Upon inspection it should be obvious that if an Eulerian circuit exists in your graph, then, that Eulerian circuit will be an optimal solution. Additionally, if there exists an Eulerian circuit, then it can be found in polynomial time Ye and Yu (2011). An example implementation of the algorithm for finding an Eulerian Circuit is in NetworkX Hagberg et al (2008).

Definition 17

(Perfect Pairing Weight) Let G be a graph. Let S be a subset of vertices of G such that there exists a perfect pairing, P, of S, \(\{(a_1,b_1),...,(a_n,b_n)\}\). Let \(W_i\) be the weight of the minimal path between \(a_i\) and \(b_i\). Then the perfect pairing weight of P is \(\sum W_i\).

Theorem 2

Let G be an undirected graph. Let W = the sum of all the edge weights in G.

1. 1.

   For every perfect pairing of the vertices of odd degree one can make a closed walk in G which traverses every edge in G and whose walk weight minus W is equal to the perfect pairing weight

2. 2.

   For every closed walk in G, there is a perfect pairing of the vertices of odd degree in G such that the walk weight minus W is greater than or equal to the perfect pairing weight

Proof

Let G be an undirected graph. Let us begin with part one. Suppose we have a perfect pairing of the vertices of odd degree labeled as \(\{(a_0,b_0),...,(a_n,b_n)\}\). Let \(W_i\) be the weight of the minimal path from \(a_i\) to \(b_i\). Now consider a new graph \(G'\) defined the same as G, but with precisely one edge added between each pair of vertices \(a_i,b_i\) with weight \(W_i\). Note that \(G'\) may be a multi-graph. By construction, every vertex in \(G'\) is of even degree, so by the Euler Circuit Criterion we know there exists an Eulerian circuit in \(G'\). Now we may pipe this Eulerian circuit in \(G'\) to a closed walk which traverses every edge in G. We do this by taking the same walk in G that was given to us in \(G'\), except when told to traverse one of the added edges between an \(a_i\) and a \(b_i\), one instead traverses a minimal path between \(a_i\) and \(b_i\). One observes that this closed walk does indeed traverse every edge in G and has walk weight equal to W + the perfect pairing weight as required.\(\square \)

Now we shall prove part two. Suppose we have a closed walk in G which traverses every edge in G. Choose one instance of each edge in the closed walk and label them as used. The remaining edges in the walk will be referred to as reused edges. Let v be a vertex of odd degree in G. In a closed walk, the number of times the walk enters a vertex must equal the number of times the walk exits a vertex. Because of this we know that, counting repetitions, the walk must use an even number of each vertex’s edges. As every edge is used in the walk and v has an odd number of edges we conclude at least one of v’s edges is reused. In fact the key fact is that we conclude v has an odd number of reused edges. Similarly a key fact is that we know that any even degree vertex must have an even number of reused edges. Note this is all counted with multiplicity. Choose one reused edge from v and give it the label of used. From now on treat v like it is a vertex of even degree since it only has an even number of reused edges left. If this connects to a vertex of odd degree, say w, then we are done with this step. Note w would have an even number of reused edges. If this connects instead to a vertex of even degree, as the edge is being reused, by similar logic as before, we know that in fact this even degree vertex must have an edge reused not yet chosen in this algorithm since it currently has an odd number of reused edges. Note that it could be the same edge as previously but counted as an additional repetition from the closed walk. Choose a not yet accounted for reused edge and now label it as used. Then once again we reach a vertex of odd degree or even degree. If the vertex is of odd degree then we are done with this step. If of even degree do the previous step again. We know this algorithm must terminate by the finiteness of the walk. Thus eventually we get a walk from v to w, both vertices of odd degree in G, built from reused edges in our given closed walk. Note this walk weight is at least as much as the minimal walk weight between v and w. From here on we will treat v and w as vertices of even degree. Additionally we will treat all the previously reused edges, counting with multiplicity, from our walk between v and w as used as described above. Note at this point v and w both have an even number of reused vertices currently. If there are more vertices of odd degree we may repeat the previous algorithm. This new process must terminate since there are only a finite number of vertices of odd degree in G. The outcome of this algorithm is a perfect pairing. It is clear from construction that the weight of the walk minus W is at least as large as the perfect pairing weight as required.

Corollary 3

Given an undirected graph, G, and a perfect pairing of the vertices of odd degree in G, whose perfect pairing weight is minimal among such perfect pairings, then one can construct an optimal solution to the Closed Undirected CPP.

We now know we may solve the Closed Undirected CPP problem by finding a minimal weight perfect pairing. The process of finding a minimal weight perfect pairing is the one we will solve on the QA.

Let G be an undirected graph with vertices of odd degree, \(\{v_1,...,v_d\}\). Let \(x_{i,j}\) be a binary variable for \(i,j\in \{1,...,d\}\) with \(i<j\). Note we will use \(x_{i,j}\) and \(x_{j,i}\) to represent the same binary variable. The variable \(x_{i,j}\) with value one or zero represents, respectively, vertices \(v_i, v_j\) being paired together or not paired together. The symbol \(W_{i,j}\) will be a constant representing the weight of the shortest path between \(v_i\) and \(v_j\). The symbol P will be a positive constant whose use will be described shortly. The QUBO problem is then defined as:

To understand this QUBO, let us examine it term by term. First consider:

We shall label this part of the equation as C, for constraint. This part of the equation is to make sure a perfect pairing is formed. If C equals zero, we may interpret this as: “for every i, the vertex \(v_i\) is paired with exactly one vertex \(v_j\) with \(j\ne i\).” Now we consider:

We shall label this part of the equation M for minimize. Let us assume that C = 0 and thus we have a perfect pairing. Then the minimum value of M, and hence the whole QUBO, will correspond to the perfect pairing amongst the odd degree vertices which adds the least total weight. In other words, the outputs of our binary variables, \(x_{i,j}\), which correspond to the minimal value of the QUBO, will in turn correspond to a solution of the Closed Undirected CPP. Note also the number of variables in this QUBO is easy to compute as it is just \({d \atopwithdelims ()2}\), where once again, d is the number of vertices of odd degree; also, the variables in the QUBO are not fully connected. Now we shall talk about the use and importance of the constant P. As we get a perfect pairing if and only if \(C = 0\), we must make sure that the QUBO will be penalized for breaking this condition. Consider for a moment a new graph with two vertices and one edge between them with \(W_{1,2} > 2\), and that we set \(P = 1\). If we set \(x_{1,2} = 0\), we won’t get a perfect pairing, but we will minimize the QUBO overall. This is because relatively C will increase by 2 while M decreases by more than 2 by switching \(x_{1,2} = 1\) to \(x_{1,2} = 0\). Thus we see the need for a constant P since it will increase the cost incurred by breaking the condition \(C = 0\). In theory, P should be set equal to some arbitrarily large number as we require that \(C = 0\). This does not work in practice because when setting up for the annealing process, all binary variable constants are scaled to fit into an interval. Due to a limit on the sensitivity of the method, values sufficiently close to zero will be treated as zero. In practice the value that should be chosen for P will depend on the graph itself and should be large enough to force \(C = 0\), but small enough to not overshadow the M component.

Undirected CPP algorithm example. The first graph introduces an example of an undirected weighted graph. Below it is a solution to the Undirected CPP for that graph presented in vertex order notation. The way to read this solution is to start at the first vertex in the list and then traverse the edge which connects to the next vertex in the list. One should continue this process until one reaches the end of the list. The second graph is the same as the first, except one extra edge was added with the weight of the shortest path between those two vertices. That edge was added because it makes every vertex have even degree and has the smallest walk weight between the two vertices

Full size image

As a quick example, the QUBO one would get from the graph in Fig. 2 would be simply,

which if we let \(P = 10\), for example, could be written as

Upon inspection one can see that the value of \(x_{3,5}\) which minimizes this equation is \(x_{3,5} = 1\) for a total value of 9 as expected.

3.4 A General Approach to the Chinese Postman Problem

We now outline an algorithm for solving a more general class of CPPs on a QA. We show how to solve variants 1 through 8 from Sect. 3.1 and discuss results for those variants in Sect. 4. Algorithm 2 is an outline of the general algorithm.

Quantum Annealing for a CPP

Now we shall explain the construction of the QUBO. Let G be a graph, directed, undirected or mixed. Let V be the set of vertices in G. Let \(i_{max}\in \mathbb {N}\). The constant \(i_{max}\) represents the maximum number of edges we will allow to be traversed in the walk and we will discuss how to choose \(i_{max}\) later. Our binary variables will be \({}_ie_{j,k}\) and \({}_{2^r}s_{j,k}\) for \(j,k\in V\), such that there is an edge going from vertex j to vertex k, \(i\in \{0,...,i_{max}\}\), and \({r\in \{0,...,ceiling(\log (i_{max}))\}}\). Let \(W_{i,j}\) be the weight of the edge going from vertex i to vertex j. The mental picture we will use to guide our thinking is that of choosing the steps in our path in an ordered manner. The variable \({}_ie_{j,k}\) taking the value of one in the solution to the QUBO will correspond to an instruction to traverse the edge going from vertex j to vertex k in the i\({}^{\text {th}}\) step of the walk. The variables, \({}_{2^r}s_{j,k}\), are slack variables, which are helpful in setting up some of our inequality conditions. Recall that we are presetting the number of steps we will take in the walk in our graph. As we do not know a priori how many steps we need for our walk, let us assume we overestimate. To compensate for this overestimation, we will allow repetition in the steps we take in our walk so as to allow a shorter walk than the one predetermined in our set-up. For example, \({}_ie_{j,k}\) and \({}_{i+1}e_{j,k}\) will be allowed to simultaneously evaluate to 1.

Using this set-up, let us talk about what conditions and constraints need to be met to create a legal path. First, at any given step in our walk, the walk should traverse precisely one edge. This can be phrased as: for all i, there is a unique pair, (j, k), such that \({}_ie_{j,k} = 1\). Written as a constraint for a QUBO this is,

The next constraint is that we do not want our walk to ’jump’ around in our graph, we only want graph walks. To do this we will require that if \({}_ie_{j,k}\) and \({}_{i+1}e_{r,s}\) are both one, then either \(k=r\) and the walk is legal at this location or \(j=r\) and \(k=s\) and we have a repetition edge whose necessity for existence was explained above. Written as a constraint for a QUBO this is,

The next constraint is that we want to make sure that every edge in the graph which is required to be included into the walk is included. This will be phrased as: for any directed edge from vertex j to vertex k which should be included in the walk, there exists at least one i such that \({}_ie_{j,k} = 1\). And for any undirected edge between vertex j and vertex k, there exists at least one i such that \({}_ie_{j,k} = 1\) or \({}_ie_{k,j} = 1\). It is for this kind of inequality that we need the slack variables. Written as a constraint for a QUBO this constraint is:

The next constraint which may occur is a required start and/or stop location. Unlike the constraints above which increase the required connectivity between variables in the QUBO, which makes it more difficult to embed on the hardware, we can use this constraint to decrease the number of variables needed and also decrease the connectivity between variables in the QUBO. We can do this by not creating unneeded variables, which means we would also omit those variables from the constraints above. If a start location is required then we shall not include variables \({}_ie_{j,k}\) for which the edge (j, k) cannot be reached in i steps, accounting for the type of repetition we spoke of previously. This is done similarly at the end of the walk if an end location is specified. Let us consider as an example the first graph in Fig. 2 and let us specify the starting vertex to be vertex 3. Then for the variables, \({}_ie_{j,k}\), for which \(i = 0\), the first step, we only have \({}_0e_{3,2}\). For \(i = 1\) we only have \({}_1e_{3,2}\), \({}_1e_{2,1}\), \({}_1e_{2,3}\), \({}_1e_{2,4}\), and \({}_1e_{2,5}\). In this way we forcibly achieve any start or stop constraint.

Let us take a brief pause from talking about constraints to introduce the part of the QUBO which will lead us to picking the best walk amongst all the legal walks which meet our requirements. The constraints above will all be zero if the walk chosen is legal and meets the preset requirements. This following part though, apart from some trivial cases, will be non-zero and is the ‘meat’ of what we are trying to minimize. The essence of this next part of the QUBO is that we want to add up all the weights of all the edges we traverse while not double counting weights when an edge is repeated solely to reach the requested number of edges, which is \(i_{max}\). This is done as follows,

Before we proceed further, it is useful to note that we have produced enough constraints to handle all combinations of variants 1 through 8 for the CPP using the QUBO,

where the \('P'\) variable’s are positive real numbers which are used to scale the weight of the constraints. How to choose those values will be discussed later.

There is an alternative optimization to the start/stop optimization which will now be described in brief. The modifications to the QUBO related to this change are similar to those at the end of Sect. 3.5. Rather than using the edge repetition method used to handle \(i_{\text {max}}\) over-estimations, one can instead use a terminal vertex method. The idea of the terminal vertex method is to add one additional vertex, the terminal vertex, to the graph which will represent the end of the walk. One then needs to add the appropriate edges. If a variable corresponding to an edge leading to the terminal vertex at step i in the walk takes the value 1 in the QUBO solution, this is interpreted as the walk ending at step i. The edges one should add are a directed edge from any vertex the walk is allowed to end at to the terminal vertex and a directed edge from the terminal vertex to itself. The terminal vertex edges should only be included in the above QUBO at time steps greater than or equal to the cardinality of the set of required edges. The terminal vertex method allows us to do two things. One, we may remove the edge repetition from M, decreasing the connectivity between variables in the QUBO, and two, we may remove the edge repetition from determining which edges are possible to reach in the \(i^{\text {th}}\) step in the start/stop optimization above, which decreases the number of variables needed. However, one must account for the increase of variables and variable connectivity induced by including the terminal vertex itself. The two optimizations both do better on different graphs, depending on the graph topology. The authors have implemented both methods and choose for each problem whichever uses the least variables. Recall that the above QUBO was implemented with results shown in Sect. 4.

3.5 Further modifications to the general approach

The following variants, variants 9 through 12, have not yet been implemented on a quantum annealing device. We provide QUBO equations for implementing these variants and discuss why the equations are valid.

To include variant 11 we need only add one additional constraint. One may recall that variant 11 includes additional information in the form of 3-tuples, (edge-in, edge-out, bonus weight). Similar to the \({}_ie_{j,k}\) variables, let us write the 3-tuple as \(((j,k),(k,r),x_{j,k,r})\) where \(j,k,r\in V\) such that (j, k), (k, r) are edges in the graph. Then the QUBO constraint can be written as,

which in conjunction to what we had before would create the QUBO,

Observe the turning constraint does not add any more variables, but does increase the connectivity between variables in the QUBO.

Adding variants 9 and 10 requires additional modifications to the QUBO construction above. Let us start with variant 10, service-based traversal. We shall replace the variables \({}_ie_{j,k}\) with \({}_ie^s_{j,k}\), \({}_ie^t_{j,k}\). The \({}_ie^s_{j,k}\) variable equal to 1 corresponds to servicing the edge going from vertex j to vertex k on the \(i^{\text {th}}\) step of the walk. Setting \({}_ie^t_{j,k}\) = 1 will correspond to merely traversing the edge going from vertex j to vertex k on the \(i^{\text {th}}\) step of the walk. We will also not use the \({}_{2^r}s_{j,k}\) variables. The modifications to the constraints are as follows:

Let \(W^s_{j,k}\) be the weight corresponding to servicing the edge going from vertex j to vertex k, while \(W^t_{j,k}\) is the weight corresponding to just traversing that edge. Then,

One caveat to the service traversal variant QUBO set-up is that if the solution involves only service steps and no traversal steps, we won’t be able to get the optimal solution if we don’t a priori know the precise number of steps our walks need as we only allow repetition on traversal steps. This is easily avoided in practice however as the only way a walk will only use service steps is if there is an Eulerian circuit on the subset of edges required, which as stated before, is computationally easy to determine. One benefit is that it is easy to to make the service based traversal hierarchical, like variant 12, for any partially ordered set (i.e. some edges must be serviced prior to others) without introducing more variables. Solving variant 12 is achieved by adding on the following constraint. Let \(x_{(j,k),(r,s)} = 1\) if the edge going from vertex j to vertex k must be serviced prior to the edge going from vertex r to vertex s, and 0 otherwise. Note \(x_{(j,k),(r,s)}\) is a given value in the problem and not a variable the annealing device solves for. Let the other notation be similar. Recall \((*,*)\) is for directed edges while \([*,*]\) is for undirected edges. Then,

The final variant to talk about is variant 9, the k-Postman Problem. As we already use k, we shall suppose there are l postmen. This variant provides us with the opportunity to introduce a slightly different idea. For variant 9 we will need to use a slight modfication of the terminal vertex paradigm. We shall use the binary variables \({}_ie^a_{j,k}\), \({}_{2^r}s^a_{j,k}\), and \({}_irest^{a}\) for \(a\in \{1,...,l\}\), all else the same. The a index will refer to the \(a^{\text {th}}\) postman walk. So \({}_ie^a_{j,k} = 1\) will correspond to the \(a^{\text {th}}\) postman traversing the edge going from vertex j to vertex k on the \(i^{\text {th}}\) step of their walk. The \({}_{2^r}s^a_{j,k}\) binary variable will be used as a slack variable similarly to before. When the variable \({}_irest^{a}\) equals one, this will correspond to the \(a^{\text {th}}\) postman at their walk’s endpoint on the \(i^{\text {th}}\) step and is their terminal vertex from the terminal vertex method described in Sect. 3.4. Let \(W^a_{j,k}\) represent the weight corresponding to the \(a^{\text {th}}\) postman traversing the edge going from vertex j to vertex k. The variations to the QUBO constraints are listed below:

Consider a use case where no two postmen may occupy the same edge going in the same direction at the same time. An example of an advantage one gains for using this resting paradigm over the repeated edge paradigm is that it becomes easy to create a constraint to avoid such collisions as

Similar constraints can be made for avoiding collisions going in the opposite direction along edges and for avoiding collisions at vertices. Additionally, if \(W^a_{j,k}\in \mathbb {N}_0\) for all i, j, a, then one may consider the k-Postman Problem With Capacity. Suppose one is given \(\{c_1,...,c_l\}\subset \mathbb {N}\), where the \(a^{\text {th}}\) postman is limited to walks of weight less than \(c_a\). Then, by introducing the slack variables \({}_{2^y}m^a\) for \(y\in \{0,...,ceiling(\log (c_a))\}\) for \(a\in \{1,...,l\}\), we have the constraint,

The slack variables in the equation allow the postmen to have walks with walk weights less than their maximum capacity without punishing such solutions.

One may also note that it is possible to combine variant 9 and 10 together with a little thought, however we shall abstain from doing so to save ourselves from the additional complex notation it would create.

In this section, we will consider the results of two kinds of experiments for both the Closed Undirected CPP and the General CPP. Here the General CPP refers to variants 1-8. The first kind is a parameter study for various tuneable parameters for running the problem directly on quantum hardware. The second kind is a comparison of results between various purely quantum, classical, and quantum-classical solutions to the same CPP problem. A reminder to help clarify the results shown is that the goal is to minimize the solution so as to minimize the weight of the walk. In each table in Sect. 4 a collection of graphs and their associated data are generated randomly using NetworkX and Python libraries. More explicit data for the graph generation will be provided near the beginning of each subsection. Each value of the dependent variable is tested on each graph and the resulting data is put in the table.

4.1 Closed Undirected CPP Parameter Study

Let us begin with a parameter study of the Closed Undirected CPP. The parameters tuned were the constraint weight, the sample number, the intersample correlation, the number of spin reversal transforms^{Footnote 1}, and the annealing time.

The tables in this subsection were generated as follows. Table 2, Table 5, and Table 6 were each generated using 80 graphs total with 20 each of 4, 6, 8, and 10 odd degree vertices. Table 4 and Table 7 each were generated using 68 graphs total with 17 each of 4, 6, 8, and 10 odd degree vertices. All the graphs used had 16 vertices with roughly \(40\%\) edge saturation. The edges were assigned uniformly random integer weights between 1 and 10 inclusive.

The constraint weight is the P variable discussed in Sect. 3.3. The constraint weight needs to be large enough to encourage valid solutions to the Closed Undirected CPP, but small enough to not overshadow the rest of the QUBO.

Some guidance is provided for understanding the tables. In Table 2, the number 3.05 in column 30 and row ’time to solution,’ means that using a P value of 30, the average wall-clock time to get the solution across all such runs was 3.05s. The wall-clock time is the time it took the algorithm to find a solution from a given QUBO. Using the D-Wave Leap based methods this includes over the internet communication plus the time it took to validate the lowest energy solution. The number 30 in column 50 and row ’\(\le 25\%\) above optimum’ means that \(30\%\) of the runs using a P value of 50 were valid and achieved a solution less than (meaning better than) or equal to \(25\%\) above (above meaning worse than) the optimal solution.

As one can see in Table 2, there is a strong correlation between the percentage of valid solutions and the percentage of optimal solutions with the size of the P value. In fact, this becomes more apparent when we separate the data by the size of the problem as in Table 3. The constraint weight for the Closed Undirected CPP runs when done strictly on quantum hardware will be set to 70. Next, we will consider the effect the sample number has on the result. The sample number is the number of times states are read from the quantum hardware.

A strong positive relationship between the validity and quality of the solutions with the number of samples is seen in Table 4. Even when viewed by problem size, the monotone increasing relationship between validity and quality of solution with sample number is preserved across every problem size. This is true except for one instance, a problem of size 8 odd degree vertices where one solution of moderate quality (\(\le \) \(25\%\) above optimum) was found for the 500 sample number, but not the 1000 sample number. A sample number of 1000 will be used for the Closed Undirected CPP when there is a choice on quantum hardware.

Next, we will explore the relation that reducing intersample correlation has with solutions in Table 5. The relationship between reducing intersample correlation and solution validity/quality is mixed with reducing intersample correlation slightly increasing validity of the solution and slightly decreasing solution quality. The time to solution is on average increased when reducing intersample correlation and so is not used moving forward when studying the Closed Undirected CPP.

We will continue our parameter study of the Closed Undirected CPP by looking at the effect the number of spin reversal transforms has on solutions in Table 6. There is little relationship between the validity of the solution and the number of spin reversal transformations. The solution quality does improve when using spin reversal transformations, with the largest jump in quality coming from the first 10 spin reversal transforms. The number of spin reversal transformations increases the time to solution significantly when a large number is used. Only 10 spin reversal transformations will be used henceforth for the Closed Undirected CPP when on quantum hardware.

The final piece of our parameter study for the Closed Undirected CPP is to study the effect that annealing time has on solutions. There is a positive relationship between the validity of solutions and the annealing time apparent in Table 7. The relationship between the annealing time and the solution quality, however, is less clear. To find a middle ground, an annealing time of \(100\mu \)s was chosen moving forward when running the Closed Undirected CPP on quantum hardware.

4.2 Closed undirected CPP comparison study

In this section we will compare the validity and quality of solutions between a classical method, such as brute force, and various methods for finding solutions to the QUBO corresponding to the problem. The classical methods, quantum methods, and quantum-hybrid methods used in our comparison are listed below.

Classical methods

• Brute force method (Standard for comparison): The brute force method only runs on problems with a maximum of 14 vertices of odd degree.

• Greedy: This algorithm has no vertices limitations. It is based on a steepest descent solver D-Wave Systems Inc. D-WaveSystemsInc. (2022a).

• Tabu search: This algorithm has no vertices limitations. It consists of a modified steepest descent algorithm which keeps track of the locations of the best solutions found and temporarily changes values in the QUBO to promote search diversity. We have also tested this algorithm in combination with both preprocessed and post-processed with a greedy algorithm (greedy tabu) Musiał et al (2017).

• Simulated Annealing (SA): This algorithm has no vertices limitations. SA is a modified hill-climbing algorithm which improves solution diversity, and often quality, over other hill-climbing algorithms by allowing worse solutions to be picked sometimes during the search Rutenbar (1989).

Quantum methods

• 2000Q: With a maximum of 10 vertices of odd degree, this consists of only using the 2000Q machine to perform the quantum annealing.

• Advantage: With a maximum of 18 vertices of odd degree, this consists of using the Advantage4.1 machine to perform the quantum annealing.

Quantum-Hybrid methods

• Greedy 2000Q: With a maximum of 10 vertices of odd degree, this consists of using the 2000Q to perform a QA, followed by post-processing with the greedy algorithm.

• Greedy Advantage: With a maximum of 18 vertices of odd degree, this consists of using the Advantage4.1 machine to perform the QAs followed by post-processing with the greedy algorithm.

• 2000Q qbsolv: With no limit on size, this consists of using qbsolv and the 2000Q machine as the back-end for performing QAs.

• Advantage qbsolv: With no limit on size, this consists of using qbsolv and the Advntage4.1 machine as the back-end for performing QAs.

For some runs we also compared qbsolv on both devices when using the fixed embedding composite (f-2000Q qbsolv and f-Advantage qbsolv respectively) versus the embedding composite in the ocean-dwave-sdk D-Wave Systems Inc. D-WaveSystemsInc. (2022a).

When running on sufficiently small problems, solution quality is compared to the brute force method which finds the optimal answer. When problems become too large for brute force, we instead compare solutions with greedy tabu which usually only provides approximate answers.

The tables in this subsection were generated as follows. Table 8 was generated using 60 graphs total with 30 each of 4 and 6 odd degree vertices. Table 9 was generated using 44 graphs total with 30 graphs with 8 odd degree vertices and 14 graphs with 10 odd degree vertices. Table 10 was generated using 30 graphs total with 15 each of 16 and 18 odd degree vertices. Table 11 was generated using 30 graphs total with 10 each of 20, 30, and 50 odd degree vertices. All the graphs used had twice the number of vertices as odd degree vertices and had roughly \(40\%\) edge saturation. The edges were given integer weights between 1 and 10 inclusive.

We first compare these methods on some small problems of 4 and 6 odd degree vertices. Note an example of how Table 8 should be read is as follows: the number 33 in the column labeled ‘10’ and row labeled ‘greedy’ means that \(33\%\) of the greedy solutions were valid and at most \(10\%\) above the optimal solution. One observes from Table 8 that on small problems we get perfect results on all methods except 2000Q, Advantage, and greedy. The 2000Q and Advantage still attained strong results on these small problems, while greedy only achieved mediocre results.

Now in Table 9 we compare some slightly larger problems of graphs of 8 and 10 odd degree vertices respectively. For these larger problems we see that all of the methods get optimal results except 2000Q, Advantage, and greedy. However, this time, 2000Q, Advantage, and greedy got poor results, with 2000Q and Advantage drastically decreasing in efficacy. It is interesting to observe that despite the fact that greedy and 2000Q individually were ineffective, when used in concert optimal results were achieved. And this holds similarly for greedy and Advantage. The advantage of a greedy post-processing is not unique to this problem and was also used to improve solution quality in Akrobotu et al 2022 and Gaydai et al 2022.

Table 10 shows results for problems which are too large to be solved by brute force or to run directly on 2000Q hardware. In fact, these are the largest problems which can be run directly on the Advantage hardware. Once again, greedy and Advantage both performed poorly alone, but when used together produced results comparable to greedy tabu. The two qbsolv methods almost always found solutions which were equal to or better than greedy tabu, with the better results occurring a non-negligible amount of the time.

In Table 11 we studied problems which were too large to run directly on quantum hardware. The fixed embedding produced better results than the non-fixed embeddings for qbsolv, especially for the Advantage device. However, the fixed embedding took significantly more overhead time for finding the initial embedding and the fixed embedding qbsolv used significantly more runs on the quantum hardware than the non-fixed embeddings did.

4.3 General CPP parameter study

Let us now examine our parameter study of the General CPP on the Advantage hardware with a greedy algorithm post-processing.

The graphs for the tables in this subsection were generated as follows. Table 12 was generated using 117 graphs. Table 13 was generated using 74 graphs. Table 14 was generated using 141 graphs. Table 15 was generated using 72 graphs. The graphs could have 3, 4, 5, or 6 vertices. The graphs could have roughly 25%, \(50\%\), or \(75\%\) edge saturation. The graphs could require about \(25\%\), \(50\%\), or \(75\%\) of the edges to be traversed, the context of this parameter being variant 7. The graphs could also have have a fixed or unfixed start or stop position. If both start and stop were fixed to a position then they could be either the same or different. The edge weights were integers chosen between 1 and 5 inclusive. Approximately \(70\%\) of the edges in the graphs were undirected. Across all combinations of the above listed options the graphs were picked in a roughly uniform manner.

In Table 12 one can see that overall, there is a negative relationship between \(P_{\text {one\_edge}}\) and solution validity and quality, with \(P_{\text {one\_edge}} = 80\) being an exception. The parameter value chosen for problems run after this is \(P_{\text {one\_edge}} = 40\). While doing strictly worse than \(P_{\text {one\_edge}} = 30\) in terms of solution validity and quality overall, \(P_{\text {one\_edge}} = 40\) actually did significantly better when looking at the larger end of problems able to run directly on the hardware in the 100-200 variable range.

Table 13 shows a strong positive relationship between the validity of the solution and \(P_{adjacency}\). If one separates the data out by problem size, \(P_{adjacency} = 70\) does the best in terms of validity and solution quality for problems in the \(0-100\) variable range, while \(P_{adjacency} = 80\) does better for problems in the \(100-250\) range. So the average of these two values is used moving forward setting \(P_{adjacency} = 75\).

As can be seen in Table 14 there is a generally negative trend for solution validity and solution quality with respect to \(P_{required}\). When one looks at the data by problem size, \(P_{required} = 30\) and \(P_{required} = 40\) each do better on certain problem sizes. So once again we take the average and set \(P_{required} = 35\) moving forward.

Table 15 highlights that having a very large chain strength^{Footnote 2} can deteriorate both the validity and quality of solutions. A chain strength of 400 leads to the highest percentage of valid solutions and mostly the highest quality solutions. However, when one looks at the data broken up by problem size, one finds that a chain strength of 500 gets generally better results on larger problems. So the chain strength moving forward has been set to 475.

4.4 General CPP comparison study

We compare results for the General CPP algorithm using tabu, greedy tabu, SA, Advantage, greedy Advantage, 2000Q qbsolv, and Advantage qbsolv. We compare how each method does on various problem sizes, for the sizes a method can run. The problem sizes are broken up into three categories: small as \(0-250\) variables, medium as \(250-1000\) variables, and large as \(1000-3200\) variables. As a reminder, how these variables are formulated is explained in Sect. 3.4. Roughly speaking, small problems correspond to graphs with \(3-4\) vertices, \(25\%-75\%\) edge saturation, all kinds of start/stop conditions, \(75\%\) undirected edges, and edge weights between 1 and 5 inclusive. Medium problems correspond to graphs with \(5-6\) vertices, and similar other data. Large problems were run on graphs with \(9-10\) vertices, \(25\%-50\%\) edge saturation, and similar other data. We compare against SA for the small and medium sized problems. However, for the medium sized problems SA took a long time to compute. For the large problems, SA became prohibitively expensive to run. The large problems are compared against greedy tabu.

Let us start with the small problems. When comparing the small problems for the General CPP in Table 16, we see once again that greedy and Advantage by themselves do not perform well, but that together get strong results. For these small problems in the \(0-250\) variable range it appears that the classical algorithms like SA and tabu are more effective than the quantum/hybrid approaches running on current D-Wave Leap resources.

When looking at the data for medium sized problems in the range of \(250-1000\) variables in Table 17, we see that the hybrid methods are comparable in solution quality to the classical methods and will sometimes get higher quality results.

Once we start to look at larger problems, as shown in Table 18, we see that the quantum-classical hybrids start to significantly outperform the classical methods in terms of solution quality.

The following insights come from the data in Sect. 4 and intuition gained from the implementation of the Closed Undirected CPP and variants 1 through 8 in the generalized algorithm for the CPP. The observations come from running the algorithms both directly on the D-Wave 2000Q and Advantage chip, and via the quantum-classical implementation of qbsolv Booth et al (2017) on the QAs.

The differences between the original algorithm Siloi et al (2021) and our modified version are as follows. First, we use \(x_{i,j}\) to represent the same binary variable as \(x_{j,i}\) whereas the original version treated them as two separate variables. The advantage of this approach is that it halves the number of variables used. Second, we are able to remove a now unnecessary constraint from the equation. The advantages of this are two-fold. One, removing the constraint makes understanding the QUBO and implementing it easier. Two, the removal of the second constraint reduces the QUBO’s variable connectivity, allowing for larger problems to fit directly on the hardware. These changes lead to being able to run a 12 odd degree vertices problem directly on the 2000Q versus the previous 8 odd degree vertices.

Now let us talk about the generalized CPP algorithm. While handling a much more general class of problems, this algorithm can use a large number of variables. Depending on which variants are used, the number of variables can grow quadratically with the number of edges in the graph. The bright side is that the variables used are not in general fully connected. This means more variables may be used when running the problem on quantum hardware. For example, on the 2000Q D-Wave chip, 109 variables for the algorithm were successfully embedded on the hardware compared to the 64 variable maximum when fully connected.

There are many ways the choice of variants can increase or decrease the QA efficiency. Specifying the start and/or end vertex will decrease the number of variables and somewhat decrease the connectivity between the variables. When implementing a Rural Postman Problem, requiring fewer edges can greatly decrease the connectivity between the variables. Variants 9 through 12 all greatly increase the number of variables required and/or increase the connectivity between variables.

One of the main determining factors one has control of which affects how many variables are required is \(i_{\text {max}}\), the maximum length of the walk allowed. To find a minimal walk weight which meets all criteria, one must allow sufficient steps in the walk to find that minimal walk weight. Roughly \((2\vert U\vert + \vert D\vert )i_{\text {max}}\) variables are required for all variants except 9, 10, and 12, which require approximately some integer multiple more variables. Thus we try to pick a minimal, yet sufficiently large \(i_{\text {max}}\). A safe value to pick, in the sense it will be sufficiently large for any variant, is \(i_{\text {max}} = 2\vert E\vert \). If this is too many variables, one may try a smaller \(i_{\text {max}}\). It is safer to greatly decrease \(i_{\text {max}}\) from \(2\vert E\vert \) when either there are a large number of undirected edges or when a significant number of edges are not required in the Rural Postman variant.

Now let us take a moment to talk about the ’P’ variables from earlier, the ones which we multiply each constraint by when adding to our QUBOs. This is where our effort becomes a bit more of an art than a science. From a mathematical perspective, one should choose the ’P’ variables to be arbitrarily large. From an implementation perspective this should not be done. When the QUBO is embedded on the hardware, all the values are scaled to fit within a specific range with limited precision and as such, if the ’P’ variables are chosen too large, then numbers which are not zero may be treated as zero, leading to poor results. There are some general guidelines for the choices. All the ’P’ variables are multiplied with constraints which, if broken, lead to an invalid solution. The ’P’ variables should at the very least be larger than the highest weight edge. The authors often found having all such variables set between 1.5 to 15 times the highest edge weight worked well. If one tries to implement the algorithms in this paper and gets results which lead to invalid solutions, then the likely culprit is the ’P’ variables. In this case, one should increase the ’P’ value for the constraint which is broken. If however one is getting valid, but non-optimal results, this may be caused by having ’P’ variables which are too large and one should try decreasing all of them slightly.

One of the surprising results is how effective combining annealing on a QA and greedy were, even when either method alone achieved poor results. An interpretation of why this occurs is as follows. The energy landscape for our QUBOs, especially the larger ones, is complex with many peaks and valleys of varying heights and depths. The greedy algorithm by itself can only ever go down, and so will descend into the nearest valley which has a low likelihood of being the deepest valley or even a deep valley. When annealing on a QA, their is a strong likelihood of arriving at the deepest, or at least one of the deepest valleys, but due to noise and flux errors D-Wave Systems Inc. (2022b). has trouble settling to the bottom of these values. So when we combine these methods together, the QA finds one of the deepest valleys and then greedy quickly gets us to the bottom of the valley.

Another surprising result appears in Sect. 4.4. For the methods tested, the data shows a comparative advantage for classical algorithms on small problems, but as the problems grow in size, the quantum-classical hybrid methods overtake the classical algorithms and achieve superior results. This trend is highlighted in Tables 16, 17, and 18.

One should note that in this paper we have defined our graphs to not include multi-graphs, graphs which may have more than one edge which go from vertex i to vertex j. This is to make the notation simpler. Everything in this paper may be extended to work with multi-graphs with the largest obstacle being the notation. For ideas on how to implement this work for multi-graphs one should look at the QUBOs for variant 9 and variant 10.

In conclusion, the authors have designed and developed a framework for solving a large number of variants of the CPP on a QA. Implementation of the framework for variants 1 through 8 on the D-Wave 2000Q were successful. Optimal results were achieved for problems which could be embedded on the hardware with only short chains and optimal results were sometimes achieved for larger problems after tuning the ’P’ variables. Future directions include the following. Implementation of the remaining variants outlined. Implementation of further variants as there are more variants which could be easily adapted to the method defined in Sects. 3.4 and 3.5, but were not included to keep this paper reasonable in length. Translating the CPP algorithm and variants for gate-based quantum architectures. Developing a more efficient way to choose optimal ’P’ variable values given the inputs from the problem. Additionally, there is room to experiment with this algorithm in conjunction with an iterative and/or graph partitioning approach to the CPP.