Vertex expansion, edit distance, and quantum testers
DefinitionQuantumBipartiteTesting_Bipartiteness_Supplement_ExpansionFor a simple graph on labeled vertices, the external boundary contains vertices outside adjacent to . Vertex expansion means for every , including the empty set. The all-cuts edge expansion predicate counts crossing edges once.
Distance to -expansion is the infimum of the numbers of edge additions and deletions over actual simple target graphs on the same vertices. It is an extended nonnegative real number, equal to if no target exists. Farness compares this distance with . The two-threshold tester must accept every -expander and reject every graph -far from -expansion with probability at least , for every packed neighbor ordering. It uses the published complex quantum circuits and XOR response encodings, rather than a supplied acceptance function.
The rate is . This layer gives the expansion-specific interface without changing the published bipartiteness distance.
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Query
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset
noncomputable section
attribute [local instance] Classical.propDecidable
/-- Definition 2.5: the external vertex boundary, with no multiplicities. -/
def Boundary {n : ℕ} (G : Finset (Edge n)) (U : Finset (Fin n)) : Finset (Fin n) :=
univ.filter fun v => v ∉ U ∧ ∃ u ∈ U, v ∈ Neighbors G u
def VertexExpander {n : ℕ} (α : ℝ) (G : Finset (Edge n)) : Prop :=
∀ U : Finset (Fin n), 2 * U.card ≤ n → α * U.card ≤ (Boundary G U).card
def Crossing {n : ℕ} (G : Finset (Edge n)) (U : Finset (Fin n)) : Finset (Edge n) :=
G.filter fun e => (e.1 ∈ U ∧ e.2 ∉ U) ∨ (e.2 ∈ U ∧ e.1 ∉ U)
def EdgeExpander {n : ℕ} (ρ : ℝ) (G : Finset (Edge n)) : Prop :=
∀ U : Finset (Fin n), ρ * min (U.card : ℝ) (n - (U.card : ℝ)) ≤ (Crossing G U).card
/-- The infimum is +∞ when there is no same-vertex-set expanding target. -/
def ExpansionDistance {n : ℕ} (α : ℝ) (G : Finset (Edge n)) : ENNReal :=
sInf {x | ∃ T : Finset (Edge n), IsGraph T ∧ VertexExpander α T ∧
x = (((G \ T).card + (T \ G).card : ℕ) : ENNReal)}
def ExpansionFar {n : ℕ} (d : ℕ) (ε α : ℝ) (G : Finset (Edge n)) : Prop :=
ENNReal.ofReal (ε * d * n) ≤ ExpansionDistance α G
/-- Correctness on every promised graph and every packed adjacency representation. -/
def ExpansionTester {n d k w q : ℕ} (ε α α' : ℝ) (E : Encoding (Fin n) k)
(A : Algorithm (Address n d) k w q)
(out : (Address n d × Bits k) × Fin w → Bool) : Prop :=
∀ G : Finset (Edge n), IsGraph G → DegreeBound d G →
∀ O : Fin n × Fin d → Option (Fin n), Represents G O →
(VertexExpander α G → 2/3 ≤ Accept E A out (LiftOracle O)) ∧
(ExpansionFar d ε α' G → Accept E A out (LiftOracle O) ≤ 1/3)
def ExpansionScale (n : ℕ) : ℝ :=
(n : ℝ) ^ (1/3 : ℝ) / (Real.log n) ^ (4/3 : ℝ)
end
end QuantumBipartiteTesting.Bipartiteness.Supplement