Quantum Computing for a Profusion of Postman Problem Variants
- URL: http://arxiv.org/abs/2208.08397v1
- Date: Wed, 17 Aug 2022 16:42:23 GMT
- Title: Quantum Computing for a Profusion of Postman Problem Variants
- Authors: Joel E. Pion, Christian F. A. Negre, Susan M. Mniszewski
- Abstract summary: We study the viability of solving the Chinese Postman Problem, a graph routing optimization problem.
We put emphasis on the explanation of how to convert such problems into quadratic unconstrained binary optimization problems.
We also expand upon a previously discovered algorithm for solving the Chinese Postman Problem on a closed undirected graph.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this paper we study the viability of solving the Chinese Postman Problem,
a graph routing optimization problem, and many of its variants on a quantum
annealing device. Routing problem variants considered include graph type,
directionally varying weights, number of parties involved in routing, among
others. We put emphasis on the explanation of how to convert such problems into
quadratic unconstrained binary optimization (QUBO) problems, one of two
equivalent natural paradigms for quantum annealing devices. We also expand upon
a previously discovered algorithm for solving the Chinese Postman Problem on a
closed undirected graph to decrease the number of constraints and variables
used in the problem. Optimal annealing parameter settings and constraint weight
values are discussed based on results from implementation on the D-Wave 2000Q
and Advantage. Results from classical, purely quantum, and hybrid algorithms
are compared.
Related papers
- Quantum Speedup for the Quadratic Assignment Problem [6.106029308649016]
We show that the search space of the quadratic assignment problem can be reduced using Grover adaptive search (GAS) with Dicke state operators.
We also show that the phase gate in the GAS can be replaced by a rotation gate about the Z axis, simplifying the quantum circuit without any penalty.
arXiv Detail & Related papers (2024-10-16T03:00:37Z) - 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) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation.
The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large.
We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
arXiv Detail & Related papers (2023-11-16T09:19:01Z) - Improving Performance in Combinatorial Optimization Problems with
Inequality Constraints: An Evaluation of the Unbalanced Penalization Method
on D-Wave Advantage [0.0]
A new method known as unbalanced penalization has been presented to avoid using slack variables.
This work tests the unbalanced penalization method using real quantum hardware on D-Wave Advantage for the traveling salesman problem (TSP)
The results show that the unbalanced penalization method outperforms the solutions found using slack variables.
arXiv Detail & Related papers (2023-05-30T05:40:50Z) - 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) - 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) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - 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) - Investigating the Chinese Postman Problem on a Quantum Annealer [0.0]
D-Wave annealers are promising platforms to solve problems in the form of quadratic unconstrained binary optimization.
We provide a formulation of the Chinese postman problem that can be used as a tool for probing the local connectivity of graphs and networks.
arXiv Detail & Related papers (2020-08-06T17:11:54Z) - Modeling Linear Inequality Constraints in Quadratic Binary Optimization
for Variational Quantum Eigensolver [0.0]
This paper introduces the use of tailored variational forms for variational quantum eigensolver.
Four constraints that usually appear in several optimization problems are modeled.
The main advantage of the proposed methodology is that the number of parameters on the variational form remain constant.
arXiv Detail & Related papers (2020-07-26T23:36:22Z)
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.