A New Kind of Instrument
Foundational quantum mechanics has traditionally been the domain of pen-and-paper proof: thought experiments, algebraic manipulations, and elegant constructions by hand. But many of the deepest questions in quantum foundations are fundamentally combinatorial — they concern the existence or non-existence of structures satisfying specific constraints across vast search spaces.
The computer is not replacing mathematical reasoning. It is extending it into territory that is inaccessible to human intuition alone. Just as the telescope revealed structure invisible to the naked eye, computational search reveals mathematical structure that no amount of clever manipulation could have uncovered.
The discovery that the golden ratio field ℤ[φ] supports
Kochen-Specker sets was invisible to direct algebraic search. It emerged only
when a computer systematically applied cross-product closure to coordinate
sets — a process that generates hundreds of candidate vectors and tests
billions of combinations.
The Computational Toolkit
Our research draws on several families of algorithms, each suited to a different aspect of the problem.
SAT Solvers for Uncolorability
The central question — can a set of quantum measurements be assigned predetermined outcomes consistently? — is a constraint satisfaction problem. We encode it as a Boolean satisfiability (SAT) instance:
- Each vector gets a Boolean variable (included in the KS set or not)
- Orthogonality constraints become clauses (exactly one vector per basis must be “true”)
- KS-uncolorability means the formula is unsatisfiable — no consistent assignment exists
Modern CDCL solvers (we use Glucose4 via PySAT) can resolve these instances in milliseconds for sets of 30–60 vectors, and provide proofs of unsatisfiability — not just answers, but certificates that can be independently verified.
Graph Algorithms
The orthogonality structure of a KS set defines a graph (vectors are vertices, orthogonal pairs are edges) and a hypergraph (bases are hyperedges). These structures encode the combinatorial skeleton of contextuality.
- Graph isomorphism (VF2): Testing whether KS sets from different algebraic rings share the same combinatorial structure
- Spectral analysis: Eigenvalues of the adjacency matrix reveal symmetry and regularity
- Lovász theta: A semidefinite programming bound that connects graph structure to quantum advantage — the ratio θ/α quantifies the contextual advantage
- Fractional chromatic number: Another graph invariant linked to the quantum-classical gap
Algebraic Search
Enumerating KS candidates requires generating vectors from algebraic number fields and testing orthogonality. The search space grows combinatorially:
- Alphabet generation: For a ring like
ℤ[√2], enumerate all vectors with coordinates of bounded norm - Cross-product closure: Given a seed set, compute all cross products to discover vectors not in the original alphabet
- Greedy minimization: Starting from a large uncolorable pool, iteratively remove vectors while preserving uncolorability
- Exhaustive minimization: SAT-based approach that provably finds minimal KS subsets
Integer and Linear Programming
Bipartite perfect quantum strategies (BPQS) require finding optimal partitions of KS bases into two sets satisfying coverage constraints. We use integer linear programming to find exact solutions when they exist, and bound the optimum otherwise.
What Computation Has Revealed
Several of our key results would have been difficult or impossible to obtain without computational methods:
| Discovery | Method | Why Computation Was Essential |
|---|---|---|
| Golden ratio KS set | Cross-product closure + SAT | Invisible to direct alphabet search; requires generating ~200 vectors and testing all subsets |
| Heegner-7 KS set | Algebraic search + SAT | Ring ℤ[(1+√-7)/2] not previously considered; found by systematic survey across number fields |
| Graph universality of CK-31 | VF2 isomorphism | Comparing graph structure across algebraically unrelated constructions requires exhaustive pairwise testing |
| 6|n conjecture | Roots-of-unity survey | Testing all n-th roots of unity for n ≤ 30 generates thousands of candidate sets |
| Realizability gap (49% vs 0%) | Random hypergraph generation + geometric embedding | Statistical claim requires sampling thousands of random structures |
| Norm-2 boundary | Systematic field survey | Negative results (no KS sets at norm ≥ 3) require exhaustive search to be convincing |
Reproducibility
Computational results in foundational physics must meet a high standard of reproducibility. Our approach:
- Fixed random seeds: All stochastic processes use
random.seed(42)for exact reproducibility - Multiple verification paths: Key results confirmed by at least two independent algorithms (e.g., SAT + direct enumeration)
- Certificate-based proofs: SAT unsatisfiability provides machine-checkable certificates
- Open methodology: Complete algorithmic descriptions in publications, enabling independent replication
The Role of AI
Large language models are emerging as a new tool in computational research — not for proof, but for exploration. In this work, AI assisted with:
- Literature synthesis: Connecting results across quantum foundations, graph theory, and algebraic number theory
- Code generation and debugging: Rapidly prototyping search algorithms and visualization tools
- Hypothesis generation: Suggesting algebraic structures to investigate based on pattern recognition
- Peer review simulation: Identifying weaknesses in arguments before formal submission
The key discipline is that AI suggestions are always verified computationally or mathematically. The computer proposes; the mathematics disposes.
The computer as collaborator: The best results in computational quantum foundations come from a tight loop between human mathematical intuition (“what structure might exist here?”) and computational power (“let me check every possibility”). Neither alone would have found the golden ratio construction. Together, they did.
Software Stack
| Tool | Role |
|---|---|
| Python 3.11 | Primary language for all computational work |
| PySAT (Glucose4) | SAT solving for uncolorability and minimization |
| NumPy / SciPy | Linear algebra, eigenvalue computation, optimization |
| CVXPY (SCS solver) | Semidefinite programming for Lovász theta |
| NetworkX | Graph construction, isomorphism (VF2), spectral analysis |
| pdflatex (MiKTeX) | Paper compilation |