Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems

• URL: http://arxiv.org/abs/2310.12852v1
• Date: Thu, 19 Oct 2023 16:03:25 GMT
• Title: Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems
• Authors: Chandeepa Dissanayake
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Closest String Problem is an NP-complete problem which appears more commonly in bioinformatics and coding theory. Less surprisingly, classical approaches have been pursued with two prominent algorithms being the genetic algorithm and simulated annealing. Latest improvements to quantum computing devices with a specialization in optimization tasks such as DWave systems, suggest that an attempt to embed the problem in a model accepted by such systems is worthwhile. In this work, two QUBO formulations have been proposed, with one being a slight modification over the other. Subsequently, an evaluation based on a few simple test cases had been carried out on both formulations. In this regard, the D-Wave annealers have been used, while providing guidelines for optimality on certain platform-specific concerns. For evaluation purposes, a metric termed Occurrence Ratio (OR) has been defined. With minimal hyperparameter tuning, the expected solutions were obtained for every test case and the optimality was guaranteed. To address practical and implementation issues, an inherent decomposition strategy based on the possibility of having substrings has been elucidated to accommodate the restricted qubit count. Conclusively, the need for further investigation on tuning the hyperparameters is emphasized.

Related papers

• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  This paper introduces in detail a non-variational quantum algorithm designed to solve a wide range of optimisation problems. The algorithm returns optimal and near-optimal solutions from repeated preparation and measurement of an amplified state.
  arXiv  Detail & Related papers  (2024-07-29T13:54:28Z)
• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
  We formulate a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computationcolorblue. The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them. We benchmark the solution quality for multiple approaches: D-Wave's hybrid quantum-classical solvers, classicals, and a branch-and-bound solver.
  arXiv  Detail & Related papers  (2024-07-09T11:44:58Z)
• Dual-Directed Algorithm Design for Efficient Pure Exploration [11.492736493413103]
  We consider pure-exploration problems in the context of sequential adaptive experiments with a finite set of alternative options. We derive a sufficient condition for optimality in terms of a notion of strong convergence to the optimal allocation of samples. Our algorithm is optimal for $epsilon$-best-arm identification and thresholding bandit problems.
  arXiv  Detail & Related papers  (2023-10-30T07:29:17Z)
• Posiform Planting: Generating QUBO Instances for Benchmarking [2.7624021966289605]
  We propose a novel method, called posiform planting, for generating random QUBO instances of arbitrary size with known optimal solutions. Our experiments demonstrate the capability of the D-Wave quantum annealers to sample the optimal planted solution of optimization problems with up to $5627$ qubits.
  arXiv  Detail & Related papers  (2023-08-10T21:23:41Z)
• 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)
• Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
  We argue that noise makes evaluations of the objective function via quantum circuits biased. We derive the missing guarantees and find that the rate of convergence is unaffected.
  arXiv  Detail & Related papers  (2022-09-21T19:18:41Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.