Circuit Design of Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems

• URL: http://arxiv.org/abs/2405.07129v2
• Date: Mon, 07 Oct 2024 12:35:27 GMT
• Title: Circuit Design of Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
• Authors: Rei Sato, Gordon Cui, Kazuhiro Saito, Hideyuki Kawashima, Tetsuro Nikuni, Shohei Watabe,
• Abstract summary: 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.
• Score: 1.4513830934124627
• License:
• Abstract: Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state -- an equal superposition of all feasible solutions satisfying the problem's constraints -- is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, 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. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher-order unconstrained binary optimization (HOBO) representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.

Related papers

• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• 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)
• Optimized General Uniform Quantum State Preparation [0.0]
  We develop an optimized general solver for a circuit that prepares a uniform superposition of any N states while minimizing depth and without the use of ancillary qubits. We show that this algorithm is efficient, especially in its use of two wire gates, and that it has been verified on an IonQ quantum computer and through application to a quantum unstructured search algorithm.
  arXiv  Detail & Related papers  (2023-11-30T22:40:33Z)
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications [44.88678858860675]
  We investigate the application of the quantum approximate optimization algorithm (QAOA) and the quantum adiabatic algorithm (QAA) to the solution of a prototypical model in this field. We compare the performance of these two algorithms in terms of solution quality, using selected evaluation metrics.
  arXiv  Detail & Related papers  (2023-11-20T09:09:55Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum Dueling: an Efficient Solution for Combinatorial Optimization [3.7398607565670536]
  We present a new algorithm for generic optimization, which we term quantum dueling. Quantum dueling innovates by integrating an additional qubit register, effectively creating a dueling'' scenario where two sets of solutions compete. Our work demonstrates that increasing the number of qubits allows the development of previously unthought-of algorithms, paving the way for advancement of efficient quantum algorithm design.
  arXiv  Detail & Related papers  (2023-02-20T18:33:55Z)
• A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem [2.208581695286558]
  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%.
  arXiv  Detail & Related papers  (2022-12-06T03:54:07Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)
• 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.