Investigating the Chinese Postman Problem on a Quantum Annealer
- URL: http://arxiv.org/abs/2008.02768v3
- Date: Mon, 5 Oct 2020 22:28:26 GMT
- Title: Investigating the Chinese Postman Problem on a Quantum Annealer
- Authors: Ilaria Siloi, Virginia Carnevali, Bibek Pokharel, Marco Fornari and
Rosa Di Felice
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The recent availability of quantum annealers has fueled a new area of
information technology where such devices are applied to address practically
motivated and computationally difficult problems with hardware that exploits
quantum mechanical phenomena. D-Wave annealers are promising platforms to solve
these problems in the form of quadratic unconstrained binary optimization. Here
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. We treat the
problem classically with a tabu algorithm and using a D-Wave device. We
systematically analyze computational parameters associated with the specific
hardware. Our results clarify how the interplay between the embedding due to
limited connectivity of the Chimera graph, the definition of logical qubits,
and the role of spin-reversal controls the probability of reaching the expected
solution.
Related papers
- Replication-based quantum annealing error mitigation [1.0878040851638]
We propose a new approach called replication based mitigation (RBM) based on parallel quantum annealing.
In RBM, physical qubits representing the same logical qubit are dispersed across different copies of the problem embedded in the hardware.
This mitigates hardware biases, is compatible with limited qubit connectivity in current annealers, and is suited for available noisy intermediate-scale quantum (NISQ) annealers.
arXiv Detail & Related papers (2024-04-09T19:06:26Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks.
In this work, we explore the potential of using this information for probabilistic balanced k-means clustering.
Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost.
This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
arXiv Detail & Related papers (2023-10-18T17:59:45Z) - Exploring the Potential of Qutrits for Quantum Optimization of Graph
Coloring [0.0]
Qutrits may be useful in solving some problems on near-term devices.
We run noiseless simulations using PennyLane to compare the formulation against qubit-based QAOA.
This work suggests that qutrits may be useful in solving some problems on near-term devices, however further work is required to assess their potential in a noisy environment.
arXiv Detail & Related papers (2023-08-15T21:31:37Z) - Efficient MILP Decomposition in Quantum Computing for ReLU Network
Robustness [2.854196251981274]
In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP)
We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach.
Our experimental results demonstrate that this approach can save up to 90% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.
arXiv Detail & Related papers (2023-04-30T13:10:56Z) - 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) - Noise Dynamics of Quantum Annealers: Estimating the Effective Noise
Using Idle Qubits [0.0]
We show that long term trends in solution quality exist on the D-Wave device, and that the unused qubits can be used to measure the current level of noise of the quantum system.
In this work, we embed a disjoint random QUBO on the unused parts of the chip alongside the QUBO to be solved, which acts as an indicator of the solution quality of the device over time.
arXiv Detail & Related papers (2022-09-12T23:06:51Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - Quantum annealing in the NISQ era: railway conflict management [0.44040106718326594]
We consider a practical railway dispatching problem: delay and conflict management on single-track railway lines.
We introduce a quadratic unconstrained binary optimization (QUBO) model of this problem, compatible with the emerging quantum annealing technology.
As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers.
arXiv Detail & Related papers (2021-12-07T13:17:21Z) - 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) - Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
We review and extend the application of deep learning to quantum geometric control problems.
We demonstrate enhancements in time-optimal control in the context of quantum circuit synthesis problems.
Our results are of interest to researchers in quantum control and quantum information theory seeking to combine machine learning and geometric techniques for time-optimal control problems.
arXiv Detail & Related papers (2020-06-19T19:12:14Z)
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.