Integer Programming from Quantum Annealing and Open Quantum Systems

• URL: http://arxiv.org/abs/2009.11970v1
• Date: Thu, 24 Sep 2020 22:18:01 GMT
• Title: Integer Programming from Quantum Annealing and Open Quantum Systems
• Authors: Chia Cheng Chang, Chih-Chieh Chen, Christopher Koerber, Travis S. Humble, Jim Ostrowski
• Abstract summary: We develop an algorithm that solves integer linear programming problems, a classically NP-hard problem, on a quantum annealer. We find that the algorithm outperforms random guessing but is limited to small problems.
• Score: 0.8049701904919515
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While quantum computing proposes promising solutions to computational problems not accessible with classical approaches, due to current hardware constraints, most quantum algorithms are not yet capable of computing systems of practical relevance, and classical counterparts outperform them. To practically benefit from quantum architecture, one has to identify problems and algorithms with favorable scaling and improve on corresponding limitations depending on available hardware. For this reason, we developed an algorithm that solves integer linear programming problems, a classically NP-hard problem, on a quantum annealer, and investigated problem and hardware-specific limitations. This work presents the formalism of how to map ILP problems to the annealing architectures, how to systematically improve computations utilizing optimized anneal schedules, and models the anneal process through a simulation. It illustrates the effects of decoherence and many body localization for the minimum dominating set problem, and compares annealing results against numerical simulations of the quantum architecture. We find that the algorithm outperforms random guessing but is limited to small problems and that annealing schedules can be adjusted to reduce the effects of decoherence. Simulations qualitatively reproduce algorithmic improvements of the modified annealing schedule, suggesting the improvements have origins from quantum effects.

Related papers

• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• Formulation and evaluation of ocean dynamics problems as optimization problems for quantum annealing machines [0.0]
  Recent advancements in quantum computing suggest the potential to revolutionize computational algorithms across various scientific domains. Quantum computation is so different from classical computation that suitable frameworks to represent oceanic and atmospheric dynamics are yet to be explored.
  arXiv  Detail & Related papers  (2024-05-20T04:55:32Z)
• Graph Learning for Parameter Prediction of Quantum Approximate Optimization Algorithm [14.554010382366302]
  Quantum Approximate Optimization (QAOA) stands out for its potential to efficiently solve the Max-Cut problem. We use Graph Neural Networks (GNN) as a warm-start technique to optimize QAOA, using GNN as a warm-start technique. Our findings show GNN's potential in improving QAOA performance, opening new avenues for hybrid quantum-classical approaches in quantum computing.
  arXiv  Detail & Related papers  (2024-03-05T20:23:25Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future. In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
  arXiv  Detail & Related papers  (2024-01-25T17:37:40Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Variational Quantum Algorithms for Computational Fluid Dynamics [0.0]
  Variational quantum algorithms are particularly promising since they are comparatively noise tolerant. We show how variational quantum algorithms can be utilized in computational fluid dynamics. We argue that a quantum advantage over classical computing methods could be achieved by the end of this decade.
  arXiv  Detail & Related papers  (2022-09-11T18:49:22Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• 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)
• 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)
• 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.