⚛️ quantum physics

SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set

This paper introduces a novel SAT-based orderly generation framework integrating recursive canonical labeling with NAUTY to overcome previous scalability limitations, enabling the first exhaustive enumeration of small Kochen-Specker sets in dimension 3 and verifying that Schütte's 33-ray set is the smallest containing the complete 25-ray state-independent contextuality set.

Original authors: Zhengyu Li, Curtis Bright, Stefan Trandafir, Adán Cabello, Vijay Ganesh

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhengyu Li, Curtis Bright, Stefan Trandafir, Adán Cabello, Vijay Ganesh

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 find a specific, tiny, and incredibly complex Lego structure hidden inside a massive, chaotic warehouse. This structure is called a Kochen-Specker (KS) set.

In the world of quantum physics, these sets are like "magic keys." They prove that the universe doesn't work like a simple, predictable machine (where every piece has a fixed setting) but rather like a game of chance where the rules change depending on how you look at them. This is called contextuality.

For decades, physicists have been hunting for the smallest possible magic key. They found a small one with 13 pieces (the "Yu-Oh set"), but they knew there must be a slightly larger, more complete "master key" hidden somewhere. The question was: What is the smallest complete master key that contains this 13-piece core?

The answer, according to this paper, is a structure with 33 pieces. But finding it was like trying to find a needle in a haystack that keeps growing bigger the more you look at it.

Here is how the authors solved this puzzle, explained simply:

1. The Problem: The "Too Many Paths" Trap

Imagine you are walking through a maze. You want to find the exit, but the maze has billions of dead ends that look exactly the same (they are just rotated versions of each other).

The Old Way: Previous computer programs tried to solve this by checking every single path. If they found a path that looked like a rotated version of one they had already seen, they would stop. But checking if two complex shapes are "rotated versions" is incredibly slow. It's like trying to compare two giant, tangled balls of yarn to see if they are the same, piece by piece. As the balls got bigger, the time it took to compare them exploded exponentially. The computer would get stuck for years just checking if a shape was "new" or "old."

2. The Solution: The "Smart Librarian" (SAT + NAUTY)

The authors built a new system that combines two powerful tools:

SAT Solver: A super-fast logic engine that can test millions of "What if?" scenarios in a blink.
NAUTY: A world-class tool (like a super-smart librarian) that can instantly recognize if two complex shapes are the same, even if they are rotated or flipped.

The Innovation:
The problem was that the "Smart Librarian" (NAUTY) was too smart for the "Logic Engine" (SAT). The Librarian could check the whole shape, but the Logic Engine needed to check the shape piece by piece as it was being built. If the Librarian said, "This half-built shape is a duplicate," the Logic Engine couldn't trust it because the Librarian's method didn't work well on half-finished shapes.

The Fix: Recursive Canonical Labeling (RCL)
The authors invented a new rule called Recursive Canonical Labeling.

The Analogy: Imagine you are building a tower of Lego bricks.
- Old Method: You build the whole tower, then ask a friend, "Is this tower unique?" If they say "No, it's the same as that one," you have to tear it all down and start over. This is slow.
- New Method (RCL): You ask your friend to check the tower after every single brick you add. "Is this 1-brick tower unique? Yes. Is this 2-brick tower unique? Yes."
- The magic is that the authors taught the "Smart Librarian" (NAUTY) how to do this piece-by-piece check without losing its speed. They wrapped the Librarian in a special "hierarchical" suit that allows it to check the tower as it grows, ensuring that if a small part is a duplicate, the whole thing is discarded immediately.

3. The Result: Finding the 33-Piece Key

Using this new "piece-by-piece" super-speed method, the authors ran a massive search on a supercomputer cluster.

They started with the known 13-piece core.
They forced the computer to add pieces one by one, checking at every step if the shape was valid and unique.
They searched all the way up to 33 pieces.

The Discovery:
They found that there is only one unique 33-piece structure that contains the 13-piece core and works as a "magic key."

This structure was actually discovered by a mathematician named Schütte back in the 90s, but nobody knew if it was the only one or if there were others hiding in the shadows.
This paper proves, with mathematical certainty, that Schütte's 33-piece set is the smallest and only one of its kind.

4. Why Does This Matter?

Think of this like finding the smallest possible engine that can power a car.

Physics: It helps us understand the fundamental rules of the universe. It proves that "contextuality" (the weirdness of quantum mechanics) is unavoidable, even in the smallest possible systems.
Technology: Smaller, simpler quantum structures are easier to build in a lab. Knowing the absolute smallest "perfect" structure helps engineers design better quantum computers and sensors that are more robust against errors.

Summary

The authors took a problem that was too hard for old computers (because checking for duplicates was too slow) and invented a new "check-as-you-go" method. This allowed them to exhaustively search a massive mathematical space and prove that a specific 33-piece quantum structure is the unique, smallest solution to a 60-year-old mystery.

In a nutshell: They built a faster, smarter way to sort through a chaotic library of shapes, proving that there is only one perfect "33-piece puzzle" that fits the rules of quantum reality.

1. Problem Statement

The paper addresses the search for Kochen-Specker (KS) sets in dimension 3. A KS set is a finite set of rays (vectors) in a Hilbert space that cannot be assigned binary values $\{0, 1\}$ such that every orthogonal basis contains exactly one "1" and no two orthogonal rays are both "1." This property proves quantum contextuality.

The Specific Challenge: While the smallest State-Independent Contextuality (SI-C) set in dimension 3 is known to be the 13-ray Yu-Oh set, the size of the smallest KS set in dimension 3 remains an open problem (known lower bound is 24; smallest known is 31).
The Goal: The authors aim to perform an exhaustive enumeration of all KS sets in dimension 3 that contain the complete 25-ray SI-C set (a rigid extension of the Yu-Oh set) and have up to 33 rays.
The Bottleneck: Previous SAT-based approaches for "orderly generation" (generating non-isomorphic graphs without redundancy) relied on lexicographical canonicity. These methods suffer from exponential scaling when checking canonicity on large, highly structured graphs, making them intractable for the 25–33 vertex instances required here.

2. Methodology

The authors propose a novel framework combining SAT solvers with the graph isomorphism tool NAUTY via Recursive Canonical Labeling (RCL).

A. Recursive Canonical Labeling (RCL)

The Issue: Standard tools like NAUTY are highly efficient at computing canonical labels but are not hereditary (a canonical graph may have non-canonical subgraphs). Orderly generation requires a hereditary property: if a partial graph is non-canonical, no extension of it can be canonical.
The Solution: The authors implement RCL (introduced by Afzaly), which wraps a base canonizer (NAUTY) to create a hierarchical, hereditary labeling.
- It recursively anchors the largest label based on the base canonizer's output.
- This allows the system to use NAUTY's speed while satisfying the prefix-preserving property required for pruning the SAT search space.

B. SAT Encoding and Constraints

The problem is encoded into a Boolean Satisfiability (SAT) instance using variables for edges ( $e_{i,j}$ ) and triangles ( $t_{i,j,k}$ ).

Structural Constraints: The graph must be square-free (no $C_4$ ), have a minimum degree of 3, and every vertex must belong to a triangle.
Non-010-Colorability: The core KS property is encoded by generating blocking clauses for all valid 010-colorings (optimizing by only blocking colorings with a small number of "1"s).
Fixed Subgraphs: The search starts with a fixed 25-ray base (the complete SI-C set). The authors fix the edge variables for this base, initializing the search space.

C. Geometric Pruning (Orthogonality Check)

Beyond combinatorial isomorphism, the search incorporates a custom propagator to enforce geometric realizability in $\mathbb{C}^3$ (or $\mathbb{R}^3$ ).

Dynamic Derivation: As the SAT solver assigns edges, the propagator calculates vector coordinates. If a new ray is orthogonal to two known rays, its direction is uniquely determined via the cross product.
Conflict Detection: If a derived vector violates orthogonality (e.g., becomes parallel to an existing vector or fails to be orthogonal to a connected neighbor), the propagator generates a blocking clause based on the specific dependency chain of decisions that caused the error.
Exact Arithmetic: All geometric checks use exact arithmetic (Z3 for real, algebraic fields for complex) to avoid floating-point errors.

D. Verification

The system produces DRAT proof certificates extended with domain-specific axioms:

t-clauses: Prove isomorph rejection is sound (blocking a graph doesn't block its canonical representative).
o-clauses: Prove geometric pruning is sound (blocking a graph is due to a genuine geometric contradiction).
An independent verifier checks these proofs to ensure the search space was exhaustively and correctly explored.

3. Key Contributions

SAT + NAUTY Framework: A new orderly generation method that integrates NAUTY into a SAT solver via RCL. This overcomes the exponential scaling bottleneck of lexicographical canonicity checks.
Performance Breakthrough: The RCL check maintains consistent millisecond-level performance ( $\approx 0.005s$ ) regardless of graph size, whereas lexicographical checks scale exponentially (taking hours for $n=26$ ).
Exhaustive Enumeration: The first complete enumeration of KS sets up to 33 rays containing the 25-ray SI-C core.
Proof Certification: The generation of independently verifiable proof certificates (approx. 13 TiB for the $n=33$ case) confirming non-existence results.

4. Results

Performance Comparison: On benchmark graphs mimicking KS structures, the RCL approach was up to 8,499 times faster than lexicographical checks at $n=26$ .
Enumeration Outcome:
- The search ran for 1,641 CPU hours (approx. 68 days) on a high-performance cluster.
- The solver found 44 combinatorial candidates satisfying the KS conditions.
- After geometric verification, only one candidate was geometrically realizable.
Main Finding: The unique solution is isomorphic to the 33-ray Schütte set.
- Conclusion: Up to order 33, the Schütte set is the only Kochen-Specker set containing the complete 25-ray SI-C set. This confirms the Schütte set is the smallest rigid KS set containing the minimal SI-C witness.

5. Significance

Quantum Foundations: The work rigorously defines the geometric boundaries of the simplest contextual structures in dimension 3. It confirms that the Schütte set is the minimal rigid extension of the Yu-Oh set, a fundamental object in quantum contextuality.
Algorithmic Advancement: The paper demonstrates that combining specialized graph tools (NAUTY) with SAT solvers via RCL is a viable strategy for solving combinatorial problems where symmetry handling is the primary bottleneck. This approach is generalizable to other domains requiring isomorph-free generation of complex structures.
Experimental Relevance: Small KS sets are crucial for designing quantum experiments (specifically "rigid" sets that allow for self-testing and certification with any full-rank state). Identifying the minimal such sets helps optimize experimental feasibility.