Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM SIGMOD International Conference on Management of Data (SIGMOD)

Applicability of Quantum Computing on Database Query Optimization

Manuel Schönberger

Published Jun 10, 2022• 25 citations
Publisher

Abstract

We evaluate the applicability of quantum computing on two fundamental query optimization problems, join order optimization and multi query optimization (MQO). We analyze the problem dimensions that can be solved on current gate-based quantum systems and quantum annealers, the two currently commercially available architectures.
DOI
10.1145/3514221.3520257

Related papers

Multiple Query Optimization Using a Gate-Based Quantum Computer

Tobias Fankhauser, Marc E. Solèr, Rudolf Marcel Füchslin +1 more

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.

IEEE Access•Jan 1, 2023•17 citations

Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing

Tobias Fankhauser, Marc E. Solèr, Rudolf Marcel Füchslin +1 more

Quantum computing promises to solve difficult optimization problems in chemistry, physics and mathematics more efficiently than classical computers, but requires fault-tolerant quantum computers with millions of qubits. To overcome errors introduced by today's quantum computers, hybrid algorithms combining classical and quantum computers are used. In this paper we tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems. We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer. We perform a detailed experimental evaluation of our algorithm and compare its performance against a competing approach that employs a quantum annealer -- another type of quantum computer. Our experimental results demonstrate that our algorithm currently can only handle small problem sizes due to the limited number of qubits available on a gate-based quantum computer compared to a quantum computer based on quantum annealing. However, our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation. Finally, we analyze how our algorithm scales with larger problem sizes and conclude that our approach shows promising results for near-term quantum computers.

arXiv:2107.10508•Jul 22, 2021•5 citations

Quantum Computing for Query Containment of Conjunctive Queries

Luisa Gerlach, Tobias Köppl, René Zander +2 more

We address the problem of checking query containment, a foundational problem in database research. Although extensively studied in theory research, optimization opportunities arising from query containment are not fully leveraged in commercial database systems, due to the high computational complexity and sometimes even undecidability of the underlying decision problem. In this article, we present the first approach to applying quantum computing to the query containment problem for conjunctive queries under set semantics. We propose a novel formulation as an optimization problem that can be solved on gate-based quantum hardware, and in some cases directly maps to quantum annealers. We formally prove this formulation to be correct and present a prototype implementation which we evaluate using simulator software as well as quantum devices. Our experiments successfully demonstrate that our approach is sound and scales within the current limitations of quantum hardware. In doing so, we show that quantum optimization can effectively address this problem. Thereby, we contribute a new computational perspective on the query containment problem.

arXiv:2602.21803•Feb 25, 2026•0 citations

Is Quantum Computing Ready for Real-Time Database Optimization?

Hanwen Liu, Ibrahim Sabek

Database systems encompass several performance-critical optimization tasks, such as join ordering and index tuning. As data volumes grow and workloads become more complex, these problems have become exponentially harder to solve efficiently. Quantum computing, especially quantum annealing, is a promising paradigm that can efficiently explore very large search spaces through quantum tunneling. It can escape local optima by tunneling through energy barriers rather than climbing over them. Earlier works mainly focused on providing an abstract representation (e.g., Quadratic Unconstrained Binary Optimization (QUBO)) for the database optimization problems (e.g., join order) and overlooked the real integration within database systems due to the high overhead of quantum computing services (e.g., a minimum 5s runtime for D-Wave's CQM-Solver). Recently, quantum annealing providers have offered more low-latency solutions, e.g., NL-Solver, which paves the road to actually realizing quantum solutions within DBMSs. However, this raises new systems research challenges in balancing efficiency and solution quality. In this talk, we show that this balance is possible to achieve. As a proof of concept, we present Q2O, the first real Quantum-augmented Query Optimizer. We show the end-to-end workflow: we encode the join order problem as a nonlinear model, a format solvable by the NL-Solver, using actual database statistics; the solution is translated into a plan hint that guides PostgreSQL's optimizer to produce a complete plan. Q2O is capable of handling actual queries in real time.

arXiv:2601.12123•IEEE International Conference on Data Engineering (ICDE)•May 1, 2026•2 citations

Relational Database Engines on Quantum Platforms: Concepts, Algorithms, and Implementations

Manish Kesarwani, Jayant R. Haritsa

Recent advances in quantum computing have led to early-stage platforms with over 1,000 qubits, alongside roadmaps targeting fault-tolerant, industry-scale systems within this decade. To harness the immense potential of these emerging systems, it is essential to explore the feasibility of hosting relational database engines on quantum platforms. Encouragingly, several early studies have already investigated the applicability of quantum computing to core DBMS components such as multi-query optimization, join-order optimization and index-configuration selection offering initial insights into key challenges and practical implementation considerations.

ACM SIGMOD International Conference on Management of Data (SIGMOD)•May 26, 2026•1 citation

Opportunities for Quantum Acceleration of Databases: Optimization of Queries and Transaction Schedules

Umut Çalıkyılmaz, Sven Groppe, Jinghua Groppe +6 more

The capabilities of quantum computers, such as the number of supported qubits and maximum circuit depth, have grown exponentially in recent years. Commercially relevant applications that take advantage of quantum computing are expected to be available soon. In this paper, we shed light on the possibilities of accelerating database tasks using quantum computing with examples of optimizing queries and transaction schedules and present some open challenges for future studies in the field.

Proceedings of the VLDB Endowment•May 1, 2023•28 citations
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.
Quantum computing promises to solve difficult optimization problems in chemistry, physics and mathematics more efficiently than classical computers, but requires fault-tolerant quantum computers with millions of qubits. To overcome errors introduced by today's quantum computers, hybrid algorithms combining classical and quantum computers are used. In this paper we tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems. We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer. We perform a detailed experimental evaluation of our algorithm and compare its performance against a competing approach that employs a quantum annealer -- another type of quantum computer. Our experimental results demonstrate that our algorithm currently can only handle small problem sizes due to the limited number of qubits available on a gate-based quantum computer compared to a quantum computer based on quantum annealing. However, our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation. Finally, we analyze how our algorithm scales with larger problem sizes and conclude that our approach shows promising results for near-term quantum computers.
We address the problem of checking query containment, a foundational problem in database research. Although extensively studied in theory research, optimization opportunities arising from query containment are not fully leveraged in commercial database systems, due to the high computational complexity and sometimes even undecidability of the underlying decision problem. In this article, we present the first approach to applying quantum computing to the query containment problem for conjunctive queries under set semantics. We propose a novel formulation as an optimization problem that can be solved on gate-based quantum hardware, and in some cases directly maps to quantum annealers. We formally prove this formulation to be correct and present a prototype implementation which we evaluate using simulator software as well as quantum devices. Our experiments successfully demonstrate that our approach is sound and scales within the current limitations of quantum hardware. In doing so, we show that quantum optimization can effectively address this problem. Thereby, we contribute a new computational perspective on the query containment problem.
Database systems encompass several performance-critical optimization tasks, such as join ordering and index tuning. As data volumes grow and workloads become more complex, these problems have become exponentially harder to solve efficiently. Quantum computing, especially quantum annealing, is a promising paradigm that can efficiently explore very large search spaces through quantum tunneling. It can escape local optima by tunneling through energy barriers rather than climbing over them. Earlier works mainly focused on providing an abstract representation (e.g., Quadratic Unconstrained Binary Optimization (QUBO)) for the database optimization problems (e.g., join order) and overlooked the real integration within database systems due to the high overhead of quantum computing services (e.g., a minimum 5s runtime for D-Wave's CQM-Solver). Recently, quantum annealing providers have offered more low-latency solutions, e.g., NL-Solver, which paves the road to actually realizing quantum solutions within DBMSs. However, this raises new systems research challenges in balancing efficiency and solution quality. In this talk, we show that this balance is possible to achieve. As a proof of concept, we present Q2O, the first real Quantum-augmented Query Optimizer. We show the end-to-end workflow: we encode the join order problem as a nonlinear model, a format solvable by the NL-Solver, using actual database statistics; the solution is translated into a plan hint that guides PostgreSQL's optimizer to produce a complete plan. Q2O is capable of handling actual queries in real time.
Recent advances in quantum computing have led to early-stage platforms with over 1,000 qubits, alongside roadmaps targeting fault-tolerant, industry-scale systems within this decade. To harness the immense potential of these emerging systems, it is essential to explore the feasibility of hosting relational database engines on quantum platforms. Encouragingly, several early studies have already investigated the applicability of quantum computing to core DBMS components such as multi-query optimization, join-order optimization and index-configuration selection offering initial insights into key challenges and practical implementation considerations.