Hybrid divide-and-conquer approach for tree search algorithms

• URL: http://arxiv.org/abs/2007.07040v4
• Date: Mon, 20 Mar 2023 11:56:22 GMT
• Title: Hybrid divide-and-conquer approach for tree search algorithms
• Authors: Mathys Rennela, Sebastiaan Brand, Alfons Laarman, Vedran Dunjko
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  We describe and experimentally validate an exact classical branch and bound solver for quadratic unconstrained binary optimization problems. Our solver leverages cheap-to-implement bounds from the literature previously proposed for Ising models. We detail a variety of techniques from high-performance computing and operations research used to boost solver performance.
  arXiv  Detail & Related papers  (2024-07-29T17:13:01Z)
• Runtime-coherence trade-offs for hybrid SAT-solvers [1.087459729391301]
  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.
  arXiv  Detail & Related papers  (2024-04-23T17:11:39Z)
• 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 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)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Hybrid Quantum-Classical Search Algorithms [0.0]
  We show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. We generalize this result to algorithms with subconstant success probabilities.
  arXiv  Detail & Related papers  (2022-02-23T11:43:17Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Multi-layer quantum search and inclusion of NP into BQP [6.362434591714693]
  We present a multi-layer quantum search method that generates an exponential speedup of the standard Grover's algorithm. Our results show that the speedup of quantum circuits is ubiquitous, and Grover's search is much more powerful than that has been demonstrated.
  arXiv  Detail & Related papers  (2020-04-23T17:44:51Z)
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed [0.0]
  We report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state.
  arXiv  Detail & Related papers  (2020-01-13T19:01:09Z)

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.