Quantum polynomial-time machines with oracle access to a generator
DefinitionICSCompute_Supplement_OracleMachineA quantum polynomial-time oracle machine is a machine with oracle access to a generator and to the channels it returns. Its classical control is a single deterministic polynomial-time function of the input , the current step number and the measurement outcomes seen so far, and at each step it issues one instruction:
- apply a quantum circuit over the gate set (with ancillas and discarded wires) to the quantum memory;
- issue a generation query with a classical description ;
- apply the channel returned for an earlier query to the first qubits of the memory;
- measure a qubit in the computational basis;
- halt with an output bit.
Queries may depend on and on everything computed before them, including returned channels, and returned channels may be used repeatedly. A circuit costs its size, and every query and every use of the channel it returned costs (plus one per step). The machine is polynomial-time if its control is polynomial-time computable and there is a polynomial such that for every generator, every input and every computation branch, the machine halts with total cost at most . is the total probability of the branches that halt with output . A machine is nonadaptive if on every branch no generation query is issued after a returned channel has been used.
Formalization Note This is the standard equivalent of a quantum Turing machine with intermediate measurements: uniform classical control, quantum memory, measurement outcomes fed back to the control. Branches carry unnormalized states, so probabilities are traces. A circuit instruction acts on the whole memory and is charged its full size (gates plus wires); this overcharges a single gate by at most the current width, which is below the total cost, so polynomial time changes by at most squaring. Channels act on the first qubits; wires are moved by SWAP gates. An instruction that cannot be executed stops the branch without output.
import Mathlib
import Definitions.Def_PvsNP
import Definitions.Def_ICSCompute_IsQuantumChannel
import Definitions.Def_ICSCompute_IsPurePMG
import Definitions.Def_ICSCompute_encDesc
import Definitions.Def_ICSCompute_Supplement_IsLinearCTCGenerator
namespace ICSCompute.Supplement
open QAlgorithms
/-- A circuit description of any dimensions: `(m, r, ℓ, C)` with `C : Desc m r ℓ`. -/
abbrev AnyDesc := Σ m : ℕ, Σ r : ℕ, Σ ℓ : ℕ, Desc m r ℓ
/-- An instruction of the classical controller of an oracle machine:
* `circ a b C` — apply the quantum circuit `C` (an `a`-to-`b` circuit over the paper's gate set,
with `|0⟩` ancillas and discarded wires) to the whole quantum memory, which must have `a`
qubits; afterwards it has `b`;
* `query m r ℓ D` — a generation query with the classical description `D = (m, C)`; the returned
channel gets the next handle (handles are `0, 1, 2, …` in query order);
* `use h` — apply the channel returned for the query with handle `h` (an `r`-to-`ℓ` channel) to
the first `r` qubits of the memory; its `ℓ` output qubits become the first qubits;
* `measure` — measure the first qubit in the computational basis; the outcome is appended to the
classical transcript;
* `halt b` — stop with output bit `b`. -/
inductive Instr where
| circ (a b : ℕ) (C : QCirc a b)
| query (m r ℓ : ℕ) (D : Desc m r ℓ)
| use (h : ℕ)
| measure
| halt (out : Bool)
/-- Whether an instruction is a generation query. -/
def Instr.isQuery : Instr → Bool
| .query _ _ _ _ => true
| _ => false
/-- Whether an instruction is a use of a returned channel. -/
def Instr.isUse : Instr → Bool
| .use _ => true
| _ => false
/-- Binary code of an instruction: a tag `0, …, 4`, then the circuit (`encQCirc`, which records
its input and output sizes), the description (`encDesc`, which records `m, r, ℓ`), the handle, or
the output bit. -/
noncomputable def encInstr : Instr → PvsNP.Str
| .circ _ _ C => encNat 0 ++ encQCirc C
| .query _ _ _ D => encNat 1 ++ encDesc D
| .use h => encNat 2 ++ encNat h
| .measure => encNat 3
| .halt b => encNat 4 ++ encBits [b]
open Classical in
/-- The instruction coded by a string, if any. -/
noncomputable def decodeInstr (s : PvsNP.Str) : Option Instr :=
if h : ∃ i, encInstr i = s then some h.choose else none
/-- The controller's input: the machine input `x`, the measurement outcomes so far, and the
current step number. The clock lets the stateless controller emit successive instructions even
when no measurement occurs between them. -/
def ctrlInput (x outcomes : PvsNP.Str) (clock : ℕ) : PvsNP.Str :=
encBits x ++ encBits outcomes ++ encNat clock
/-- Re-indexing `S(a) = S(b)` along `a = b`. -/
def castBits {a b : ℕ} (h : a = b) : Qubits a ≃ Qubits b :=
Equiv.arrowCongr (finCongr h) (Equiv.refl Bool)
/-- `(Φ ⊗ id)(ρ)`: an `r`-to-`ℓ` map applied to the first `r` of the `w` qubits of `ρ`; the result
has the `ℓ` output qubits first, followed by the untouched `w − r` qubits. -/
def applyFront {r ℓ w : ℕ} (h : r ≤ w)
(Φ : Matrix (Qubits r) (Qubits r) ℂ →ₗ[ℂ] Matrix (Qubits ℓ) (Qubits ℓ) ℂ)
(ρ : Matrix (Qubits w) (Qubits w) ℂ) :
Matrix (Qubits (ℓ + (w - r))) (Qubits (ℓ + (w - r))) ℂ :=
let e : Qubits w ≃ Qubits r × Qubits (w - r) :=
(castBits (by omega : w = r + (w - r))).trans (splitQ r (w - r))
Matrix.reindex (splitQ ℓ (w - r)).symm (splitQ ℓ (w - r)).symm
(tensorId Φ (Matrix.reindex e e ρ))
/-- The unnormalized post-measurement state for outcome `b` of the first qubit:
`(|b⟩⟨b| ⊗ I) ρ (|b⟩⟨b| ⊗ I)`. -/
def projectFirst {w : ℕ} (hw : 0 < w) (b : Bool) (ρ : Matrix (Qubits w) (Qubits w) ℂ) :
Matrix (Qubits w) (Qubits w) ℂ :=
Matrix.of fun x y => if x ⟨0, hw⟩ = b ∧ y ⟨0, hw⟩ = b then ρ x y else 0
/-- A computation branch: the classical transcript, the queries issued, the instructions executed,
the accumulated cost, and the unnormalized quantum state (its trace is the branch probability). -/
structure Branch where
/-- Measurement outcomes so far. -/
outcomes : List Bool
/-- Generation queries issued so far; the handle of a query is its position. -/
queries : List AnyDesc
/-- Instructions executed so far. -/
log : List Instr
/-- Accumulated cost. -/
cost : ℕ
/-- Number of qubits of the quantum memory. -/
width : ℕ
/-- The unnormalized state of the quantum memory. -/
state : Matrix (Qubits width) (Qubits width) ℂ
/-- The output bit, once the branch halted with `halt b`. -/
output : Option Bool
/-- The branch has stopped (by `halt`, or by an invalid instruction, without output). -/
halted : Bool
/-- The initial branch: empty transcript, no qubits, state `1`. -/
def Branch.init : Branch :=
{ outcomes := [], queries := [], log := [], cost := 0, width := 0, state := 1,
output := none, halted := false }
/-- One step of the machine with controller `ctrl`, generator `G` and input `x` on one branch.
Costs: `1` per halt and measurement, `1 + |C|` per circuit, `1 + m + |C|` per query `(m, C)` and
per use of the channel it returned. An instruction that cannot be executed (the string decodes to
no instruction, a circuit whose input size is not the memory width, an unknown handle, a channel
with more inputs than the memory has qubits, a measurement of an empty memory) stops the branch
without output. -/
noncomputable def step (ctrl : PvsNP.Str → PvsNP.Str) (G : Generator) (x : PvsNP.Str)
(β : Branch) : List Branch :=
if β.halted then [β] else
match decodeInstr (ctrl (ctrlInput x β.outcomes β.log.length)) with
| none => [{ β with halted := true }]
| some i =>
let lg := β.log ++ [i]
match i with
| .halt b => [{ β with log := lg, output := some b, halted := true, cost := β.cost + 1 }]
| .circ a b C =>
if h : β.width = a then
[{ β with
log := lg, cost := β.cost + 1 + C.size, width := b,
state := C.channel (Matrix.reindex (castBits h) (castBits h) β.state) }]
else [{ β with log := lg, halted := true }]
| .query m r ℓ D =>
[{ β with
log := lg, queries := β.queries ++ [⟨m, r, ℓ, D⟩],
cost := β.cost + 1 + m + D.size }]
| .use hd =>
match β.queries[hd]? with
| none => [{ β with log := lg, halted := true }]
| some ⟨m, r, ℓ, D⟩ =>
if hr : r ≤ β.width then
[{ β with
log := lg, cost := β.cost + 1 + m + D.size, width := ℓ + (β.width - r),
state := applyFront hr (G.A m r ℓ D) β.state }]
else [{ β with log := lg, halted := true }]
| .measure =>
if hw : 0 < β.width then
[false, true].map fun b =>
{ β with
log := lg, outcomes := β.outcomes ++ [b], cost := β.cost + 1,
state := projectFirst hw b β.state }
else [{ β with log := lg, halted := true }]
/-- All branches after `t` steps. -/
noncomputable def runFor (ctrl : PvsNP.Str → PvsNP.Str) (G : Generator) (x : PvsNP.Str) :
ℕ → List Branch
| 0 => [Branch.init]
| t + 1 => (runFor ctrl G x t).flatMap (step ctrl G x)
/-- **Quantum polynomial-time oracle machine** `M^A` (Shmueli, *What Can Be Computed with
Indefinite Causal Structure?*, arXiv:2610.40573, version of 2026-11-03, sha256 d3e36399…b606,
§4.2, "Oracle access and cost", p.22 (PDF p.24)): "`M^A` denotes a machine `M` with oracle access
to a generator `A` and the channels it returns. Every generation query `(m, C)` has a classical
description. Queries may depend on the input `x` and on the preceding computation, and may be
adaptive. Every query `(m, C)` and every use of the channel it returns costs `Θ(|C|)` time."
A machine is a classical controller `ctrl` together with a time bound `time`: at each step, the
controller maps `x`, the measurement outcomes so far, and the current step number to the next
instruction (`Instr`, coded by `encInstr`). `IsPolyTime` asks that `ctrl` is polynomial-time computable and that, for
every generator and every input, every branch has halted within `time(|x|)` steps with total cost
at most `time(|x|)`.
**Formalization Note** This is the standard equivalent of a quantum Turing machine with
intermediate measurements: a uniform, deterministic, polynomial-time classical control that
issues gates, measurements, generation queries and channel uses, and reads measurement outcomes.
The controller sees `x`, the outcomes, and the current step number; it can recompute its earlier
queries and handles from them. The quantum memory starts with no qubits; a circuit instruction acts on the whole memory
(adding `|0⟩` ancillas and discarding wires as the circuit says), and its cost is its size
`|C|` (gates plus wires), so a gate costs at most the current width, which a machine of cost
`T` keeps below `T`; this changes polynomial time by at most squaring. A query `(m, C)` and every
use of its channel cost `1 + m + |C|` (the size `|D|` includes `m` and `|C|`, Definition 4.5).
Channels act on the first qubits of the memory; wires are rearranged by circuits (SWAP gates).
Branches are kept with their unnormalized states, so measurement probabilities are traces. The
polynomial bound must hold for **every** generator and on **every** branch, so the machine's
cost never depends on the oracle's answers. -/
structure OracleMachine where
/-- The classical controller, on `ctrlInput x outcomes clock`. -/
ctrl : PvsNP.Str → PvsNP.Str
/-- The time bound, a polynomial in the input length. -/
time : Polynomial ℕ
/-- All branches of `M^G(x)` after `time(|x|)` steps. -/
noncomputable def OracleMachine.run (M : OracleMachine) (G : Generator) (x : PvsNP.Str) :
List Branch :=
runFor M.ctrl G x (M.time.eval x.length)
/-- `Pr[M^G(x) = b]`: the total trace of the branches that halted with output `b`. -/
noncomputable def OracleMachine.prob (M : OracleMachine) (G : Generator) (x : PvsNP.Str)
(b : Bool) : ℝ :=
((M.run G x).map fun β => if β.output = some b then (Matrix.trace β.state).re else 0).sum
/-- `M` is a quantum polynomial-time oracle machine: its controller is polynomial-time
computable, and for every generator and input every branch halts within cost `time(|x|)`. -/
def OracleMachine.IsPolyTime (M : OracleMachine) : Prop :=
PvsNP.PolyTimeComputable M.ctrl ∧
∀ (G : Generator) (x : PvsNP.Str), ∀ β ∈ M.run G x,
β.halted = true ∧ β.cost ≤ M.time.eval x.length
/-- `M` makes only nonadaptive generation queries: on every branch, for every generator and
input, no generation query is issued after a returned channel has been used. -/
def OracleMachine.IsNonadaptive (M : OracleMachine) : Prop :=
∀ (G : Generator) (x : PvsNP.Str), ∀ β ∈ M.run G x,
∀ i j : Fin β.log.length, i < j → (β.log.get i).isUse = true →
(β.log.get j).isQuery = false
end ICSCompute.Supplement