💻 computer science

Computing Short SAT Implicants via Ising/QUBO Encodings

This paper introduces a novel Ising/QUBO encoding framework that utilizes dual-polarity representation to incorporate "don't-care" semantics, enabling the efficient computation of short partial satisfying assignments (implicants) and their minimization through ground state retrieval.

Original authors: Giuseppe Spallitta, Leonardo Duenas-Osorio, Moshe Y. Vardi

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Giuseppe Spallitta, Leonardo Duenas-Osorio, Moshe Y. Vardi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant, complex puzzle. In the world of computer logic (called SAT), the goal is usually to find one way to fit all the pieces together so the picture makes sense. Traditionally, computers do this by filling in every single piece of the puzzle, even the ones that don't really matter to the final picture. They give you a "total" solution where every variable is either "On" or "Off."

But often, you don't need the whole picture. You just need a few key pieces that prove the puzzle works. Maybe you want to know why a system failed, or you want to compress a massive list of solutions into a tiny, easy-to-read summary. In these cases, you want a "partial" solution: a few pieces set to "On" or "Off," while the rest are left blank, like a "Don't Care" sign.

The problem is that the tools used to solve these puzzles (specifically a type of math model called Ising/QUBO, which is popular for quantum computers) are like rigid robots. They hate leaving things blank. They insist on assigning a value to every single piece, even if it's unnecessary.

The New "Don't Care" Trick

The authors of this paper invented a clever way to teach these rigid robots how to leave pieces blank. They did this by giving every puzzle piece two faces instead of one.

Think of a standard variable as a light switch that is either ON or OFF.
The authors' new method gives every variable two switches:

A "Positive" switch (for ON).
A "Negative" switch (for OFF).

Here is the magic:

If the Positive switch is ON, the variable is True.
If the Negative switch is ON, the variable is False.
If both switches are OFF, the variable is Unassigned (a "Don't Care").
If both switches are ON, it's a mistake (forbidden).

By using this "dual-switch" system, the computer can now naturally represent a "Don't Care" state by simply turning both switches off.

The "Energy" Game

The computer solves these puzzles by trying to find the state with the lowest "energy" (like a ball rolling down a hill to the lowest point). The authors designed the rules of the game so that:

The Rules Must Be Followed: If a puzzle rule (clause) is broken, the energy goes up massively. The computer must avoid this.
Simplicity is Rewarded: The authors added a rule that says, "Every time you turn a switch ON, you pay a small fee."

Because the computer wants the lowest total energy, it will try to satisfy all the rules while turning on as few switches as possible. It will naturally leave the unnecessary switches in the "both OFF" (Don't Care) position.

Shrinking and Focusing

The paper shows two main ways to use this trick:

Shrinking: Imagine you already have a full solution (all switches ON or OFF). You can use this new method to "shrink" it. You tell the computer, "Keep the switches that are already ON, but try to turn off as many as possible without breaking the rules." The computer will strip away the extra switches, leaving you with the smallest possible group of switches that still solves the puzzle.
Focusing (Projection): Sometimes, you only care about a specific group of variables (like the "visible" pieces of a puzzle), while others are just hidden support. The authors show how to tell the computer: "Only charge a fee for turning on the visible switches. The hidden ones can be whatever they need to be." This forces the computer to find the shortest explanation using only the important variables.

What They Found

The authors tested this idea on random puzzles and complex formulas. They found that:

The computer successfully found solutions where about one-third of the variables were left blank (unassigned), proving the puzzle still worked.
By running the computer in a loop (finding a solution, then trying to shrink it again), they could almost always find the shortest possible solution.
The method works well even when the puzzle is converted into a different format (like turning a complex sentence into a list of simple rules), as long as the "hidden" support variables are treated correctly.

The Bottom Line

This paper provides a new "language" for these optimization computers. It allows them to stop forcing a value on every single variable and instead learn to say, "I don't know, and I don't need to know," while still guaranteeing the answer is correct. This helps computers find the simplest, most concise explanations for complex logical problems.

Technical Summary: Computing Short SAT Implicants via Ising/QUBO Encodings

1. Problem Statement

Many reasoning tasks, including explanation, diagnosis, and model compression, require short partial satisfying assignments (implicants) rather than total assignments. In these contexts, unassigned variables act as genuine "don't-cares," and often only a subset of variables (visible variables) is semantically relevant, while others serve as hidden support.

While modern SAT solvers efficiently compute total satisfying assignments, deriving short implicants typically requires repeated SAT calls or dedicated post-processing. Similarly, standard SAT-to-Ising/QUBO formulations are inherently limited: they map CNF formulas to quadratic energy functions where ground states correspond to total assignments. The Ising/QUBO model assigns a value to every spin, lacking a native representation for "unassigned" variables. Consequently, computing short implicants has historically been left to external algorithms rather than being captured within the quadratic optimization model itself.

2. Methodology

The authors propose a unified optimization framework that natively supports three-valued partial assignments (True, False, Unassigned) within a quadratic Ising/QUBO model.

2.1 Dual-Polarity Representation

To represent unassigned variables, the framework introduces a dual-polarity encoding. For each propositional variable $A_i$ , two binary spins $(p_i, n_i)$ are used:

$(1, 0) \implies A_i = \top$
$(0, 1) \implies A_i = \bot$
$(0, 0) \implies A_i$ is unassigned (don't-care)
$(1, 1) \implies$ Inconsistent (forbidden)

A semantic consistency penalty $M \cdot p_i n_i$ is added to forbid the inconsistent state.

2.2 Clause Encoding

Clauses are encoded using standard quadratic penalty functions. For a clause $C_k = (\ell_1 \lor \ell_2 \lor \ell_3)$ , the literals are mapped to their corresponding polarity spins. To maintain quadratic form, an auxiliary variable $c_k$ is introduced to capture the condition where the first two literals are false. The energy function penalizes configurations where all literals are false (i.e., all corresponding spins are 0).

2.3 Sparsity and Objective Function

A sparsity term is added to the energy function: $E_{sparse} = \gamma \sum (p_i + n_i)$ . This term penalizes active spins, biasing the optimizer toward configurations with fewer assigned variables (shorter implicants).
The total energy function is:
$E_F = \sum M p_i n_i + \sum E_{clause}(k) + \gamma \sum (p_i + n_i)$

2.4 Weight Regimes

The paper establishes theoretical conditions on the weights ( $\lambda$ for clause penalties, $M$ for consistency, $\gamma$ for sparsity) to ensure correctness. Specifically, if $\lambda > n\gamma$ and $M > n\gamma$ (where $n$ is the number of variables), the ground states of the energy function correspond exactly to minimum-cardinality implicants.

2.5 Shrinking and Projection

Implicant Shrinking: Given a total satisfying assignment, the framework restricts the search space by fixing the "opposite" polarity spins to 0. This allows the optimizer to only drop literals from the existing assignment, finding the shortest sub-assignment that remains a valid implicant.
Projection: To focus on a subset of visible variables $P$ , the sparsity penalty is applied only to variables in $P$ . Hidden variables $H$ remain unconstrained by sparsity, acting as free auxiliary support. This allows the model to find short assignments over $P$ while satisfying the formula via $H$ .

3. Key Contributions

Native Three-Valued Encoding: A SAT-to-Ising/QUBO encoding that natively represents partial assignments (True/False/Unassigned) via dual-polarity semantics, eliminating the need for external post-processing to interpret "unassigned" states.
Flexible Objective Variants: QUBO formulations where implicant shrinking is achieved by polarity restrictions and projection is achieved by restricting sparsity penalties to visible variables, all within a single fixed quadratic model structure.
Theoretical Guarantees: Identification of specific weight regimes ( $\lambda > n\gamma, M > n\gamma$ ) that guarantee ground states correspond to minimum-cardinality implicants. The paper provides a criterion for recognizing valid implicants directly from the final energy value.
Empirical Validation: An evaluation using simulated annealing on random 3-SAT and non-CNF formulas, demonstrating the encoding's ability to produce short partial assignments and achieve minimality through iterative refinement.

4. Experimental Results

The authors evaluated the encoding using Simulated Annealing (SA) on two benchmark sets:

Random 3-SAT: Satisfiable instances with low clause-to-variable density ( $m/n = 1.5$ ).
Non-CNF Formulas: Boolean formulas converted to CNF via Tseitin/Plaisted-Greenbaum transformations, creating a projected setting with hidden auxiliary variables.

Key Findings:

Compactness: On random 3-SAT, the encoding leaves approximately one-third of variables unassigned on average while preserving satisfiability.
Minimality: While baseline SA often finds minimum-cardinality assignments on small-to-medium instances, success rates decrease as problem size grows due to local minima. However, iterative refinement (freezing the best solution and re-running SA to shrink further) significantly improves results.
Minimality vs. Minimum-Cardinality: Iterative refinement achieves inclusion-minimality (prime implicants) with high probability. Achieving minimum-cardinality (global minimum size) is harder but frequently observed, particularly in non-CNF benchmarks where the structure allows uniform hidden completions.
Projected Setting: In the projected mode, the method successfully recovers minimum-cardinality assignments over visible variables, even with a high proportion of hidden auxiliary variables (65–70% of total variables).

5. Significance and Claims

The paper claims that this framework offers a unified optimization approach for computing short partial assignments, replacing the need for external shrinking subroutines in AllSAT or explanation pipelines.

Theoretical Significance: It bridges the gap between the "total assignment" nature of Ising models and the "partial assignment" requirements of many reasoning tasks by introducing a dual-polarity representation with provable weight regimes for minimality.
Practical Significance: The encoding serves as a "drop-in replacement" for shrinking steps in existing workflows. The authors emphasize that the approach is robust under generic optimization backends (like Simulated Annealing) and does not require specialized hardware to demonstrate semantic validity, though they note that quantum annealers or specialized Ising machines could potentially yield better results.
Limitations: The authors modestly acknowledge that while the encoding guarantees minimum-cardinality ground states theoretically, heuristic optimizers may get trapped in local minima. Furthermore, in the projected setting, the encoding enforces a "uniform witness" (a single hidden assignment for all visible completions), which is a stricter requirement than standard projected implicant semantics, though the authors argue this holds for many practical non-CNF conversions.

The work positions itself as a semantic validation of quadratic encodings for partial reasoning, demonstrating that with appropriate parameter tuning and iterative refinement, Ising/QUBO models can effectively compute minimal and minimum-cardinality implicants.