Reducing the Number of Qubits from n² to nlog₂ (n) to Solve the Traveling Salesman Problem with Quantum Computers: A Proposal for Demonstrating Quantum Supremacy in the NISQ Era

2024/02/28 by Ramezani, Mehdi, Salami, Sadegh, Shokhmkar, Mehdi +2 · 2 citations
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2402.18530

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² to nlog₂ (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.

Cited by

• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem
• Resource-efficient variational quantum solver for the travelling salesman problem and its silicon photonics implementation

Related

• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Theory and Implementation of the Quantum Approximate Optimization Algorithm: A Comprehensible Introduction and Case Study Using Qiskit and IBM Quantum Computers
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Strategies for running the QAOA at hundreds of qubits
• QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem