A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem

• URL: http://arxiv.org/abs/2212.02735v1
• Date: Tue, 6 Dec 2022 03:54:07 GMT
• Title: A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem
• Authors: Jieao Zhu, Yihuai Gao, Hansen Wang, Tiefu Li, and Hao Wu
• Abstract summary: The paper proposes a quantum algorithm for the traveling salesman problem (TSP) based on the Grover Adaptive Search (GAS) The strategy fully considers the reversibility requirement of quantum computing, overcoming the difficulty that the used qubits cannot be simply overwritten or released. For the seven-node TSP, we only need 31 qubits, and the success rate in obtaining the optimal solution is 86.71%.
• Score: 2.208581695286558
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The paper proposes a quantum algorithm for the traveling salesman problem (TSP) based on the Grover Adaptive Search (GAS), which can be successfully executed on IBM's Qiskit library. Under the GAS framework, there are at least two fundamental difficulties that limit the application of quantum algorithms for combinatorial optimization problems. One difficulty is that the solutions given by the quantum algorithms may not be feasible. The other difficulty is that the number of qubits of current quantum computers is still very limited, and it cannot meet the minimum requirements for the number of qubits required by the algorithm. In response to the above difficulties, we designed and improved the Hamiltonian Cycle Detection (HCD) oracle based on mathematical theorems. It can automatically eliminate infeasible solutions during the execution of the algorithm. On the other hand, we design an anchor register strategy to save the usage of qubits. The strategy fully considers the reversibility requirement of quantum computing, overcoming the difficulty that the used qubits cannot be simply overwritten or released. As a result, we successfully implemented the numerical solution to TSP on IBM's Qiskit. For the seven-node TSP, we only need 31 qubits, and the success rate in obtaining the optimal solution is 86.71%.

Related papers

• Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
  The travelling salesman problem (TSP) is a popular NP-hard-combinatorial optimization problem. We present an algorithm that solves an arbitrary TSP using a single qubit by invoking the principle of quantum parallelism. The underlying framework of our algorithm is a quantum version of the classical Brachistochrone approach.
  arXiv  Detail & Related papers  (2024-07-24T12:06:37Z)
• Circuit Design of Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems [1.4513830934124627]
  We propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state.
  arXiv  Detail & Related papers  (2024-05-12T01:44:19Z)
• A Framework to Formulate Pathfinding Problems for Quantum Computing [2.9723999564214267]
  We propose a framework to automatically generate QUBO formulations for pathfinding problems. It supports three different encoding schemes that can easily be compared without requiring manual reformulation efforts. The resulting QUBO formulations are robust and efficient, reducing the previously tedious and error-prone reformulation process.
  arXiv  Detail & Related papers  (2024-04-16T18:00:06Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation Algorithm [7.581898299650999]
  We introduce a simple yet efficient algorithm named Quantum Qubit Rotation Algorithm (QQRA) The approximate solution of the max-cut problem can be obtained with probability close to 1. We compare it with the well known quantum approximate optimization algorithm and the classical Goemans-Williamson algorithm.
  arXiv  Detail & Related papers  (2021-10-15T11:19:48Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.