Corollary 8: quantum signal processing using reflections
ProvedQSVT19.Main.corollary_8linear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-computingquantum-signal-processingsingular-value-transformation
Let and let have degree , parity , on , for , and, if is even, for all real . Then there is such that for every
Moreover, for this , for , and, if is even, .
This converts the -based characterization of quantum signal processing into the reflection form used for singular value transformation.
Formalization Note The hypothesis is added: at the constant , , meets every condition but the empty product is ; the paper's proof says "for some ". Phases are 0-based, so becomes .
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, Corollary 8, pp. 12–13: "Let P ∈ C[x] be a degree-d polynomial, such that
• P has parity-(d mod 2), • ∀x ∈ [−1, 1]: |P(x)| ≤ 1, • ∀x ∈ (−∞, −1] ∪ [1, ∞): |P(x)| ≥ 1,
• if d is even, then ∀x ∈ R: P(ix)P^∗(ix) ≥ 1.
Then there exists Φ ∈ R^d such that ∏_{j=1}^d (e^{iφ_jσ_z}R(x)) = [P(x) .; . .]. (14)
Moreover for x ∈ {−1, 1} we have that P(x) = x^d ∏_{j=1}^d e^{iφ_j}, and for d even
P(0) = e^{−i∑_{j=1}^d(−1)^jφ_j}."
**Formalization Note.** The four bullets and "degree-d" are `Cor8Requirements d P`. (14) is
required for every `x ∈ [−1, 1]`, the domain of `R(x)` (Definition 7); "`[P(x) .; . .]`" says that
the top-left entry is `P(x)`. The "Moreover" values are stated for the same `Φ`. `Φ` is 0-based, so
the paper's `(−1)^j` (with `j = 1, …, d`) is `(−1)^(j+1)` for `j : Fin d`. The hypothesis `1 ≤ d`
is added: at `d = 0` the statement is false (`P ≡ e^{iα}`, `α ∉ 2πℤ`, meets every bullet, while
the empty product is `I`); the proof says "for some d ≥ 1". -/
theorem corollary_8 (d : ℕ) (hd : 1 ≤ d) (P : ℂ[X]) (hP : Cor8Requirements d P) :
∃ Φ : Fin d → ℝ, (∀ x ∈ Set.Icc (-1 : ℝ) 1, qspRefl Φ x 0 0 = P.eval (x : ℂ)) ∧ (∀ x : ℝ, (x = -1 ∨ x = 1) → P.eval (x : ℂ) = (x : ℂ) ^ d * ∏ j : Fin d, Complex.exp (Φ j * Complex.I)) ∧ (Even d → P.eval 0 = Complex.exp (-(∑ j : Fin d, (-1 : ℂ) ^ (j.val + 1) * (Φ j : ℂ)) * Complex.I)) := by sorry
end QSVT19.Main
Source
Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, p. 12–13, Corollary 8, (14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.