Exhaustive search for -Subset-Sum as a uniformly generated qutrit circuit
ProvedF3SubsetSum.exhaustive_search_circuitLet . For an instance of -Subset-Sum (Problem 1.1), with each , a solution is a nonempty set with . Write for the probability, over independent and uniform in , that a solution exists.
There are a deterministic multi-stack Turing machine (Boolean input and output alphabets) and a constant such that for all , on input the machine halts within
steps with the code of a qutrit circuit over the gate set on its output stack, where:
- has at least wires (the input wires followed by the output wires);
- has at most gates and at most wires;
- run on and measured in the computational basis, outputs a solution of with probability at least , averaged over uniform .
In words: exhaustive search over all subsets can be carried out by a uniformly generated qutrit circuit of size that finds a solution whenever one exists. In the proof of Theorem 1.3 this handles the regime , where and the success guarantee comes from Fact 1.2.
Formalization Note Circuits, their code encodeCircuit, the input layout and successProb are those of F3SubsetSum.theorem_1_3; is probSolvable. The runtime is deliberately loose (any suffices downstream).
import Mathlib import Definitions.Def_F3SubsetSum_SubsetSum import Definitions.Def_HMBinPacking_OutputsWithin import Definitions.Def_F3SubsetSum_MachineCodes import Definitions.Def_F3SubsetSum_QutritCircuit
namespace F3SubsetSum
/-- **Exhaustive search as a circuit** (used for the regime `κn ≤ m = O(n)` of Theorem 1.3 of
Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, p.4).
There are a circuit generator `G` and a constant `C` such that for all `n`, `m`, on input
`1ⁿ 0 1ᵐ` the generator writes, within `C(n + m + 2^m + 1)^C` steps, a qutrit circuit over `G₃`
with at least `nm + m` and at most `C(n + m + 2^m + 1)^C` wires and gates that solves
Problem 1.1 on every solvable instance: its success probability is at least the probability
`probSolvable n m` that a solution exists.
Proof idea: a classical reversible circuit (gates `x`, `csum`, `ccmul` and inverses) that tries
the `2^m − 1` nonempty subsets in a fixed order, computing each subset sum into scratch wires,
testing it for zero, recording the first solution on the output wires `nm, …, nm + m − 1` under a
"found" flag, and uncomputing the scratch. On basis inputs it is a permutation, so the
measurement outputs that solution with probability `1`.
**Formalization Note** Circuits, codes and `successProb` are as in `theorem_1_3`. -/
theorem exhaustive_search_circuit :
∃ (G : Turing.TM2ComputableAux Bool Bool) (circ : ℕ → ℕ → Circuit) (C : ℕ),
∀ n m : ℕ,
HMBinPacking.OutputsWithin G (unaryD n ++ unary m) (encodeCircuit (circ n m))
(C * (n + m + 2 ^ m + 1) ^ C) ∧
n * m + m ≤ (circ n m).wires ∧
(circ n m).gates.length ≤ C * (n + m + 2 ^ m + 1) ^ C ∧
(circ n m).wires ≤ C * (n + m + 2 ^ m + 1) ^ C ∧
probSolvable n m ≤ successProb n m (circ n m) := by sorry
end F3SubsetSum