A parallel and distributed fixed-point quantum search algorithm for solving SAT problems

• URL: http://arxiv.org/abs/2604.09980v1
• Date: Sat, 11 Apr 2026 01:28:20 GMT
• Title: A parallel and distributed fixed-point quantum search algorithm for solving SAT problems
• Abstract summary: Solving the SAT problem requires $mathcalO(sqrt2n)$ queries--where n denotes the number of logic variables in the problem.<n>We propose a parallel fixed-point (PFP) search algorithm to solve the SAT problem.
• Score: 6.341973606434514
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Boolean satisfiability (SAT) problem is of fundamental importance in computer science and many application domains. For Grover's algorithm, solving the SAT problem requires $\mathcal{O}(\sqrt{2^n})$ queries--where n denotes the number of logic variables in the problem. However, Grover's algorithm suffers from the Souffle problem: specifically, when the number of solutions is unknown, terminating the algorithm too early or too late leads to a significant reduction in the probability of obtaining a solution. In this paper, we propose a parallel fixed-point (PFP) search algorithm to solve the SAT problem. By exploiting entanglement, each clause in the conjunctive normal form (CNF) formula can be processed independently, leading to a significant reduction in circuit depth. We also discuss how to perform the algorithm in distributed manner. These make the PFPS algorithm particularly suitable for the noisy intermediate-scale quantum (NISQ) era.

Related papers

• Quantangle-SAT: A Quantum SAT Solver Based on Entanglement and Equivalence Checking [2.0164889460156417]
  We propose a novel quantum SAT solver based on entanglement and equivalence checking.<n>Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting.
  arXiv  Detail & Related papers  (2026-04-20T13:03:08Z)
• Distributed quantum-classical hybrid algorithm for solving K-SAT problem [2.909558920415837]
  Recently, Dunjko et al.(PRL) proposed an algorithm for accelerating the solution of 3-satisfiability problems using a small-scale quantum computer.<n>In this paper, we design a distributed quantum-classical hybrid algorithm for solving K-satisfiability problems.
  arXiv  Detail & Related papers  (2026-04-15T16:36:42Z)
• 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)
• Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems [1.4513830934124627]
  We propose a two-step quantum search (TSQS) algorithm that employs two sets of operators.<n>In the first step, all the feasible solutions are amplified into their equal superposition state.<n>In the second step, the optimal solution state is amplified from this superposition state.
  arXiv  Detail & Related papers  (2024-05-12T01:44:19Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Quantum Teleportation [1.5201992393140886]
  We develop a parallel quantum SAT solver, which reduces the time complexity in each iteration from linear time O(m) to constant time O(1) by utilising extra entangled qubits. We have proved the correctness of our approaches and demonstrated them in simulations.
  arXiv  Detail & Related papers  (2023-08-07T06:52:06Z)
• Quantum optimization algorithm based on multistep quantum computation [0.0]
  We present a quantum algorithm for finding the minimum of a function based on multistep quantum computation. In this algorithm, the dimension of the search space of the problem can be reduced exponentially step by step. We have tested the algorithm for some continuous test functions.
  arXiv  Detail & Related papers  (2023-06-30T01:58:23Z)
• Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis [2.0981723008692392]
  We show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We outline how this algorithm can be applied by adiabatic quantum computers.
  arXiv  Detail & Related papers  (2022-10-28T12:22:15Z)
• 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)
• Towards Meta-Algorithm Selection [78.13985819417974]
  Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates. We show that meta-algorithm-selection can indeed prove beneficial in some cases.
  arXiv  Detail & Related papers  (2020-11-17T17:27:33Z)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  We propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution.
  arXiv  Detail & Related papers  (2020-09-11T17:31:39Z)
• 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)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.<n>The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.<n>It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.