Multiple Query Optimization Using a Gate-Based Quantum Computer
Open Access
- 12 October 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 11, 114031-114043
Abstract
Quantum computing promises to solve difficult optimization problems in chemistry, physics and mathematics more efficiently than classical computers. However, it requires fault-tolerant quantum computers with millions of qubits; a technological challenge still not mastered by engineers. To lower the barrier, hybrid algorithms combining classical and quantum computers are used, where quantum computing is only used for those parts of computation that cannot be solved efficiently otherwise. In this paper, we tackle the multiple query optimization problem (MQO), an important NP-hard problem in database research. We present an implementation based on a scheme called quantum approximate optimization algorithm to solve the MQO on a gate-based quantum computer. We perform a detailed experimental evaluation of our implementation and compare its performance against a competing approach that employs a quantum annealer – another type of quantum computer. Our implementation shows a qubit efficiency of close to 99%, which is almost a factor of 2 higher than the state-of-the-art implementation. We emphasize that the problems we can solve with current gate-based quantum technology are fairly small and might not seem practical yet compared to state-of-the-art classical query optimizers. However, our experiments on using a hybrid approach of classical and quantum computing show that our implementation scales favourably with larger problem sizes. Hence, we conclude that our approach shows promising results for near-term quantum computers and thus sets the stage for a challenging avenue of novel database research.Keywords
Funding Information
- Zurich University of Applied Sciences
This publication has 32 references indexed in Scilit:
- A variational eigenvalue solver on a photonic quantum processorNature Communications, 2014
- Ising formulations of many NP problemsFrontiers in Physics, 2014
- Adiabatic quantum programming: minor embedding with hard faultsQuantum Information Processing, 2013
- Colloquium: Quantum annealing and analog quantum computationReviews of Modern Physics, 2008
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete ProblemScience, 2001
- Two-bit gates are universal for quantum computationPhysical Review A, 1995
- On the multiple-query optimization problemIEEE Transactions on Knowledge and Data Engineering, 1990
- Access Path Selection in a Relational Database Management System1989
- Multiple-query optimizationACM Transactions on Database Systems, 1988
- Beweis des AdiabatensatzesThe European Physical Journal A, 1928