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.
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.
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.
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.
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UA and the right-hand side through a state-preparation oracle Ub. The optimal query complexities of these two oracles are known separately: O(κlog(1/ε)) queries to UA and O(κ/s) queries to Ub, where s=α∥A−1b∥. Whether a single algorithm can achieve both bounds simultaneously has remained open.
We resolve this question affirmatively. Given a constant-factor estimate of s, we give a quantum linear-system algorithm that prepares the normalized solution to error ε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UA and O(κ/s) queries to Ub. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy.
We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both Ω(κlog(1/ε)) matrix queries and Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
Quantum algorithms based on Quantum Signal Processing (QSP) offer the potential for speedups across a broad range of applications, with block encodings serving as the central input model. In this framework, non-unitary matrices are embedded into larger unitary operators, and the cost of constructing these encodings often dominates the overall gate complexity. In this work, we introduce Tag-and-Restore Encoding (TARE), a block-encoding method for linear combinations of Pauli strings. In this method coefficient magnitudes are absorbed into a unitary built from a set of mutually anti-commuting Pauli strings acting on the system register. These Pauli strings are then mapped to the target Pauli strings through appropriate transformations, yielding a block encoding of the target operator. The ancilla register size scales logarithmically with the number of Pauli strings and can be extended to larger registers providing a width/depth tradeoff. We evaluate TARE through numerical simulations of the transverse-field Ising model, the Jordan-Wigner image of a fermionic star Hamiltonian, and random Pauli-string operators. Compared with standard Linear Combination of Unitaries (LCU), TARE substantially reduces the T-gate count while improving circuit depth in several cases. These results suggest that TARE can provide resource-efficient block encodings for a wide range of relevant systems.