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.
The minimal sampling overhead of the quadratic collective phase
e−iγK2 over one layer of single-qubit rotations is decided by the continued fraction of
γ/π. Here
K is a collective observable with spectrum
{0,…,n}, such as the permutation-symmetric Hamming weight. This gate is the cardinality-penalty layer of constrained optimization, the one-axis-twisting gate of spin squeezing and the Kerr phase of a bosonic mode. Instead of compiling it to two-qubit gates, we sample it as an LCU over such layers at overhead
Γ. Our results give an optimality theory for this overhead. Ancilla-free sampling reproduces the target's outcome probabilities up to the minimal
Γ, and no smaller factor works for every input; for permutation-symmetric
K, independent per-qubit angles or one layer of arbitrary single-qubit gates give no further reduction. Rational angles
πp/q in lowest terms cost exactly
q once
n≥2q−2, attained uniquely by a uniform
q-point sampler; the cost is
Θ(n) if and only if
γ/π is badly approximable, and bounded in
n if and only if it is rational. A second result shows what the symmetry buys: without it, the squaring phase of Fourier arithmetic on
m qubits costs at least
20.557m−O(1) over single-qubit gates, beyond the
2m/2 of every cut bound, by a new certificate-lifting argument. For constructions known only through upper bounds, it gives the optimum: the Fourier-based LCU of Carrera Vazquez, Egger and Woerner is, at fixed
n, optimal up to a constant at typical angles and beaten by
(n+1)/q at rational ones with an
n-independent sampler; the Kerr decomposition of Upreti, Quesada and Chabaud is the unique optimum over phase shifters at rational parameters without photon-number cutoff; and it identifies the rational couplings where one-axis twisting admits optimal cat decompositions.
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.
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.