Quantum Databases



Database Systems Lab
Indian Institute of Science


[About] [Publications] [Source Code] [Team] [Contact]
About Quantum Database
Welcome to the Quantum Database research performed at the Database Systems Lab, Indian Institute of Science. Recent advances in quantum computing have led to the deployment of quantum computers featuring more than 1,000 qubits, with development roadmaps projecting capacities exceeding 100,000 qubits by the next decade. To harness the immense potential of these upcoming systems, it is imperative to concurrently investigate the feasibility of hosting relational database engines on quantum platforms.
[CODS-COMAD 2024 Tutorial] Relational Database Engines on Quantum Platforms
In this tutorial, we present a deep-dive on how quantum computing can be leveraged for database purposes. We begin with an overview of quantum computing fundamentals, followed by a survey of the unique technical challenges that arise on these platforms. Then we consider quantum-based optimization, which can be applied to several DBMS modules, including query optimization, physical schema design, transaction scheduling, resource allocation, etc. We follow up with quantum-based query execution for the basic relational operators, highlighting the architectural mechanisms proposed to work around the restrictions imposed by the probabilistic computational model. Finally, we enumerate the key technical challenges that remain to be addressed to make quantum database engines a reality.

In the concluding session, participants will be guided through a hands-on experience of constructing quantum database algorithms, and executing them on both quantum simulators and real quantum hardware.

Overall, the tutorial is planned for 3 hours, covering the five stages summarised below:
  • Stage I: Quantum Computing Fundamentals [~30 min]
  • Stage II: Quantum Computing Challenges [~15 min]
  • Stage III: Quantum Query Optimization [~45 min]
  • Stage IV: Quantum Query Execution [~30 min]
  • Stage V: Demo + Hands-On Exercise [~60 min]
[VLDB 2024] Index Advisors on Quantum Platforms
The first problem that we explored is of Index Selection. Formally, Given an SQL workload and a storage constraint "S", Index Advisor tools are used for the creation of performance-beneficial indexes that satisfy "S".

Current commercial 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 O(√L) 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.

Publications
Index Advisors on Quantum Platforms
Manish Kesarwani, Jayant Haritsa
Proc. of 50th International Conference on Very Large Data Bases (VLDB), Guangzhou, China, August 2024
published as
PVLDB Journal, 17(11), August 2024, pgs. 3615-3628

Is Quantum-Based SQL Query Execution Viable?
Manish Kesarwani, and Jayant Haritsa
Proc. of 2nd International Workshop on Quantum Data Science and Management (QDSM), In Conjunction with VLDB 2024 Guangzhou, China, August 2024

Relational Database Engines on Quantum Platforms (3 hour tutorial)
Manish Kesarwani, and Jayant Haritsa
Proc. of 8th ACM India Joint Intl. Conf. on Data Science and Management of Data (CODS-COMAD 2024), Jodhpur, December 2024

Source Code
Github Repo: QIA Source Code
Tutorial Notebook: Cods Comad Tutorial hands-on session Jupyter Notebook

Contact
Email: haritsa [AT] iisc [dot] ac [dot] in

Primary Contributors (in chronological order of participation)