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.
Sources
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
Andras Gilyen, Yuan Su, Guang Hao Low, Nathan Wiebe, 2019
Lean context
Copy a short prompt with the import, theorem name, citations, and public source link.