# Can Quantum Computers (not simulators) solve a 4 node TSP?

I am currently researching the Traveling Salesman Problem, and it is known that Quantum Computers have a strong likelihood to increase the efficiency of TSPs in industry. I have mainly heard this in regard to Quantum Annealing processors however, like D-Wave's, which is not publicly available (for free) like IBMQ or (to an extent) Quantinuum. I have been using Grover's search algorithm to design the circuit, and only have work on paper at this point, but is it even possible to solve a 4 node TSP with 5-20 qubits over the cloud? Even if I just wanted to represent locations or distances in binary, I can't think of a way with that few bits to represent the locations/distances. I have considered switching to a different algorithm besides Grover's, but currently can't see how that few qubits can represent all of the variables even basic TSPs exhibit. Thank you in advance for your help!

• You do not need to worry about the encoding, each possible solution is just an element of some set (or database) and you are searching over that set using Grover and the oracle computes the path weight. Jul 6, 2022 at 21:17

First of all, the TSP can be converted into a decision/search problem by iteratively asking if there is a path of weight $$k$$, then looking for a path of weight $$k-1$$ etc... This procedure will eventually find you the optimal solution provided the weights are integer.
The number of Hamiltonian paths in an undirected graph on $$4$$ vertices is $$(4-1)!/2=3$$ and so in any case the search size over all possible tours is at most $$3$$. Theoretically, this means you could implement a Grover search approach to the TSP on 4 nodes using a device with only $$2$$ qubits to represent the search space.
In this 2017 work the authors implement Grover's search on a database of size $$8$$ using $$3$$ qubits on a "programmable quantum computer". However, it is my understanding that there is a limit to the scalability of these algorithms, in terms of the number of qubits, with existing error correction (or lack thereof) on current devices.