Bandit Algorithm Driven by a Classical Random Walk and a Quantum Walk

Area of Science:

• Quantum computing and algorithms
• Theoretical computer science
• Machine learning

Background:

• Classical random walks (RWs) exhibit linear spreading but lack localization.
• Quantum walks (QWs) uniquely combine linear spreading and localization.
• Multi-armed bandit (MAB) problems involve balancing exploration and exploitation.

Purpose of the Study:

• To develop novel algorithms for MAB problems using both RW and QW frameworks.
• To investigate the performance advantages of QW-based approaches over RW-based ones for MAB.
• To leverage the distinct properties of QWs for improved MAB strategy.

Main Methods:

• Development of RW-based algorithms for MAB.
• Development of QW-based algorithms for MAB.
• Comparative analysis of algorithm performance under various settings.

Main Results:

• QW-based algorithms demonstrate superior performance compared to RW-based algorithms in specific MAB scenarios.
• The enhanced performance is attributed to the QW's ability to effectively manage exploration and exploitation.
• Localization and spreading properties of QWs are key to their MAB advantage.

Conclusions:

• Quantum walks provide a powerful framework for addressing complex MAB problems.
• QW-based strategies offer a promising alternative for optimizing decision-making under uncertainty.
• This research highlights the practical applicability of quantum walk properties in machine learning.