Theorem 5.2 — with polynomially many nonadaptive formula queries
OpenICSCompute.Supplement.theorem_5_2complexity-theoryindefinite-causal-orderp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1process-matricesquantum-information
- : every language in NP, as the promise problem , is in .
- The algorithm for SAT has the following form. There is a quantum polynomial-time oracle machine that decides SAT (strings coding no CNF formula are NO instances) with error at most for every linear CTC generator, such that
- its generation queries are nonadaptive: on every branch, no query is issued after a returned channel has been used;
- it makes polynomially many queries: at most on every branch, for a polynomial ;
- every query is built from a formula: there is a polynomial-time map from formula codes to description codes such that every query of is for some CNF formula ;
- whenever has exactly one satisfying assignment, codes a description, and that description is a PMG whose generated channel is unitary.
Linearity of the CTC evolution was proposed as a way to exclude the PP-hard power of postselected CTCs; this theorem shows that linear CTC generation still captures NP, while every query the algorithm relies on is a valid PMG with unitary generated channel.
Formalization Note NP and SAT are the published PvsNP.NP and PvsNP.SAT. The machine model is OracleMachine; the error bound must hold for every linear CTC generator, and the time bound for every generator and branch. "Exactly one satisfying assignment" is relative to the variables occurring in (UniquelySat).
Differences from the source:
- encoding: NP ⊆ BQPℓCTC, a containment of a class of languages in a class of promise problems → for every L in the published PvsNP.NP, the promise problem (L, complement of L) is in the class; reason: the usual identification of a language with a promise problem with empty promise
- encoding: quantum polynomial-time Turing machine M with oracle access to the generator (cost Θ(|C|) per query and per channel use) → OracleMachine: one polynomial-time classical controller of x, the current step number and the measurement outcomes, issuing circuits, computational-basis measurements, queries and channel uses; cost |C| per circuit and m + |C| per query and per use; polynomial bound on every branch; reason: standard equivalent of a QTM with intermediate measurements; the cost rule differs from the source's by at most squaring, so polynomial time is the same
- reading: M is a quantum polynomial-time machine, then: for every generator A … → the polynomial time bound holds for every generator and on every branch; reason: Definition 4.12 fixes M, and with it its running time, before quantifying over A; a QTM's time bound covers every computation path
- reading: the algorithm makes nonadaptive generation queries → on every branch, for every generator and input, no query instruction follows a channel-use instruction; reason: queries then depend only on x and on measurement outcomes of oracle-free computation (random coins), the standard randomized nonadaptive model; the proof's Valiant–Vazirani randomness is such coins
- reading: polynomially many generation queries → a polynomial p with at most p(|x|) queries on every branch, for every generator and input; reason: the same quantifiers as the time bound
- reading: the formula used in a query → a polynomial-time map q on binary strings with every query of M coded as q(encodeCNF φ*) for some CNF φ*; reason: Step 2 of the proof (p.29) builds each query deterministically from the reduced formula φ*
- generalization: whenever a formula used in a query has exactly one satisfying assignment, the query is a PMG and its generated channel is unitary → for every UniquelySat φ*, q(encodeCNF φ*) codes a PMG with IsUnitaryChannel (pmoD D), whether or not that formula occurs on a branch; reason: Step 2 uses one uniform deterministic circuit construction on every reduced formula, so this specializes to every formula actually used in a query; the existence clause rules out a vacuous code
- encoding: exactly one satisfying assignment → UniquelySat: satisfiable, and all satisfying assignments agree on the variables occurring in φ*; reason: published PvsNP assignments are total functions ℕ → Bool
Preamble
import Mathlib import Definitions.Def_PvsNP import Definitions.Def_ICSCompute_IsPurePMG import Definitions.Def_ICSCompute_encDesc import Definitions.Def_ICSCompute_Supplement_IsUnitaryChannel import Definitions.Def_ICSCompute_Supplement_UniquelySat import Definitions.Def_ICSCompute_Supplement_InBQPlCTC
Formal statement
namespace ICSCompute.Supplement
open QAlgorithms
/-- **Theorem 5.2** (Shmueli, *What Can Be Computed with Indefinite Causal Structure?*,
arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606, Theorem 5.2, p.29 (PDF p.31)).
"`NP ⊆ BQP_ℓCTC`. The algorithm makes polynomially many nonadaptive generation queries. Whenever
the formula used in a query has exactly one satisfying assignment, the query is a PMG and its
generated channel is unitary."
**Formalization Note** First conjunct: every `L ∈ PvsNP.NP`, as the promise problem
`(L, complement of L)`, is in `BQP_ℓCTC`. Second conjunct, the algorithm for `SAT` (the published
`PvsNP.SAT`; strings coding no formula are NO instances): a quantum polynomial-time oracle
machine `M` deciding `(SAT, complement)` with error `2^{−|x|}` for every linear CTC generator,
such that on every branch (for every generator and input) no query follows a channel use
(nonadaptive), the number of queries is at most a polynomial in `|x|`, and there is a
polynomial-time map `q` from formula codes to description codes with every query of `M` equal to
`q(φ*)` for some CNF `φ*` (the formula used in the query); whenever `φ*` has exactly one
satisfying assignment (over its variables, `UniquelySat`), `q(φ*)` codes a description, and that
description is a PMG whose generated channel is unitary (Definition 4.6). -/
theorem theorem_5_2 :
(∀ L ∈ PvsNP.NP, InBQPlCTC (ofLanguage L)) ∧
∃ M : OracleMachine, M.IsPolyTime ∧ M.Decides pmgValid (ofLanguage PvsNP.SAT) ∧
M.IsNonadaptive ∧
(∃ p : Polynomial ℕ, ∀ (G : Generator) (x : PvsNP.Str), ∀ β ∈ M.run G x,
β.queries.length ≤ p.eval x.length) ∧
∃ q : PvsNP.Str → PvsNP.Str, PvsNP.PolyTimeComputable q ∧
(∀ (G : Generator) (x : PvsNP.Str), ∀ β ∈ M.run G x, ∀ d ∈ β.queries,
∃ φ : PvsNP.CNF, q (PvsNP.encodeCNF φ) = encDesc d.2.2.2) ∧
∀ φ : PvsNP.CNF, UniquelySat φ →
(∃ (m r ℓ : ℕ) (D : Desc m r ℓ), q (PvsNP.encodeCNF φ) = encDesc D) ∧
∀ (m r ℓ : ℕ) (D : Desc m r ℓ), q (PvsNP.encodeCNF φ) = encDesc D →
IsPMG D ∧ IsUnitaryChannel (pmoD D) := by sorry
end ICSCompute.Supplement
Source
Shmueli, What Can Be Computed with Indefinite Causal Structure?, arXiv:2610.40573 (version of 2026-11-03, sha256 d3e36399…b606), Theorem 5.2, p.29 (PDF p.31); proof pp.29–30