Traveling Salesman -- number of qubits required? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:49:39Z https://cs.stackexchange.com/feeds/question/83871 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/83871 6 Traveling Salesman -- number of qubits required? user https://cs.stackexchange.com/users/80208 2017-11-09T02:35:19Z 2017-11-15T07:35:25Z <p>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 <a href="https://github.com/QISKit/qiskit-tutorial/blob/master/4_applications/classical_optimization.ipynb" rel="noreferrer">the one on MaxCut problems</a>. 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?</p> <p>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.</p> <p>Thanks!</p> https://cs.stackexchange.com/questions/83871/-/83948#83948 3 Answer by Yuval Filmus for Traveling Salesman -- number of qubits required? Yuval Filmus https://cs.stackexchange.com/users/683 2017-11-15T07:35:25Z 2017-11-15T07:35:25Z <p>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.</p> <p>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$.</p>