# 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!

## migrated from physics.stackexchange.comNov 13 '17 at 20:25

This question came from our site for active researchers, academics and students of physics.

• 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). – Yuval Filmus 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)... – pushpen.paul Apr 16 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$.