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• 1 citation
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•1 citation

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

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

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

Likelihood-Based Quantum Computing Monte Carlo for Rare-Event Probability Estimation

Jehn‐Ruey Jiang, Hanas Subakti

Rare-event probability estimation is essential for reliability analysis in safety-critical engineering. When the target probability$p$is small, classical Monte Carlo (MC) methods require a large number of samples to achieve an additive estimation error$\varepsilon$. Achieving accuracy$\varepsilon$requires$N=\mathrm{O}\left(1/\varepsilon^{2}\right)$samples, since the root-mean-square error (RMSE) of MC scales as$\mathrm{O}(1/\sqrt{N})$. Quantum Computing Monte Carlo (QCMC), based on amplitude estimation, reduces the required oracle complexity to$\mathrm{O}(1/\varepsilon)$, providing a quadratic improvement in sample complexity. This study proposes a QCMC approach for estimating the Gaussian exceedance probability$p=\mathbb{P}(X>\tau)$, where$X \sim \mathcal{N}(0,1)$and$\tau$denotes a failure threshold set to 2.0, 2.5 or 3.0. The continuous distribution is truncated to a finite interval [−4, 4] and discretized into 1024-point grid using$n=10$qubits. We adopt Likelihood-based Iterative Amplitude Estimation (IAE), which avoids the deep circuits required by phase estimation and is thus suitable for near-term quantum devices. Experimental results show that the proposed QCMC-IAE achieves target accuracy with significantly fewer oracle calls than classical MC before reaching a discretization bias of$0.48 \times 10^{-4}$(0.77% relative error for$\tau=2.5)$. The results confirm that QCMC-IAE follows the predicted$O(1/N)$convergence behavior until it reaches the precision limit imposed by the grid resolution.

IEEE International Conference on Consumer Electronics - Taiwan (ICCE-Taiwan)•Jul 1, 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•28 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.
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.
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
Rare-event probability estimation is essential for reliability analysis in safety-critical engineering. When the target probabilitypppis small, classical Monte Carlo (MC) methods require a large number of samples to achieve an additive estimation errorε\varepsilonε. Achieving accuracyε\varepsilonεrequiresN=O(1/ε2)N=\mathrm{O}\left(1/\varepsilon^{2}\right)N=O(1/ε2)samples, since the root-mean-square error (RMSE) of MC scales asO(1/N)\mathrm{O}(1/\sqrt{N})O(1/N​). Quantum Computing Monte Carlo (QCMC), based on amplitude estimation, reduces the required oracle complexity toO(1/ε)\mathrm{O}(1/\varepsilon)O(1/ε), providing a quadratic improvement in sample complexity. This study proposes a QCMC approach for estimating the Gaussian exceedance probabilityp=P(X>τ)p=\mathbb{P}(X>\tau)p=P(X>τ), whereX∼N(0,1)X \sim \mathcal{N}(0,1)X∼N(0,1)andτ\tauτdenotes a failure threshold set to 2.0, 2.5 or 3.0. The continuous distribution is truncated to a finite interval [−4, 4] and discretized into 1024-point grid usingn=10n=10n=10qubits. We adopt Likelihood-based Iterative Amplitude Estimation (IAE), which avoids the deep circuits required by phase estimation and is thus suitable for near-term quantum devices. Experimental results show that the proposed QCMC-IAE achieves target accuracy with significantly fewer oracle calls than classical MC before reaching a discretization bias of0.48×10−40.48 \times 10^{-4}0.48×10−4(0.77% relative error forτ=2.5)\tau=2.5)τ=2.5). The results confirm that QCMC-IAE follows the predictedO(1/N)O(1/N)O(1/N)convergence behavior until it reaches the precision limit imposed by the grid resolution.
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.