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=∑j cj Uj, where cj>0 and each unitary Uj can be implemented using Cj primitive queries. Given an upper bound a≥ |A|, our algorithm implements a block-encoding of A/α with rescaling factor α=𝒪(a), using 𝒪̃ (Cmax+C̅ λ/a ) primitive queries, where λ=∑j cj, Cmax=maxj Cj, and C̅= ∑j cj Cj/λ. By comparison, the standard LCU construction requires 𝒪̃ (Cmax λ/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 𝒪(K log(1/ε)) queries to the transducer, improving the precision dependence from polynomial to logarithmic.
Related
- Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization
- Exploiting all ancilla outcomes in linear combinations of unitaries: low-rank recovery and quantum trapdoor functions
- Optimal Linear Combination of Hamiltonian Simulation for Dissipative Dynamics
- Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity
- Optimal kernel functions for linear combination of Hamiltonian simulation
BibTeX
@misc{an2026transducerbased,
title = {{Transducer-based linear combination of unitaries: theory and applications}},
author = {Dong An and Dekuan Dong and Changpeng Shao and Yuxin Zhang and Chenhao Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40073},
eprint = {2609.40073},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40073},
}
RIS
TY - UNPB
TI - Transducer-based linear combination of unitaries: theory and applications
AU - Dong An
AU - Dekuan Dong
AU - Changpeng Shao
AU - Yuxin Zhang
AU - Chenhao Zhao
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40073
UR - https://arxiv.org/abs/2609.40073
AB - 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=∑_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≥ |A|, our algorithm implements a block-encoding of A/α with rescaling factor α=𝒪(a), using 𝒪̃ (C_max+C̅ λ/a ) primitive queries, where λ=∑_j c_j, C_max=max_j C_j, and C̅= ∑_j c_j C_j/λ. By comparison, the standard LCU construction requires 𝒪̃ (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 𝒪(K log(1/ε)) queries to the transducer, improving the precision dependence from polynomial to logarithmic.
ER -