Multi-Armed Bandits and Quantum Channel Oracles

Simon Buchholz; Jonas M. Kübler; Bernhard Schölkopf

doi:10.22331/q-2025-03-25-1672

Multi-Armed Bandits and Quantum Channel Oracles

Simon Buchholz, Jonas M. Kübler, and Bernhard Schölkopf

Max Planck Institute for Intelligent Systems, Tübingen, Germany

Published:	2025-03-25, volume 9, page 1672
Editor:	Tongyang Li
Eprint:	arXiv:2301.08544v4
Doi:	https://doi.org/10.22331/q-2025-03-25-1672
Citation:	Quantum 9, 1672 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Multi-armed bandits are one of the theoretical pillars of reinforcement learning. Recently, the investigation of quantum algorithms for multi-armed bandit problems was started, and it was found that a quadratic speed-up (in query complexity) is possible when the arms and the randomness of the rewards of the arms can be queried in superposition. Here we introduce further bandit models where we only have limited access to the randomness of the rewards, but we can still query the arms in superposition. We show that then the query complexity is the same as for classical algorithms. This generalizes the prior result that no speed-up is possible for unstructured search when the oracle has positive failure probability.

Featured image: Summary of the main results, establishing query complexity bounds for different types of bandit oracles.

Popular summary

In the classical multi-armed bandit problem, the goal is to identify the best action (or "arm") from a finite set of choices. In each round, we select an arm to query and receive a random reward, drawn independently from a probability distribution. Recently, researchers have explored quantum extensions of this problem, where arms can, for example, be queried in superposition. The central question is whether these quantum features enable more efficient algorithms.

A fundamental example of a bandit problem is unstructured search, where the task is to identify a unique marked arm. Prior work has shown that quantum bandits can achieve a quadratic speedup, generalizing the results for unstructured search. However, this speedup critically depends on how the bandit problem is implemented.

In this work, we introduce alternative implementations of the quantum bandit problem that incorporate classical randomness—where arms are modeled using a quantum channel instead of a unitary map. This framework may better capture scenarios such as interactions with an unknown quantum system. Our main result shows that, in this setting, no quantum speedup is possible, even though arms can still be queried in superposition. This highlights the fundamental challenge of achieving quantum speedups in the presence of classical randomness.

► BibTeX data

@article{Buchholz2025multiarmedbandits,
  doi = {10.22331/q-2025-03-25-1672},
  url = {https://doi.org/10.22331/q-2025-03-25-1672},
  title = {Multi-{A}rmed {B}andits and {Q}uantum {C}hannel {O}racles},
  author = {Buchholz, Simon and K{\"{u}}bler, Jonas M. and Sch{\"{o}}lkopf, Bernhard},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1672},
  month = mar,
  year = {2025}
}

► References

[1] P. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM Journal on Computing 26, 1484–1509 (1997).
https://doi.org/10.1137/S0097539795293172

[2] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Phys. Rev. Lett. 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502

[3] Lov K. Grover. ``A fast quantum mechanical algorithm for database search''. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996. Pages 212–219. ACM (1996).
https://doi.org/10.1145/237814.237866

[4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. ``Quantum machine learning''. Nature 549, 195–202 (2017).
https://doi.org/10.1038/nature23474

[5] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. ``Quantum support vector machine for big data classification''. Physical Review Letters 113 (2014).
https://doi.org/10.1103/physrevlett.113.130503

[6] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631–633 (2014).
https://doi.org/10.1038/nphys3029

[7] Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems''. CoRR abs/1603.08675 (2016). arXiv:1603.08675.
arXiv:1603.08675

[8] Esma Aïmeur, Gilles Brassard, and Sébastien Gambs. ``Quantum speed-up for unsupervised learning''. Mach. Learn. 90, 261–287 (2013).
https://doi.org/10.1007/s10994-012-5316-5

[9] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. ``q-means: A quantum algorithm for unsupervised machine learning''. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems. Volume 32. Curran Associates, Inc. (2019). url: https://proceedings.neurips.cc/paper/2019/file/16026d60ff9b54410b3435b403afd226-Paper.pdf.
https://proceedings.neurips.cc/paper/2019/file/16026d60ff9b54410b3435b403afd226-Paper.pdf

[10] Daoyi Dong, Chunlin Chen, Han-Xiong Li, and Tzyh Jong Tarn. ``Quantum reinforcement learning''. IEEE Trans. Syst. Man Cybern. Part B 38, 1207–1220 (2008).
https://doi.org/10.1109/TSMCB.2008.925743

[11] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig. ``Quantum machine learning: a classical perspective''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170551 (2018).
https://doi.org/10.1098/rspa.2017.0551

[12] William R. Thompson. ``On the likelihood that one unknown probability exceeds another in view of the evidence of two samples''. Biometrika 25, 285–294 (1933).
https://doi.org/10.1093/biomet/25.3-4.285

[13] Herbert Robbins. ``Some aspects of the sequential design of experiments''. Bulletin of the American Mathematical Society 58, 527 – 535 (1952). url: https://www.ams.org/journals/bull/1952-58-05/S0002-9904-1952-09620-8/S0002-9904-1952-09620-8.pdf.
https://www.ams.org/journals/bull/1952-58-05/S0002-9904-1952-09620-8/S0002-9904-1952-09620-8.pdf

[14] T.L Lai and Herbert Robbins. ``Asymptotically efficient adaptive allocation rules''. Advances in Applied Mathematics 6, 4–22 (1985).
https://doi.org/10.1016/0196-8858(85)90002-8

[15] Sébastien Bubeck and Nicolò Cesa-Bianchi. ``Regret analysis of stochastic and nonstochastic multi-armed bandit problems''. Found. Trends Mach. Learn. 5, 1–122 (2012).
https://doi.org/10.1561/2200000024

[16] T. Lattimore and C. Szepesvári. ``Bandit algorithms''. Cambridge University Press. (2020).
https://doi.org/10.1017/9781108571401

[17] Daochen Wang, Xuchen You, Tongyang Li, and Andrew M. Childs. ``Quantum exploration algorithms for multi-armed bandits''. Proceedings of the AAAI Conference on Artificial Intelligence 35, 10102–10110 (2021).
https://doi.org/10.1609/aaai.v35i11.17212

[18] Stefano Pirandola, Riccardo Laurenza, Cosmo Lupo, and Jason L. Pereira. ``Fundamental limits to quantum channel discrimination''. npj Quantum Information 5, 50 (2019).
https://doi.org/10.1038/s41534-019-0162-y

[19] Oded Regev and Liron Schiff. ``Impossibility of a quantum speed-up with a faulty oracle''. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games. Volume 5125 of Lecture Notes in Computer Science, pages 773–781. Springer (2008).
https://doi.org/10.1007/978-3-540-70575-8_63

[20] Tze Leung Lai. ``Adaptive Treatment Allocation and the Multi-Armed Bandit Problem''. The Annals of Statistics 15, 1091 – 1114 (1987).
https://doi.org/10.1214/aos/1176350495

[21] Peter Auer. ``Using confidence bounds for exploitation-exploration trade-offs''. J. Mach. Learn. Res. 3, 397–422 (2003). url: https://jmlr.org/papers/v3/auer02a.html.
https://jmlr.org/papers/v3/auer02a.html

[22] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. ``PAC bounds for multi-armed bandit and markov decision processes''. In Jyrki Kivinen and Robert H. Sloan, editors, Computational Learning Theory, 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, 2002, Proceedings. Volume 2375 of Lecture Notes in Computer Science, pages 255–270. Springer (2002).
https://doi.org/10.1007/3-540-45435-7_18

[23] Shie Mannor and John N. Tsitsiklis. ``The sample complexity of exploration in the multi-armed bandit problem''. J. Mach. Learn. Res. 5, 623–648 (2004). url: http://jmlr.org/papers/volume5/mannor04b/mannor04b.pdf.
http://jmlr.org/papers/volume5/mannor04b/mannor04b.pdf

[24] Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. ``Best arm identification in multi-armed bandits''. In Adam Tauman Kalai and Mehryar Mohri, editors, COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010. Pages 41–53. Omnipress (2010). url: https://www.learningtheory.org/colt2010/conference-website/papers/59Audibert.pdf.
https://www.learningtheory.org/colt2010/conference-website/papers/59Audibert.pdf

[25] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. ``Best arm identification: A unified approach to fixed budget and fixed confidence''. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, Léon Bottou, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States. Pages 3221–3229. (2012). url: https://proceedings.neurips.cc/paper/2012/hash/8b0d268963dd0cfb808aac48a549829f-Abstract.html.
https://proceedings.neurips.cc/paper/2012/hash/8b0d268963dd0cfb808aac48a549829f-Abstract.html

[26] Aurélien Garivier and Emilie Kaufmann. ``Optimal best arm identification with fixed confidence''. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory. Volume 49 of Proceedings of Machine Learning Research, pages 998–1027. Columbia University, New York, New York, USA (2016). PMLR. url: https://proceedings.mlr.press/v49/garivier16a.html.
https://proceedings.mlr.press/v49/garivier16a.html

[27] Kevin G. Jamieson, Matthew Malloy, Robert D. Nowak, and Sébastien Bubeck. ``lil' UCB : An optimal exploration algorithm for multi-armed bandits''. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014. Volume 35 of JMLR Workshop and Conference Proceedings, pages 423–439. JMLR.org (2014). url: http://proceedings.mlr.press/v35/jamieson14.html.
http://proceedings.mlr.press/v35/jamieson14.html

[28] Lijie Chen, Jian Li, and Mingda Qiao. ``Towards instance optimal bounds for best arm identification''. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017. Volume 65 of Proceedings of Machine Learning Research, pages 535–592. PMLR (2017). url: http://proceedings.mlr.press/v65/chen17b.html.
http://proceedings.mlr.press/v65/chen17b.html

[29] Balthazar Casalé, Giuseppe Di Molfetta, Hachem Kadri, and Liva Ralaivola. ``Quantum bandits''. Quantum Mach. Intell. 2, 1–7 (2020).
https://doi.org/10.1007/s42484-020-00024-8

[30] M. A. Nielsen and I. L. Chuang. ``Quantum Computation and quantum Information''. Cambridge University Press. (2000).
https://doi.org/10.1017/CBO9780511976667

[31] Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang, and Xiaoming Sun. ``Quantum multi-armed bandits and stochastic linear bandits enjoy logarithmic regrets''. CoRR abs/2205.14988 (2022). arXiv:2205.14988.
https://doi.org/10.48550/arXiv.2205.14988
arXiv:2205.14988

[32] Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, Siyi Yang, and Miklos Santha. ``Quantum algorithms for hedging and the learning of ising models''. Phys. Rev. A 103, 012418 (2021).
https://doi.org/10.1103/PhysRevA.103.012418

[33] Andris Ambainis. ``Variable time amplitude amplification and quantum algorithms for linear algebra problems''. In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France. Volume 14 of LIPIcs, pages 636–647. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012).
https://doi.org/10.4230/LIPIcs.STACS.2012.636

[34] C. L. Degen, F. Reinhard, and P. Cappellaro. ``Quantum sensing''. Rev. Mod. Phys. 89, 035002 (2017).
https://doi.org/10.1103/RevModPhys.89.035002

[35] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. ``Quantum advantage in learning from experiments''. Science 376, 1182–1186 (2022).
https://doi.org/10.1126/science.abn7293

[36] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. ``Advances in quantum metrology''. Nature Photonics 5, 222–229 (2011).
https://doi.org/10.1038/nphoton.2011.35

[37] A Acín. ``Statistical distinguishability between unitary operations''. Physical review letters 87, 177901 (2001).
https://doi.org/10.1103/physrevlett.87.177901

[38] Stefano Pirandola, Riccardo Laurenza, Cosmo Lupo, and Jason L. Pereira. ``Fundamental limits to quantum channel discrimination''. npj Quantum Information 5, 50 (2019).
https://doi.org/10.1038/s41534-019-0162-y

[39] Quntao Zhuang and Stefano Pirandola. ``Ultimate limits for multiple quantum channel discrimination''. Phys. Rev. Lett. 125, 080505 (2020).
https://doi.org/10.1103/PhysRevLett.125.080505

[40] Neil Shenvi, Kenneth R. Brown, and K. Birgitta Whaley. ``Effects of a random noisy oracle on search algorithm complexity''. Phys. Rev. A 68, 052313 (2003).
https://doi.org/10.1103/PhysRevA.68.052313

[41] T. Lindvall. ``Lectures on the coupling method''. Dover Books on Mathematics. Dover Publications. (2012).

[42] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. ``Quantum lower bounds by polynomials''. J. ACM 48, 778–797 (2001).
https://doi.org/10.1145/502090.502097

[43] Andris Ambainis. ``Quantum lower bounds by quantum arguments''. J. Comput. Syst. Sci. 64, 750–767 (2002).
https://doi.org/10.1006/jcss.2002.1826

[44] Yeong-Cherng Liang, Yu-Hao Yeh, Paulo E M F Mendonça, Run Yan Teh, Margaret D Reid, and Peter D Drummond. ``Quantum fidelity measures for mixed states''. Reports on Progress in Physics 82, 076001 (2019).
https://doi.org/10.1088/1361-6633/ab1ca4

Cited by

[1] Nico Meyer, Christian Ufrecht, Maniraman Periyasamy, Daniel D. Scherer, Axel Plinge, and Christopher Mutschler, "A Survey on Quantum Reinforcement Learning", arXiv:2211.03464, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-08 18:47:28). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-08 18:47:27).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.