Independent two-run equality procedure
DefinitionIQPForrelation832_SingleQuery_Supplement_RepetitionLet be a published one-query program, its branch, and its accepting decider. For two independent fresh-register executions, define the acceptance event to mean equality of the two decoded decision bits. If their output states are and , its conditional probability is the ordinary Born probability of that event in . Average over two independent fair branch coins:
Here equality compares the Boolean acceptance predicates, including equality when both predicates are false. Two-run validity requires actual compilations of the two programs into IQP middle blocks whose joint-oracle counts sum to two. The published per-run compiler, decider and efficiency model are reused without alteration. This definition supplies only the composition and its measurement event, with no acceptance identity assumed.
import Definitions.Def_IQPForrelation832_SingleQuery_Programs
set_option autoImplicit false
namespace IQPForrelation832.SingleQuery.Supplement
open QAlgorithms QAlgorithms.Complexity
/-- Two independent measurements on fresh registers; the event compares the two decoded
bits. The uniform branch coins are summed separately in `twoRunBorn`. -/
noncomputable def equalDecisionBorn (n : ℕ) (p q : Program) (a : Str → Str)
(b c : Bool) (f g : Cube n → ℝ) : ℝ := by
classical
exact match compile n p, compile n q with
| some cp, some cq =>
probEvent (tensorVec (run cp f g) (run cq f g))
(fun z => accepts a n b z.1 ↔ accepts a n c z.2)
| _, _ => 0
noncomputable def twoRunBorn (n : ℕ) (p : ℕ → Bool → Program) (a : Str → Str)
(f g : Cube n → ℝ) : ℝ :=
(∑ b : Bool, ∑ c : Bool, equalDecisionBorn n (p n b) (p n c) a b c f g) / 4
/-- The two physical runs have exactly two occurrences of the joint oracle altogether. -/
def TwoRunValid (n : ℕ) (p : ℕ → Bool → Program) : Prop :=
∀ b c, ∃ cp cq, compile n (p n b) = some cp ∧ compile n (p n c) = some cq ∧
IsIQP cp ∧ IsIQP cq ∧
OracleCircuit.queryCount cp 0 + OracleCircuit.queryCount cq 0 = 2
end IQPForrelation832.SingleQuery.Supplement