Quantum Simulation of M/G/1/K Queues Achieves 0.99 Fidelity with 63 Qubits, Enabling Variance Reduction of 0.76 and 3% Error
Summarize this article with:
Finite-capacity queues underpin countless real-world systems, yet accurately simulating their performance becomes increasingly difficult as complexity rises. Or Peretz, Michal Koren from the School of Industrial Engineering and Management at Shenkar, and Nir Perel now demonstrate the first coherent quantum circuit capable of simulating an M/G/1/K queue with arbitrary service-time distributions. Their method encodes service variability using a streamlined quantum structure and enforces buffer limits with a novel comparator-controlled gate, all while retaining the benefits of quantum speed-up. This achievement unlocks a new framework for simulating complex queueing systems, delivering high fidelity results and significantly reducing waiting-time estimation errors, and establishes a concrete foundation for accelerated performance analysis in service-oriented architectures. Quantum Algorithms for Stochastic Modelling This collection of research explores the intersection of quantum computing with stochastic modelling, particularly queuing theory and statistical inference. Scientists aim to leverage quantum algorithms to improve or accelerate classical methods for analyzing and simulating complex systems, focusing on tasks like Monte Carlo simulation, linear equation solving, and optimization. Combining quantum machine learning with statistical inference could lead to more accurate and reliable models, while effective error mitigation is essential for realizing the potential of Noisy Intermediate-Scale Quantum (NISQ) algorithms. A key aspect of this work involves measuring the similarity or dissimilarity between probability distributions, essential for statistical and machine learning applications. The combination of queuing theory and quantum computing is particularly impactful, as classical queuing theory struggles with the computational complexity of simulating large systems, a limitation quantum algorithms may overcome.
This research seeks to harness the power of quantum computing to solve challenging problems in stochastic modelling and statistical inference, suggesting a deep understanding of both the classical and quantum foundations of this research area. Quantum Simulation of Variable Demand Queues Scientists engineered a novel quantum circuit to simulate M/G/1/K queues, systems commonly used to model networks and service systems with variable demands. This study pioneers a method for encoding arbitrary service-time distributions using a logarithmic-depth ladder of rotations, effectively translating the characteristics of service variability into quantum states.
The team implemented buffer constraints using a comparator-controlled phase gate, a quantum mechanism that enforces the capacity limits of the queue and prevents overflow. To estimate the expected number of customers in the system, scientists employed Grover iterations, a quantum search algorithm that amplifies the probability of obtaining the correct answer, yielding provable variance reduction and allowing for the establishment of closed-form confidence bounds. Experiments utilized a variable number of qubits, demonstrating fidelity above 0. 99 with four qubits and above 0. 76 with ten qubits. Waiting-time estimation errors decreased by an order of magnitude as system load approached capacity, and results remained within 3% in high-traffic regimes, even when using registers of up to 63 qubits. This study established the first end-to-end simulation framework for finite-buffer, non-Markovian queueing systems, providing a concrete foundation for accelerating performance analysis in service-oriented architectures. Scientists harnessed reversible arithmetic components to enable garbage-free increment and decrement operations, minimizing the need for additional qubits and streamlining the simulation process. Quantum Simulation of Finite Capacity Queues Scientists have developed a novel quantum circuit capable of simulating finite-capacity single-server queues, specifically the M/G/1/K model. This work establishes the first end-to-end quantum simulation framework for these types of queueing systems, offering a foundation for accelerated performance analysis in service-oriented architectures. The circuit encodes service-time distributions using a logarithmic-depth ladder of rotations and enforces buffer constraints with a comparator-controlled phase gate, while maintaining the efficiency of amplitude amplification. Experiments conducted using IBM quantum simulators demonstrate high fidelity, exceeding 0. 99 with four qubits and remaining above 0. 76 with ten qubits. Throughout these tests, the Jensen-Shannon divergence remained below 0. 11, indicating a close match between the quantum simulation and the expected behavior of the queue. Furthermore, waiting-time estimation errors decreased by an order of magnitude as the system load approached full capacity, and measurements reveal that even in high-traffic regimes, waiting-time estimation errors remained within 3% when using registers of up to 63 qubits.
The team achieved these results by leveraging reversible logic for queue transitions and efficient oracle compilation, minimizing qubit overhead. These findings demonstrate the potential for quantum computing to provide substantial performance gains in analyzing and optimizing systems reliant on queueing models.
Simulating Queues With Quantum Circuits Researchers have developed a novel quantum circuit capable of simulating single-server queues with varied service times, a system fundamental to numerous real-world applications. This achievement marks the first coherent circuit designed to model an M/G/1/K queue, accommodating arbitrary service-time distributions. The circuit encodes service distributions using a series of rotations and employs a comparator-controlled phase gate to manage buffer constraints, while maintaining the efficiency of amplitude amplification.
The team demonstrated the circuit’s effectiveness by estimating the expected number of customers in the system, achieving significant variance reduction and establishing clear confidence bounds for the results. Empirical evaluations on quantum simulators, using four and ten qubits, yielded high fidelity scores, above 0. 99 and 0. 76 respectively, and low Jensen-Shannon divergence, indicating accurate simulation. Furthermore, estimations of waiting times showed substantial improvement, with errors remaining within 3% even under high traffic loads.
This research establishes a foundational framework for accelerating performance analysis in service-oriented architectures and opens new avenues for optimizing queuing systems using quantum computation. Future work will focus on extending the framework to more complex systems and improving the scalability of the quantum circuit. 👉 More information 🗞 Quantum-Amplified M/G/1/K Simulation: A Comparator-Controlled Framework for Arbitrary Service Distributions 🧠 ArXiv: https://arxiv.org/abs/2512.10558 Tags: