Quantum Approximation for Multi-Scale Scheduling

Asa Hopkins, Viv Kendon

One way to approximate a quantum annealing schedule is to use multiple quantum walks chained together, without intermediate measurements, to produce a multi-stage quantum walk (MSQW). Previous work has shown that a MSQW is better than QAOA (quantum alternating operator ansatz) for solving optimization tasks using multiple stages [Gerblich et al, arXiv:2407.06663]. In this work, we develop an efficient heuristic for choosing the free parameters in MSQW, and use it to obtain improved scaling compared to single stage quantum walks. We show numerically that the heuristic works well for problems with a large minimum energy gap, giving a polynomial scaling in the number of stages, and leading to an overall algorithm that scales polynomially in time. For problems with a small minimum gap, the scaling breaks down such that adding more stages decreases the success probability, leading to an overall scaling that is exponential in time as expected. Our methods are general and can be applied to any optimization problem to obtain good annealing schedules.

Poojith U Rao, Balwinder Sodhi

Cynthia A. Phillips, Robert D. Carr, Anand Ganti

Soohyun Park, Hankyul Baek, Joongheon Kim

In modern network applications, the concept of metaverse is an emerging technology, and one of its key characteristics is the separation between the physical-space of the users and the virtual meta-space of the avatars. Based on this, a novel quantum multi-agent reinforcement learning (QMARL)-based scheduler, prioritizing the improvement of the performance of meta-space rendering is proposed in this article. The increase in performance can be achieved by controlling the number of utilized point cloud segments depending on avatar-popularity under the consideration of physical-space constraints. During this process, QMARL-centered quantum artificial intelligence (AI) algorithms are utilized for sequential scheduling action decision-making over time. By utilizing this QMARL, our proposed scheduler is designed to reduce the number of scheduling action dimensions into logarithmic scales. This is beneficial in the noisy intermediate-scale quantum (NISQ) era as the number of usable qubits is inherently limited. After this QMARL-based scheduling, the scheduled regions will be re-constructed over meta-space with prioritized point cloud registration. Finally, our performance evaluation results show that our proposed scheduler outperforms classical multi-agent reinforcement learning (MARL)-based scheduling in terms of utility between 12.6 and 20.7 percent, under various avatar distributions.

Soumyadip Paul, Sarit Chakraborty

Quantum technology offers a transformative approach to solving complex computational challenges in decentralized systems, particularly in blockchain transaction scheduling. Efficient transaction scheduling is critical in distributed ledger systems, which often face challenges like dynamic transaction loads. This work proposes a novel approach namely Hybrid Quantum Approximate Optimization Algorithm (HQAOA) which combines Multi-Agent QAOA (MA-QAOA) and Adaptive Layer QAOA (AL-QAOA) to provide a robust solution to such issues. HQAOA leverages a decentralized optimization framework where multiple agents, each representing a node in the network, optimize local transaction scheduling while considering global constraints. Additionally, HQAOA adapts to varying transaction loads by dynamically adjusting the number of quantum layers for each agent, ensuring computational efficiency under different conditions. Such dynamic layer adjustment mechanisms mitigate the adverse effects of quantum noise and ensures optimal performance in scenarios with fluctuating transaction loads. In contrast to traditional QAOA, which struggles with noise and scaling issues, HQAOA provides improved performance by balancing the complexity of the problem with available quantum resources. Experimental results signify the future potential of HQAOA to outperform QAOA, particularly in noisy environments and irregular transaction conditions. This work demonstrates the potential of HQAOA to optimize blockchain transaction scheduling in decentralized systems.

Robert L. Smith, Michael J. Curtis, Anthony Polloreno +3 more