We compute the integral of a function or the expectation of a random variable with minimal cost and use, for our new algorithm and for upper bounds of the complexity, i.i.d. samples. Under certain assumptions it is possible to select a sample size based on a variance estimation, or -- more generally -- based on an estimation of a (central absolute)
p-moment. That way one can guarantee a small absolute error with high probability, the problem is thus called solvable. The expected cost of the method depends on the
p-moment of the random variable, which can be arbitrarily large. In order to prove the optimality of our algorithm we also provide lower bounds. These bounds apply not only to methods based on i.i.d. samples but also to general randomized algorithms. They show that -- up to constants -- the cost of the algorithm is optimal in terms of accuracy, confidence level, and norm of the particular input random variable. Since the considered classes of random variables or integrands are very large, the worst case cost would be infinite. Nevertheless one can define adaptive stopping rules such that for each input the expected cost is finite. We contrast these positive results with examples of integration problems that are not solvable.
We study the sample median of independently generated quasi-Monte Carlo estimators based on randomized digital nets and prove it approximates the target integral value at almost the optimal convergence rate for various function spaces. In contrast to previous methods, the algorithm does not require a priori knowledge of underlying function spaces or even an input of pre-designed ( t , m , s ) (t,m,s) -digital nets, and is therefore easier to implement. This study provides further evidence that some types of randomized quasi-Monte Carlo estimators are heavy-tailed when applied to smooth integrands and taking the median can significantly improve the error by filtering out the outliers.
Trotter product formulas are a fundamental class of methods for Hamiltonian simulation, particularly attractive due to their low qubit requirements. However, they are often overlooked for use with fault-tolerant quantum algorithms, because of their perceived higher gate counts and the difficulty of estimating Trotter error. Here, we introduce Symmetry-Protected Randomized near-Integrable Trotter (SPRINT) formulas, a framework for building optimized product formulas for electronic structure Hamiltonians widely used in quantum chemistry. SPRINT integrates a generalization of classical near-integrability, randomization, symmetry protection, use of QROM, and other techniques into a thoroughly optimized methodology for Hamiltonian simulation. When applied to concrete simulation tasks, we find SPRINT leads to substantial reduction in gate count compared to previous approaches. Alongside SPRINT, we introduce and analyze a Generalized Rank Decomposition (GRADE) of electronic Hamiltonians that generalizes previous factorization methods. We apply these techniques to the task of simulating the X-ray absorption spectrum of Li
4Mn
2O, a candidate battery cathode material, leveraging recent advances in tight Trotter error estimation to carefully identify the best version of SPRINT for this problem. Using a Trotter error estimation tool developed in the PennyLane software platform, we show that SPRINT reduces the Toffoli gate cost by a factor of
4.5 relative to the previous state of the art for this problem, with a gate cost only
×2.5 higher than qubitization, while requiring a dramatic
×5.5 fewer logical qubits. These results establish well-designed Trotter product formulas as an attractive Hamiltonian simulation method for industrially relevant problems in chemistry and materials science.
We present a hybrid quantum algorithm for estimating gaps in many-body energy spectra, supported by an analytic proof of its inherent resilience to state preparation and measurement errors, as well as midcircuit multiqubit depolarizing noise. Our analysis extends to a broader class of Markovian noise, employing error mitigation strategies that optimize the utilization of quantum resources. By integrating trial-state optimization and classical signal processing into the algorithm, we amplify the signal peak corresponding to the exact target gap beyond the error threshold, thereby significantly reducing gap estimate errors. The algorithm's robustness is demonstrated through noisy simulations on the Qiskit Aer simulator and demonstrations on IBM Quantum processors. These results underscore the potential to enable accurate quantum simulations on near-term noisy quantum devices without resource-intensive error correction.