Quantum Speedup of Multi-armed Bandits at Scale by Tackling Memory Decoherence

Recent advances in online learning have achieved an $O(n/{\Delta }_{[2]})$ query complexity in quantum $n$-arm multi-armed bandits (MABs) for best-arm identification, which represents a quadratic speedup over their classical counterparts. Here and throughout, ${\Delta }_{[2]}$ is the gap between the mean of the best and second-best arms. However, the implementations of these algorithms remain on a small scale due to various aspects of quantum hardware restrictions. One of the most significant restrictions is memory decoherence, in which the qubits quickly lose information after a short period of time. Memory decoherence can occur at intra-circuit and inter-circuit levels. Intra-circuit decoherence happens often in near-term quantum computers, where the noise becomes overwhelming when the circuit is deep. On the other hand, inter-circuit decoherence captures future quantum machines, where a quantum memory is promising, but objects stored in the memory for too long can still become decoherent. In this paper, we present a comprehensive treatment of both memory decoherence problems. For inter-circuit decoherence, we derive a framework based on streaming bandits, and we obtain an algorithm that finds the best arm with high constant probability using $O(n/{\Delta }_{[2]})$ queries and an $O(\log n)$ decoherence window. This is the first quantum algorithm for MABs that achieves an $o(n)$ decoherence window, which represents an exponential improvement. For intra-circuit decoherence, we observe that only $O(1)$-depth circuits can be used to avoid significant decoherence. Therefore, we devise various hardware optimizations and a destructive SWAP test subroutine to speed up the empirical performance. On the IBM Q System One machine with 127 qubits, our implementation scales the quantum MABs to over $1000$ arms, and our algorithms consistently achieve significant efficiency improvements over classical bandit algorithms in both physical experiments and computer simulations.