Where Quantum Actually Meets the Database (and Where It Doesn’t)
Quantum computing might be the most famous technology that almost nobody has actually used. It shows up in movie plots, in nervous headlines about “the end of encryption,” and in the occasional promise that it will soon cure diseases, design new materials, and untangle city traffic, all at once. If you have heard exactly one thing about it, it is probably the box with the cat that is somehow alive and dead at the same time (the Schrödinger cat). If you have heard two things, the second is probably that a quantum computer will one day crack the password protecting your bank account.
Lately, the excitement around quantum computing has reached our database community, and it raises a natural question: Can quantum computing help our database systems? The real answer is more modest than the hype suggests, but also more concrete than the skeptics assume. In this post, I try to pin down exactly where it is real.
First, what quantum is good at for databases
Database systems perform many different kinds of work, but quantum computing is not equally suited to all of them. Its clearest potential lies in optimization problems where a small input gives rise to an enormous number of possible solutions. Join ordering, index selection, workload optimization, and transaction scheduling all have this shape. To understand why quantum computing may help with these problems, we first need a brief look at what makes it different from classical computing.
A classical computer stores bits, and each bit is either a 0 or a 1. A quantum computer instead stores qubits, and a qubit can hold a blend of 0 and 1 at the same time. A coin is a good way to picture this. A classical bit is a coin lying flat, showing heads or tails. A qubit is a coin spinning in the air, in a blend of both at once, and it becomes definitely heads or tails only when it lands, which is the moment we measure it. That spinning blend is called superposition. Qubits can also be linked, so that measuring one instantly tells you something about another. This property is called entanglement, and even Einstein found it spooky. Together, these two properties allow quantum algorithms to explore large spaces of possible solutions in ways that classical bits cannot. With n classical bits, you can store exactly one of the 2^n possible patterns at any instant. With n qubits, you can hold a weighted blend of all 2^n at once, and entanglement lets those possibilities interfere and reinforce one another. A quantum algorithm is designed so that paths leading to wrong answers cancel out, while paths leading to right answers reinforce. The correct result is then far more likely to appear when we finally measure. There is a catch, though. Qubits are fragile. They lose their delicate state to heat, stray fields, and other noise, an effect called decoherence, and every operation adds a little error. On today’s hardware, these errors pile up quickly, which is why a real quantum computer is far less reliable than the clean picture above.
Two algorithms, both introduced a few decades ago, are responsible for most of the excitement about quantum computing. Grover’s search [1] looks for a marked item in a completely unstructured space of N candidates. It finds that item in about the square root of N tries, a quadratic speedup over the roughly N tries a classical scan needs in the worst case. Despite its name and its superficial resemblance to database search, Grover’s algorithm does not mean that a quantum computer can simply replace a database index or accelerate an ordinary table scan. Loading database records into a quantum device and retrieving the result introduce fundamental practical limitations. Shor’s algorithm [2] factors a large integer in time that grows only polynomially with the number’s size. That is exponentially faster than the best classical methods we know, and it is what threatens the RSA-style encryption that protects your bank details. Both algorithms are backed by real mathematics. However, both also assume a large-scale, reliable, error-corrected quantum computer that does not quite exist yet.
But you do not need a full universal quantum computer to attack an optimization problem. Two nearer-term styles do exactly that. “Quantum annealing” takes a hard optimization problem with many discrete choices and encodes it as an energy landscape. The hardware then settles into a low valley that corresponds to a good, near-optimal solution. One phenomenon of quantum annealing is worth knowing here: quantum tunneling. A classical search, like simulated annealing, has to climb over a tall hill to escape a bad solution. A quantum system can pass straight through the hill instead, slipping out of the local traps that stall ordinary methods. “Variational methods”, such as QAOA, take a different route. They run a small, tunable quantum circuit on a gate-based device, while a classical optimizer adjusts its knobs round after round toward a good solution. These two paradigms differ in how easily they fit inside a real-time system today. A quantum annealer returns many candidate solutions in a single quick call, which suits tight time budgets. A variational method needs many circuit runs inside a classical optimization loop, so it is more flexible but, for now, slower to drop into a live query engine. When you read “quantum for databases” these days, it almost always means annealing or variational methods, not the far-off universal gate-based dream. That is no accident: databases are full of hard combinatorial optimization problems, which is exactly what these methods target. As error correction matures, general gate-based computing may bring a wider range of database problems within reach. For now, though, hybrid classical-quantum optimization is where the practical work happens.
The best way to think about exploiting quantum computing in a database system today is as an “accelerator,” similar to today’s CPU-GPU computation model. There, the CPU stays in charge and offloads its most compute-heavy, data-parallel kernels to a GPU that is built for exactly that kind of work. A quantum optimizer can play the same role for a database engine, taking on hard optimization sub-problems while the classical engine runs everything else. Now, let’s look at where this accelerator genuinely helps, and then turn to where it does not.
What is real
Quantum machines are bad at taking in large amounts of data, but many of our hardest database optimization problems are not about large data at all. They start from a small input and blow up into a huge search space. Join order optimization is the standard example: the input consists of just a few tables and some statistics, yet the number of possible plans grows exponentially as tables are added. Reusing shared work across many queries, picking a set of indexes under a storage budget, and scheduling transactions all look the same way: a small input with an enormous number of ways to arrange it. This is exactly the shape quantum optimization is built for. But the device cannot read a query plan directly, so you first represent the problem in a form the hardware understands. For example, with annealers, that form is called QUBO, short for Quadratic Unconstrained Binary Optimization. Each decision becomes a 0/1 variable, and the cost you want to minimize becomes a sum of penalties over those variables and their pairs (i.e., correlations). A low-cost setting of the variables then corresponds to a good plan. Variational methods encode the same kind of objective for gate-based hardware.
Importantly, this line of research has progressed from problem formulations and isolated evaluations toward real-hardware integration. Earlier work mapped multiple-query optimization to a formulation suitable for D-Wave annealers [5], while subsequent studies explored quantum approaches to query optimization and transaction scheduling more broadly [6]. Today, a D-Wave annealer with more than 5,000 qubits is accessible through the cloud, so hardware access is no longer the main obstacle. The harder question is whether the gains survive after the method is integrated into a real engine and all overhead is counted. The QDBO prototype [3] takes a step in this direction by integrating a quantum-augmented optimizer directly with PostgreSQL. It casts each optimization task into QUBO form and refines the answer using the annealer’s sampling feedback. As one example, on the Cardinality Estimation Benchmark, QDBO achieved up to 49 times execution-time speedup and up to 37 times end-to-end speedup, including quantum and cloud overhead. These results simply show that “faster end to end, inside a real engine, on real hardware” is now something we can actually achieve.
What is still hard
The quantum-based results are promising, but they remain demonstrations rather than large-scale deployments. Turning a working demo into a production system means addressing problems that the excitement usually skips over. Here, I lay out three challenges that keep coming up when we put quantum computing to work inside database systems. What strikes me about all three is that they are database problems more than quantum-hardware problems.
The first is controlling the hybrid classical-quantum workflow. The easy approach to performing quantum optimization is to use a hosted, black-box quantum solver (e.g., D-Wave’s Stride or Amazon’s Braket). You hand over the optimization problem and get an answer back, with no view into what the service does internally, how long it runs on the quantum processor (QPU), or how it arrives at the final answer. Some services even enforce a minimum response time of several seconds, which is a non-starter for a query planner that has milliseconds to spend. The alternative is to run the loop yourself, choosing how to sample and how to spend a time budget you can adjust on the fly. QDBO [3] demonstrated that, by driving the quantum sampling directly, you can outperform the vendor’s black-box solver and stay within a real latency budget. However, this work only scratched the surface, and a general way to trade solution quality for time across many kinds of queries is still missing. Transparency here is not good manners; it is the performance lever.
The second is scalability, which really turns out to be a consistency problem. For example, a 50-relation join already needs more than 10,000 optimization variables to be mapped to qubits, while the largest annealer offers only about 5,000 qubits, still far more than gate-based models provide. So the whole problem will not fit on the machine at once. You have to break it into smaller sub-problems that do fit, solve each one, and stitch the answers back together. The final quality then depends less on solving each piece well than on how carefully you handle the boundaries where the pieces meet. Getting that global consistency right, rather than just optimizing fragments, is an open problem. It is one that databases have long experience with.
The third is data management, which is where our field’s instincts help most directly. A single quantum run produces information worth keeping: how a large problem was broken up, which optimization variable was mapped to which qubit, and the partial results that came back. Today, all of that is thrown away between runs. Treated instead like reusable materialized views or caches, that information could be maintained, looked up, and reused whenever a later problem overlaps with an earlier one. The optimizer could then skip work it has already done, and the scheduler could load a prepared mapping instead of rebuilding it. Intermediate quantum-workflow data deserves real storage management, not a temporary file.
Underneath all three challenges sits one blunt measurement, and it is why I keep calling this an integration problem rather than a hardware one. In one of our query-optimization runs [4], a single call to the quantum optimizer took about 3,200 milliseconds end to end, from the database sending the problem to getting a plan back. Of that time, the quantum processor itself was busy for well under 100 milliseconds. Almost all the rest went to cloud communication and classical solving. The quantum device is not the bottleneck. The round trips and orchestration around it are, and those are ours to fix.
The quantum hardware is not standing still either. Two advances now taking shape will widen what quantum can reach for databases, and both are worth watching today, not in ten years. The first is “quantum error correction”, which bundles many noisy physical qubits into a single, more reliable one. Recent hardware milestones suggest the field is turning the corner. As reliable qubits arrive, the fragile gate-based machines become real candidates, and the range of database problems quantum computing can touch grows well beyond annealing-friendly optimization. The second is “distributed quantum computing”, which links several processors into one larger fabric, much as we once networked classical machines. It would lift the qubit ceiling that limits problem size today and bring larger join graphs and workload-wide index tuning into range. Neither is here at full strength nowadays, but both are close enough to plan for.
The other direction, briefly
So far, I have focused on quantum for databases. There are also research opportunities in the reverse direction, databases for quantum. Because large error-corrected machines do not yet exist, we rely on classical computers to simulate and prepare quantum circuits, and it turns out that database techniques can help. Mapping quantum states and operations onto relational queries, and using query processing to drive circuit simulation and transpilation, are real and useful ideas [7]. Earlier work also explored representing relational data and relational operations in quantum form [8], although measurement remains a deep obstacle because reading a quantum state changes it. This direction is genuinely interesting, and I invite our community to explore it.
Open questions
Let me end with a few questions that are still open, the ones I encourage our community to help answer.
Where does quantum genuinely help data management beyond join ordering? Optimization is the beachhead. Is there a second one, perhaps privacy primitives with no classical analogue, or sampling for approximate query processing, that clears the same end-to-end bar?
Which database problems are honestly poor matches? Anything that needs large concrete data loaded into the device seems disqualified. What else belongs on the “do not bother” list, and can we agree on it so that students stop rediscovering it the hard way?
What should a fair benchmark measure? If a better formulation score is the wrong metric and end-to-end latency in a real DBMS is the right one, then who builds the shared benchmark that lets us compare quantum, classical, and learned methods on equal footing?
Which of our own methods could help the quantum side? Cost-based optimization, materialized views, adaptive query processing? How many of these transfer directly to orchestrating quantum workloads?
My bet is that the next real progress here will not come from waiting for a quantum machine that makes integration unnecessary. It will come from database people treating the quantum processor as one more accelerator to integrate well, the way we once learned to use any hardware accelerator (e.g., GPUs, TPUs). If that is right, the work in front of us is familiar work.
References
[1] Lov K. Grover. “A fast quantum mechanical algorithm for database search.” In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC ’96), pages 212-219, 1996.
[2] Peter W. Shor. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Journal on Computing, 26(5):1484-1509, 1997. (Earlier version in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), 1994.)
[3] Hanwen Liu, Abhishek Kumar, Federico Spedalieri, and Ibrahim Sabek. “QDBO: A Real-time Quantum-augmented Database System Optimizer.” Proceedings of the VLDB Endowment (PVLDB), 19(11):3606-3620, 2026.
[4] Hanwen Liu and Ibrahim Sabek. “Towards a Hybrid Quantum-Classical Computing Framework for Database Optimization Problems in a Real-Time Setup.” In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2026.
[5] Immanuel Trummer and Christoph Koch. “Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer.” Proceedings of the VLDB Endowment (PVLDB), 9(9):648-659, 2016.
[6] Umut Çalikyilmaz, Sven Groppe, Jinghua Groppe, Tobias Winker, Stefan Prestel, Farida Shagieva, Daanish Arya, Florian Preis, and Le Gruenwald. “Opportunities for Quantum Acceleration of Databases: Optimization of Queries and Transaction Schedules.” Proceedings of the VLDB Endowment (PVLDB), 16(9):2344-2353, 2023.
[7] Andrei Ilinescu, Aadi Patwardhan, and Rihan Hai. “InferQ: A Database-Oriented Benchmark for Quantum Circuits Simulation.” Proceedings of the ACM on Management of Data (SIGMOD), 4(4), 2026.
[8] Paul Cockshott. “Quantum Relational Databases.” arXiv:quant-ph/9712025, 1997.
Author Bio: Ibrahim Sabek is an Assistant Professor of Computer Science at the University of Southern California. He leads the Next-generation Data-Intensive Systems Group (NexDIG), where his research focuses on building the next generation of data management, processing, and analysis systems using quantum computing and machine learning. Before joining USC, Ibrahim was a Postdoctoral Associate with the MIT Data Systems Group. He earned his PhD in Computer Science from the University of Minnesota. His research has been recognized with several awards and honors, including the 2026 NSF CAREER Award, the 2025 Google ML and Systems Junior Faculty Award, the 2024 and 2025 Google Data Analytics and Insights (DANI) Awards, and the NSF Computing Innovation Fellowship (2020-2023), among others. For more information, please visit his website: https://viterbi-web.usc.edu/~sabek/.