3
$\begingroup$

Consider the modified version of the Traveling Salesman Problem where you are searching for a path of length less than some $k$. We can solve this problem using Grover's search where we encode each one of the possible paths as a quantum state and then search for the ones that have length less than $k$.

The oracle for this problem is supposed to add the weights of the edges in the given path, check if the total weight is less than $k$ and output 1 if it is the case. How can one construct an oracle for this problem? Is there a practical implementation? How and where to encode the weights of the edges?

Improve this question
$\endgroup$
3
  • $\begingroup$ Hi cssstyler, does there need to be something uniquely quantum in your question? Could you not use the standard Karp reduction to $\mathsf{SAT}$, satisfiability? $\endgroup$
    – Mark Spinelli
    Commented Dec 1, 2019 at 21:21
  • 1
    $\begingroup$ So you suggest that we can reduce it to satisfiability and then solve it since the oracle for that is obvious. But in that case I wondered if we could write an oracle without using a reduction. $\endgroup$
    – usercs
    Commented Dec 3, 2019 at 21:26
  • $\begingroup$ Have you seen this repository github.com/Naphann/Solving-TSP-Grover ? $\endgroup$
    – julien rodriguez
    Commented May 18, 2020 at 10:36

0

Reset to default

Your Answer

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