Runtime-coherence trade-offs for hybrid SAT-solvers

• URL: http://arxiv.org/abs/2404.15235v1
• Date: Tue, 23 Apr 2024 17:11:39 GMT
• Title: Runtime-coherence trade-offs for hybrid SAT-solvers
• Authors: Vahideh Eshaghian, Sören Wilkening, Johan Åberg, David Gross,
• Abstract summary: We argue that there exists a simple trade-off relation between the total runtime and the coherence-time. We present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.
• Score: 1.087459729391301
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many search-based quantum algorithms that achieve a theoretical speedup are not practically relevant since they require extraordinarily long coherence times, or lack the parallelizability of their classical counterparts.This raises the question of how to divide computational tasks into a collection of parallelizable sub-problems, each of which can be solved by a quantum computer with limited coherence time. Here, we approach this question via hybrid algorithms for the k-SAT problem. Our analysis is based on Sch\"oning's algorithm, which solves instances of k-SAT by performing random walks in the space of potential assignments. The search space of the walk allows for "natural" partitions, where we subject only one part of the partition to a Grover search, while the rest is sampled classically, thus resulting in a hybrid scheme. In this setting, we argue that there exists a simple trade-off relation between the total runtime and the coherence-time, which no such partition based hybrid-scheme can surpass. For several concrete choices of partitions, we explicitly determine the specific runtime coherence-time relations, and show saturation of the ideal trade-off. Finally, we present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.

Related papers

• Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
  Combination of Quantum Minimum Finding and dynamic programming has proved particularly efficient in improving the complexity of NP-hard problems. In this paper, we provide a bounded-error hybrid algorithm that achieves such an improvement for a broad class of NP-hard single-machine scheduling problems. Our algorithm reduces the exponential-part complexity compared to the best-known classical algorithm, sometimes at the cost of an additional pseudo-polynomial factor.
  arXiv  Detail & Related papers  (2024-08-11T10:28:49Z)
• Quantum Dissipative Search via Lindbladians [0.0]
  We analyze the convergence criteria and the convergence speed of a Markovian, purely dissipative quantum random walk on an unstructured search space. We map the results onto an actual implementation to correctly estimate the potential and show that it is no more efficient than classical search.
  arXiv  Detail & Related papers  (2024-07-16T14:39:18Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
  We consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We apply our method to some simple quantum speedups of classical algorithms for solving the well-studied MAX-$k$-SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines.
  arXiv  Detail & Related papers  (2022-03-09T19:00:00Z)
• Parallelizing Contextual Linear Bandits [82.65675585004448]
  We present a family of (parallel) contextual linear bandit algorithms, whose regret is nearly identical to their perfectly sequential counterparts. We also present an empirical evaluation of these parallel algorithms in several domains, including materials discovery and biological sequence design problems.
  arXiv  Detail & Related papers  (2021-05-21T22:22:02Z)
• Hybrid divide-and-conquer approach for tree search algorithms [0.0]
  We study the hybrid divide-and-conquer method in the context of tree search algorithms. We provide conditions for speedups for the well known algorithm of DPLL. We briefly discuss the limitations of hybrid methods in providing speed-ups for larger problems.
  arXiv  Detail & Related papers  (2020-07-14T13:57:12Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.