Introduction
Reinforcement learning (RL) agents interact with environments by receiving percepts and selecting actions to maximize rewards. A critical bottleneck in this process is the deliberation time—the internal processing time required for an agent to search its memory and decide on an action. Classically, if a rewarded action has a low probability $\epsilon$, finding it takes approximately $1/\epsilon$ attempts. This paper demonstrates an experimental proof-of-principle using quantum hardware to achieve a quadratic speed-up in this deliberation phase.
The Projective Simulation Paradigm
The researchers utilize Projective Simulation (PS), a framework where an agent's memory is represented as a network of "clips" (past experiences). Decision-making is modeled as a random walk on this network.
In the Quantum Projective Simulation (Q-RPS) variant, the search process is accelerated using a Szegedy quantum walk combined with amplitude amplification (a generalization of Grover’s algorithm). This allows the agent to explore possible actions in superposition, reducing the expected deliberation time to $1/\sqrt{\epsilon}$.
Experimental Implementation
The experiment was conducted on a two-qubit ion trap quantum processor using $^{171}\text{Yb}^+$ ions. Key technical features included:
- MAGIC (Magnetic Gradient Induced Coupling): Individual ions were addressed via radiofrequency radiation within a static magnetic field gradient.
- Rank-One Simplification: To fit the algorithm on two qubits, the team focused on rank-one Markov chains, allowing the process to be represented on a single Hilbert space.
- Dynamical Decoupling: To maintain coherence during the complex diffusion steps (up to 30ms), "Universal Robust" (UR14) sequences of 140 RF $\pi$-pulses were employed.
Key Results
The experimental results confirmed the theoretical quantum advantage:
- Quadratic Scaling: The deliberation cost scaled as $O(\epsilon^{-0.57(5)})$, closely matching the ideal $O(\epsilon^{-0.5})$ and significantly outperforming the classical $O(\epsilon^{-1})$.
- Success Probability: Despite noise, the agent successfully outputted rewarded actions with up to 88% probability in a single step.
- Preference Preservation: The quantum algorithm maintained the relative probabilities of different rewarded actions, ensuring that the agent's learned preferences were not lost during the speed-up.
Conclusion and Future Outlook
This work represents the first experimental demonstration of quantum-accelerated decision-making in RL. While limited to a two-qubit "rank-one" structure, it paves the way for more complex agents. Future research will focus on scaling to general-rank Q-RPS and integrating the quantum processor into the full learning loop, where it can also handle the updating of memory based on environmental feedback.
Summary updated