Corollary 18: singular value transformation by real polynomials
ProvedQSVT19.Main.corollary_18Let be a unitary and orthogonal projectors on a finite-dimensional Hilbert space. Let and let be a polynomial of degree with parity and for all . Then there is such that, for every singular value decomposition of , Here is the singular value transformation of Definition 16, the alternating phase modulation sequence (31), and on one ancilla qubit.
Every bounded real polynomial of definite parity can thus be applied to the singular values of a block of a unitary, with one ancilla qubit and uses of and ; this is the identity behind the paper's applications.
Formalization Note The hypothesis is added: for a constant satisfies the conditions, its transformation is , while the right-hand side is . The ancilla is the first tensor factor; is chosen before the decomposition.
import Definitions.Def_QSVT19_Main_Setting set_option autoImplicit false open scoped ComplexOrder open Polynomial Matrix
namespace QSVT19.Main
/-- Gilyén, Su, Low, Wiebe, arXiv:1806.01838v1, Corollary 18 (Singular value transformation by real polynomials), p. 19: "Let U, Π, Π̃ be
as in Theorem 17. Suppose that P_ℜ ∈ R[x] is a degree-n polynomial satisfying that
• P_ℜ has parity-(n mod 2) and • for all x ∈ [−1, 1]: |P_ℜ(x)| ≤ 1.
Then there exist Φ ∈ R^n, such that
P_ℜ^{(SV)}(Π̃UΠ) = (⟨+| ⊗ Π̃)(|0⟩⟨0| ⊗ U_Φ + |1⟩⟨1| ⊗ U_{−Φ})(|+⟩ ⊗ Π) if n is odd, and
(⟨+| ⊗ Π)(|0⟩⟨0| ⊗ U_Φ + |1⟩⟨1| ⊗ U_{−Φ})(|+⟩ ⊗ Π) if n is even. (33)"
**Formalization Note.** `H_U` is `ι → ℂ` for a finite type `ι`, with inner product
`star v ⬝ᵥ w`; `Π, Π̃` are `Proj, Projt`; "unitary" is `U ∈ Matrix.unitaryGroup ι ℂ` and
"orthogonal projector" is `IsStarProjection` (self-adjoint idempotent). "degree-n" is `natDegree = n`; the parity of `P_ℜ` is that of its image in `ℂ[X]`.
`P_ℜ^{(SV)}(Π̃UΠ)` is Definition 16 applied to `x ↦ P_ℜ(x)` over a singular value decomposition
`S` of `Π̃UΠ` (`svtOdd` for odd `n`, `svtEven` for even `n`); the identity is asserted for every
such decomposition, with `Φ` chosen before it (as `P^{(SV)}` does not depend on the
decomposition). `U_Φ` is `altPhaseSeq`, `⟨+| ⊗ M`, `|+⟩ ⊗ M` and `|0⟩⟨0| ⊗ V + |1⟩⟨1| ⊗ W` are
`plusBra`, `plusKet`, `ctrlSel`, with the ancilla qubit as the first tensor factor. The
hypothesis `1 ≤ n` is added: at `n = 0`, `P_ℜ ≡ c` with `c ≠ 1` satisfies the bullets, its
transformation is `cΠ`, while `Φ ∈ R^0` gives `U_Φ = I` and the right-hand side `Π`. -/
theorem corollary_18 {ι : Type*} [Fintype ι] [DecidableEq ι] (U Proj Projt : Matrix ι ι ℂ) (hU : U ∈ Matrix.unitaryGroup ι ℂ) (hProj : IsStarProjection Proj) (hProjt : IsStarProjection Projt) (n : ℕ) (hn : 1 ≤ n) (PR : ℝ[X]) (hdeg : PR.natDegree = n) (hpar : QAlgorithms.HasParity (PR.map Complex.ofRealHom) n) (hbd : ∀ x ∈ Set.Icc (-1 : ℝ) 1, |PR.eval x| ≤ 1) :
∃ Φ : Fin n → ℝ, ∀ S : ProjUnitarySVD U Proj Projt, (Odd n → svtOdd (fun x : ℝ => ((PR.eval x : ℝ) : ℂ)) S = plusBra Projt * ctrlSel (altPhaseSeq U Proj Projt Φ) (altPhaseSeq U Proj Projt (-Φ)) * plusKet Proj) ∧ (Even n → svtEven (fun x : ℝ => ((PR.eval x : ℝ) : ℂ)) S = plusBra Proj * ctrlSel (altPhaseSeq U Proj Projt Φ) (altPhaseSeq U Proj Projt (-Φ)) * plusKet Proj) := by sorry
end QSVT19.Main
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.