Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1105.3454

Computing in the fractal cloud: modular generic solvers for SAT and Q-SAT variants

Denys Duchier, Jérôme Olivier Durand-Lose, Maxime Senot

Published May 17, 2011• 0 citations
arXivHTMLPDF

Abstract

Abstract geometrical computation can solve hard combinatorial problems efficiently: we showed previously how Q-SAT can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propose an approach for constructing a particular generic machine for the same task. This machine deploies the Map/Reduce paradigm over a fractal structure. Moreover our approach is modular: the machine is constructed by combining modules. In this manner, we can easily create generic machines for solving satifiability variants, such as SAT, #SAT, MAX-SAT.

DOI
10.48550/arxiv.1105.3454

Related papers

SATIC: An Optimizing Ising Compiler for SAT(isfiability)

Ahmet Efe, Hüsrev Cılasun, Abhimanyu Kumar +9 more

Ising machines show great potential as hardware solvers for combinatorial optimization problems such as Boolean Satisfiability (SAT) - one of the hardest classic problems of practical importance. Unlocking this potential, however, is only possible by bridging the gap between SAT problem characteristics and Ising machine specifics. In this paper, we introduce a novel optimizing compiler featuring a bag of powerful heuristic tricks, SATIC, toward this goal. We evaluate SATIC on a representative manufactured Ising chip. Our measurements show that SATIC enables Ising machines to solve up to$\text{73} \times$larger SAT problems than the hardware capacity would otherwise allow, demonstrating unmatched performance and scalability.

Proceedings - International Symposium on Computer Architecture/Proceedings•Jun 1, 2026•1 citation

Coherent SAT solvers: a tutorial

Sam Reifenstein, Timothee G. Leleu, Timothy P. McKenna +6 more

The coherent Ising machine (CIM) is designed to solve the NP-hard Ising problem quickly and energy efficiently. Boolean satisfiability (SAT) and maximum satisfiability (Max-SAT) are classes of NP-complete and NP-hard problems that are equally important and more practically relevant combinatorial optimization problems. Many approaches exist for solving Boolean SAT, such as quantum annealing and classical stochastic local search (SLS) solvers; however, they all are expected to require many steps to solve hard SAT problems and, thus, require large amounts of time and energy. In addition, a SAT problem can be converted into an Ising problem and solved by an Ising machine; however, we have found that this approach has drawbacks. As well as reviewing existing approaches to solving the SAT problem, we have extended the CIM algorithm and architecture to solve SAT and Max-SAT problems directly. This new technique is termed a coherent SAT solver (CSS). We have studied three implementations of the CSS, all-optical, hybrid optical–digital and all digital (cyber-CSS), and have compared the time-to-solution and energy-to-solution of three machines. The cyber-CSS, which is already implemented using a graphics processing unit (GPU), demonstrates competitive performance against existing SLS solvers such as probSAT. The CSS is also compared with another continuous-time SAT solver known as the CTDS, and the scaling behavior is evaluated for random 3-SAT problems. The hybrid optical–digital CSS is a more performant and practical machine that can be realized in a short term. Finally, the all-optical CSS promises the best energy-to-solution cost; however various technical challenges in nonlinear optics await us in order to build this machine.

Advances in Optics and Photonics•Mar 22, 2023•18 citations

A Unified Theoretical Framework for Fractal Computational Complexity and Quantum Phase Transitions

changzheng zhou, ZIQING zhou

This paper establishes a new paradigm of computational complexity based onfractal dimensions, proposing a rigorous mathematical framework for dimension?covariant complexity, classified as NPDH. By constructing fractal input spaces andverification protocols, we demonstrate that for Hausdorff dimensions DH > Dc,NP-complete problems can be solved in polynomial time, revealing the critical roleof dimension as an order parameter for computational difficulty. Using supercon?ducting quantum chips, we fabricated Sierpi´nski fractal qubit arrays and, for thefirst time, observed the critical dimensional phase transition for the 3-SAT problem(Dc = 3.15±0.02) and quantum acceleration effects (T ∝ n0.92). This work providesboth theoretical and experimental validation for the application of fractal geome?try in quantum computing and proposes an interdisciplinary research paradigm of”quantum phase transitions and dimensional reduction.”

•Feb 19, 2025•0 citations

Quantum Annealing and the Satisfiability Problem

Kristen L. Pudenz, Tallant Gregory S., Todd R. Belote +1 more

The utility of satisfiability (SAT) as an application focused hard computational problem is well established. We explore the potential of quantum annealing to enhance classical SAT solving, especially where sampling from the space of all possible solutions is of interest. We address the formulation of SAT problems to make them suitable for commercial quantum annealers, practical concerns in their implementation, and how the performance of the resulting quantum solver compares to and complements classical SAT solvers.

arXiv:1612.07258•Advances in parallel computing•Jan 1, 2017•7 citations

On the Limits of Ising Machines for Circuit-Derived SAT

Ahmet Efe, Abhimanyu Kumar, Nafisa Sadaf Prova +9 more

Emerging Ising machines are promising for solving computationally hard optimization problems, yet their limits on structured, circuit-derived satisfiability (SAT) problems remain poorly understood. Using semiprime factorization as a representative benchmark, we show that tight constraints, when mapped into optimization form, fundamentally distort the energy landscape, and that these distortions are amplified when problems are decomposed to fit limited Ising machine capacity. To address this, we propose a hybrid flow that offloads Ising-harmful structure to lightweight preprocessing while reserving the genuinely hard search for the Ising machine. We further show that generic, circuit-structure-unaware decomposition is insufficient for circuit-derived instances, and that structure-aware partitioning is essential. These findings identify constraint handling as a central obstacle, highlighting hybrid hardware-software approaches as the path forward for scaling Ising machines to real-world SAT workloads. Evaluated on fabricated 45-spin all-to-all Ising chips, our flow extends solvable problem sizes from 8-bit (94 variables) to 11-bit (190 variables) without any hardware changes.

arXiv:2511.21046•Nov 26, 2025•1 citation

A Parallel and Distributed Quantum SAT Solver Based on Entanglement and Teleportation

Shang‐Wei Lin, Tzu‐Fan Wang, Yean-Ru Chen +3 more

Abstract Boolean satisfiability (SAT) solving is a fundamental problem in computer science. Finding efficient algorithms for SAT solving has broad implications in many areas of computer science and beyond. Quantum SAT solvers have been proposed in the literature based on Grover’s algorithm. Although existing quantum SAT solvers can consider all possible inputs at once, they evaluate each clause in the formula one by one sequentially, making the time complexityO(m), linear to the number of clausesm,per Grover iteration. In this work, we develop aparallelquantum SAT solver, which reduces the time complexity in each iteration to constant timeO(1) by utilising extra entangled qubits. To further improve the scalability of our solution in case of extremely large problems, we develop a distributed version of the proposed parallel SAT solver based on quantum teleportation such that the total qubits required are shared and distributed among a set of quantum computers (nodes), and the quantum SAT solving is accomplished collaboratively by all the nodes. We prove the correctness of our approaches and evaluate them in simulations and real quantum computers.

Lecture notes in computer science•Jan 1, 2024•5 citations
Abstract geometrical computation can solve hard combinatorial problems efficiently: we showed previously how Q-SAT can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propose an approach for constructing a particular generic machine for the same task. This machine deploies the Map/Reduce paradigm over a fractal structure. Moreover our approach is modular: the machine is constructed by combining modules. In this manner, we can easily create generic machines for solving satifiability variants, such as SAT, #SAT, MAX-SAT.
Ising machines show great potential as hardware solvers for combinatorial optimization problems such as Boolean Satisfiability (SAT) - one of the hardest classic problems of practical importance. Unlocking this potential, however, is only possible by bridging the gap between SAT problem characteristics and Ising machine specifics. In this paper, we introduce a novel optimizing compiler featuring a bag of powerful heuristic tricks, SATIC, toward this goal. We evaluate SATIC on a representative manufactured Ising chip. Our measurements show that SATIC enables Ising machines to solve up to73×\text{73} \times73×larger SAT problems than the hardware capacity would otherwise allow, demonstrating unmatched performance and scalability.
The coherent Ising machine (CIM) is designed to solve the NP-hard Ising problem quickly and energy efficiently. Boolean satisfiability (SAT) and maximum satisfiability (Max-SAT) are classes of NP-complete and NP-hard problems that are equally important and more practically relevant combinatorial optimization problems. Many approaches exist for solving Boolean SAT, such as quantum annealing and classical stochastic local search (SLS) solvers; however, they all are expected to require many steps to solve hard SAT problems and, thus, require large amounts of time and energy. In addition, a SAT problem can be converted into an Ising problem and solved by an Ising machine; however, we have found that this approach has drawbacks. As well as reviewing existing approaches to solving the SAT problem, we have extended the CIM algorithm and architecture to solve SAT and Max-SAT problems directly. This new technique is termed a coherent SAT solver (CSS). We have studied three implementations of the CSS, all-optical, hybrid optical–digital and all digital (cyber-CSS), and have compared the time-to-solution and energy-to-solution of three machines. The cyber-CSS, which is already implemented using a graphics processing unit (GPU), demonstrates competitive performance against existing SLS solvers such as probSAT. The CSS is also compared with another continuous-time SAT solver known as the CTDS, and the scaling behavior is evaluated for random 3-SAT problems. The hybrid optical–digital CSS is a more performant and practical machine that can be realized in a short term. Finally, the all-optical CSS promises the best energy-to-solution cost; however various technical challenges in nonlinear optics await us in order to build this machine.
This paper establishes a new paradigm of computational complexity based onfractal dimensions, proposing a rigorous mathematical framework for dimension?covariant complexity, classified as NPDH. By constructing fractal input spaces andverification protocols, we demonstrate that for Hausdorff dimensions DH > Dc,NP-complete problems can be solved in polynomial time, revealing the critical roleof dimension as an order parameter for computational difficulty. Using supercon?ducting quantum chips, we fabricated Sierpi´nski fractal qubit arrays and, for thefirst time, observed the critical dimensional phase transition for the 3-SAT problem(Dc = 3.15±0.02) and quantum acceleration effects (T ∝ n0.92). This work providesboth theoretical and experimental validation for the application of fractal geome?try in quantum computing and proposes an interdisciplinary research paradigm of”quantum phase transitions and dimensional reduction.”
The utility of satisfiability (SAT) as an application focused hard computational problem is well established. We explore the potential of quantum annealing to enhance classical SAT solving, especially where sampling from the space of all possible solutions is of interest. We address the formulation of SAT problems to make them suitable for commercial quantum annealers, practical concerns in their implementation, and how the performance of the resulting quantum solver compares to and complements classical SAT solvers.
Emerging Ising machines are promising for solving computationally hard optimization problems, yet their limits on structured, circuit-derived satisfiability (SAT) problems remain poorly understood. Using semiprime factorization as a representative benchmark, we show that tight constraints, when mapped into optimization form, fundamentally distort the energy landscape, and that these distortions are amplified when problems are decomposed to fit limited Ising machine capacity. To address this, we propose a hybrid flow that offloads Ising-harmful structure to lightweight preprocessing while reserving the genuinely hard search for the Ising machine. We further show that generic, circuit-structure-unaware decomposition is insufficient for circuit-derived instances, and that structure-aware partitioning is essential. These findings identify constraint handling as a central obstacle, highlighting hybrid hardware-software approaches as the path forward for scaling Ising machines to real-world SAT workloads. Evaluated on fabricated 45-spin all-to-all Ising chips, our flow extends solvable problem sizes from 8-bit (94 variables) to 11-bit (190 variables) without any hardware changes.
Abstract Boolean satisfiability (SAT) solving is a fundamental problem in computer science. Finding efficient algorithms for SAT solving has broad implications in many areas of computer science and beyond. Quantum SAT solvers have been proposed in the literature based on Grover’s algorithm. Although existing quantum SAT solvers can consider all possible inputs at once, they evaluate each clause in the formula one by one sequentially, making the time complexityO(m), linear to the number of clausesm,per Grover iteration. In this work, we develop aparallelquantum SAT solver, which reduces the time complexity in each iteration to constant timeO(1) by utilising extra entangled qubits. To further improve the scalability of our solution in case of extremely large problems, we develop a distributed version of the proposed parallel SAT solver based on quantum teleportation such that the total qubits required are shared and distributed among a set of quantum computers (nodes), and the quantum SAT solving is accomplished collaboratively by all the nodes. We prove the correctness of our approaches and evaluate them in simulations and real quantum computers.