# Hype or Heuristic? Quantum Reinforcement Learning for Join Order Optimisation

arXiv: https://arxiv.org/abs/2405.07770 · HTML: https://mlsanity.com/paper/2405.07770/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Quantum reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 33 of its 111 references that are in the map.
- First posted on arXiv 13 May 2024.

## Placed in

- Deep reinforcement learning methods / [Quantum reinforcement learning](https://mlsanity.com/deeprl/quantum-reinforcement-learning/)

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [The effect of data encoding on the expressive power of variational quantum machine learning models](https://mlsanity.com/paper/2008.08605/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Variational Quantum Circuits for Deep Reinforcement Learning](https://mlsanity.com/paper/1907.00397/) (2019)
- [Quantum Natural Gradient](https://mlsanity.com/paper/1909.02108/) (2019)
- [Parametrized quantum policies for reinforcement learning](https://mlsanity.com/paper/2103.05577/) (2021)
- [Better than classical? The subtle art of benchmarking quantum machine learning models](https://mlsanity.com/paper/2403.07059/) (2024)
- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [Reinforcement Learning with Quantum Variational Circuits](https://mlsanity.com/paper/2008.07524/) (2020)
- [TensorFlow Quantum: A Software Framework for Quantum Machine Learning](https://mlsanity.com/paper/2003.02989/) (2020)
- [Bao: Learning to Steer Query Optimizers](https://mlsanity.com/paper/2004.03814/) (2020)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Learning to Optimize Join Queries With Deep Reinforcement Learning](https://mlsanity.com/paper/1808.03196/) (2018)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [Deep Reinforcement Learning for Join Order Enumeration](https://mlsanity.com/paper/1803.00055/) (2018)
- [Quantum Policy Gradient Algorithm with Optimized Action Decoding](https://mlsanity.com/paper/2212.06663/) (2022)
- [Balsa: Learning a Query Optimizer Without Expert Demonstrations](https://mlsanity.com/paper/2201.01441/) (2022)
- [Uncovering Instabilities in Variational-Quantum Deep Q-Networks](https://mlsanity.com/paper/2202.05195/) (2022)
- [Incremental Data-Uploading for Full-Quantum Classification](https://mlsanity.com/paper/2205.03057/) (2022)
- [Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage](https://mlsanity.com/paper/2307.00523/) (2023)
- [Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer](https://mlsanity.com/paper/1510.06437/) (2015)
- [Guided-SPSA: Simultaneous Perturbation Stochastic Approximation assisted by the Parameter Shift Rule](https://mlsanity.com/paper/2404.15751/) (2024)
- [Solving the Join Ordering Problem via Mixed Integer Linear Programming](https://mlsanity.com/paper/1511.02071/) (2015)
- [Join Query Optimization Techniques for Complex Event Processing Applications](https://mlsanity.com/paper/1801.09413/) (2018)

## Built on by (most cited first, 1 of 1)

- [QCardEst/QCardCorr: Quantum Cardinality Estimation and Correction](https://mlsanity.com/paper/2509.08817/) (2025)

## Abstract (arXiv)

Identifying optimal join orders (JOs) stands out as a key challenge in database research and engineering. Owing to the large search space, established classical methods rely on approximations and heuristics. Recent efforts have successfully explored reinforcement learning (RL) for JO. Likewise, quantum versions of RL have received considerable scientific attention. Yet, it is an open question if they can achieve sustainable, overall practical advantages with improved quantum processors. In this paper, we present a novel approach that uses quantum reinforcement learning (QRL) for JO based on a hybrid variational quantum ansatz. It is able to handle general bushy join trees instead of resorting to simpler left-deep variants as compared to approaches based on quantum(-inspired) optimisation, yet requires multiple orders of magnitudes fewer qubits, which is a scarce resource even for post-NISQ systems. Despite moderate circuit depth, the ansatz exceeds current NISQ capabilities, which requires an evaluation by numerical simulations. While QRL may not significantly outperform classical approaches in solving the JO problem with respect to result quality (albeit we see parity), we find a drastic reduction in required trainable parameters. This benefits practically relevant aspects ranging from shorter training times compared to classical RL, less involved classical optimisation passes, or better use of available training data, and fits data-stream and low-latency processing scenarios. Our comprehensive evaluation and careful discussion delivers a balanced perspective on possible practical quantum advantage, provides insights for future systemic approaches, and allows for quantitatively assessing trade-offs of quantum approaches for one of the most crucial problems of database management systems.