Academia, industry, and societies are showing increasing interest in the possibilities of quantum computing. The research in the intersection of quantum computing and databases is still in its initial steps. This work represents several crucial data management and query processing problems that will benefit from quantum computing. We outline how quantum computing will tackle these challenges and what kind of outcomes and speed-ups we expect. We discuss the position of quantum computing in data management and raise awareness of possible security threats in encryption. We aim to be realistic and point out technical dificulties that currently restrict implementations.
sides conventional CPU-based computing. Nowadays,
the most exciting computing paradigm is quantum
computing. It is based on quantum mechanics [
The quantum computers difer in their hardware. The conducting (IBM, Google, Rigetti), photonic (Xanadu), trapped ion (IonQ, Honeywell), adiabatic (D-wave), and silicon spin qubits (Intel, HRL). Amazon Braket, IBM Quantum, Xanadu, and D-wave Leap ofer access to quantum computers and simulators in the cloud. The wide variety of hardware types shows that none of the types has yet become standard, and the competition between the quantum hardware companies is still going on. The future will show which quantum computing hardware type will become dominant.
Quantum computers will not take over classical computing. Instead, they will be computing units, like GPU processors or supercomputers, along with classical computers and databases. We can send them specific and computationally complex problems. Thus the hybrid approach will be the most realistic option for practical
PhD Workshop of the 48th International Conference on Very Large
Databases (VLDB 2022)
nEvelop-O
based quantum computing is [
= |0⟩ + |1⟩, where , ∈
C are complex numbers whose norms satisfy | | 2 + || 2 = 1. The numbers and are called probability amplitudes. The requirement | | 2 + || 2 = 1 can be interpreted probabilistic way: the outcome |0⟩ is determined by the amplitude so that the probability of measuring |0⟩ is | | 2. The probability of obtaining either
In general, a quantum system consists of multiple qubits. The system usually starts from the state |00 ⋯ 0⟩.
tum logic gates to the system. Mathematically the gates are unitary matrices whose entries are complex numbers.
Finally, the system is measured and ends up in a state determined by the probabilities associated with the amplitudes. The measured outcome is the result of the algorithm, a sequence of classical bits.
Quantum annealing is similar to simulated annealing but performed on a quantum computer utilizing certain quantum mechanical phenomena. Quantum annealing is a heuristic method. To solve problems with quantum annealers, the problems are formulated in either the quadratic unconstrained binary optimization (QUBO) model or the Ising model, which are equivalent. As the damental and NP-hard computer science problems using Ising and QUBO models. That shows strong evidence that many NP-hard problems in the database field can be solved using quantum computers. lems using Ising and QUBO models is [10]. Let for = 1, … , be binary variables. Then the objective function is
∑ =1 =+1 =1 () = ∑ , + ∑ , (1) coeficients where ∈ {0, 1} and , , ∈ R for 1 ≤ , ≤ . where , ∈ R. The main goal of quantum annealing is to find a point ∗ such that ( ∗) is a global minimum of the objective function. The leading company building quantum annealers is D-wave.
lines research directions on optimizing databases with
selection, a classical database optimization problem. The lution to the problem uses dynamic programming. The current research has tackled the problem with deep reinforcement learning [12].
These kinds of combinatorically hard problems are the best match for quantum computing. Studying the problem using quantum computing, we aim to speed up the computation and improve the quality of the solution by extending the search space. formulations in [10] indicate, we can express many fun- relations 1, 2 and 3. The problem fast becomes in
The comprehensive introduction on formulating prob- the single relations and the relation 1 ⋈ 2 ⋈ 3. Although various optimization methods have been cen- is large in the problem. tral topics of database research since the beginning, there is still much room for improvement. This section out- 3.2. Size bound of conjunctive queries problem is relatively well-studied [11]. The classical so- related to information-theoretical entropy vectors. where rmax() is the largest relation in the database . The value () is a solution to a linear program that parameterized circuits for SQL queries will be trained maximizes the entropy of the variable 0 concerning cer- to estimate the query execution time, result’s size, and tain information theoretic constraints. The constraints cost. We are studying if the circuits will perform faster arise from the functional dependencies in the database . than the current estimation methods [24] and if they will Unfortunately, to obtain the optimal solution, the linear provide better-quality estimations. program has infinitely many constraints and becomes Natural continuation for this work is also express infeasible. Since the solutions to the size bounds are rep- graph and document query languages with their diagramresented as linear programs, there is already a known matic representations and study query transformations quantum algorithm [15] to solve them. between them. We have worked on data transforma
We believe that quantum computing will provide new tions [17] between relational, graph, and tree data modaspects to modeling the problem. Because the problem els. Query transformations are the next step, and they is probabilistic and classically very hard, the quantum are an essential part of multi-model databases. As catcomputing approach might produce good heuristic re- egory theory creates a consistent connection between sults and help understand the problem from a diferent schema and data [19], it will also create a solid connection angle. It is interesting to transfer the current solutions between queries and instances. Because the query transinto a quantum computing format and research possible formation depends on the database schema and instance, speed-ups and quality improvements. category theory will be a suitable theoretical framework for defining the transformations.
conceptual framework to unify and model multi-model databases using category theory [18]. Our work has been a continuation of the research, which proves that relational databases are naturally category theoretical [19]. Category theory is a meta-mathematical field of mathematics, but it also has a lot of concrete applications, which are represented, for example, at the annual Applied Category Theory conference. Multi-model databases [20] are a particular class of databases whose single, integrated backend supports multiple data models and formats. In modern data management systems, it is crucial that we can handle a wide variety of data models seamlessly.
In [21] authors develop a comprehensive diagrammatic theory to model quantum processes and quantum computing. The approach is based on category theory. Since our previous research on multi-model databases [16, 17] is also based on category theory, this approach appears promising to connect the fields theoretically. Category theory as a high-level theoretical framework is needed since quantum computers are growing, and the gatelevel design and coding of the algorithms are becoming harder. We need rigorous theoretical tools to model and design higher-level quantum computing systems, and the category theory-based approach seems to tackle the challenge well.
In [21, 22] authors use the category theory-based ideas to develop quantum natural language processing (QNLP) based on Lambek’s pregroup grammars [23] and parametrized quantum circuits. We are working on applying these diagrammatic and category theory-based methods to represent SQL queries as parameterized quantum circuits. SQL is based on context-free grammar, equivalent to pregroup grammar in a certain sense. The
in the possibilities of quantum computing. The optimization of data management and query processing will benefit from quantum computing frameworks. Although quantum computers are at an early stage, developing algorithms to tackle the presented challenges is essential.
The database community should be aware of the security threats to the encryption that quantum computing eventually will create.
This work proposes multiple research directions to study join order optimization, determine the size bound of conjunctive queries, transform queries into parametrized circuits and perform query transformations using diagrammatic formalism. Quantum computers will solve countless problems in database research, and we are excited to be part of this new research area. [4] T. Bittner, S. Groppe, Avoiding blocking by schedul- URL: https://doi.org/10.1109/FOCS.2008.43. doi:10. ing transactions using quantum annealing, in: 1109/FOCS.2008.43.
Proceedings of the 24th Symposium on Interna- [14] G. Gottlob, S. T. Lee, G. Valiant, P. Valiant, Size tional Database Engineering & Applications, IDEAS and treewidth bounds for conjunctive queries, ’20, Association for Computing Machinery, New J. ACM 59 (2012). URL: https://doi.org/10.1145/ York, NY, USA, 2020. URL: https://doi.org/10.1145/ 2220357.2220363. doi:10.1145/2220357.2220363. 3410566.3410593. doi:10.1145/3410566.3410593. [15] A. W. Harrow, A. Hassidim, S. Lloyd, Quantum [5] I. Trummer, C. Koch, Multiple query optimiza- algorithm for linear systems of equations, Phys. Rev. tion on the d-wave 2x adiabatic quantum computer, Lett. 103 (2009) 150502. URL: https://link.aps.org/ Proc. VLDB Endow. 9 (2016) 648–659. URL: https: doi/10.1103/PhysRevLett.103.150502. doi:10.1103/ //doi.org/10.14778/2947618.2947621. doi:10.14778/ PhysRevLett.103.150502.
2947618.2947621. [16] V. Uotila, J. Lu, D. Gawlick, Z. H. Liu, S. Das, [6] M. Schönberger, Applicability of quantum com- G. Pogossiants, Multicategory: Multi-model query puting on database query optimization, in: ACM processing meets category theory and functional SIGMOD Student Research Competition 2022 (un- programming, Proc. VLDB Endow. 14 (2021) dergraduate), 2022. 2663–2666. URL: https://doi.org/10.14778/3476311. [7] W. Liu, P. Gao, Z. Liu, H. Chen, M. Zhang, A 3476314. doi:10.14778/3476311.3476314. quantum-based database query scheme for pri- [17] V. Uotila, J. Lu, A formal category theoretical framevacy preservation in cloud environment, Secu- work for multi-model data transformations, in: E. K. rity and Communication Networks 2019 (2019) Rezig, V. Gadepally, T. Mattson, M. Stonebraker, 1–14. URL: http://dx.doi.org/10.1155/2019/4923590. T. Kraska, F. Wang, G. Luo, J. Kong, A. Dubovitdoi:10.1155/2019/4923590. skaya (Eds.), Heterogeneous Data Management, [8] V. Giovannetti, S. Lloyd, L. Maccone, Quantum pri- Polystores, and Analytics for Healthcare, Springer vate queries, Phys. Rev. Lett. 100 (2008) 230502. URL: International Publishing, Cham, 2021, pp. 14–28. https://link.aps.org/doi/10.1103/PhysRevLett.100. [18] E. Riehl, Category Theory in Context, Aurora: 230502. doi:10.1103/PhysRevLett.100.230502. Dover Modern Math Originals, Dover Publications, [9] G. Alagic, J. Alperin-Sherif, D. Apon, D. Cooper, 2017. URL: https://math.jhu.edu/~eriehl/context.
Q. Dang, J. Kelsey, Y.-K. Liu, C. Miller, D. Moody, pdf.
R. Peralta, R. Perlner, A. Robinson, D. Smith-Tone, [19] D. I. Spivak, Functorial data migration, 2013. Status Report on the Second Round of the NIST Post- arXiv:1009.1166.
Quantum Cryptography Standardization Process, [20] J. Lu, I. Holubová, Multi-model databases: A new NIST Internal or Interagency Report (NISTIR) 8309, journey to handle the variety of data, ACM Com2020. URL: https://csrc.nist.gov/publications/detail/ put. Surv. 52 (2019). URL: https://doi.org/10.1145/ nistir/8309/final. doi:10.6028/NIST.IR.8309. 3323214. doi:10.1145/3323214. [10] A. Lucas, Ising formulations of many np problems, [21] B. Coecke, A. Kissinger, Picturing Quantum ProFrontiers in Physics 2 (2014). URL: http://dx.doi.org/ cesses: A First Course in Quantum Theory and 10.3389/fphy.2014.00005. doi:10.3389/fphy.2014. Diagrammatic Reasoning, Cambridge University 00005. Press, 2017. doi:10.1017/9781316219317. [11] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, [22] R. Piedeleu, D. Kartsaklis, B. Coecke, M. Sadrzadeh, R. A. Lorie, T. G. Price, Access path selection in a Open system categorical quantum semantics in natrelational database management system, in: Pro- ural language processing, arXiv:1502.00831 [cs, ceedings of the 1979 ACM SIGMOD International math] (2015). URL: http://arxiv.org/abs/1502.00831, Conference on Management of Data, SIGMOD ’79, arXiv: 1502.00831.
Association for Computing Machinery, New York, [23] J. Lambek, Type Grammar Revisited, volume 1582 NY, USA, 1979, p. 23–34. URL: https://doi.org/10. of Lecture Notes in Computer Science, Springer 1145/582095.582099. doi:10.1145/582095.582099. Berlin Heidelberg, 1999, p. 1–27. URL: http:// [12] S. Krishnan, Z. Yang, K. Goldberg, J. Heller- link.springer.com/10.1007/3-540-48975-4_1. doi:10. stein, I. Stoica, Learning to optimize join 1007/3-540-48975-4_1. queries with deep reinforcement learning, 2019. [24] H. Lan, Z. Bao, Y. Peng, A survey on advancarXiv:1808.03196. ing the dbms query optimizer: Cardinality esti[13] A. Atserias, M. Grohe, D. Marx, Size bounds mation, cost model, and plan enumeration, Data and query plans for relational joins, in: Proceed- Science and Engineering 6 (2021) 86–101. doi:10. ings of the 2008 49th Annual IEEE Symposium 1007/s41019-020-00149-7. on Foundations of Computer Science, FOCS ’08, IEEE Computer Society, USA, 2008, p. 739–748.