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.



migrated from physics.stackexchange.com Nov 13 '17 at 20:25

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

  • 1
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus Nov 13 '17 at 20:34
  • $\begingroup$ Ah, thanks! I see that on a closer read. I was confused with the brute force approach, which talked about (n-1)! combinations. $\endgroup$ – user Nov 14 '17 at 16:01
  • $\begingroup$ In case @user you got a grasp, consider sharing your experience (by a blog/video/report)... $\endgroup$ – pushpen.paul Apr 16 at 17:36

The notebook describes how to solve combinatorial optimization problems by encoding them as minimizing a binary quadratic form, which can in turn be phrased as finding the minimal eigenvalue of a Hamiltonian, and so solved by a quantum computer. The number of qubits needed is the dimension of the Hamiltonian, which is also the number of bits in the encoding.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.