Signal transformation ยท Primitives

Polynomial transformation on block encodings (Hermitian)

Theorem statement

Let $m,n,L\geq0$ be integers, $P=\sum_{j=0}^{L}c_jx^j$ be a degree-$L$ complex polynomial such that $|P(x)|\leq1$ for every $x\in[-1,1]$, and $U$ be a $(1,m,0)$-block-encoding of an $n$-qubit Hermitian matrix $A$. Given access to $U$, $U^\dagger$ and controlled-$U$, there exists a quantum circuit $\mathcal V$ that implements a $(4,m',0)$-block-encoding of $P(A)=\sum_{j=0}^{L}c_jA^j$ for $m\leq m'\leq m+3$, using at most 3 ancilla qubits, $L$ queries to $U$ and $U^\dagger$, 1 query to controlled-$U$, $((192m+6)L+6)$ CNOT gates, and $((296m+6)L+13)$ single-qubit gates.
$P$
Polynomial applied to the encoded Hermitian matrix.

Copy a short prompt with the import, theorem name, citations, and public source link.

Open Lean source