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.
AI Summary
The paper asks whether coherent linear combination of unitaries (LCU) can exploit differing constituent costs rather than repeatedly paying the maximum cost. For $A=\sum_j c_jU_j$, define $\lambda=\sum_jc_j$, $C_{\max}=\max_jC_j$, and $\overline C=\sum_jc_jC_j/\lambda$. Given $a\geq\|A\|$, it constructs an $\mathcal O(a)$-normalized block-encoding with error $\mathcal O(\epsilon)$ using $\mathcal O(C_{\max}\log(1/\epsilon)+(\lambda/a)\overline C\log^2(1/\epsilon))$ primitive queries, versus $\widetilde{\mathcal O}(C_{\max}\lambda/a)$ for standard LCU with normalization amplification. The construction also accommodates block-encoded matrices.
The method encodes constituent circuit histories into transducers, combines them into a transducer for a Cayley transform, and represents inverse-Cayley transformation and amplification through a QSVT transducer. An operator-level composition analysis controls the private-block resolvent norm $K=\|(I-T)^{-1}\|$. An extrapolation-based finite-reuse procedure then converts the public action into a block-encoding using $\mathcal O(K\log(1/\epsilon))$ transducer queries, without preparing the catalyst.
Magnitude-binned sparse-matrix decompositions yield constant-normalization block-encodings using $\widetilde{\mathcal O}(\sqrt d)$ sparse-oracle queries. Applications give $\widetilde{\mathcal O}(\sqrt d\,T)$ Hamiltonian simulation and $\widetilde{\mathcal O}(\sqrt d\,\kappa)$ linear-system solving, with polylogarithmic precision dependence.
The bounds count queries, excluding coefficient preparation and oracle-free gates. They require known circuit descriptions, coherently selectable shared primitives, and a known norm bound; savings require nonuniform costs and substantial normalization reduction. High-precision conversion requires a controlled resolvent norm, which can exceed catalyst complexity. The paper notes weaker general norm dependence than prior simulation work and concurrent sparse-block-encoding and linear-system results that remove its extra polylogarithmic overheads.
Little sign of AI-generated textAI use disclosed
The authors wrote the initial manuscript, and used the LLM to refine the presentation of selected sections.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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=∑jcjUj, 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 α=O(a), using O(Cmax+Cλ/a) primitive queries, where λ=∑jcj, Cmax=maxjCj, and C=∑jcjCj/λ. By comparison, the standard LCU construction requires O(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 O(Klog(1/ε)) queries to the transducer, improving the precision dependence from polynomial to logarithmic.
The paper asks whether coherent linear combination of unitaries (LCU) can exploit differing constituent costs rather than repeatedly paying the maximum cost. For A=∑jcjUj, define λ=∑jcj, Cmax=maxjCj, and C=∑jcjCj/λ. Given a≥∥A∥, it constructs an O(a)-normalized block-encoding with error O(ϵ) using O(Cmaxlog(1/ϵ)+(λ/a)Clog2(1/ϵ)) primitive queries, versus O(Cmaxλ/a) for standard LCU with normalization amplification. The construction also accommodates block-encoded matrices.
The method encodes constituent circuit histories into transducers, combines them into a transducer for a Cayley transform, and represents inverse-Cayley transformation and amplification through a QSVT transducer. An operator-level composition analysis controls the private-block resolvent norm K=∥(I−T)−1∥. An extrapolation-based finite-reuse procedure then converts the public action into a block-encoding using O(Klog(1/ϵ)) transducer queries, without preparing the catalyst.
Magnitude-binned sparse-matrix decompositions yield constant-normalization block-encodings using O(d) sparse-oracle queries. Applications give O(dT) Hamiltonian simulation and O(dκ) linear-system solving, with polylogarithmic precision dependence.
The bounds count queries, excluding coefficient preparation and oracle-free gates. They require known circuit descriptions, coherently selectable shared primitives, and a known norm bound; savings require nonuniform costs and substantial normalization reduction. High-precision conversion requires a controlled resolvent norm, which can exceed catalyst complexity. The paper notes weaker general norm dependence than prior simulation work and concurrent sparse-block-encoding and linear-system results that remove its extra polylogarithmic overheads.
Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state using a catalyst, an auxiliary vector that is left unchanged. They are a powerful tool in quantum algorithm design, especially in the context of quantum query complexity: feasible points of the (dual) adversary semidefinite program directly translate into transducers and the optimal transduction complexity is equal to the adversary bound, i.e. the Las Vegas complexity, which is known to characterize bounded-error quantum query complexity. Moreover, contrary to bounded-error algorithms, transducers compose exactly, which limits overheads due to controlling errors in algorithms constructed by composition. Constructing efficient, let alone optimal, transducers in terms of quantum query complexity nevertheless remains a hard task since it still requires solving the adversary SDP and constructing the unitary to obtain an explicit algorithm. In this paper, we show how using the symmetry group of state-conversion problems simplifies both steps. First, using a symmetrization argument, we prove an optimal catalyst can always be chosen covariant under a representation of the symmetry group. Second, we prove that the transducer intertwines two different representations of the group and can thus be chosen block diagonal in the isotypic decomposition of the Hilbert space. Using those methods, we then derive optimal transducers, with optimal constants, for different widely used quantum algorithmic primitives, such as unstructured search, amplitude amplification and amplitude estimation. Our approach extends previous work on the use of representation theory to compute adversary lower bounds (Høyer, Lee, and {\v S}palek, 2007; Ambainis, Magnin, Roetteler and Roland, 2011) to the systematic construction of optimal algorithms.
For the problem of simulating Lindblad evolution for time t to precision ε, Hamiltonian simulation provides an additive query lower bound, informally, Ω(t+polylog(1/ε)). However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, O(tpolylog(1/ε)), in query complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. We further achieve nearly optimal gate complexity in evolution time and precision through history compression and an efficient implementation of the query-free part of the transducer using operation reordering and linear combinations of unitaries, while preserving the optimal query complexity.
Linear combination of Hamiltonian simulation (LCHS) provides an asymptotically optimal framework for the quantum simulation of linear non-unitary dynamics. The LCHS approach approximately implements the Peano--Baker propagator through an integral representation determined by a kernel function. We establish an LCHS approximation theorem for a broadened class of admissible kernel functions, defined by natural complex-analytic conditions. In the standard time-independent block-encoding access model, we explicitly construct, for each target error ε, the unique kernel function in this class minimizing the query-cost functional and show that the minimum of this functional has the asymptotic expansion π2e(logε1−loglogε1+o(1)) as ε↓0. The provably optimal leading coefficient 2e/π improves by a factor of approximately 2.1 on the coefficient obtained empirically by Low and Somma through numerical minimization over their family of optimally scaling kernel functions. We construct a spectrally convergent quadrature with explicit bounds on operator error and linear combination of unitaries (LCU) subnormalization, proving that this asymptotic improvement persists after discretization into a finite linear combination of unitaries suitable for implementation. Our results are based on Hardy space theory and convex analysis.
We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under H=∑jHj with weighted quasinorm cost ≈t⟨λ,C⟩1/2+O(∥C∥1log(1/ε)) for block-encoding normalizations λ and costs C; (2) sparse simulation with optimal time--norm Θ(d∥H∥1→2t) and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost t⟨λeff,Ceff⟩1/2 further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.
To process a problem with a Quantum Processing Unit (QPU), it must be transformed into a sequence of quantum operators, or gates. These operators are either packed into a query (i.e. quantum algorithm primitive) that encodes the problem, or used to construct the cost function for Variationnal Quantum Algorithm (VQA). Typical queries are the problem Hamiltonian Simulation (HS) and the problem Block-Encoding (BEing). To construct the circuits associated with the quantum description, the problem must be mapped as a Linear Combination of Hamiltonian (LCH) or a Linear Combination of nitaries (LCU) matrices. All the summed Hamiltonian matrices or unitary matrices must have a known decomposition in basic gates. The complexity of this query should be incorporated into the quantum algorithm's query complexity, thereby limiting the processing possibilities of QPU for many problems. In this work, we propose Hamiltonian matrices used to map the problem of interest, and that behave like a single qubit when expressed in the appropriate basis. It leads to a framework, the Special Tripotent Hamiltonian (STH) Framework, able to implement most of the typical problems considered for quantum computing. These methods address many problems implemented on QPUs, ranging from second-quantization chemistry operators to graphs associated with Partial Differential Equations (PDE), sparse matrices, and higher-order optimization problems. This work underlines interesting properties associated with the STH basic gate decomposition. These include the ability to switch between LCH and LCU, map non-Hermitian problems, and construct the quantum circuit queries required for quantum computing. We also provide a list of STH that are used for the matrix decomposition of many structured matrices. These structured matrices are associated with graph adjacency matrices that can be combined to implement structured matrices.
We present a novel framework for Linear Combination of Unitaries (LCU)-style decomposition tailored to structured sparse matrices, which frequently arise in the numerical solution of partial differential equations (PDEs). While LCU is a foundational primitive in both variational and fault-tolerant quantum algorithms, conventional approaches based on the Pauli basis can require a number of terms that scales quadratically with matrix size. We introduce the Sigma basis, a compact set of simple, non-unitary operators that can better capture sparsity and structure, enabling decompositions with only polylogarithmic scaling in the number of terms. We develop both numerical and semi-analytical methods for computing Sigma basis decompositions of arbitrary matrices. Given this new basis is comprised of non-unitary operators, we leverage the concept of unitary completion to design efficient quantum circuits for evaluating observables in variational quantum algorithms and for constructing block encodings in fault-tolerant quantum algorithms. We compare our method to related techniques like unitary dilation, and demonstrate its effectiveness through several PDE examples, showing exponential improvements in decomposition size while retaining circuit efficiency.