Abstract Simulating time evolution under quantum Hamiltonians is one of the most natural applications of quantum computers. We introduce TE-PAI, which simulates time evolution exactly by sampling random quantum circuits for the purpose of estimating observable expectation values at the cost of an increased circuit repetition. The approach builds on the Probabilistic Angle Interpolation (PAI) technique and we prove that it simulates time evolution without discretisation or algorithmic error while achieving shallow circuit depths with optimal scaling that saturates the Lieb–Robinson bound. Another significant advantage of TE-PAI is that it only requires executing random circuits that consist of Pauli rotation gates of only two kinds of rotation angles ± Δ and π , along with measurements. While TE-PAI is highly beneficial for NISQ devices, we additionally develop an optimised early fault-tolerant implementation using catalyst circuits and repeat-until-success teleportation, concluding that the approach requires orders of magnitude fewer T-states than conventional techniques, such as Trotterization—we estimate 3 × 10 5 T states are sufficient for the fault-tolerant simulation of a 100-qubit Heisenberg spin Hamiltonian. Furthermore, TE-PAI allows for a highly configurable trade-off between circuit depth and measurement overhead by adjusting the rotation angle Δ arbitrarily. We expect that the approach will be a major enabler in the late NISQ and early fault-tolerant periods as it can compensate circuit-depth and qubit-number limitations through an increased circuit repetition.
Abstract Simulating time evolution under quantum Hamiltonians is one of the most natural applications of quantum computers. We introduce TE-PAI, which simulates time evolution exactly by sampling random quantum circuits for the purpose of estimating observable expectation values at the cost of an increased circuit repetition. The approach builds on the Probabilistic Angle Interpolation (PAI) technique and we prove that it simulates time evolution without discretisation or algorithmic error while achieving shallow circuit depths with optimal scaling that saturates the Lieb–Robinson bound. Another significant advantage of TE-PAI is that it only requires executing random circuits that consist of Pauli rotation gates of only two kinds of rotation angles ± Δ and π , along with measurements. While TE-PAI is highly beneficial for NISQ devices, we additionally develop an optimised early fault-tolerant implementation using catalyst circuits and repeat-until-success teleportation, concluding that the approach requires orders of magnitude fewer T-states than conventional techniques, such as Trotterization—we estimate 3 × 10 5 T states are sufficient for the fault-tolerant simulation of a 100-qubit Heisenberg spin Hamiltonian. Furthermore, TE-PAI allows for a highly configurable trade-off between circuit depth and measurement overhead by adjusting the rotation angle Δ arbitrarily. We expect that the approach will be a major enabler in the late NISQ and early fault-tolerant periods as it can compensate circuit-depth and qubit-number limitations through an increased circuit repetition.
Quantum computing requires a universal set of gate operations; regarding gates as rotations, any rotation angle must be possible. However a real device may only be capable of B bits of resolution, i.e., it might support only 2^{B} possible variants of a given physical gate. Naive discretization of an algorithm's gates to the nearest available options causes coherent errors, while decomposing an impermissible gate into several allowed operations increases circuit depth. Conversely, demanding higher B can greatly complexify hardware. Here, we explore an alternative: probabilistic angle interpolation (PAI). This effectively implements any desired, continuously parametrized rotation by randomly choosing one of three discretized gate settings and postprocessing individual circuit outputs. The approach is particularly relevant for near-term applications where one would in any case average over many runs of circuit executions to estimate expected values. While PAI increases that sampling cost, we prove that (a) the approach is optimal in the sense that PAI achieves the least possible overhead and (b) the overhead is remarkably modest even with thousands of parametrized gates and only seven bits of resolution available. This is a profound relaxation of engineering requirements for first generation quantum computers where even 5-6 bits of resolution may suffice and, as we demonstrate, the approach is many orders of magnitude more efficient than prior techniques. Moreover we conclude that, even for more mature late noisy intermediate-scale quantum era hardware, no more than nine bits will be necessary.
Estimating the energy spectra of quantum many-body systems is a fundamental task in quantum physics, with applications ranging from chemistry to condensed matter. Algorithmic shadow spectroscopy is a recent method that leverages randomized measurements on time-evolved quantum states to extract spectral information. However, implementing accurate time evolution with low-depth circuits remains a key challenge for near-term quantum hardware. In this work, we propose a hybrid quantum-classical protocol that integrates Time Evolution via Probabilistic Angle Interpolation (TE-PAI) into the shadow spectroscopy framework. TE-PAI enables the simulation of time evolution using shallow stochastic circuits while preserving unbiased estimates through quasiprobability sampling. We construct the combined estimator and derive its theoretical properties. Through numerical simulations, we demonstrate that our method accurately resolves energy gaps and exhibits enhanced robustness to gate noise compared to first-order Trotter-based shadow spectroscopy. We further validate the protocol experimentally on up to 20 qubits using IBM quantum hardware. This makes TE-PAI shadow spectroscopy a promising tool for spectral analysis on noisy intermediate-scale quantum (NISQ) devices.
Tensor-network simulations of quantum many-body dynamics are fundamentally limited by entanglement build-up, which leads to exponentially growing computational costs. Furthermore, these classical simulation algorithms are inherently sequential as typically a tensor network representation of the quantum state is updated incrementally at each time step. We build on recently introduced randomized quantum algorithms for time evolution (TE-PAI), and adapt them to the classical simulation context with the purpose of enabling massive parallelisation. Our MPS TE-PAI approach achieves exact time evolution on average (unbiased estimator) and proceeds by representing an ensemble of randomized shallow Trotter-variant circuits as tensor networks. As each circuit instance yields a deterministic quantum state (or observable expecation value), the only source of randomness is the sampling of circuit variants; the absence of shot noise therefore yields a reduced estimator variance relative to quantum hardware implementations of TE-PAI. We simulate representative disordered one-dimensional spin-ring Hamiltonians, and numerically observe reductions in the per-sample gate-count by a factor of up to 103 relative to Trotterized MPS evolution, yielding orders of magnitude reduction in the time-to-solution under realistic levels of parallelisation. Finally, we numerically observe that MPS TE-PAI is substantially more robust against severe bond-dimension truncation than product formulas, potentially making it useful for the simulation of strongly correlated systems where truncation is necessary in practice. We also demonstrate that the approach can be used naturally in combination with existing time evolution algorithms, effectively extending their time depth via parallelisation.
Standard variational quantum simulation seeks to reproduce the evolution of the full quantum state, although many applications require only the expectation values of a few observables. We study a variational method for pure-state Hamiltonian dynamics that updates circuit parameters to reproduce the evolution of selected expectation values. An exact error identity guides the choice of observables, motivating a construction based on repeated commutators of the target with the Hamiltonian. For Pauli observables and Pauli-rotation circuits, the update can be estimated without ancillary qubits or controlled operations for overlap estimation. Across six- and ten-qubit spin, fermionic, and molecular benchmarks, the observable-targeted update extends the median time within the target-error tolerance compared with standard variational quantum simulation with equal shot budgets. These results show that directing the variational update toward the target observable can extend accurate simulation without increasing the measurement cost per time step.
The classical simulation of universal quantum circuits is crucial both fundamentally and practically for quantum computation. We propose SyQMA, a simulator with several convenient features, particularly suited for quantum error correction (QEC). SyQMA simulates universal quantum circuits with incoherent Pauli noise and computes exact expectation values and measurement probabilities as symbolic functions of circuit parameters: rotation angles, measurement outcomes, and noise rates. This simulator can sample measurement outcomes, enabling the simulation of dynamic quantum programs where circuit composition depends on prior measurement outputs. For QEC, it performs circuit-level maximum-likelihood decoding, provides exact symbolic expressions for logical error rates, and verifies the fault distance of fault-tolerant (FT) stabiliser and magic state preparation protocols. These features are enabled by an intuitive extension of stabiliser simulators, where each non-Clifford Pauli rotation and incoherent Pauli channel is compactly represented via auxiliary qubits and a modified trace. Representing the state requires only polynomial memory and time, while computing expectation values and measurement probabilities takes exponential time in the number of non-Clifford rotations and deterministic measurements, but only polynomial memory. The FT preparation of stabiliser and magic states, including the first stage of magic state cultivation, is analysed without approximations. We also exactly convert the disjoint error probabilities of a general multi-qubit Pauli channel to independent ones, a key step for creating and sampling from detector error models. The code is publicly available and open-source.
Computing the ground-state properties of quantum many-body systems is a promising application of near-term quantum hardware with a potential impact in many fields. The conventional algorithm quantum phase estimation uses deep circuits and requires fault-tolerant technologies. Many quantum simulation algorithms developed recently work in an inexact and variational manner to exploit shallow circuits. In this work, we combine quantum Monte Carlo with quantum computing and propose an algorithm for simulating the imaginary-time evolution and solving the ground-state problem. By sampling the real-time evolution operator with a random evolution time according to a modified Cauchy-Lorentz distribution, we can compute the expected value of an observable in imaginary-time evolution. Our algorithm approaches the exact solution given a circuit depth increasing polylogarithmically with the desired accuracy. Compared with quantum phase estimation, the Trotter step number, i.e. the circuit depth, can be thousands of times smaller to achieve the same accuracy in the ground-state energy. We verify the resilience to Trotterisation errors caused by the finite circuit depth in the numerical simulation of various models. The results show that Monte Carlo quantum simulation is promising even without a fully fault-tolerant quantum computer.