Transducer-based linear combination of unitaries: theory and applications

Abstract:Linear combination of unitaries (LCU) is a fundamental primitive in quantum algorithms, whose cost is typically governed by the most expensive unitary appearing in the combination. We develop a transducer-based LCU framework that reduces this worst-case dependence to a weighted average query complexity, when the constituent unitaries share access to a common set of primitive oracles. Consider $A=\sum_j c_j U_j$, where $c_j>0$ and each unitary $U_j$ can be implemented using $C_j$ primitive queries. Given an upper bound $a\geq \|A\|$, our algorithm implements a block-encoding of $A/\alpha$ with rescaling factor $\alpha=\mathcal{O}(a)$, using $\widetilde{\mathcal{O}} (C_{\max}+\overline{C} {\lambda}/{a} )$ primitive queries, where $\lambda=\sum_j c_j$, $C_{\max}=\max_j C_j$, and $\overline{C}= {\sum_j c_j C_j}/{\lambda}$. By comparison, the standard LCU construction requires $\widetilde{\mathcal{O}} (C_{\max} {\lambda}/{a} )$ primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and $\lambda/a$ is large. As applications, we obtain improved block-encodings of sparse matrices, leading to quantum algorithms for sparse Hamiltonian simulation and quantum linear systems with near-optimal query complexity up to polylogarithmic factors in all relevant parameters. Our main technique is the transducer framework developed by Belovs, Jeffery, and Yolcu [Quantum, 8:1444 (2024)]. Here we develop a complementary operator-level theory tailored to block-encodings. We identify the resolvent norm $K$ as a key complexity measure for transducer implementation besides the existing catalyst complexity. We show that the transducer action can be converted into an $\epsilon$-approximate block-encoding using only $\mathcal{O}\left(K \log(1/\epsilon)\right)$ queries to the transducer, improving the precision dependence from polynomial to logarithmic.

arXiv:2609.40073 [quant-ph]

(or arXiv:2609.40073v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.40073 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.