Index Advisors on Quantum Platforms

• Published in: Proceedings of the VLDB Endowment 2024-07, Vol.17 (11), p.3615-3628
• Main Authors: Kesarwani, Manish, Haritsa, Jayant R.
• Format: Article
• Language: English
• ISSN: 2150-8097; 2150-8097
• DOI: 10.14778/3681954.3682025

Index Advisor tools settle for sub-optimal index configurations based on greedy heuristics, owing to the computational hardness of index selection. We investigate here how this limitation can be addressed by leveraging the computing power offered by quantum platforms. Specifically, we present a hybrid Quantum-Classical Index Advisor that judiciously incorporates gate-based quantum computing within a classical index selection wrapper. Two distinct trade-offs between solution quality and computational complexity are considered. First, index selection is modeled as a Quadratic Unconstrained Binary Optimization problem and solved using the popular Quantum Approximate Optimization Algorithm. The obtained solution is approximate, like greedy, but significantly better in quality while incurring only O (log( L )) computations, where L is the total number of candidate configurations. Second, index selection is modeled as a fully enumerative search and solved using the seminal Grover Search algorithm. A novel quantum oracle is proposed that performs computations on data hosted in the relative phase of a quantum superposition state, and is encoded using only standard quantum gates. This approach identifies, with high probability, the optimal index configuration with computations. We have implemented these two designs using the Qiskit SDK and performed proof-of-concept evaluations on both simulation and hardware platforms. Substantive quality improvements, by a multiplicative factor of 1.5 to 2 and approaching optimality, are obtained as compared to a commercial database engine implementing a greedy approach. Moreover, their quantum resource requirements effectively scale linearly with problem size, an essential feature from a feasibility perspective.