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.
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.
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.
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 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 introduce random-LCHS, a circuit-efficient randomized-compilation framework for simulating linear non-unitary dynamics of the form
∂tu(t)=−A(t)u(t)+b(t) built on the linear combination of Hamiltonian simulation (LCHS). We propose three related settings: the general random-LCHS for time-dependent inhomogeneous linear dynamics; the observable-driven random-LCHS, which targets estimation of an observable's expectation at the final time; and the symmetric random-LCHS, a time-independent, homogeneous reduction that can exploit physical symmetries. Our contributions are threefold: first, by randomizing the outer linear-combination-of-unitaries (LCU) layer as well as the deterministic inner Hamiltonian simulation layer, random-LCHS attains favorable resource overheads in the circuit design for early fault-tolerant devices; second, the observable-driven variant employs an unbiased Monte-Carlo estimator to target expectation values directly, reducing sample complexity; and third, integrating the physical symmetry in the model with the sampling scheme yields further empirical improvements, demonstrating tighter error bounds in realistic numerics. We illustrate these techniques with theoretical guarantees as well as numerical verifications and discuss implementation trade-offs for near-term quantum hardware.
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.