Output law of an explicit oracle circuit
DefinitionCertRandQROM_Supplement_circOutLawcertified-randomnesscryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquery-complexityrandom-oracle-model
Let be an explicit quantum circuit on qubits (gates and controlled oracle calls) and a quantum oracle. Run on and measure wires in the computational basis. The probability of the outcome is
This is the distribution of the classical output of a quantum algorithm given as a circuit; it is used to say that a circuit family implements the honest prover.
Formalization Note The circuit model, its gate semantics qRun and the wire reader bitAt are the published QStateSearch.Supplement definitions. Intermediate measurements are deferred. No classical Boolean oracle is supplied (the model's classical-query gate sees the constant oracle).
Definition code
import Mathlib
import Definitions.Def_QStateSearch_Supplement_QCircuit
import Definitions.Def_QStateSearch_Supplement_qRun
set_option autoImplicit false
namespace CertRandQROM.Supplement
open Classical in
/-- **Output law of an explicit oracle circuit**: run the gates of `C` (published model
`QStateSearch.Supplement.QCircuit`, gates `{H, S, T, X, CNOT}` and controlled oracle calls) on
the all-zero state of its `C.wires` qubits with the quantum oracle `U`, then measure wires
`0, …, L − 1` in the computational basis; `circOutLaw U C L s` is the probability of the
outcome `s ∈ {0,1}^L`, `Σ_{z : z|_{[L]} = s} |(C|0…0⟩)(z)|²`.
Used for "`Prove^H(1^λ, 1^{h∞}) → π` … outputs a classical proof `π`" (Definition 6.1, Syntax,
p.27 of Coladangelo et al., arXiv:2608.31112, sha256 b75095a2…).
**Formalization Note** Intermediate measurements are deferred, so a circuit is unitary gates
followed by one measurement of the output wires. No classical Boolean oracle is supplied: the
gate `cquery` of the published model sees the constant-`0` oracle. Wires `≥ C.wires` read `0`
(`bitAt`). -/
noncomputable def circOutLaw (U : QStateSearch.Supplement.QOracle)
(C : QStateSearch.Supplement.QCircuit) (L : ℕ) (s : Fin L → Bool) : ℝ :=
∑ z : Fin C.wires → Bool,
if ∀ j : Fin L, QStateSearch.Supplement.bitAt z j.val = s j then
‖QStateSearch.Supplement.qRun U (fun _ => false) C.gates
(fun z0 : Fin C.wires → Bool => if z0 = fun _ => false then (1 : ℂ) else 0) z‖ ^ 2
else 0
end CertRandQROM.Supplement
Source
Coladangelo, Khurana, Mutreja, Roberts, Slote, Tal, Unconditional Certified Randomness without Structure, arXiv:2608.31112 (sha256 b75095a2…), Definition 6.1, Syntax, p.27 (PDF p.29)