Solving TSP with Grover's

[a-matsuo]

Abstract

Solve Optimization problems such as TSP with Grover's algorithm.

Description

Solve Optimization problems such as TSP with Grover's algorithm. You need some ingenuity and creativity to make Grover's circuits with less costs. The following links will help you to get some ingenuity.

quantum-challenge/2019/problems/final/answer_and_comment_by_judges_en.ipynb https://github.com/quantum-challenge/2019/blob/master/problems/final/answer_and_comment_by_judges_en.ipynb

quantum-challenge/2019/top ten submissions/ https://github.com/quantum-challenge/2019/tree/master/top%20ten%20submissions

Members

• @githubhandle
• @githubhandle - Slack: @slackhandle email: example@example.com
• Qiskit Coach: @a-matsuo

Deliverable

GitHub repo

[xenoicwyce]

Hi, I'm interested in solving TSP using quantum computing. I've read papers like https://arxiv.org/abs/1805.10928 which uses phase estimation to estimate the path distance, then using a "quantum minimum searching algorithm" (https://arxiv.org/abs/quant-ph/9607014), which in turn relates to the Grover's algorithm. We can try to implement this using Qiskit.

[a-matsuo]

That's a nice idea. I think that topic can be different topic by itself. Why don't you create your own issue?

[Naphann]

I'm interested in this topic.
What I have in mind right now is a straight-forward approach which would need (n - 1) log n + log k plus some extra 2-3 clean ancilla bits where n is the number of TSP node and k being the maximum total distance.
We still need to use quantum minimum searching algorithm mentioned by @xenoicwyce and by dynamically generate oracle circuit to mark candidate solutions which has less total distance than best known so far until we get the best solution (or stop after some iteration of the minimum searching since this is an optimization problem).

[xenoicwyce]

@Naphann I think we can discuss more on this. But first I might need to collect more information on this, e.g. how to implement and stuffs.

[Naphann]

I only have a rough idea in mind right now. I'll try to explain what my idea is.

1. Three sets of register are needed, input which stores the order of cities we plan to visit, distance which will store the total distance, and anc which is a clean ancilla bits to work with.
2. A function/circuit traverse(u, v, distance) that will add distance from city u to city v to distance register. (and traverse_inverse(u, v, distance) to clear this for each iteration)
3. A function/circuit check_distance(distance) that flips the sign of input if distance is more than the best distance so far. This can be done by adding max possible distance - best distance and let the sum result overflow into anc register which was initialized as |->(minus state). This check_distance() must be changed every time we have a new best distance.

The three lists above should be enough for us to implement the oracle for each iteraction of the minimum finding algorithm.

I think it's doable but not really sure at the moment.

[a-matsuo]

@Naphann @xenoicwyce I think that @Naphann 's implementation idea including "quantum minimum search algorithm" @xenoicwyce mentioned is wonderful! I will be extremely happy if you guys can work on this project ; D

[jsupasil]

Hello. From what I understand, "quantum minimum searching algorithm" is the search problem that have unknown number of solutions which is an issue for Grover's algorithm. However, this paper https://arxiv.org/abs/quant-ph/9605034 which was written from the same author has shown the method to solve it. I understand that we may need to observe the state and re-initial circuit for some iterations before get an answer. If I understand correctly, the expected time is still be the same as Grover's algorithm with known number of solutions (but have to implement more than one circuit ).

[xenoicwyce]

@Naphann Thanks for your superb idea. In that case, is the input going to be the superposition of all the possible paths? And then we will mark the minimum distance with (-) sign, and also flip back the sign which is previously marked (-) if a new minimum is detected in every iteration?

[jsupasil]

I am interested.

[coscoskoskos]

I'm interested in this project!

[ranaarp]

I'm interested too!

[Naphann]

I'm Naphan Benchasattabuse. I'm in :)

[jsupasil]

@coscoskoskos we already have a table. You may come to join us :)

[xenoicwyce]

I'm interested. I'm Lee Xin Wei.

[Naphann]

• This is the link to our GDoc for ideas.
• This is the link to presentation

[Naphann]

The repo

Also for the adder, I think we can use this

[Naphann]

This paper explains in details how to implement a better MCT than the qiskit ones

[xenoicwyce]

https://medium.com/mdr-inc/checking-the-unitary-matrix-of-the-quantum-circuit-on-qiskit-5968c6019a45

[xenoicwyce]

https://algassert.com/quirk

[coscoskoskos]

2019年11月20日(水) 9:44 xenoicwyce notifications@github.com:

https://algassert.com/quirk

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/qiskit-community/qiskit-camp-asia-19/issues/8?email_source=notifications&email_token=AMAZDJG4JR22VRGAABS7PDTQUSB5BA5CNFSM4JKRZU42YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEEQJFKQ#issuecomment-555782826, or unsubscribe https://github.com/notifications/unsubscribe-auth/AMAZDJCAGDVB3RZJ763EK2LQUSB5BANCNFSM4JKRZU4Q .

[Naphann]

https://github.com/Naphann/Solving-TSP-Grover The Repo I put it here again

[Naphann]

This is the slides we used for our presentations