[challenge]: Occam's Circuit — recover a hidden logic function from polynomially many examples

Released by

Jin-Guo Liu, HKUST(Guangzhou)

Contact email

cacate0129@gmail.com

Method

MPS Based Algorithm

Challenge issue

Occam's Circuit — recover a hidden logic function from polynomially many examples

The problem

We hand you a dataset of input–output pairs of a hidden Boolean function $f:{0,1}^{2n}\to{0,1}^m$. The input bitstring encodes two $n$-bit integers $x$ and $y$; the output encodes some arithmetic function of them — perhaps $x+y$, perhaps $x\cdot y$, perhaps $x^2+y^2$, perhaps something else. We reveal only polynomially many samples out of the $4^n$ possible inputs (as little as 3% of the table).

The number of Boolean functions on $2n$ bits is $2^{m \cdot 4^n}$ — superexponential. A polynomial-size dataset therefore pins down nothing: astronomically many functions fit the data perfectly and disagree everywhere else. The problem is ill-posed... unless you demand the simplest explanation.

Your task: find the smallest circuit consistent with the training data, and use it to predict the hidden test outputs. The scientific question behind the game is Occam's razor itself — does minimizing circuit size recover the ground truth?

Why this is a real (and hard) question

• Occam's razor is a theorem. Blumer–Ehrenfeucht–Haussler–Warmuth (1987) proved that any algorithm returning a near-minimum hypothesis consistent with the data is automatically a PAC learner: parsimony ⇒ predictive power. Inf. Proc. Lett. 24(6):377
• But finding the minimum is NP-hard. Hirahara (FOCS 2022) proved NP-hardness of exactly this problem — minimizing circuit size against a partial truth table (partial MCSP). Paper So bring heuristics, not brute force.
• It is the discrete cousin of grokking. Neural networks trained on partial arithmetic tables famously generalize suddenly, long after overfitting (Power et al. 2022); recent work connects this to entanglement transitions in tensor-network learning (arXiv:2503.10483). Here you get to make the razor explicit instead of hoping SGD applies it for you.
• A circuit is a tensor network. Each gate is a small tensor; the truth table is the contraction. Minimal-size circuit search is a tensor-factorization problem, and matrix-product-state representations of Boolean functions (≅ binary decision diagrams) were recently formalized in arXiv:2505.01930. Tensor-train completion theory even explains why polynomial data can suffice: low-rank tensor completion has poly sample complexity (arXiv:2401.02592).

Theory-backed difficulty ladder

The minimal representation size across the $x|y$ cut is governed by communication complexity, so the instances have provably different difficulty:

Function	Minimal BDD/MPS size	Difficulty
$x+y$	linear in $n$ (one carry bit crosses the cut)	warm-up
$\lvert x-y\rvert$	linear in $n$	easy
$x\cdot y$	exponential in $n$ for any variable ordering (Bryant 1991)	boss level
$x^2+y^2$	contains multiplication	boss level

Multiplication being provably BDD-hard is why the mystery instances keep $n$ small — and why beating them is worth bragging about.

Datasets

The challenge ships 2 practice instances (ground truth disclosed) and 4 mystery instances (function hidden; difficulty not ordered A→D).

📦 Download the full package (60 KB) — datasets, generator, verifier, example circuit, and a self-contained README:
https://github.com/QuantumBFS/quantum.harness/releases/download/occam-circuit-data-v1/occam-circuit.zip
(sha256: c15f84839a365dd9daab686ccfd58a50ce286d5f1071d7f093e9fdd091ecaa1b)

The SHA-256 commitments below are anchored in this issue now, so the hidden test outputs are provably fixed before anyone starts:

Instance	$2n$ (input bits)	$m$ (output bits)	train	test	observed fraction
practice-add-n4	8	5	120	136	47%
practice-mul-n4	8	8	120	136	47%
mystery-A	16	9	2000	2000	3.1%
mystery-B	14	7	1500	2000	9.2%
mystery-C	12	12	1200	1500	29%
mystery-D	10	11	400	624	39%

Each instance ships train.csv (input,output bitstring pairs) and test_inputs.csv; the withheld test_outputs.csv files are revealed on Day 5 and must hash to:

a02fa3f4aa915b97534fd5c70ba89a08522991030423f1eeb92260bc8539671a  practice-add-n4
f9e600cdd707f60639138e4e14656ea0c420fbce9b9fdde52d630d83076e88fa  practice-mul-n4
51e3f026def41778ecd0d7dcaee9f970b9937488e6716891932b73824c16d4c7  mystery-A
e2c9d0e23ee36bfc0f12d7f39fdfe2ca5a8abe8eb194fec56500733694b75c28  mystery-B
c7b37413844bf0b10ebad0010046469f500354a22cc2ba95cbe42709f8e8337d  mystery-C
b445a717483303fa3c5d8a1f7abe81888b267b7c472121c9c464fa9766808580  mystery-D

Encoding. Input = $2n$ characters: the $n$ bits of $x$ then the $n$ bits of $y$, both LSB-first (character $i$ of a block is bit $i-1$). Output = $m$ characters, LSB-first.

Regenerate practice instances (or make your own) with generate.jl:

julia generate.jl add 4 120 136 11 datasets/practice-add-n4

Circuit format & scoring

Submit a plain-text netlist of fanin-2 gates (AND OR XOR NAND NOR XNOR); inverters (~) are free:

INPUTS 16
w1 = XOR x1 x9
w2 = AND x1 x9
w3 = XOR ~w1 x2
...
OUTPUTS w1 w3 w7 ...

Score with the provided verifier — no setup, stdlib only:

julia verify.jl mycircuit.txt datasets/mystery-A/train.csv
  gates:            37  (inverters free)
  exact-match acc:  1.0
  bit accuracy:     1.0

Leaderboard order: (1) exact-match accuracy on the hidden test set, (2) fewer gates breaks ties. A circuit that memorizes the training set is easy to make and will bomb the test set — that is the point of the challenge.

Reference solution to beat: a textbook ripple-carry adder solves mystery-A(?) at 37 gates and 100% test accuracy. Can your search find such structure without being told what the function is?

Suggested attack routes (non-exhaustive)

• Tensor-network completion: DMRG-style alternating optimization of an MPS/BMP over the training entries with a bond-dimension penalty; round to a BDD, extract a circuit.
• Decision-diagram learning: build BDDs/ZDDs consistent with samples, minimize via variable reordering (sifting).
• SAT/IP exact synthesis: encode "∃ circuit with $k$ gates fitting all samples" as SAT/MILP; increment $k$. Exact and certificate-producing at small sizes — pairs beautifully with the NP-hardness story.
• Logic synthesis toolchain: treat train pairs as an incompletely-specified function; feed to ABC / espresso, then minimize.
• Symbolic regression / LLM agent: guess the semantic function ($x \cdot y$?) from a few samples, then synthesize the known optimal circuit for it. Legal and encouraged — recognizing structure IS the game.
• Hybrid: use a cheap learner to guess the function family, then exact synthesis to compress.

Deliverables (standard fork & PR model)

Fork, work under tracks/qcs/solutions/<your-team>/, and open a PR containing: your circuits (mystery-*.txt), predicted test_outputs.csv per mystery instance, committed search scripts, and a pitch-style README explaining your method and what you believe each hidden function is. Generated data goes to the gitignored results/.

Why this leads to research output

• An explicit test of Occam's razor. Grokking showed neural networks implicitly find simple solutions on partial arithmetic tables; here minimality is the explicit objective, and the gate-count-vs-generalization curve students map out is publishable evidence on when the razor works — the discrete, certificate-friendly counterpart of the grokking literature.
• New territory for tensor networks. MPS/BMP representations of Boolean functions (arXiv:2505.01930) exist as a representation; using TN completion to learn Boolean functions under a complexity constraint is unexplored, and any working DMRG-style discrete completion algorithm is a contribution on its own.
• Certificates at the hardness frontier. SAT-based exact synthesis ("∃ a k-gate circuit fitting all samples?") yields provably minimal circuits at small sizes against a problem that is NP-hard in general (partial MCSP) — a clean playground for comparing heuristic vs exact search.

References

1. Blumer, Ehrenfeucht, Haussler, Warmuth, Occam's razor, Inf. Proc. Lett. 24, 377 (1987).
2. S. Hirahara, NP-hardness of learning programs and partial MCSP, FOCS 2022.
3. A. Power et al., Grokking: generalization beyond overfitting on small algorithmic datasets, arXiv:2201.02177.
4. Usturali, Chamon, Ruckenstein, Mucciolo, A matrix product state representation of Boolean functions, arXiv:2505.01930.
5. R. E. Bryant, On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication, IEEE Trans. Comput. 40, 205 (1991).
6. Grokking as an entanglement transition in tensor network machine learning, arXiv:2503.10483.
7. Qin et al., Guaranteed nonconvex factorization approach for tensor train recovery, arXiv:2401.02592.

Download occam-circuit.zip and read its README, then inspect generate.jl and verify.jl before choosing an attack route. Work under tracks/qcs/solutions// and validate circuits against the provided training data. Done means a PR with mystery-*.txt circuits, predicted test_outputs.csv files, search scripts, and a README describing the method and inferred functions.