Question on the Traveling Salesman 48 City Matrix

Why does the algorithm use a 2304 by 2304 matrix?  Would it not be more intuitive to use a 48 by 48 matrix?

Why does the lower triangle of that array consist entirely of zeroes?

 

1

Comments

2 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.

    0
    Comment actions Permalink
  • 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.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post