Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler

• URL: http://arxiv.org/abs/2406.14252v1
• Date: Thu, 20 Jun 2024 12:25:00 GMT
• Title: Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler
• Authors: Daniel Goldsmith, Joe Day-Evans,
• Abstract summary: We present a novel formulation which needs fewer binary variables, and where, by design, there are no penalty terms because all outputs from the quantum device are mapped to valid routes. Although we worked with a boson sampler, we believe that this novel formulation is relevant to other quantum devices.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: The Travelling Salesman Problem (TSP) is an important combinatorial optimisation problem, and is usually solved on a quantum computer using a Quadratic Unconstrained Binary Optimisation (QUBO) formulation or a Higher Order Binary Optimisation(HOBO) formulation. In these formulations, penalty terms are added to the objective function for outputs that don't map to valid routes. We present a novel formulation which needs fewer binary variables, and where, by design, there are no penalty terms because all outputs from the quantum device are mapped to valid routes. Simulations of a quantum boson sampler were carried out which demonstrate that larger networks can be solved with this penalty-free formulation than with formulations with penalties. Simulations were successfully translated to hardware by running a non-QUBO formulation with penalties on an early experimental prototype ORCA PT-1 boson sampler. Although we worked with a boson sampler, we believe that this novel formulation is relevant to other quantum devices. This work shows that a good embedding for combinatorial optimisation problems can solve larger problems with the same quantum computing resource. The flexibility of boson sampling quantum devices is a powerful asset in solving combinatorial optimisation problem, because it enables formulations where the output string is always mapped to a valid solution, avoiding the need for penalties.

Related papers

• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems [0.0]
  Closest String Problem is an NP-complete problem which appears more commonly in bioinformatics and coding theory. Two QUBO formulations have been proposed, with one being a slight modification over the other. DWave annealers have been used, while providing guidelines for optimality on certain platform-specific concerns.
  arXiv  Detail & Related papers  (2023-10-19T16:03:25Z)
• QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing [4.589533935256401]
  The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence. Recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup. We introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing.
  arXiv  Detail & Related papers  (2023-09-22T07:37:20Z)
• 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)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• 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)
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization [0.0]
  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 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.
  arXiv  Detail & Related papers  (2021-06-16T18:01:31Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Multimodal Container Planning: a QUBO Formulation and Implementation on a Quantum Annealer [0.0]
  We present an application on multimodal container planning. We show how to map this problem to a QUBO problem formulation and how the practical implementation can be done on the quantum annealer produced by D-Wave Systems.
  arXiv  Detail & Related papers  (2020-07-03T14:51:41Z)
• Quantum Approximate Optimization for Hard Problems in Linear Algebra [0.0]
  We explore using QAOA for Binary Linear Least Squares (BLLS) as a building block of several other hard problems in linear algebra. For the scope of this work, our experiments were done on noiseless quantum simulators, a simulator including a device-realistic noise-model, and two IBM Q 5-qubit machines. Our numerics show that Simulated Annealing can outperform QAOA for BLLS at a QAOA depth of $pleq3$ for the probability of sampling the ground state.
  arXiv  Detail & Related papers  (2020-06-27T20:13:24Z)

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.