Quantum Estimation of Delay Tail Probabilities in Scheduling and Load Balancing

• URL: http://arxiv.org/abs/2602.09059v1
• Date: Sun, 08 Feb 2026 21:28:09 GMT
• Title: Quantum Estimation of Delay Tail Probabilities in Scheduling and Load Balancing
• Authors: R. Srikant,
• Abstract summary: Estimating delay tail probabilities in scheduling and load balancing systems is a critical but computationally prohibitive task.<n>We develop a framework for quantum simulation of delay tail probabilities based on truncated regenerative simulation.
• Score: 5.978087783577949
• License: http://creativecommons.org/licenses/by/4.0/
• 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-Optimized Selective State Space Model for Efficient Time Series Prediction [39.146761527401424]
  We propose a hybrid quantum-optimized approach that integrates state space dynamics with a variational quantum gate.<n>We empirically validate Q-SSM on three widely used benchmarks, i.e., ETT, Traffic, and Exchange Rate.<n>Results show that Q-SSM consistently improves over strong baselines.
  arXiv  Detail & Related papers  (2025-08-29T22:00:48Z)
• Hybrid quantum-classical algorithm for near-optimal planning in POMDPs [39.682133213072554]
  Reinforcement learning (RL) provides a principled framework for decision-making in partially observable environments.<n>Recent advances demonstrate that inference on sparse Bayesian networks can be accelerated using quantum rejection sampling combined with amplitude amplification.<n>We introduce Quantum Bayesian Reinforcement Learning (QBRL), a hybrid quantum-classical look-ahead algorithm for model-based RL in partially observable environments.
  arXiv  Detail & Related papers  (2025-07-24T17:42:30Z)
• Beating the break-even point with autonomous quantum error correction [23.98841239616206]
  Quantum error correction (QEC) protects fragile quantum information from errors by encoding it in high-dimensional Hilbert spaces.<n>Here, we realize autonomous QEC with a logical qubit encoded in multiple internal spin states of a single trapped ion.<n>We extend the logical qubit lifetime to approximately 11.6 ms, substantially outperforming lifetime for both the physical qubit and the uncorrected logical qubit.
  arXiv  Detail & Related papers  (2025-04-23T14:16:41Z)
• Adiabatic quantum unstructured search in parallel [0.0]
  We present an optimized adiabatic quantum schedule for unstructured search building.<n>In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time.<n>Our findings suggest that quantum advantage may still be achievable under constrained coherence times.
  arXiv  Detail & Related papers  (2025-02-12T17:32:27Z)
• Stochastic resetting in discrete-time quantum dynamics: steady states and correlations in few-qubit systems [0.0]
  We investigate the steady-state properties of discrete-time reset dynamics on quantum computers.<n>For Poissonian resets, we compute the stationary state of the process and demonstrate the existence of "resonances" in the quantum gates.<n>We show that, when the reset probability vanishes sufficiently rapidly with time, the system does not approach a steady state.
  arXiv  Detail & Related papers  (2024-10-15T11:07:25Z)
• Disorder-Free Localization for Benchmarking Quantum Computers [0.0]
  We show how a canonical model of Disorder-free localization can be efficiently implemented on gate-based quantum computers. We show that the simultaneous observation of the absence of correlation spreading and tunable entanglement growth to a volume law provides an ideal testbed for benchmarking the capabilities of quantum computers.
  arXiv  Detail & Related papers  (2024-10-10T18:00:00Z)
• Robust Extraction of Thermal Observables from State Sampling and Real-Time Dynamics on Quantum Computers [49.1574468325115]
  We introduce a technique that imposes constraints on the density of states, most notably its non-negativity, and show that this way, we can reliably extract Boltzmann weights from noisy time series. Our work enables the implementation of the time-series algorithm on present-day quantum computers to study finite temperature properties of many-body quantum systems.
  arXiv  Detail & Related papers  (2023-05-30T18:00:05Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Making Trotterization adaptive and energy-self-correcting for NISQ devices and beyond [0.0]
  Simulation of continuous time evolution requires time discretization on both classical and quantum computers. We introduce a quantum algorithm to solve this problem, providing a controlled solution of the quantum many-body dynamics of local observables. Our algorithm can be potentially useful on a more general level whenever time discretization is involved concerning, for instance, also numerical approaches based on time-evolving block decimation methods.
  arXiv  Detail & Related papers  (2022-09-26T12:54:32Z)
• Probing finite-temperature observables in quantum simulators of spin systems with short-time dynamics [62.997667081978825]
  We show how finite-temperature observables can be obtained with an algorithm motivated from the Jarzynski equality. We show that a finite temperature phase transition in the long-range transverse field Ising model can be characterized in trapped ion quantum simulators.
  arXiv  Detail & Related papers  (2022-06-03T18:00:02Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Simulating hydrodynamics on noisy intermediate-scale quantum devices with random circuits [0.0]
  We show that random circuits provide tailor-made building blocks for simulating quantum many-body systems. Specifically, we propose an algorithm consisting of a random circuit followed by a trotterized Hamiltonian time evolution. We numerically demonstrate the algorithm by simulating the buildup of correlation functions in one- and two-dimensional quantum spin systems.
  arXiv  Detail & Related papers  (2020-12-04T19:00:00Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.