1
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Condo
    Jul 6, 2022 at 21:17

1 Answer 1

2
$\begingroup$

Yes, it certainly seems possible with current quantum technology.

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.

How one turns a decision/oracle problem into something implemented on a quantum computer with Grover search is akin to the way Grover search is used to solve a Sudoku problem in the linked Qiskit tutorial.

$\endgroup$
2
  • 1
    $\begingroup$ Hi @Sam_QC, I'm not sure what eigenstates you are referring to? $\endgroup$
    – Condo
    Jul 13, 2022 at 14:59
  • $\begingroup$ Accidentally added a comment to the wrong question, sorry! $\endgroup$
    – Sam_QC
    Jul 13, 2022 at 16:59

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.