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.
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.
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.
Clifford+T synthesis of rotation gates is an important routine in fault-tolerant quantum compilation. While Clifford+T synthesis is scalable, it has a high overhead of tens of T gates per rotation in practice, translating to high resource estimates for many fault-tolerant algorithms. However, these well-known results, including those using probabilistic mixtures [Quantum 7, 1208 (2023)], are independent of the rotation angle θ, requiring O(log1/δ) T gates. We show that it is possible to do much better for small angles, reducing the T cost to O~(θ2/δ), and returning to existing O(log1/δ) results in the worst case. This is particularly important since many algorithms, such as Trotterization, are dominated by small-angle rotations. Further, we perform a detailed theoretical and numerical study of quasi-probabilities, which can further reduce the total T cost of large circuits by orders of magnitude with only a small overhead in sample complexity. We also develop a scheme based on quasi-probability mixtures of Clifford+T fallback channels. We derive new θ-dependent formulas that can be used for resource estimation of fault-tolerant quantum algorithms. As an application of our results, we show that the gate cost of Trotterization circuits compiled to a Clifford+T gate set is constant in the small Trotter step size limit, and can be reduced by orders of magnitude even for large step sizes. The cost of fault-tolerant Trotterization for a variety of applications should be re-examined in light of these results. Our work dispels the widely-stated claim that Clifford+T rotation synthesis has a high cost independent of θ, and further develops a scalable quasi-probability method for rotation synthesis. We also expect our results to bring forward useful early fault-tolerant quantum computing by reducing required magic state resources.
Successful implementations of quantum technologies require protocols and algorithms that use as few quantum resources as possible. However, many important quantum operations, such as continuous rotation gates in quantum computing or broadband pulses in NMR or magnetic resonance imaging (MRI) applications, can only be implemented approximately using finite quantum resources. This work develops an approach that, on average—at the cost of a modestly increased measurement repetition rate—enables exact implementations. One proceeds by first building a library of a large number of different approximations to the desired gate operation; by randomly selecting these operations according to a preoptimized probability distribution, one can on average implement the desired operation with a rigorously controllable approximation error. The approach relies on sophisticated tools from convex optimization to efficiently find optimal probability distributions. A diverse spectrum of applications are demonstrated as (a) exactly synthesizing rotations in fault-tolerant quantum computers using only low T -count circuits and (b) synthesizing broadband and band-selective pulses of superior performance in quantum optimal control with (c) further applications in NMR or MRI. The approach is very general and a broad spectrum of practical applications in quantum technologies are explicitly demonstrated. Published by the American Physical Society 2024
The present era of quantum processors with hundreds to thousands of noisy qubits has sparked interest in understanding the computational power of these devices and how to leverage it to solve practically relevant problems. For applications that require estimating expectation values of observables the community developed a good understanding of how to simulate them classically and denoise them. Certain applications, like combinatorial optimization, however demand more than expectation values: the bit-strings themselves encode the candidate solutions. While recent impossibility and threshold results indicate that noisy samples alone rarely beat classical heuristics, we still lack classical methods to replicate those noisy samples beyond the setting of random quantum circuits.Focusing on problems whose objective depends only on two-body correlations such as Max-Cut, we show that Gaussian randomized rounding in the spirit of Goemans-Williamson applied to the circuit's two-qubit marginals produces a distribution whose expected cost is provably close to that of the noisy quantum device. For instance, for Max-Cut problems we show that for any depth-D circuit affected by local depolarizing noise p, our sampler achieves a recovery ratio 1 − O [ ( 1 − p ) D ] , giving ways to efficiently sample from a distribution that behaves similarly to the noisy circuit for the problem at hand. Beyond theory we run large-scale simulations and experiments on IBMQ hardware, confirming that the rounded samples faithfully reproduce the full energy distribution, and we show similar behaviour under other various noise models. Our results supply a simple classical surrogate for sampling noisy optimization circuits, clarify the realistic power of near-term hardware for combinatorial tasks, and provide a quantitative benchmark for future error-mitigated or fault-tolerant demonstrations of quantum advantage.
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.
Randomized protocols are procedures that incorporate probabilistic choices during their execution and they play a central role in quantum algorithms, spanning Hamiltonian simulation, noise mitigation, and measurement tasks. In practical implementations, the dominant cost of such protocols typically arises from circuit execution and measurement, and depends on hardware-specific resources such as gate counts, circuit depth, runtime, or dissipated energy. We introduce a general framework for applying classical importance sampling to randomized quantum protocols. Given a cost function for running quantum circuits, the proposed approach minimizes a net-cost figure of merit that jointly captures the computational expense per circuit and the estimator variance. We further extend the framework to scenarios where the quantum computation is subject to errors arising either from algorithmic approximations or from physical noise, proving that importance sampling preserves estimator bias despite altering the sampling distribution, and to settings with error-detection schemes, where we characterize the resulting changes in the optimal sampling strategy and achievable net-cost reduction. Representative applications include the Qdrift protocol, dephasing channels, mixed-states simulation, composite observables estimation, classical shadows, and probabilistic error cancellation. Overall, our results establish a principled approach for reducing the computational resources required by randomized quantum protocols through classical sampling optimization.