Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem

• URL: http://arxiv.org/abs/2307.07243v1
• Date: Fri, 14 Jul 2023 09:35:58 GMT
• Title: Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• Authors: Wenyang Qian, Robert A. M. Basili, Mary Eshaghian-Wilner, Ashfaq Khokhar, Glenn Luecke, James P. Vary
• Abstract summary: We tackle the Traveling Salesman Problem (TSP) using the quantum approximate optimization algorithm (QAOA) approach. We present numerical results obtained from the gate-based digital quantum simulator. We find a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run.
• Score: 0.06524460254566902
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The Traveling Salesman Problem (TSP) is one of the most often-used NP-Hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layerwise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.

Related papers

• Surrogate-guided optimization in quantum networks [0.9148747049384086]
  We propose an optimization algorithm to improve the design and performance of quantum communication networks. Our framework allows for more comprehensive quantum network studies, integrating surrogate-assisted optimization with existing quantum network simulators.
  arXiv  Detail & Related papers  (2024-07-24T11:55:18Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Quantum-Enhanced Simulation-Based Optimization for Newsvendor Problems [5.500172106704342]
  We exploit the enhanced efficiency of Quantum Amplitude Estimation (QAE) compared to classical Monte Carlo simulation. In this work, we make use of a quantum-enhanced algorithm for simulation-based optimization and apply it to solve a variant of the classical News problem known to be NP-hard.
  arXiv  Detail & Related papers  (2024-03-26T05:14:50Z)
• Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut Problems with QAOA [1.5047640669285467]
  Quantum approximate optimization algorithm (QAOA) is one of the popular quantum algorithms that are used to solve optimization problems via approximations. However, performing QAOA on virtual quantum computers suffers from a slow simulation speed for solving optimization problems. We propose techniques to accelerate QCS for QAOA using mathematical optimizations to compress quantum operations.
  arXiv  Detail & Related papers  (2023-12-05T06:08:57Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Performance comparison of optimization methods on variational quantum algorithms [2.690135599539986]
  Variational quantum algorithms (VQAs) offer a promising path towards using near-term quantum hardware for applications in academic and industrial research. We study the performance of four commonly used gradient-free optimization methods: SLSQP, COBYLA, CMA-ES, and SPSA.
  arXiv  Detail & Related papers  (2021-11-26T12:13:20Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• 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.