arXiv preprint ·
Transducer-based linear combination of unitaries: theory and applications
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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/α$ with rescaling factor $α=\mathcal{O}(a)$, using $\widetilde{\mathcal{O}} (C_{\max}+\overline{C} λ/{a} )$ primitive queries, where $λ=\sum_j c_j$, $C_{\max}=\max_j C_j$, and $\overline{C}= {\sum_j c_j C_j}/λ$. By comparison, the standard LCU construction requires $\widetilde{\mathcal{O}} (C_{\max} λ/{a} )$ primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and $λ/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 $ε$-approximate block-encoding using only $\mathcal{O}\left(K \log(1/ε)\right)$ queries to the transducer, improving the precision dependence from polynomial to logarithmic.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Exponential separation in sensing continuous signals via squeezing
Complexity study of the Hartle-Hawking state in JT gravity
Polarisation-resolved identification of spontaneous four-wave mixing processes in a multimode fused tapered fibre coupler
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
A Separation Between Types of Quantum Oracle Separations
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.