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.
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 Ry 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) 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.
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)probability extraction. This eliminates classical iterative optimization, achieving an approximately600×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π-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 probabilitypis small, classical Monte Carlo (MC) methods require a large number of samples to achieve an additive estimation errorε. Achieving accuracyεrequiresN=O(1/ε2)samples, since the root-mean-square error (RMSE) of MC scales asO(1/N). Quantum Computing Monte Carlo (QCMC), based on amplitude estimation, reduces the required oracle complexity toO(1/ε), providing a quadratic improvement in sample complexity. This study proposes a QCMC approach for estimating the Gaussian exceedance probabilityp=P(X>τ), whereX∼N(0,1)andτ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=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−4(0.77% relative error forτ=2.5). The results confirm that QCMC-IAE follows the predictedO(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.