6
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 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
    Commented Nov 13, 2017 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
    Commented Nov 14, 2017 at 16:01
  • $\begingroup$ In case @user you got a grasp, consider sharing your experience (by a blog/video/report)... $\endgroup$
    – hola
    Commented Apr 16, 2019 at 17:36

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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