Exact and Efficient Circuit Construction for Block Encoding Matrix Polynomials
TL;DR
The resulting algorithm achieves a computational cost of $\mathcal{O}(d\log d)$ for explicitly constructing block encodings of matrix polynomials, improving upon the best-known theoretical bounds of previous methods.
Abstract
A recent interpolation-based Quantum Signal Processing (QSP) framework by Alase bypasses the phase-finding procedures required in conventional QSP, allowing for a direct encoding of the target polynomial into a quantum circuit. However, this approach assumes access to a diagonal block encoding of function values without providing an explicit circuit construction. In this work, we address this gap by developing an explicit circuit construction method for diagonal block encodings. The resulting algorithm achieves a computational cost of $\mathcal{O}(d\log d)$ for explicitly constructing block encodings of matrix polynomials, improving upon the best-known theoretical bounds of previous methods. Numerical results confirm this scaling, demonstrating that circuit parameters for polynomial degrees up to $10^7$ can be computed in about a minute on a standard CPU.