Important Quantum Gates for Quantum Algorithms of Travelling Salesman Problem
Taruli Jeremia Halasan Sinaga, Khoirul Anwar, Nadya Amalia, Gagus Ketut Sunnardianto, Gelar Budiman · 2023
This paper proposes $B\left(\displaystyle \frac{1}{k}\right)$ gates as important gates to generate W state for the quantum approximate optimization algorithm (QAOA) to tackle the popular optimization problem known as the traveling salesman problem (TSP). We also provide a simple proof for the $B\left(\displaystyle \frac{1}{k}\right)$ gates followed by the corresponding quantum circuit. We present the Ising Hamiltonian tailored specifically for the TSP, including its associated constraints. We perform a performance comparison for QAOA with the conventional state initialization method involving the Hadamard gate and QAOA with state initialization using the W state. We found that the performance of QAOA is significantly influenced by two key factors of (i) the number of p layers and (ii) the chosen state initialization method. Our findings highlight that the generation and integration of W state initialization results in a substantial reduction in the search space for QAOA, consequently reducing the required number of p layers for the search process.