We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method ( Single-Ancilla LCU ) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach ( Analog LCU ) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method ( Ancilla-free LCU ) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.
We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method ( Single-Ancilla LCU ) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach ( Analog LCU ) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method ( Ancilla-free LCU ) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.
The randomized linear combination of unitaries (LCU) method with many applications to early fault-tolerant quantum computing algorithms has been proposed. This quantum algorithm computes the same expectation values as the original, fully coherent LCU algorithm using a shallower quantum circuit with a single ancilla qubit, at the cost of a quadratically larger sampling overhead. In this work, we propose a quantum algorithm intermediate between the original and randomized LCU that manages the trade-off between the sampling overhead and circuit complexity. Our algorithm divides the set of unitary operators into several groups and then randomly samples LCU circuits from these groups to evaluate the target expectation value. Notably, we reveal that across all grouping strategies, the mechanism of the sampling overhead reduction can be solely characterized by a metric we call the reduction factor. Moreover, we analytically prove an underlying monotonicity of the reduction factor in the group size: larger group sizes entail smaller sampling overhead. Finally, our framework enables a more flexible algorithmic design by systematically yielding intermediate implementations of LCU-based algorithms; we provide intermediate implementations of non-Hermitian dynamics simulation, ground-state property estimation, and quantum error detection. Besides, we demonstrate this principle by deriving intermediate trade-off scaling in sample complexity and ancillary space for quantum linear system solver.
Randomisation is widely used in quantum algorithms to reduce the number of quantum gates and ancillary qubits required. A range of randomised algorithms, including eigenstate property estimation by spectral filters, Hamiltonian simulation, and perturbative quantum simulation, though motivated and designed for different applications, share common features in the use of unitary decomposition and Hadamard-test-based implementation. In this work, we start by analysing the role of randomised linear-combination-of-unitaries (LCU) in quantum simulations, and present several quantum circuits that realise the randomised composite LCU. A caveat of randomisation, however, is that the resulting state cannot be deterministically prepared, which often takes an unphysical form UρV† with unitaries U and V. Therefore, randomised LCU algorithms are typically restricted to only estimating the expectation value of a single Pauli operator. To address this, we introduce a quantum instrument that can realise a non-completely-positive map, whose feature of frequent measurement and reset on the ancilla makes it particularly suitable in the fault-tolerant regime. We then show how to construct an unbiased estimator of the effective (unphysical) state UρV† and its generalisation. Moreover, we demonstrate how to effectively realise the state prepared by applying an operator that admits a composite LCU form. Our results reveal a natural connection between randomised LCU algorithms and shadow tomography, thereby allowing simultaneous estimation of many observables efficiently. As a concrete example, we construct the estimators and present the simulation complexity for three use cases of randomised LCU in Hamiltonian simulation and eigenstate preparation tasks.
Estimating the expectation value of an observable O for a quantum state evolved under a general, possibly non-unitary, operator A is a fundamental task in quantum simulation, chemistry, and variational algorithms. Existing linear-combination-of-unitaries (LCU) approaches implement A on hardware, requiring ancilla qubits, controlled unitaries and, in randomized variants, fresh circuit executions for every Monte Carlo sample. These costs are prohibitive on NISQ and early fault-tolerant devices. We propose HERMES (Hardware-Efficient Reusable Measurements for Estimating LCU-based expectation valueS), which moves the processing of A entirely to the classical domain. Expanding A and O in the Pauli basis and sampling pairs of Pauli terms classically, HERMES rewrites μ=Tr(OAρA†)/Tr(AρA†) as a ratio of weighted sums of Pauli expectation values on the unmodified state ρ, with no ancillas, controlled unitaries, or quantum implementation of A. A two-level measurement reduction scheme (Pauli deduplication and commuting-group partitioning) bounds the number of distinct measurement settings independently of the sample count, unlike randomized LCU methods whose circuit executions grow linearly with it. On ground-state energy estimation of H2 and LiH via imaginary-time evolution, HERMES matches or beats Pauli single-ancilla LCU baseline using shallow circuits with no two-qubit gates beyond state preparation under qubit-wise commuting grouping. It is also more robust to noise and completes a noisy LiH simulation infeasible for the baseline, at the cost of classical overhead growing with the number of Pauli terms in A.
The linear combination of unitaries (LCU) is a fundamental quantum computing primitive used to embed non-unitary operators into larger systems via ancilla post-selection. In standard LCU implementations, only the zero-state ancilla outcome is retained, while all other measurement branches are discarded as unusable overhead. We study these discarded parts. Every computational-basis outcome of the ancilla projects the system onto a different linear combination of the target unitaries; collecting these outcome states in a matrix gives a factorization Φ=CX, where C is determined by the ancilla preparation and the rows of X are the states Ut∣ψ⟩, so that rank(Φ)≤K. Although this holds for any LCU circuit; to make the analysis easier, we use a simplified model circuit with Hadamard gates on the index register and a single rotation qubit in place of the coefficient preparation unitary, in which C is explicit. The structure suggests two complementary applications: (i) in an explicit amplitude-access model, classical low-rank matrix completion can reconstruct the full output (including the target) from a subset of its amplitude entries, while computational basis counts provide intensities and generally require additional phase information for full complex recovery; (ii) treating C as a secret key suggests a candidate quantum trapdoor function, whose security remains informal and depends on the difficulty of structured phase retrieval. The scheme thus turns the "junk" ancilla outcomes into a structured resource, possibly opening paths for further applications.
We investigate ancilla-free linear combination of unitaries (LCU) as a framework for approximating complex quantum circuits. This is particularly effective for quantum optimization algorithms, where candidate solutions can be evaluated classically and the task is to sample high-quality bitstrings rather than reproduce the full output distribution. We show that Fourier-based LCU constructions efficiently decompose broad classes of diagonal and non-diagonal unitaries, replacing highly connected qubit interactions with single-qubit gate layers or significantly simpler structures at the cost of a polynomial sampling overhead. Applied to algorithms such as QAOA, this yields efficient, hardware-friendly decompositions of, for instance, cardinality-constraint penalties and the fully connected XY-mixer, while maintaining rigorous performance guarantees compared to fully coherent implementations. Furthermore, we establish a formal connection between Fourier-based quantum penalties and Lagrangian relaxation, offering a unified perspective on constraint handling. We validate our approach using exact statevector simulations of 12-qubit circuits and large-scale experiments on 106 superconducting qubits. Our results illustrate how approximate sampling via an LCU systematically trades circuit complexity for sampling overhead, extending the practical reach of near-term quantum optimization.
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.