We propose the quasi Monte Carlo method for linear combination of unitaries via classical postprocessing (LCU-CPP) on quantum applications. The LCU-CPP framework has been proposed as an approach to reduce hardware resources, expressing a general target operator F ( A ) as F ( A ) = ∫ V f ( t ) G ( A , t ) d t , where each G ( A , t ) is proportional to a unitary operator. On a quantum device, Re [ Tr ( G ( A , t ) ρ ) ] can be estimated using the Hadamard test and then combined through classical integration, allowing for the realization of nonunitary functions with reduced circuit depth. While previous studies have employed the Monte Carlo method or the trapezoid rule to evaluate the integral in LCU-CPP, we show that the quasi Monte Carlo method can achieve even lower errors. In two numerical experiments, ground-state property estimation and Green’s function estimation, the quasi Monte Carlo method achieves the lowest errors with a number of Hadamard test shots per unitary that is practical for real hardware implementations. These results indicate that quasi Monte Carlo is an effective integration strategy within the LCU-CPP framework.
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.
Numerical integration with Monte Carlo methods is a central computational task in many scientific and industrial applications, including financial derivative pricing and risk management. Classical Monte Carlo algorithms are computationally demanding: achieving an accuracy
ε typically requires a number of function evaluations scaling as
O(1/ε2). Quantum-accelerated Monte Carlo methods based on quantum amplitude estimation can in principle quadratically improve this dependence. However, \textit{quasi}-Monte Carlo methods have not been explored in the quantum context. In this work, we introduce a quantum quasi-Monte Carlo algorithm that combines low-discrepancy nets with quantum amplitude estimation. The proposed method prepares the quasi-random point set coherently in superposition. The method does not yield an asymptotic improvement over classical quasi-Monte Carlo, since the total error separates into a discretization error, determined by the finite net, and a quantum estimation error. Instead, we explore a pre-asymptotic advantage window: for a target accuracy that would classically require
2q low discrepancy points, one can prepare a higher-resolution net of size
2Q, with
Q>q, in superposition and reach the same accuracy using significantly fewer function queries. This window can be controlled by tuning the circuit resolution and amplitude-estimation parameters, making the approach relevant for practical regimes where the number of queries is finite rather than asymptotically large.
We present near-term quantum algorithms for auxiliary-field quantum Monte Carlo (AFQMC), viewed as imaginary-time projection for ground-state calculation as an ensemble of one-body propagators driven by stochastic fields
Ω. Starting from the Feynman-Kac formula, we convert each trajectory into a sequence of piecewise-constant one-body generators using stochastic Magnus expansions up to second order, and embed the resulting nonunitary slices into unitaries with a small ancilla overhead. This lifts the projector dynamics to a unitary evolution, enabling coherent circuit execution in the regime
∥Ω∥τ=O(1) and reducing the need for frequent mid-circuit measurement. We further derive an equivalent linear-combination-of-unitaries (LCU) form that yields system-only, shallower circuits by trading ancilla cost for additional trajectory sampling. Benchmarks on the Hubbard model verify the accuracy of the dilation and Magnus expansions classically and demonstrate multi-step executions on IBM 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.
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.
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.