The travelling salesman problem and adiabatic quantum computation: an algorithm

DOI10.1007/S11128-019-2206-9MaRDI QIDQ670009zbMATH OpenOpenAlexFDO

Authors T. D. Kieu

Publication date 15 March 2019

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.07859

zbMATH Keywords

adiabatic quantum computationquantum algorithmstravelling salesman problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Point estimation (62F10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Selfadjoint operator theory in quantum theory, including spectral analysis (81Q10) Coherent states (81R30) Combinatorial optimization (90C27)

Abstract: An explicit algorithm for the travelling salesman problem is constructed in the framework of adiabatic quantum computation, AQC. The initial Hamiltonian for the AQC process admits canonical coherent states as the ground state, and the target Hamiltonian has the shortest tour as the desirable ground state. Some estimates/bounds are also given for the computational complexity of the algorithm with particular emphasis on the required energy resources, besides the space and time complexity, for the physical process of (quantum) computation in general.

Recommendations

• Adapting the traveling salesman problem to an adiabatic quantum computer
• The complexity of the quantum adiabatic algorithm
• An alternative adiabatic quantum algorithm for the Hamiltonian cycle problem
• scientific article; zbMATH DE number 1984609
• Quantum branch-and-bound algorithm and its application to the travelling salesman problem

Cites work

• Energy and efficiency of adiabatic quantum search algorithms
• scientific article; zbMATH DE number 3167699 (Why is no real title available?)
• scientific article; zbMATH DE number 5320186 (Why is no real title available?)
• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• Maximum speedup in quantum search: \(O\)(1) running time
• Performance of two different quantum annealing correction codes
• Quantum computation and quantum information. 10th anniversary edition
• QUANTUM PHASE TRANSITIONS AND ENTANGLEMENT IN J₁–J₂ MODEL
• The traveling salesman problem. A computational study.
• The travelling salesman problem and adiabatic quantum computation: an algorithm

Cited in

(12)

• Quantizers ad the worst case Euclidean traveling salesman problem
• Entangling problem Hamiltonian for adiabatic quantum computation
• Quantum branch-and-bound algorithm and its application to the travelling salesman problem
• Eigenpath traversal by phase randomization
• Adapting the traveling salesman problem to an adiabatic quantum computer
• A class of time-energy uncertainty relations for time-dependent Hamiltonians
• An alternative adiabatic quantum algorithm for the Hamiltonian cycle problem
• ON THE PRACTICALITY OF ADIABATIC QUANTUM COMPUTING WITH OPTICAL SCHEMES
• Solving the traveling salesman problem with a hybrid quantum-classical feedforward neural network
• A study of heuristic guesses for adiabatic quantum computation
• The travelling salesman problem and adiabatic quantum computation: an algorithm
• Dynamic programming in economics on a quantum annealer

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: The travelling salesman problem and adiabatic quantum computation: an algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q670009)