Theorem 1.1 — , also when valid queries must be purifiable with unitary generated channel
OpenICSCompute.Supplement.theorem_1_1complexity-theoryindefinite-causal-orderp2o-gran-per-chapterp2o-plan-paperp2o-v1process-matricesquantum-information
- .
- The containment continues to hold when the valid generation queries are required to describe purifiable processes (Definition 4.10) whose generated channels are unitary (Definition 4.6): every language in NP is decided, with error at most , by one quantum polynomial-time oracle machine for every generator that returns the generated channel on those descriptions that are purifiable PMGs with a unitary generated channel, and returns an arbitrary quantum channel of the right dimensions on all other descriptions.
The second part is the stronger statement, since such generators are obliged on fewer descriptions than linear CTC generators. It shows that NP-solving power survives even if only processes that meet the purification postulate and generate unitary evolutions are honoured, although the generating circuits themselves are not unitary (the processes are not pure).
Formalization Note NP is the published PvsNP.NP, with a language identified with the promise problem . Both classes use the machine model OracleMachine with error exactly ; they differ only in the generator's obligation (pmgValid versus purifiableUnitaryValid).
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 valid generation queries are required to describe purifiable processes whose generated channels are unitary → the class of Definition 4.12 in which the generator must equal PMO_D only on purifiable PMGs with unitary generated channel (purifiableUnitaryValid), arbitrary channels elsewhere; reason: requiring validity of more structure from the queries the oracle must honour constrains the oracle less, so this is the stronger containment; the proof (Lemma 5.1, Proposition 5.1) only relies on such queries
Preamble
import Mathlib import Definitions.Def_PvsNP import Definitions.Def_ICSCompute_Supplement_InBQPlCTC
Formal statement
namespace ICSCompute.Supplement
/-- **Theorem 1.1** (Shmueli, *What Can Be Computed with Indefinite Causal Structure?*,
arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606, Theorem 1.1, p.3 (PDF p.5)).
"Let `BQP_ℓCTC` as in Definition 4.12. Then, `NP ⊆ BQP_ℓCTC`. The containment continues to hold
even given two more conditions: the valid generation queries are required to describe purifiable
processes (Definition 4.10) whose generated channels (Definition 4.5) are unitary."
**Formalization Note** `NP` is the published `PvsNP.NP`; a language `L` is identified with the
promise problem `(L, complement of L)`. The second conjunct is the class of Definition 4.12 in
which the generator must return `PMO_D` only on descriptions that are purifiable PMGs with a
unitary generated channel (`purifiableUnitaryValid`) and may return any channel elsewhere; it
constrains the generator less, so this containment is the stronger one (reading of the italic
clause; the proof, via Lemma 5.1 and Proposition 5.1, only ever relies on such queries). -/
theorem theorem_1_1 :
(∀ L ∈ PvsNP.NP, InBQPlCTC (ofLanguage L)) ∧
∀ L ∈ PvsNP.NP, InBQPCTCWith purifiableUnitaryValid (ofLanguage L) := 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 1.1, p.3 (PDF p.5); Theorem 5.2, p.29; Proposition 5.1, pp.26–27