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:
- Where does the speed-up come from if we need to have all Hamiltonian cycles in TSP listed in advance?
- 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).
