Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization

Abstract

Quantum computing is offering a novel perspective for solving combinatorial optimization problems. To fully explore the possibilities offered by quantum computers, the problems need to be formulated as unconstrained binary models, taking into account limitation and advantages of quantum devices. In this work, we provide a detailed analysis of the Travelling Salesman Problem with Time Windows (TSPTW) in the context of solving it on a quantum computer. We introduce quadratic unconstrained binary optimization and higher order binary optimization formulations of this problem. We demonstrate the advantages of edge-based and node-based formulations of the TSPTW problem. Additionally, we investigate the experimental realization of the presented methods on a quantum annealing device. The provided results pave the path for utilizing quantum computer for a variety of real-world task which can be cast in the form of Travelling Salesman Problem with Time Windows problem.

arXiv comment26 pages

References in corpus (15)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Approximate Optimization Algorithm
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Defining and detecting quantum speedup
• Perspectives of quantum annealing: Methods and implementations
• Robustness of adiabatic quantum computation
• Quantum annealing of the Traveling Salesman Problem
• Next-Generation Topology of D-Wave Quantum Processors
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
• Readiness of Quantum Optimization Machines for Industrial Applications
• Quadratization in discrete optimization and quantum mechanics
• Space-efficient binary optimization for variational computing

Cited by in corpus (17)

• Error mitigation for variational quantum algorithms through mid-circuit measurements
• Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization
• Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
• Multi-disk clutch optimization using quantum annealing
• Performance analysis of a filtering variational quantum algorithm
• Statistical quality assessment of Ising-based annealer outputs
• Solving the Turbine Balancing Problem using Quantum Annealing
• Resource-Efficient Quantum Optimization via Higher-Order Encoding