Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Exact Error Estimates and Optimal Randomized Algorithms for Integration

Ivan Dimov, Emanouil I. Atanassov

Published Jan 1, 2007• 9 citations
Publisher
DOI
10.1007/978-3-540-70942-8_15

Related papers

Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation

Woo‐Ram Lee, Nathan M. Myers, V. W. Scarola

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.

arXiv:2405.10306•Physical Review A•Feb 12, 2025•2 citations

A Practical Approach to the Error Estimation of Quasi-Monte Carlo Integrations

Hozumi Morohosi, Masanori Fushimi

Springer eBooks•Jan 1, 2000•23 citations

Automatic optimal-rate convergence of randomized nets using median-of-means

Zexin Pan

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.

arXiv:2411.01397•Mathematics of Computation•Mar 26, 2025•9 citations

Theory and practice of Trotter product formulas for quantum chemistry

Pablo A. M. Casares, William Maxwell, Danial Motlagh +7 more

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$_4$Mn$_2$O, 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 $\times 2.5$ higher than qubitization, while requiring a dramatic $\times 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.

quant-pharXiv:2606.30741•Jul 1, 2026•5 citations

Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration

Michael Gnewuch, M. Wnuk

arXiv:1903.02276•Journal of Approximation Theory•Nov 23, 2019•6 citations

Optimal Summation and Integration by Deterministic, Randomized, and Quantum Algorithms

Stefan Heinrich, Erich Novak

arXiv:quant-ph/0105114•Springer eBooks•Jan 1, 2002•29 citations
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.
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 Li4_44​Mn2_22​O, 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.54.54.5 relative to the previous state of the art for this problem, with a gate cost only ×2.5\times 2.5×2.5 higher than qubitization, while requiring a dramatic ×5.5\times 5.5×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.