Reducing the Number of Qubits from $n^2$ to $n{\log }_2(n)$ to Solve the Traveling Salesman Problem with Quantum Computers: A Proposal for Demonstrating Quantum Supremacy in the NISQ Era

Abstract

In our pursuit of quantum supremacy during the NISQ era, this research introduces a novel approach rooted in the Quantum Approximate Optimization Algorithm (QAOA) framework to address the Traveling Salesman Problem (TSP). By strategically reducing the requisite qubit count from $n^2$ to $n{\log }_2(n)$, our QAOA-based algorithm not only contributes to the ongoing discourse on qubit efficiency but also demonstrates improved performance based on established metrics, underscoring its potential for achieving NISQ-era supremacy in solving real-world optimization challenges.

4+2 pages, 1 figure