Theorem 4 (first claim): which extend to a quantum signal processing pair
ProvedQSVT19.Main.theorem_4_first_claimlinear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-computingquantum-signal-processingsingular-value-transformation
Let and . There is such that form a QSP pair of degree (properties (i)–(iii) of Theorem 3) if and only if , has parity , and
- (iv.a) for all ;
- (iv.b) for all ;
- (iv.c) if is even, then for all ,
These are exactly the requirements that Corollary 8 places on the target polynomial.
Formalization Note In (iv.c), "" for a complex number means real and at least (Mathlib's ComplexOrder). has the conjugated coefficients. The theorem's second claim, about , is not included.
Preamble
import Definitions.Def_QSVT19_Main_Setting set_option autoImplicit false open scoped ComplexOrder open Polynomial Matrix
Formal statement
namespace QSVT19.Main
/-- Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, Theorem 4 (first claim), p. 10: "Let k ∈ N be fixed. Let P ∈ C[x], there exists some
Q ∈ C[x] such that P, Q satisfy properties (i)-(iii) of Theorem 3 if and only if P satisfies
properties (i)-(ii) of Theorem 3 and
(iv.a) ∀x ∈ [−1, 1]: |P(x)| ≤ 1
(iv.b) ∀x ∈ (−∞, −1] ∪ [1, ∞): |P(x)| ≥ 1
(iv.c) if k is even, then ∀x ∈ R: P(ix)P^∗(ix) ≥ 1."
**Formalization Note.** Properties (i)–(iii) of Theorem 3 are `IsQSPPair k P Q`; (i)–(ii) for
`P` alone are `deg P ≤ k` and parity `k mod 2`. `P^*` is `P.map (starRingEnd ℂ)`. In (iv.c) the
comparison `1 ≤ z` of complex numbers is Mathlib's `ComplexOrder`: `z` is real and at least
`1`. The second claim of Theorem 4 ((v.a)–(v.b), about `Q`) is not part of this statement. -/
theorem theorem_4_first_claim (k : ℕ) (P : ℂ[X]) :
(∃ Q : ℂ[X], IsQSPPair k P Q) ↔ ((P.degree ≤ k ∧ QAlgorithms.HasParity P k) ∧ (∀ x ∈ Set.Icc (-1 : ℝ) 1, ‖P.eval (x : ℂ)‖ ≤ 1) ∧ (∀ x : ℝ, 1 ≤ |x| → 1 ≤ ‖P.eval (x : ℂ)‖) ∧ (Even k → ∀ x : ℝ, (1 : ℂ) ≤ P.eval (Complex.I * x) * (P.map (starRingEnd ℂ)).eval (Complex.I * x))) := by sorry
end QSVT19.Main
Source
Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, p. 10, Theorem 4 (first claim, (iv.a)–(iv.c))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.