Theorem 5.1 — unique-witness search with one query to a PMG whose generated channel is unitary
OpenICSCompute.Supplement.theorem_5_1There is a classical deterministic polynomial-time algorithm with the following property. Given a Boolean circuit with exactly one satisfying input , it computes a circuit description such that
- , uniformly in : for a constant that does not depend on ;
- is a process matrix generator (PMG);
- the generated channel is unitary;
- one query recovers with probability : applying to , measuring in the computational basis and decoding the outcome (by a polynomial-time map of the circuit and ) yields with probability exactly :
This is the core construction of Part I of the paper: a witness that is hard to find classically is extracted from one use of a generated channel. Theorem 5.2 combines it with the Valiant–Vazirani reduction to solve all of NP.
Formalization Note The algorithm is a pair of polynomial-time functions on binary strings (PvsNP.PolyTimeComputable): f maps the code of to the code encDesc D of , and g maps the code of followed by encBits w to encBits z. has external input and output qubits ( : Desc n r r), which Definition 4.6 requires of a unitary channel.
Differences from the source:
- encoding: algorithm M computing (n, C) and recovering z → polynomial-time f (encBool v ↦ encDesc D) and g (encBool v ++ encBits w ↦ encBits z) on binary strings; reason: the base mission's convention for algorithms (paper.md decision 7); injective, polynomially bounded codes
- encoding: Boolean circuit v : {0,1}ᵏ → {0,1} with exactly one satisfying input z → BoolCircuit v with v.nIn = k, one output wire, v(z) = [true] and every satisfying z′ equal to z; reason: the published Boolean circuit layer; single output wire is the codomain {0,1}
- encoding: n = O(k) → ∃ c (chosen before v) with n ≤ c·(k + 1); reason: k may be 0; for k ≥ 1, c·(k+1) ≤ 2c·k, so this is the usual O(k)
- encoding: generated channel is unitary → IsUnitaryChannel (pmoD D) with D : Desc n r r; reason: Definition 4.6 is for n-to-n channels
- generalization: using one query to the generated channel, M recovers z with probability 1 → the query applies PMO_D to |0^r⟩⟨0^r|, measures in the computational basis, and g decodes z with probability exactly 1; reason: this is the query of the proof (p.29, applying the channel to |0^k⟩⟨0^k|); a fixed recovering query implies the source's existence of one
- generalization: k ∈ ℕ (positive integers, p.19) → k : ℕ, including 0; reason: the Lean statement specializes to every positive value
import Mathlib import Definitions.Def_PvsNP import Definitions.Def_ICSCompute_IsPurePMG import Definitions.Def_ICSCompute_BoolCircuit import Definitions.Def_ICSCompute_encDesc import Definitions.Def_ICSCompute_Supplement_IsUnitaryChannel
namespace ICSCompute.Supplement
open QAlgorithms
/-- **Theorem 5.1 (Unique-witness search)** (Shmueli, *What Can Be Computed with Indefinite
Causal Structure?*, arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606, Theorem 5.1,
p.27 (PDF p.29)).
"There exists a classical deterministic polynomial-time algorithm `M` that, given a Boolean
circuit `v : {0,1}ᵏ → {0,1}` with exactly one satisfying input `z`, computes a pair `(n, C)` for
`n = O(k)` which is a PMG and whose generated channel is unitary. Moreover, using one query to
this generated channel, `M` recovers `z` with probability 1."
**Formalization Note** The algorithm is a pair of polynomial-time functions on binary strings
(`PvsNP.PolyTimeComputable`), total on all strings: `f` maps the code `encBool v` of the
Boolean circuit to the code `encDesc D` of `D = (n, C)`, and `g` maps `encBool v` followed by a
measurement outcome `w` to the code `encBits z` of the recovered witness. `v` has `k` input wires
and one output wire; "exactly one satisfying input" is `∃! z, v(z) = 1`. `n = O(k)`: one constant
`c`, fixed before `v`, with `n ≤ c (k + 1)`. The generated channel `PMO_D` is unitary
(Definition 4.6, which forces `r = ℓ`). The query applies `PMO_D` to `|0^r⟩⟨0^r|` and measures
in the computational basis; the probability of the outcomes `w` that `g` decodes to `z` is
exactly `1`. `k : ℕ` includes `0`. -/
theorem theorem_5_1 :
∃ f : PvsNP.Str → PvsNP.Str, PvsNP.PolyTimeComputable f ∧
∃ g : PvsNP.Str → PvsNP.Str, PvsNP.PolyTimeComputable g ∧
∃ c : ℕ, ∀ (k : ℕ) (v : BoolCircuit), v.nIn = k → v.outs.length = 1 →
∀ z : Qubits k, v.eval (List.ofFn z) = [true] →
(∀ z' : Qubits k, v.eval (List.ofFn z') = [true] → z' = z) →
∃ (n r : ℕ) (D : Desc n r r), f (encBool v) = encDesc D ∧ n ≤ c * (k + 1) ∧
IsPMG D ∧ IsUnitaryChannel (pmoD D) ∧
∑ w : Qubits r,
(if g (encBool v ++ encBits (List.ofFn w)) = encBits (List.ofFn z) then
pmoD D (Matrix.single (fun _ => false) (fun _ => false) 1) w w else 0) = 1 := by sorry
end ICSCompute.Supplement