# Traveling Salesman -- number of qubits required?

I'm trying (in vain) to get a beginner's grasp of quantum computing, so doing a lot of reading. I've started looking at IBM's QISkit Jupyter Notebooks, and came across the one on MaxCut problems. In there, they give an example of how you could use quantum computers to solve the Traveling Salesman problem, for 4 cities. I may have missed the explanation somewhere in the notebook, but they use 9 qubits to address the problem -- can someone explain why 9? It is a hardcoded value in the actual code, which indicates to me that you could use different numbers...so what would be the tradeoffs with using more or fewer qubits, and how would that scale with the number of cities?

I understand that I can run the notebook and change the value to see how the results change, but I'd like to get a better theoretical grasp of why.

Thanks!

• This is explained in your link. In order to solve TSP using a quantum computer, you map it to some other problem – finding the minimum eigenvalue of an operator. The number of qubits needed is the dimension of the matrix. The reduction involves encoding TSP using binary variables (whose number is the dimension of the matrix), and the encoding suggested in the introduction uses matrices of dimension $(n-1)^2$ (where $n$ is the number of vertices). Nov 13 '17 at 20:34
• Ah, thanks! I see that on a closer read. I was confused with the brute force approach, which talked about (n-1)! combinations.
– user
Nov 14 '17 at 16:01
• In case @user you got a grasp, consider sharing your experience (by a blog/video/report)...
– hola
Apr 16 '19 at 17:36

In TSP, the optimization is over permutations. The notebook suggests encoding a permutation by encoding its permutation matrix, which is an $n\times n$ binary matrix. Since the rows and columns sum to 1, we can deduce the final row and column from the rest of the entry, and so need to keep only $(n-1)^2$ variables. In your example, $n = 4$ and so $(n-1)^2 = 9$.