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

Parallel and Distributed Fixed-Point Quantum Search for SAT Problems

Introduction

The Boolean satisfiability (SAT) problem resides at the core of combinatorial and computational complexity, underpinning applications in verification, circuit design, and cryptanalysis. Designing quantum algorithms with improved efficiency and practical feasibility for SAT, particularly in the noisy intermediate-scale quantum (NISQ) era, is a strategic focus within quantum computation. The presented work introduces a parallel and distributed fixed-point (PFP) quantum search algorithm for SAT solving, optimizing for both circuit depth and robustness against the so-called Soufflé problem endemic to Grover-based strategies. Notably, the algorithm leverages entanglement-assisted parallelism at the clause level, and is distributable across multiple quantum nodes, aligning with current hardware limitations and future scalability requirements (2604.09980).

Background: Limitations of Grover’s Algorithm

Grover’s algorithm enables quadratic speedup in unstructured search problems, reducing the query complexity for SAT from $\mathcal{O}(2^n)$ (classical) to $\mathcal{O}(\sqrt{2^n})$ (quantum). However, Grover’s performance critically degrades if the number of solutions is unknown. The characteristic “Soufflé problem” arises due to the oscillatory probability of success as a function of iteration count—imprecise halting results in significant performance loss. While fixed-point quantum search variants address this issue by ensuring monotonic probability amplification, previous approaches sacrificed either robustness or speedup, or failed to exploit parallelism necessary for NISQ viability.

Algorithmic Framework

Parallel Fixed-Point Quantum Search

The PFP algorithm structurally augments the fixed-point quantum search paradigm by enabling parallel processing of SAT clauses. The formulation requires three quantum registers (variable, formula, control) and an associated classical register. Critically, variable qubits are organized into entangled groups—specifically GHZ states—when variables appear in multiple clauses. This guarantees outcome consistency across parallel clause operations. The clause-wise oracles are constructed with mutually exclusive qubits, enabling all clause oracles to be evaluated concurrently. Consequently, the circuit depth for oracle application is reduced from $\mathcal{O}(m)$ to $\mathcal{O}(1)$ for $m$ clauses.

The controlled-oracle sequence is interleaved with a controlled diffuser, following a measurement-driven adaptive regime reminiscent of prior critically damped search models. The phase parameter $\phi_t$ in the control rotations is dynamically updated according to the recurrence $$\cos\phi_t = \frac{1 - \sin(\pi/(2t))}{1 + \sin(\pi/(2t))}$$, ensuring monotonic convergence toward the solution subspace even with unknown solution counts.

Distributed Implementation via Teleportation

The algorithm supports distribution over multiple quantum devices, a crucial adaptation given limited qubit availability in NISQ machines. Distributed multi-controlled gates are realized using quantum teleportation. Bell pairs are pre-shared between master and sub-nodes. Clause oracle computations requiring global control are mapped to local operations by teleporting relevant qubit states to the master and back, mediated by classical communication (measurement outcomes) and corrective $X$/$Z$ gates. This enables clause subcircuits to reside on separate quantum processors, allowing problem partitioning under hardware constraints, and offering an elementary privacy-preserving mechanism.

Numerical Results

Empirical validation is presented on a 3-variable SAT instance ($(a)\land(a\lor b)\land(a\lor c)$) with a unique solution. Comparative analysis with standard Grover’s algorithm demonstrates:

• Grover’s algorithm rapidly achieves high solution probability (>0.9 within six steps), but exhibits strong oscillatory behavior characteristic of the Soufflé problem.
• The PFP algorithm, in both fixed and adaptive $\mathcal{O}(\sqrt{2^n})$0 variants, displays monotonic increase in success probability, surpassing Grover’s performance as the iteration count grows, and completely eliminating oscillations.

  Figure 2: Numerical results for solving SAT formula $\mathcal{O}(\sqrt{2^n})$1 with Grover's algorithm and PFP search algorithm.

Performance overhead is minimal—PFP requires at most 1.5x the number of oracle queries compared to ideal Grover’s search, but is robust in the absence of solution count and immune to suboptimal early or late termination.

Implications and Future Directions

This work’s principal contributions are as follows:

• Parallel Oracle Construction: Enabling simultaneous evaluation of all SAT clauses reduces depth, crucially lowering error accumulation in NISQ circuits.
• Deterministic Convergence without Solution Count: The fixed-point property ensures successful state preparation without Grover’s oscillation risk, even for unknown solution multiplicity.
• Distributed Quantum Computation: The teleportation-based distributed protocol aligns with imminent quantum networking capabilities, enabling the partition of otherwise intractable SAT instances across small-q hardware.
• Practical NISQ Suitability: These innovations collectively push quantum SAT solving closer to tractable, near-term hardware realization.

Potential future work includes experimental deployment on multi-node quantum devices, improved $\mathcal{O}(\sqrt{2^n})$2 update schedules for further acceleration, and generalized extension to broader classes of NP-complete problems beyond SAT.

Conclusion

The PFP quantum search algorithm outlined in this work advances the state of quantum SAT solving along both scalability and robustness axes. By enabling clause-level parallelism and supporting distributed execution, the approach optimizes for the architectural constraints of the NISQ era. Theoretical guarantees are supported by strong numerical evidence for both efficiency and resilience against oracle count ambiguity. As quantum infrastructures mature, this framework offers a compelling architecture for scalable, high-assurance quantum-enhanced satisfiability and combinatorial search.