4
$\begingroup$

Recently a pre-print of article Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience appeared. The authors use a phase estimation as a core for their algorithm. This part of the algorithm is used for a length calculation of a particular Hamiltonian cycle in TSP.

After that a minimization algorithm introduced in A Quantum Algorithm for Finding the Minimum is employed to find an actual soulution of TSP.

Briefly, the proposed algorithm work as follows:

Firstly a matrix $A$ containing distances among $N$ cities (i.e. element $a_{ij}$ is distance from city $i$ to city $j$) is converted to matrix $B$ which elements are $b_{ij} = \mathrm{e^{i a_{ij}}}$ in order to represent distances among cities as a phase. Note that $a_{ij}$ are normalized on interval $(0;2\pi)$.

After that, for each city a diagonal matrix $U^{(i)}$ is constructed. An element $u^{(i)}_{jj} = b_{ij}$ i.e. a distance from city $i$ to city $j$.

Then a final operator $U = U^{(1)}\otimes U^{(2)} \otimes \dots \otimes U^{(N)}$ is constructed. The matrix $U$ is diagonal hence its eigenvectors are vectors constituing z-basis (or standard basis) and respective eigenvalues are diagonal elements of the matrix. Because of approach how $U$ is constructed, $(N-1)!$ of $N^N$ diagonal elements contain length of all possible Hamiltonian cycles in TSP.

Each Hamiltonian cycle can be represented wiht eigenvector obtained followingly:

$$ |\psi\rangle = \otimes_{j} |i(j) - 1\rangle $$ for $j \in \{1\dots N\}$ and function $i(j)$ returns city $i$ we traveled to $j$ from. For example, consider four cities and cycle $1 \rightarrow 2 \rightarrow 3\rightarrow 4\rightarrow 1$. In this case

  • $i(1) - 1 = 4 - 1 = 3$, so $|3_{10}\rangle = |11\rangle$
  • $i(2) - 1 = 1 - 1 = 0$, so $|0_{10}\rangle = |00\rangle$
  • $i(3) - 1 = 2 - 1 = 1$, so $|1_{10}\rangle = |01\rangle$
  • $i(4) - 1 = 3 - 1 = 2$, so $|2_{10}\rangle = |10\rangle$

Hence $|\psi\rangle = |11 00 01 10\rangle$. Multiplication $U|\psi\rangle$ returns lenght of the Hamiltonian cycle.

This setting allows to use phase estimation to get lenght of a cycle. Setting respective $\psi$ as an input to phase estimation leads after inverse Fourier transform to obtaining lenght of the cycle.

So far, I understand everything. However, the authors proposed:

We get the phases in form of binary output from phase estimation algorithm, then we can easily perform the quantum algorithm for finding the minimum [10] to find the minimum cost and the corresponding route that is to be taken for that particular cost.

Note that [10] is the second article I mentioned above.

Since the complexity of minimum finding is $\mathcal{O}(\sqrt{N})$ we get quadratic speed-up for TSP solving, so complexity of TSP would be $\mathcal{O}(\sqrt{(N-1)!})$. But if my understanding is correct, we need to have a table of all Hamiltonian cycles prepared before phase estimation and to prepare a quantum state which is superposition of all eigenstates describing these cycles.

But to prepare all cycles in advance will take $\mathcal{O}((N-1)!)$ time unless there is a faster algorithm for permutation generation.

So my questions are:

  1. Where does the speed-up come from if we need to have all Hamiltonian cycles in TSP listed in advance?
  2. Is there a quantum algorithm for preparing all permutation of set $\{1 \dots N\}$ faster than on classical computer?

Note: since the paper is a pre-print there are some mistakes, e.g. $d+c-a-b$ in equation (8) should be d-c+a-b. Figure S1 is not completed, moreover, there is a more efficient way how to implement $\mathrm{C-U^{(i)}}$ gate (avoiding Toffolis).

$\endgroup$
  • 2
    $\begingroup$ The abstract and introduction of the paper only talk about a quadratic improvement over the classical brute force method, which is what you’ve understood. I think they’re misusing the term efficient in the title. $\endgroup$ – DaftWullie Jan 13 at 6:47
  • $\begingroup$ @DaftWullie: Thanks for answer, I had the same opinion. But what about preparing the table of Hamiltonian cycles? Am I right that the table has to be prepared in advance? If yes, is there a more efficient "quantum" way how to do so? $\endgroup$ – Martin Vesely Jan 13 at 10:16
  • 1
    $\begingroup$ I've not read the paper in sufficient detail (and don't have time right now). I was drawn in by the title of the paper you were referencing which seems quite misleading, so thought I'd make a note for others in a similar position. $\endgroup$ – DaftWullie Jan 13 at 10:19
2
$\begingroup$

Based on comment by DaftWullie and my experience with the algortihm, it seems that a title of the article is misleading.

The authors claim that algorithm they proposed is efficient. However, this is true only partialy. The authors devised only part of an algorithm for solving TSP. In particular, they are able to calculate length of a Hamiltonian cycle described by an eigenstate but this has to be provided in advance. The authors also mentioned application of a quantum function minimization algorithm but this algorithm is based on assumption that we have a list of all possible function values. In this case these values are eigenstates representing all Hamiltonian cycles and there are $(n-1)!$ such eigenstates. Moreover, the list has to be stored in a memory (maybe qRAM). However, qRAM is rather experimental nowadays.

To sum up:

  • The proposed algorithm is in fact only part of complete algorithm for solving TSP
  • The algorithm is efficient only if it is possible to list all Hamiltonian cycles efficiently about which I am not sure (at least I was not able to find any algorithm for doing so) (THIS IS THE MAIN OBSTACLE)
  • The algorithm needs qRAM which is not avaiable now
| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Don't know is it useful or not: I just find in the Michael R. Garey, David S. Johnson "Computers and Intractability: A Guide to the Theory of NP-Completeness" book a theorem on page 56: Teorem 3.4 Hamiltonian circuit is NP-complete. So even finding one single Hamiltonian circuit/cycle is an NP-complete problem. $\endgroup$ – Davit Khachatryan Mar 14 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.