The QUBO is actually taking the form of a permutation matrix, to ensure that all cities are visited in this trip, and that all cities are visited exactly once in this trip.
The lower triangle of the QUBO matrix consists of zeros, because the graph embedded on the QPU is non-directional.
In a simple matrix, the upper half of the matrix refers to traveling from A to B, while the lower half would correspond to traveling from B to A.
Since the QPU treats both directions as the same edge, the opposite direction is not weighted.
I hope this was helpful!
Please feel free to reach out with more questions or for further clarification.
Comments
Hello,
Our apologies for the confusion.
This presentation (on slide 30) has a little more information about the problem formulation:
https://arcb.csc.ncsu.edu/~mueller/qc/qc18/readings/gottlieb.pdf
The QUBO is actually taking the form of a permutation matrix, to ensure that all cities are visited in this trip, and that all cities are visited exactly once in this trip.
The lower triangle of the QUBO matrix consists of zeros, because the graph embedded on the QPU is non-directional.
In a simple matrix, the upper half of the matrix refers to traveling from A to B, while the lower half would correspond to traveling from B to A.
Since the QPU treats both directions as the same edge, the opposite direction is not weighted.
I hope this was helpful!
Please feel free to reach out with more questions or for further clarification.
Also check out the paper by Andrew Lucas:
https://arxiv.org/abs/1302.5843
It is referenced in the presentation, but I have included it here as well.
Please sign in to leave a comment.