The complexity class
DefinitionICSCompute_Supplement_InBQPlCTCA promise problem is a pair of sets of binary strings; a language is the promise problem . The class (Definition 4.12) consists of the promise problems for which there is a quantum polynomial-time oracle machine such that, for every linear CTC generator ,
The same definition with the generator's obligation weakened, so that need return the generated channel only on descriptions that are purifiable PMGs (Definition 4.10) with a unitary generated channel (Definition 4.6), gives the smaller class of the second sentence of Theorem 1.1.
Formalization Note The error is exactly , with the input length, not a constant. The machine model and its cost rule are OracleMachine; the polynomial time bound holds for every generator. InBQPCTCWith Valid is the class for an arbitrary obligation Valid, and InBQPlCTC is the case pmgValid.
import Mathlib
import Definitions.Def_PvsNP
import Definitions.Def_ICSCompute_IsPurePMG
import Definitions.Def_ICSCompute_Supplement_IsUnitaryChannel
import Definitions.Def_ICSCompute_Supplement_IsPurifiablePMG
import Definitions.Def_ICSCompute_Supplement_IsLinearCTCGenerator
import Definitions.Def_ICSCompute_Supplement_OracleMachine
namespace ICSCompute.Supplement
open QAlgorithms
/-- A promise problem `Π = (Π_YES, Π_NO)` of binary strings. -/
structure PromiseProblem where
/-- The YES instances. -/
yes : Set PvsNP.Str
/-- The NO instances. -/
no : Set PvsNP.Str
/-- The promise problem `(L, complement of L)` of a language. -/
def ofLanguage (L : Language Bool) : PromiseProblem :=
{ yes := {x | x ∈ L}, no := {x | x ∉ L} }
/-- `M` decides `Π` with error `2^{−|x|}` for every generator that agrees with `PMO_D` on the
descriptions satisfying `Valid`: `Pr[M^A(x) = 1] ≥ 1 − 2^{−|x|}` on YES instances and
`Pr[M^A(x) = 0] ≥ 1 − 2^{−|x|}` on NO instances. -/
def OracleMachine.Decides (M : OracleMachine) (Valid : ValidityPredicate)
(PP : PromiseProblem) : Prop :=
∀ G : Generator, G.AgreesOn Valid → ∀ x : PvsNP.Str,
(x ∈ PP.yes → 1 - ((2 : ℝ) ^ x.length)⁻¹ ≤ M.prob G x true) ∧
(x ∈ PP.no → 1 - ((2 : ℝ) ^ x.length)⁻¹ ≤ M.prob G x false)
/-- Membership in the class of Definition 4.12 with the generator's obligation given by
`Valid`: some quantum polynomial-time oracle machine decides `Π` for every such generator. -/
def InBQPCTCWith (Valid : ValidityPredicate) (PP : PromiseProblem) : Prop :=
∃ M : OracleMachine, M.IsPolyTime ∧ M.Decides Valid PP
/-- The weaker obligation of Theorem 1.1's second sentence: the generator must return `PMO_D`
only on descriptions that are purifiable PMGs (Definition 4.10) whose generated channel is
unitary (Definition 4.6). -/
def purifiableUnitaryValid : ValidityPredicate :=
fun _ _ _ D => IsPurifiablePMG D ∧ IsUnitaryChannel (pmoD D)
/-- **The complexity class `BQP_ℓCTC`** (Shmueli, *What Can Be Computed with Indefinite Causal
Structure?*, arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606, Definition 4.12,
p.23 (PDF p.25)): "The class `BQP_ℓCTC` consists of the promise problems `Π := (Π_YES, Π_NO)`
for which there exists a quantum polynomial-time Turing machine `M` such that, for every linear
CTC generator `A` as in Definition 4.11, `∀ x ∈ Π_YES : Pr[M^A(x) = 1] ≥ 1 − 2^{−|x|}`, and
`∀ x ∈ Π_NO : Pr[M^A(x) = 0] ≥ 1 − 2^{−|x|}`."
**Formalization Note** The machine model is `OracleMachine` (uniform polynomial-time classical
control with intermediate measurements, adaptive queries, repeated channel use, cost `|C|` per
query and per use, polynomial bound for every generator and every branch). The error is exactly
`2^{−|x|}`, with `|x|` the input length. A linear CTC generator is a `Generator` agreeing with
`PMO_D` on every PMG (`pmgValid`), i.e. `IsLinearCTCGenerator`. -/
def InBQPlCTC (PP : PromiseProblem) : Prop :=
InBQPCTCWith pmgValid PP
end ICSCompute.Supplement