Acceptance polynomial of the actual finite quantum query circuit
ProvedQuantumBipartiteTesting.Bipartiteness.actual_acceptance_polynomialLet be a finite address set and a finite non-null response alphabet. Fix an injective binary response encoding with zero-encoded null, a -query quantum circuit with an input-independent unit start vector and input-independent complex unitaries, and a fixed Boolean computational-basis output event. The query adds the encoded response by XOR and acts as the identity on the finite workspace.
There is a real polynomial in the response indicators, of total degree at most , such that for every oracle ,
The polynomial depends only on the circuit, encoding, and output event. All oracles, binary answer-register states, and finite workspaces remain included. This is the polynomial-existence step of Lemma 2.9; canonical response-table interpolation subsequently preserves its degree and values.
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Query open QuantumBipartiteTesting.Bipartiteness
theorem QuantumBipartiteTesting.Bipartiteness.actual_acceptance_polynomial
{I S : Type} [Fintype I] [Fintype S] [DecidableEq I] [DecidableEq S]
{k w q : ℕ} (E : Encoding S k) (A : Algorithm I k w q)
(out : (I × Bits k) × Fin w → Bool) :
∃ P : MvPolynomial (I × S) ℝ, P.totalDegree ≤ 2*q ∧
∀ O : I → Option S, MvPolynomial.eval (Indicators O) P = Accept E A out O := by sorry