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

arXiv:2602.09059

Quantum Estimation of Delay Tail Probabilities in Scheduling and Load Balancing

R. Srikant

quant-phmath.PRSubmitted Feb 8, 2026• Announced Feb 10, 2026• 0 citations
arXivHTMLPDF

Abstract

Estimating delay tail probabilities in scheduling and load balancing systems is a critical but computationally prohibitive task due to the rarity of violation events. Quantum Amplitude Estimation (QAE) offers a generic quadratic reduction in sample complexity 1/sqrt(p) vs 1/p, but applying it to steady-state queueing networks in challenging: classical simulations involve unbounded state spaces and random regeneration cycles, whereas quantum circuits have fixed depth and finite registers. In this paper, we develop a framework for quantum simulation of delay tail probabilities based on truncated regenerative simulation. We show that regenerative rare-event estimators can be reformulated as deterministic, reversible functions of finite random seeds by truncating regeneration cycles. To control the resulting bias, we use Lyapunov drift and concentration arguments to derive exponential tail bounds on regeneration times. This allows the truncation horizon--and hence the quantum circuit depth--to be chosen such that the bias is provably negligible compared to the statistical error. The proposed framework enables quantum estimation in models with countably infinite state spaces, avoiding the challenge of determining the sufficient mixing time required for direct finite-horizon simulation. We provide bounds on qubit and circuit complexity for a GI-GI-1 queue, a wireless network under MaxWeight scheduling, and a multi-server system with Join-the-Shortest-Queue (JSQ) routing.

Related papers

Quantum-Amplified M/G/1/K Simulation: A Comparator-Controlled Framework for Arbitrary Service Distributions

Or Peretz, Michal Koren, Nir Perel

Finite-capacity single-server queues with general service-time distributions form the backbone of numerous real-world systems, yet classical simulation of performance metrics such as blocking probabilities and delay becomes computationally prohibitive as service variability or required precision increases. This work presents the first coherent quantum circuit for simulating an M/G/1/K queue under arbitrary service-time laws. The circuit encodes the service distribution through a logarithmic-depth ladder of $R_y$ rotations and enforces buffer constraints via a comparator-controlled phase gate, while preserving the quadratic speed-up of amplitude amplification. Grover iterations center on estimating the expected number of customers in the system, yielding provable $O(\sqrt{N})$ variance reduction and closed-form confidence bounds, where $N$ denotes the number of shots. Empirical evaluations on IBM quantum simulators across four service distributions and three traffic intensities demonstrate fidelity above 0.99 with four qubits and above 0.76 with ten qubits, with Jensen-Shannon divergence below 0.11. Waiting-time estimation errors decrease by an order of magnitude as system load approaches capacity and remain within 3% in high-traffic regimes using registers of up to 63 qubits. These results establish the first end-to-end quantum simulation framework for finite-buffer, non-Markovian queueing systems and provide a concrete foundation for quantum-accelerated performance analysis in service-oriented architectures.

quant-pharXiv:2512.10558•Dec 12, 2025•0 citations

Quantum Rare-Event Estimation for Ising Graphical Models with Belief-Propagation State Preparation

Mario Hernández Vera, Narges Jamialahmadi, Burak Mete +2 more

Quantum amplitude estimation can reduce the sampling cost of rare-event probability estimation, but applying it to correlated Ising graphical models is limited by the difficulty of preparing the target distribution and building a practical event oracle. This work explores two approximate strategies for mitigating these challenges. We introduce a sample-free state-preparation method combining loopy belief propagation with the Chow--Liu algorithm. The resulting tree approximation is compiled into a quantum circuit with linear gate count and depth, and its accuracy is evaluated across graph families spanning different topologies, coupling strengths, and coupling signs. We also construct a structural oracle that evaluates threshold rules with reversible Boolean gates. Using a twenty-node supply-chain disruption model as a case study, we compare maximum likelihood amplitude estimation against four classical Monte Carlo baselines. Under the fixed-depth schedule used throughout this work, the quantum estimator has the same asymptotic error scaling as the classical methods but achieves lower estimation error by a constant factor. This reduction narrows when amplitude-encoding queries replace raw shots as the resource metric. We separate statistical error from the deterministic errors caused by approximate state preparation and oracle construction, and identify the requirements for achieving an improvement beyond a constant factor.

quant-pharXiv:2608.26840•Aug 28, 2026•0 citations

Hardware-Efficient Quantum Grid Sampling for Low-Latency Amplitude Estimation

Yu-Ting Kao, Haoyu Lu, Yeong-Jar Chang +3 more

High-performance computing heavily relies on Monte Carlo (MC) simulation, but achieving high precision imposes massive computational loads due to its low convergence rate. To overcome this classical bottleneck, Quantum Amplitude Estimation (QAE) has emerged as a powerful algorithmic alternative, theoretically offering a quadratic speedup by offloading these workloads to quantum accelerators. However, mitigating Quantum Fourier Transform (QFT) discretization errors typically require Maximum Likelihood Estimation (MLE). MLE introduces prohibitive iterative latency and struggles with shot-noise in low-measurement regimes. To address this, we propose a comprehensive, hardware-efficient framework that integrates uniform state preparation with a novel Peak Estimation Refinement (PER) readout technique. PER exploits the symmetric conjugate eigenvalues of the quantum operator to provide deterministic,${O}(\mathrm{1})$probability extraction. This eliminates classical iterative optimization, achieving an approximately$600 \times$reduction in post-processing latency while inherently amplifying the signal-to-noise margin to resist stochastic fluctuations in low-shot environments. Validated via an RTL-to-quantum compilation flow and a 10 -qubit$\pi$-estimation synthesis benchmark, we demonstrate an estimation error of 0.007 %, proving the viability of migrating complex probabilistic workloads to real-time quantum accelerators

IEEE Dallas Circuits and Systems Conference (DCAS)•Apr 10, 2026•0 citations

Quantum Amplitude Estimation for Travel Time Estimation in Stochastic Vehicle Routing Problems

Xingyue Wang, Monika Filipovska

Solving the Vehicle Routing Problem (VRP) in Stochastic Transportation Networks (STNs), a core task in Intelligent Transportation Systems (ITS), introduces estimation challenges for stochastic path travel times and the resulting VRP objective function. These challenges have typically been addressed through computationally expensive sampling-based techniques such as Monte Carlo simulation, whose performance depends on sample size, the sampling strategy, and the underlying travel time distributions. To address these issues, this study proposes and validates a quantum computing technique, Quantum Amplitude Estimation (QAE) for path-level travel time estimation in STNs. Without relying on sampling or prior assumptions of the travel time distribution, the proposed framework encodes all feasible travel time realizations into a quantum superposition, enabling a theoretical quadratic speed-up over Monte Carlo simulation. Four QAE variants are implemented in IBM's Qiskit framework, namely Canonical AE (CAE), Iterative AE (IAE), Maximum Likelihood AE (MLAE), and Faster AE (FAE), together with four rotation-angle scaling strategies for handling different discrete travel time distributions. Experiments on a small-scale STN show that the choice of scaling method and rotation-angle range significantly affects estimation accuracy, while the four QAE variants produce comparable estimates across all tested conditions, with IAE exhibiting the most stable overall performance. The results provide practical guidance on parameter selection for future hybrid quantum-classical optimization frameworks in ITS applications.

quant-pharXiv:2608.06145•Aug 7, 2026•0 citations

Quantum Amplitude Estimation in the Presence of Noise

Brown, Eric G., Oktay Göktaş, W. K. Tham

Quantum Amplitude Estimation (QAE) -- a technique by which the amplitude of a given quantum state can be estimated with quadratically fewer queries than by standard sampling -- is a key sub-routine in several important quantum algorithms, including Grover search and Quantum Monte-Carlo methods. An obstacle to implementing QAE in near-term noisy intermediate-scale quantum (NISQ) devices has been the need to perform Quantum Phase Estimation (QPE) -- a costly procedure -- as a sub-routine. This impediment was lifted with various QPE-free methods of QAE, wherein Grover queries of varying depths / powers (often according to a "schedule") are followed immediately by measurements and classical post-processing techniques like maximum likelihood estimation (MLE). Existing analyses as to the optimality of various query schedules in these QPE-free QAE schemes have hitherto assumed noise-free systems. In this work, we analyse QPE-free QAE under common noise models that may afflict NISQ devices and report on the optimality of various query schedules in the noisy regime. We demonstrate that, given an accurate noise characterization of one's system, one must choose a schedule that balances the trade-off between the greater ideal performance achieved by higher-depth circuits, and the correspondingly greater accumulation of noise-induced error.

arXiv:2006.14145•Jun 25, 2020•11 citations

Quantum Monte Carlo Integration for Credit-Portfolio Tail Risk

Kavy Upadhyay

Monte Carlo simulations underpin computational quantitative finance, where they are used for derivative pricing, risk quantification and scenario analysis whenever closed-form solutions are unavailable. Their main limitation is the slow O(N^-1/2) convergence of classical sampling. Quantum amplitude estimation promises a quadratic improvement in query complexity over classical Monte Carlo, reducing the sample requirement from O(eps^-2) to O(eps^-1) under idealised conditions. This thesis measures the extent to which the quadratic improvement in query complexity survives a concrete risk task under gate noise when compared to classical Monte Carlo. A four-obligor correlated portfolio, whose loss distribution can be computed exactly, is encoded into quantum circuits, and its value at risk and expected shortfall are estimated by iterative amplitude estimation under exactly simulated depolarising noise on every two-qubit gate. Six configurations of 11 to 15 qubits vary the portfolio, the factor grid and the arithmetic construction. At matched loss-model evaluation budgets and without noise, amplitude estimation reduces the RMSE of the tail probability against classical Monte Carlo by a factor of 13.6 at the largest budget tested. The error budget is dominated by the circuit encoding, not the estimator. As a result, the value at risk at the 95% level picks the wrong loss level in none of the noiseless repetitions, while the encoding understates expected shortfall by 0.177 loss units. Under noise, the signal decays with every amplification round. The number of rounds that still help falls from 64 at an error rate of 3x10^-6 to none at 3x10^-2. This work concludes that amplification benefits only while the product of gate count and error rate stays small against one. Because every obligor added enlarges the circuit, the error rate at which amplification remains useful falls as the portfolio grows, and advantage starts depending on circuit compression instead of estimator design.

•Sep 4, 2026•0 citations
Estimating delay tail probabilities in scheduling and load balancing systems is a critical but computationally prohibitive task due to the rarity of violation events. Quantum Amplitude Estimation (QAE) offers a generic quadratic reduction in sample complexity 1/sqrt(p) vs 1/p, but applying it to steady-state queueing networks in challenging: classical simulations involve unbounded state spaces and random regeneration cycles, whereas quantum circuits have fixed depth and finite registers.
In this paper, we develop a framework for quantum simulation of delay tail probabilities based on truncated regenerative simulation. We show that regenerative rare-event estimators can be reformulated as deterministic, reversible functions of finite random seeds by truncating regeneration cycles. To control the resulting bias, we use Lyapunov drift and concentration arguments to derive exponential tail bounds on regeneration times. This allows the truncation horizon--and hence the quantum circuit depth--to be chosen such that the bias is provably negligible compared to the statistical error. The proposed framework enables quantum estimation in models with countably infinite state spaces, avoiding the challenge of determining the sufficient mixing time required for direct finite-horizon simulation. We provide bounds on qubit and circuit complexity for a GI-GI-1 queue, a wireless network under MaxWeight scheduling, and a multi-server system with Join-the-Shortest-Queue (JSQ) routing.
Finite-capacity single-server queues with general service-time distributions form the backbone of numerous real-world systems, yet classical simulation of performance metrics such as blocking probabilities and delay becomes computationally prohibitive as service variability or required precision increases. This work presents the first coherent quantum circuit for simulating an M/G/1/K queue under arbitrary service-time laws. The circuit encodes the service distribution through a logarithmic-depth ladder of RyR_yRy​ rotations and enforces buffer constraints via a comparator-controlled phase gate, while preserving the quadratic speed-up of amplitude amplification. Grover iterations center on estimating the expected number of customers in the system, yielding provable O(N)O(\sqrt{N})O(N​) variance reduction and closed-form confidence bounds, where NNN denotes the number of shots. Empirical evaluations on IBM quantum simulators across four service distributions and three traffic intensities demonstrate fidelity above 0.99 with four qubits and above 0.76 with ten qubits, with Jensen-Shannon divergence below 0.11. Waiting-time estimation errors decrease by an order of magnitude as system load approaches capacity and remain within 3% in high-traffic regimes using registers of up to 63 qubits. These results establish the first end-to-end quantum simulation framework for finite-buffer, non-Markovian queueing systems and provide a concrete foundation for quantum-accelerated performance analysis in service-oriented architectures.
Quantum amplitude estimation can reduce the sampling cost of rare-event probability estimation, but applying it to correlated Ising graphical models is limited by the difficulty of preparing the target distribution and building a practical event oracle. This work explores two approximate strategies for mitigating these challenges. We introduce a sample-free state-preparation method combining loopy belief propagation with the Chow--Liu algorithm. The resulting tree approximation is compiled into a quantum circuit with linear gate count and depth, and its accuracy is evaluated across graph families spanning different topologies, coupling strengths, and coupling signs. We also construct a structural oracle that evaluates threshold rules with reversible Boolean gates. Using a twenty-node supply-chain disruption model as a case study, we compare maximum likelihood amplitude estimation against four classical Monte Carlo baselines. Under the fixed-depth schedule used throughout this work, the quantum estimator has the same asymptotic error scaling as the classical methods but achieves lower estimation error by a constant factor. This reduction narrows when amplitude-encoding queries replace raw shots as the resource metric. We separate statistical error from the deterministic errors caused by approximate state preparation and oracle construction, and identify the requirements for achieving an improvement beyond a constant factor.
High-performance computing heavily relies on Monte Carlo (MC) simulation, but achieving high precision imposes massive computational loads due to its low convergence rate. To overcome this classical bottleneck, Quantum Amplitude Estimation (QAE) has emerged as a powerful algorithmic alternative, theoretically offering a quadratic speedup by offloading these workloads to quantum accelerators. However, mitigating Quantum Fourier Transform (QFT) discretization errors typically require Maximum Likelihood Estimation (MLE). MLE introduces prohibitive iterative latency and struggles with shot-noise in low-measurement regimes. To address this, we propose a comprehensive, hardware-efficient framework that integrates uniform state preparation with a novel Peak Estimation Refinement (PER) readout technique. PER exploits the symmetric conjugate eigenvalues of the quantum operator to provide deterministic,O(1){O}(\mathrm{1})O(1)probability extraction. This eliminates classical iterative optimization, achieving an approximately600×600 \times600×reduction in post-processing latency while inherently amplifying the signal-to-noise margin to resist stochastic fluctuations in low-shot environments. Validated via an RTL-to-quantum compilation flow and a 10 -qubitπ\piπ-estimation synthesis benchmark, we demonstrate an estimation error of 0.007 %, proving the viability of migrating complex probabilistic workloads to real-time quantum accelerators
Solving the Vehicle Routing Problem (VRP) in Stochastic Transportation Networks (STNs), a core task in Intelligent Transportation Systems (ITS), introduces estimation challenges for stochastic path travel times and the resulting VRP objective function. These challenges have typically been addressed through computationally expensive sampling-based techniques such as Monte Carlo simulation, whose performance depends on sample size, the sampling strategy, and the underlying travel time distributions. To address these issues, this study proposes and validates a quantum computing technique, Quantum Amplitude Estimation (QAE) for path-level travel time estimation in STNs. Without relying on sampling or prior assumptions of the travel time distribution, the proposed framework encodes all feasible travel time realizations into a quantum superposition, enabling a theoretical quadratic speed-up over Monte Carlo simulation. Four QAE variants are implemented in IBM's Qiskit framework, namely Canonical AE (CAE), Iterative AE (IAE), Maximum Likelihood AE (MLAE), and Faster AE (FAE), together with four rotation-angle scaling strategies for handling different discrete travel time distributions. Experiments on a small-scale STN show that the choice of scaling method and rotation-angle range significantly affects estimation accuracy, while the four QAE variants produce comparable estimates across all tested conditions, with IAE exhibiting the most stable overall performance. The results provide practical guidance on parameter selection for future hybrid quantum-classical optimization frameworks in ITS applications.
Quantum Amplitude Estimation (QAE) -- a technique by which the amplitude of a given quantum state can be estimated with quadratically fewer queries than by standard sampling -- is a key sub-routine in several important quantum algorithms, including Grover search and Quantum Monte-Carlo methods. An obstacle to implementing QAE in near-term noisy intermediate-scale quantum (NISQ) devices has been the need to perform Quantum Phase Estimation (QPE) -- a costly procedure -- as a sub-routine. This impediment was lifted with various QPE-free methods of QAE, wherein Grover queries of varying depths / powers (often according to a "schedule") are followed immediately by measurements and classical post-processing techniques like maximum likelihood estimation (MLE). Existing analyses as to the optimality of various query schedules in these QPE-free QAE schemes have hitherto assumed noise-free systems. In this work, we analyse QPE-free QAE under common noise models that may afflict NISQ devices and report on the optimality of various query schedules in the noisy regime. We demonstrate that, given an accurate noise characterization of one's system, one must choose a schedule that balances the trade-off between the greater ideal performance achieved by higher-depth circuits, and the correspondingly greater accumulation of noise-induced error.
Monte Carlo simulations underpin computational quantitative finance, where they are used for derivative pricing, risk quantification and scenario analysis whenever closed-form solutions are unavailable. Their main limitation is the slow O(N^-1/2) convergence of classical sampling. Quantum amplitude estimation promises a quadratic improvement in query complexity over classical Monte Carlo, reducing the sample requirement from O(eps^-2) to O(eps^-1) under idealised conditions. This thesis measures the extent to which the quadratic improvement in query complexity survives a concrete risk task under gate noise when compared to classical Monte Carlo. A four-obligor correlated portfolio, whose loss distribution can be computed exactly, is encoded into quantum circuits, and its value at risk and expected shortfall are estimated by iterative amplitude estimation under exactly simulated depolarising noise on every two-qubit gate. Six configurations of 11 to 15 qubits vary the portfolio, the factor grid and the arithmetic construction. At matched loss-model evaluation budgets and without noise, amplitude estimation reduces the RMSE of the tail probability against classical Monte Carlo by a factor of 13.6 at the largest budget tested. The error budget is dominated by the circuit encoding, not the estimator. As a result, the value at risk at the 95% level picks the wrong loss level in none of the noiseless repetitions, while the encoding understates expected shortfall by 0.177 loss units. Under noise, the signal decays with every amplification round. The number of rounds that still help falls from 64 at an error rate of 3x10^-6 to none at 3x10^-2. This work concludes that amplification benefits only while the product of gate count and error rate stays small against one. Because every obligor added enlarges the circuit, the error rate at which amplification remains useful falls as the portfolio grows, and advantage starts depending on circuit compression instead of estimator design.