On "Solving The Travelling Salesman Problem Using A Single Qubit" vs. Quantum Genetic Optimization: Are we there?

A recent work has proposed a revolutionary approach to optimize the Travelling Salesman Problem (TSP) using a single Quantum Bit (QuBit), by invoking the principle of quantum parallelism. Specifically, a quantum version of the classical Brachistochrone algorithm was presented, claiming to solve TSP with more accurate solutions, than existing quantum algorithms. More importantly, it was argued that, using the proposed method, potential speed-up of polynomial time over classical algorithms is achievable. In this work, we critically analyze these claims, with the main argument that the single-qubit approach is still, algorithmically, stochastic. We analyze the level of randomization of the single-qubit method, and develop an equivalently random Quantum Genetic Algorithm (QGA). We compare the optimality of our solution results with that obtained by the single-qubit method. We show that similar accuracy levels can be obtained, using our QGA, even with orders of magnitude fewer optimization iterations, which experimentally refutes some of the major claims within the single-qubit method proposal.