Shortest path QUBO Objective function
Hi,
I am working in a simple model to calculate the shortest distance between nodes. I started with a 3 node case where qubits are the distances between the nodes (ab,bc,ac) with biases being the actual value of the distance. Constraints are ab+ac=1 and bc+ac=1 (nodes a and c are the start and end).
I am struggling to come up with a QUBO objective function as the combination (0,0,0) has zero energy (as all they a(i) are zero) and any other combination has higher energy. Does anyone know how to handle this case where the lowest energy state is not a solution?
Thanks!
Comments
Hello Llorenc,
D-Wave has a set of tools called D-Wave NetworkX designed to help explore network problems. You might be particularly interested in the reference documentation and source code for the Traveling Sales Person function. The traveling salesman tool incorporates shortest path as one of its constraints, so this may help you.
Hi Llorenc,
You might want to check out a book called Complex Network Analysis in Python by Dmitry Zinoviev, published in 2018 by Pragmatic Bookshelf, ISBN-13 978-1680502695. The main tool used in the book is NetworkX, which the D-Wave folks have built upon. I'm studying the book myself right now and finding it approachable and engaging.
Cheers,
Scott D.
Thanks Scott and Luca. I will certainly look into these two references
Hi Luca,
The link provided by you for Traveling Salesman function doesn't seem to work. Kindly help sharing the link to reference documentation for Dwave solution to TSP
Thank you
Hello Llorenc,
I've updated the link in my comment above - you can also take a look at the high-level documentation for the same function.
The traveling salesman code uses edges as the qubits, each with a weight proportionate to its geographic length (similar to your approach above). The constraint that each city is visited only once is created by writing a minimization equation, then taking the coefficients and adding them to the QUBO.
In the original 3-node problem you provided, you might write a constraint like “Node a is visited only once” like this:
ab + ac = 1
ab + ac – 1 = 0
minimize (ab + ac – 1)^2
minimize (ab^2 + ab*ac – ab + ab*ac + ab^2 – ac – ab – ac + 1)
*note that for binary values x^2 = x
minimize (2*ab*ac – ab – ac + 1)
QUBO linear terms: (ab: -1, ac: -1)
QUBO quadratic terms: (ab,ac): 2
Please sign in to leave a comment.