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

Information Theory and Applications Workshop (ITA)

On the riddle of coding equality function in the garden hose model

Oded Margalit

Published Feb 1, 2014• 3 citations
Publisher

Abstract

Recently, Harry Buhrman et al introduced a novel communication complexity model, called “garden-hose”. This model sprout from a research on using quantum properties to allow for position based cryptography. SAT is one of the fundamental NP-Complete problem - finding a satisfying assignment to a CNF (conjunctive Normal Form) formula, or proving that none exists. We will not get into the details of the quantum physics, neither we are going to explain the internal work of SAT solver. Instead we will start from the mathematical garden hose model; describe the way we used SAT solver as a tool; give some lower and upper bounds on implementing the equality function; and conclude with open questions.

DOI
10.1109/ita.2014.6804262

Related papers

The garden-hose model

Harry Buhrman, Serge Fehr, Christian Schaffner +1 more

We define a new model of communication complexity, called the garden-hose model. Informally, the garden-hose complexity of a function f:{0,1}n x {0,1}n -> {0,1} is given by the minimal number of water pipes that need to be shared between two parties, Alice and Bob, in order for them to compute the function f as follows: Alice connects her ends of the pipes in a way that is determined solely by her input x ∈ {0,1}n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y ∈ {0,1}n. Alice turns on the water tap that she also connected to one of the pipes. Then, the water comes out on Alice's or Bob's side depending on the function value f(x,y).

arXiv:1109.2563•Conference on Innovations in Theoretical Computer Science•Jan 3, 2013•54 citations

Quantangle-SAT: A Quantum SAT Solver Based on Entanglement and Equivalence Checking

Shang-Wei Lin, Ji-Qing Yan, Yean-Ru Chen +2 more

Satisfiability (SAT) is a central problem in computer science, and advances in SAT-solving algorithms have a far-reaching impact across many fields. Recent works have proposed quantum SAT solvers based on Grover's algorithm, a quantum search technique. However, Grover-based approaches face a key limitation: they typically require prior knowledge of the number of satisfying assignments of the target Boolean formula. This information is unavailable in most practical settings. Quantum counting can be used to estimate this quantity, but it incurs a computational overhead that is several orders of magnitude higher than Grover search. In this paper, we propose a novel quantum SAT solver based on entanglement and equivalence checking. Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting. Although the worst case time complexity is inevitably exponential, we prove that the expected time complexity of our approach is only constant time O(1) over random Boolean functions. Experimental results also support our theoretical claim.

quant-pharXiv:2604.18218•Apr 21, 2026•0 citations

A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability

Ahmed Younes, Jonathan E. Rowe

The aim of the paper is to answer a long-standing open problem on the relationship between NP and BQP. The paper shows that BQP contains NP by proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the MAX-E3-SAT problem is to find the variable assignment that maximizes the number of satisfied clauses. The proposed algorithm runs in $O(m^2)$ for an E3-CNF Boolean formula with $m$ clauses and in the worst case runs in $O(n^6)$ for an E3-CNF Boolean formula with $n$ inputs. The proposed algorithm maximizes the set of satisfied clauses using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of $1-ε$ for small $ε>0$ using a polynomial resources. In addition to solving the MAX-E3-SAT problem, the proposed algorithm can also be used to decide if an E3-CNF Boolean formula is satisfiable or not, which is an NP-complete problem, based on the maximum number of satisfied clauses.

arXiv:1507.05061•Jul 16, 2015•5 citations

The Garden-Hose Game and Application to Position-Based Quantum Cryptography

Harry Buhrman, Serge Fehr, Christian Schaffner +1 more

•Jan 1, 2011•0 citations

qSAT: Design of an Efficient Quantum Satisfiability Solver for Hardware Equivalence Checking

Abhoy Kole, Mohammed Elkacem Djeridane, Lennart Weingarten +2 more

The use of Boolean Satisfiability (SAT) solver for hardware verification incurs exponential runtime in several instances. In this work, we have proposed an efficient quantum SAT (qSAT) solver for equivalence checking of Boolean circuits employing Grover’s algorithm. The Exclusive-Sum-of-Product (ESOP)-based generation of the Conjunctive Normal Form (CNF) equivalent clauses demands less qubits and minimizes the gates and depth of quantum circuit interpretation. The consideration of reference circuits for verification affecting Grover’s iterations and quantum resources are also presented as a case study. Experimental results are presented assessing the benefits of the proposed verification approach using open source Qiskit platform and IBM quantum computer.

arXiv:2409.03917•ACM Journal on Emerging Technologies in Computing Systems•Apr 10, 2025•3 citations

Performance Gains in Quantum SAT Solvers Using ESOP Encoding

Majd Assaad, Abhoy Kole, Rolf Drechsler

The Boolean Satisfiability (SAT) problem is a canonical NP-complete problem and a natural candidate for quantum acceleration via search-based algorithms. In Grover-based quantum SAT solvers, the dominant computational cost stems from the construction of a reversible oracle that evaluates the Boolean formula, rendering the choice of SAT encoding crucial for overall quantum resource efficiency. Although SAT instances are conventionally expressed in Conjunctive Normal Form (CNF), such encodings typically translate into quantum circuits with significant qubit overhead and high non-Clifford gate complexity. In this work, we investigate an Exclusive-Sum-of-Products (ESOP)-based CNF (e-CNF) representation tailored for quantum SAT solving and analyze its impact on oracle construction. We derive tighter upper bounds on qubit requirements and Clifford+$T$ gate counts for Grover-based SAT solvers when e-CNF encodings are employed in place of standard CNF. In addition, we propose a scalable transformation from Boolean formulas to e-CNF and present a systematic procedure for interpreting e-CNF representations as reversible quantum circuits suitable for oracle implementation. Experimental evaluation on representative SAT benchmarks demonstrates that the proposed e-CNF-based approach yields substantial and consistent reductions in quantum resources, including qubit count, T-gate complexity, and circuit depth, when compared to CNF-based oracle constructions. These results establish e-CNF as an effective quantum-aware SAT encoding that significantly improves the practicality of oracle-based quantum SAT solving.

quant-pharXiv:2605.16202•May 18, 2026•0 citations
Recently, Harry Buhrman et al introduced a novel communication complexity model, called “garden-hose”. This model sprout from a research on using quantum properties to allow for position based cryptography. SAT is one of the fundamental NP-Complete problem - finding a satisfying assignment to a CNF (conjunctive Normal Form) formula, or proving that none exists. We will not get into the details of the quantum physics, neither we are going to explain the internal work of SAT solver. Instead we will start from the mathematical garden hose model; describe the way we used SAT solver as a tool; give some lower and upper bounds on implementing the equality function; and conclude with open questions.
We define a new model of communication complexity, called the garden-hose model. Informally, the garden-hose complexity of a function f:{0,1}n x {0,1}n -> {0,1} is given by the minimal number of water pipes that need to be shared between two parties, Alice and Bob, in order for them to compute the function f as follows: Alice connects her ends of the pipes in a way that is determined solely by her input x ∈ {0,1}n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y ∈ {0,1}n. Alice turns on the water tap that she also connected to one of the pipes. Then, the water comes out on Alice's or Bob's side depending on the function value f(x,y).
Satisfiability (SAT) is a central problem in computer science, and advances in SAT-solving algorithms have a far-reaching impact across many fields. Recent works have proposed quantum SAT solvers based on Grover's algorithm, a quantum search technique. However, Grover-based approaches face a key limitation: they typically require prior knowledge of the number of satisfying assignments of the target Boolean formula. This information is unavailable in most practical settings. Quantum counting can be used to estimate this quantity, but it incurs a computational overhead that is several orders of magnitude higher than Grover search. In this paper, we propose a novel quantum SAT solver based on entanglement and equivalence checking. Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting. Although the worst case time complexity is inevitably exponential, we prove that the expected time complexity of our approach is only constant time O(1) over random Boolean functions. Experimental results also support our theoretical claim.
The aim of the paper is to answer a long-standing open problem on the relationship between NP and BQP. The paper shows that BQP contains NP by proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the MAX-E3-SAT problem is to find the variable assignment that maximizes the number of satisfied clauses. The proposed algorithm runs in O(m2)O(m^2)O(m2) for an E3-CNF Boolean formula with mmm clauses and in the worst case runs in O(n6)O(n^6)O(n6) for an E3-CNF Boolean formula with nnn inputs. The proposed algorithm maximizes the set of satisfied clauses using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of 1−ε1-ε1−ε for small ε>0ε>0ε>0 using a polynomial resources. In addition to solving the MAX-E3-SAT problem, the proposed algorithm can also be used to decide if an E3-CNF Boolean formula is satisfiable or not, which is an NP-complete problem, based on the maximum number of satisfied clauses.
The use of Boolean Satisfiability (SAT) solver for hardware verification incurs exponential runtime in several instances. In this work, we have proposed an efficient quantum SAT (qSAT) solver for equivalence checking of Boolean circuits employing Grover’s algorithm. The Exclusive-Sum-of-Product (ESOP)-based generation of the Conjunctive Normal Form (CNF) equivalent clauses demands less qubits and minimizes the gates and depth of quantum circuit interpretation. The consideration of reference circuits for verification affecting Grover’s iterations and quantum resources are also presented as a case study. Experimental results are presented assessing the benefits of the proposed verification approach using open source Qiskit platform and IBM quantum computer.
The Boolean Satisfiability (SAT) problem is a canonical NP-complete problem and a natural candidate for quantum acceleration via search-based algorithms. In Grover-based quantum SAT solvers, the dominant computational cost stems from the construction of a reversible oracle that evaluates the Boolean formula, rendering the choice of SAT encoding crucial for overall quantum resource efficiency. Although SAT instances are conventionally expressed in Conjunctive Normal Form (CNF), such encodings typically translate into quantum circuits with significant qubit overhead and high non-Clifford gate complexity. In this work, we investigate an Exclusive-Sum-of-Products (ESOP)-based CNF (e-CNF) representation tailored for quantum SAT solving and analyze its impact on oracle construction. We derive tighter upper bounds on qubit requirements and Clifford+TTT gate counts for Grover-based SAT solvers when e-CNF encodings are employed in place of standard CNF. In addition, we propose a scalable transformation from Boolean formulas to e-CNF and present a systematic procedure for interpreting e-CNF representations as reversible quantum circuits suitable for oracle implementation. Experimental evaluation on representative SAT benchmarks demonstrates that the proposed e-CNF-based approach yields substantial and consistent reductions in quantum resources, including qubit count, T-gate complexity, and circuit depth, when compared to CNF-based oracle constructions. These results establish e-CNF as an effective quantum-aware SAT encoding that significantly improves the practicality of oracle-based quantum SAT solving.