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.