Pauli coefficients and -Pauli-sparse operators
DefinitionFRouting_Supplement_PauliSparsef-routingp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-position-verification
Let . Every operator on qubits expands as
is -Pauli-sparse if its Pauli spectrum has support size at most :
This is the resource restriction of §7; Theorem 7.10 applies it to the unitaries of quantum circuits.
Formalization Note The Pauli strings and coefficients are the published UnitalMIP.pauliString and UnitalMIP.pauliCoeff, whose labels give (that is ) and whose coefficient is , as Pauli strings are Hermitian. The definition is stated for any operator on qubits; unitarity comes from where it is applied.
Definition code
import Definitions.Def_UnitalMIP_pauliString
set_option autoImplicit false
open Matrix
namespace FRouting.Supplement
open scoped Classical in
/-- **`(q, s)`-Pauli-sparse.** Renard, *Computational Bounds for f-Routing*, arXiv:2609.40278 (held
copy, sha256 4a327f29…), Definition 7.1, p.31: "A unitary U is (q, s)-Pauli-sparse if U acts on q qubits
and its Pauli spectrum has support size at most s, namely |Supp(Û)| ≤ s", where (p.31)
`U = ∑_{P ∈ Pauli_q} Û(P) P` with `Û(P) = 2^{-q} tr(UP)`.
**Formalization Note** The Pauli strings and coefficients are the published `UnitalMIP.pauliString` and
`UnitalMIP.pauliCoeff`: labels `(a, b) ∈ 𝔽₂²` give `i^{ab} X^a Z^b`, i.e. `I, X, Z, Y`, and
`pauliCoeff U α = 2^{-q} tr(P_α† U) = 2^{-q} tr(U P_α)` since Pauli strings are Hermitian, so the support
is the paper's. `q` is the index type `Fin q → Fin 2`; unitarity comes from where the notion is applied. -/
def IsPauliSparse {q : ℕ} (U : Matrix (Fin q → Fin 2) (Fin q → Fin 2) ℂ) (s : ℕ) : Prop :=
(Finset.univ.filter fun α : Fin q → Fin 2 × Fin 2 => UnitalMIP.pauliCoeff U α ≠ 0).card ≤ s
end FRouting.Supplement
Source
Renard, Computational Bounds for f-Routing, arXiv:2609.40278 (held copy, sha256 4a327f29…), §7.1 and Definition 7.1, p.31