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.
Quantum simulation, the simulation of quantum processes on quantum computers, suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry, and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling on the one hand and higher-order multi-product formulas, as they are used for example in linear-combination-of-unitaries (LCU) algorithms or quantum error mitigation, on the other hand. In doing so, we propose a framework of randomized sampling that is expected to be useful for programmable quantum simulators and present two new multi-product formula algorithms tailored to it. Our framework reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by the implementation of multi-product formulas using standard LCU methods, rendering it especially useful for early quantum computers used to estimate the dynamics of quantum systems instead of performing full-fledged quantum phase estimation. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We demonstrate the functioning of the approach for several physically meaningful examples of Hamiltonians, including fermionic systems and the Sachdev–Ye–Kitaev model, for which the method provides a favorable scaling in the effort.
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.
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.
Quantum simulation suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry and materials science. While the majority of quantum simulation algorithms is deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling and higher-order multi-product formulas as they are used in linear-combination-of-unitaries (LCU) algorithms. In doing so, we propose a framework of randomized sampling that could prove useful for programmable quantum simulators and present two new algorithms tailored to it. Our framework greatly reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by standard LCU methods, rendering it especially useful for near-term quantum computing. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We also discuss examples at hand of a Hamiltonian comprising pairwise anticommuting terms.