Theorem 5: real parts of quantum signal processing polynomials
ProvedQSVT19.Main.theorem_5linear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-computingquantum-signal-processingsingular-value-transformation
Let and . There exist forming a QSP pair of degree (properties (i)–(iii) of Theorem 3: , , parities and , and on ) with and if and only if
- and ;
- has parity and has parity ;
- for all ,
This tells which real polynomials can be realized as real parts of QSP polynomials; it underlies Corollary 10 and hence Corollary 18.
Formalization Note is the polynomial of the real parts of the coefficients. The theorem's parenthetical remark on imaginary parts 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 5, p. 11: "Let k ∈ N be fixed. Let P̃, Q̃ ∈ R[x], there exists some
P, Q ∈ C[x] satisfying properties (i)-(iii) of Theorem 3 such that P̃ = ℜ[P], Q̃ = ℜ[Q], if and
only if P̃, Q̃ satisfy properties (i)-(ii) of Theorem 3 and
(vi) ∀x ∈ [−1, 1]: P̃(x)^2 + (1 − x^2)Q̃^2 ≤ 1."
**Formalization Note.** Properties (i)–(iii) of Theorem 3 (p. 8) are `IsQSPPair k P Q`;
`ℜ[P] = P̃` is `RePartEq P Pt` (real parts of the coefficients, §2). Properties (i)–(ii) for the
real pair are written out: `deg P̃ ≤ k`, `deg Q̃ ≤ k − 1` (as `Q̃.degree < k`), `P̃` of parity
`k mod 2`, `Q̃` of parity `k − 1 mod 2` (as `HasParity _ (k + 1)` of the complexification). The
printed "`Q̃^2`" in (vi) is `Q̃(x)^2`. The parenthetical remark after the theorem (ℑ variants,
`Q̃ ≡ 0`) is not part of this statement. -/
theorem theorem_5 (k : ℕ) (Pt Qt : ℝ[X]) :
(∃ P Q : ℂ[X], IsQSPPair k P Q ∧ RePartEq P Pt ∧ RePartEq Q Qt) ↔ ((Pt.degree ≤ k ∧ Qt.degree < k) ∧ (QAlgorithms.HasParity (Pt.map Complex.ofRealHom) k ∧ QAlgorithms.HasParity (Qt.map Complex.ofRealHom) (k + 1)) ∧ ∀ x ∈ Set.Icc (-1 : ℝ) 1, Pt.eval x ^ 2 + (1 - x ^ 2) * Qt.eval x ^ 2 ≤ 1) := by sorry
end QSVT19.Main
Source
Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, p. 11, Theorem 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.