Leveraging Quantum Computing for Database Index Selection
Immanuel Trummer, Davide Venturelli · 2024
We present an approach to solve the NP-hard database index selection problem on a D-Wave 2X adiabatic quantum annealer with over 1000 qubits. One of our main contributions is an efficient algorithm that maps instances of the index selection problem onto the qubits of the quantum annealer. Our mapping algorithm introduces several novel techniques that have not been used in the context of quantum annealing so far. Compared to prior approaches, we exploit qubits more efficiently which increases the size of the problem instances that can be represented with the given number of qubits by orders of magnitude. Furthermore, our algorithm decreases mapping time by many orders of magnitude compared to prior methods. The fundamental ideas that we present in this paper are applicable to similar optimization problems (e.g., other database related tuning problems). We analyze our algorithm formally and present experimental results on a real quantum annealer located at NASA Ames Research Center in California.