# Quantum Data Management: From Theory to Opportunities

Rihan Hai  Web Information Systems Group
Delft University of Technology
<EMAIL_ADDRESS>Shih-Han Hung  Institute of Information Science
Academia Sinica
<EMAIL_ADDRESS>Sebastian Feld  Quantum Machine Learning Group
Delft University of Technology
<EMAIL_ADDRESS>
###### Abstract

Quantum computing has emerged as a transformative tool for future data
management. Classical problems in database domains, including query
optimization, data integration, and transaction management, have recently been
addressed using quantum computing techniques. This tutorial aims to establish
the theoretical foundation essential for enhancing methodologies and practical
implementations in this line of research. Moreover, this tutorial takes a
forward-looking approach by delving into recent strides in quantum internet
technologies and the nonlocality theory. We aim to shed light on the uncharted
territory of future data systems tailored for the quantum internet.

##  I Introduction

In recent years, the realm of computer science has been abuzz with the
potential of quantum mechanics. Quantum computing, which leverages the
principles of superposition and entanglement, promises computational
capacities far beyond what traditional computers can achieve [1]. Moreover,
the _quantum internet_ holds the potential to offer advantages and
capabilities beyond the power of classical internet systems, e.g., secure
communication [2] or distributed computing [3]. A quantum internet is a
network connecting end nodes that range from simple quantum devices with one
qubit to large-scale quantum computers [4]. Recent studies showed the
possibility of real-world quantum internet in the scale of kilometers, e.g.,
248 kilometers realized using optical fiber [5] and 1203 kilometers with
satellite [6]. One vision is that there will be cloud data centers across
continents linked by quantum internet, with quantum entanglement promising
instantaneous, consistent, and ultimately secure data transmission.

Since the 1960s, database systems have evolved significantly, transitioning
from early hierarchical and network models to the widespread adoption of the
relational model [7] and relational databases in the 70s-80s. With the birth
of the World Wide Web and the surge of web-based applications in the 90s, we
witnessed the rise of distributed databases and object-oriented databases [8,
9]. In the 2010s, the emergence of big data technologies, NoSQL databases, and
cloud computing further reshaped the landscape of data management [10]. As
data continues to grow drastically in both volume and variety, the
conventional means of data management will eventually hit the ceiling. Quantum
computing, with its revolutionary potential, positions itself as a pivotal
future technology in the ongoing evolution of data management systems.

With the rapid advancement and increasing accessibility of quantum computing
technologies [11, 12, 13, 14], a pressing need arises to understand the
intricacies of data management using quantum computers and the quantum
internet. Guaranteeing the management and accessibility of data within a
quantum computing environment is prominent. This requires understanding and
utilizing the innovations of quantum technologies. Even further, it calls for
a fundamental rethinking of data handling and management paradigms. _Entering
the era of quantum computing, what is the future of data management?_

Figure 1: (a) Cloud quantum computer222Quantum Inspire (www.quantum-
inspire.com). Photo taken by Marieke de Lorijn for QuTech.at QuTech, TU Delft.
(b) A five-qubit quantum chip using superconducting technology [15]. (c) The
basic unit of a quantum internet: end nodes (quantum devices) and a repeater.
The repeater establishes quantum entanglement (yellow lines) with each end
node, enabling data transmission through quantum teleportation [2].

##  II Fundamentals of quantum computing

We will start the tutorial by introducing the basic concepts of quantum
computing [1] related to our discussion in Sec. III-IV. For understandability,
we introduce below qubits with their analogous concept in classical
computation, i.e., bits. We explain qubits at the abstract mathematical level,
such that it is general for diverse software and hardware realization.

###  II-A Basics: qubit, superposition, and entanglement

Quantum bit, or qubit, is the fundamental concept of quantum computing.
Classical computers use binary digits, bits, as the basic unit of information,
which can exist in one of two states: 0 or 1. Similarly, two basic states for
a qubit are $\ket{0}$ and $\ket{1}$. To represent the state of a quantum
system, the term _ket_ is used, denoted with the Dirac notation $\ket{\ }$.

Superposition. The first difference between a classical and quantum bit is: a
classical bit can only be 0 or 1, like a coin with a head or tail; but a qubit
can exist in a _superposition_ of $\ket{0}$ and $\ket{1}$ at the same time.
Mathematically, the superposition of a qubit is represented using the linear
combination of basic states $\ket{0}$ and $\ket{1}$:

$\vspace{-0.1cm}\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$

Here, $\ket{\psi}$ is the state of the qubit with $\alpha$ and $\beta$ being
complex numbers. $\alpha\ket{0}+\beta\ket{1}$ means that a qubit would be
measured as 0 with the probability of $\left|\alpha\right|^{2}$ and 1 with the
probability of $\left|\beta\right|^{2}$.

######  Example II.1.

Consider the qubit in the following superposition:

$\ket{\psi}=\frac{1}{\sqrt{2}}\ket{0}+\frac{1}{\sqrt{2}}\ket{1}$

When measuring this qubit, there is an equal probability of 50%
($\left|\alpha\right|^{2}=\left|\beta\right|^{2}=\frac{1}{2}$) to get a 0 or 1
as a result.

Entanglement. Another difference between qubits and bits is _entanglement_
[16, 17], referred to as the _spooky action at a distance_ by Einstein.

Imagine two qubits with qubit A being in Amsterdam and qubit B in San
Francisco. When qubit A and qubit B are entangled this means their states are
correlated. The _spooky_ part is that if we measure qubit A in Amsterdam and
find it in a state of 0 (or 1), we instantaneously know the state of qubit B
is 0 (or 1), even though it is far away in San Francisco. This correlation is
maintained independently of the physical distance between them.

We can consider entangled qubits as a valuable resource in quantum computing
[1], which cannot be provided by classical bits. This shared state allows
quantum computers to process information in ways that classical computers
cannot. A quantum computer with several entangled qubits in superposition can
be processed in a single operation, providing a significant advantage for
certain problems, e.g., factoring large numbers [18] or searching unsorted
databases [19].

TABLE I: Recent data management works using quantum computers: an overview Reference | DB problem | Subproblem | Formulation |  | Intermediate
---
quantum algorithm
Quantum computer
[20] | Query optimization |  Multiple query optimization (MQO) | QUBO | – | Annealing-based
[21, 22] | QAOA | Gate-based
[23, 24, 25] | Join ordering (JO) | QAOA | Gate-based & annealing-based
[26] | QAOA, VQE | Gate-based & annealing-based
[27] | – | VQC | Gate-based
[28] | Data integration | Schema matching | QUBO | QAOA | Gate-based & annealing-based
[29, 30, 31] | Transaction management | Two-phase locking | QUBO | – | Annealing-based

###  II-B Quantum computers and libraries

Architecture. Quantum computers come in various models, using different
approaches to maintain and manipulate the quantum state of qubits, and are
suitable for specific tasks. The most important types of quantum computers
include quantum annealers and physical systems for implementing gate-based
models such as trapped-ion quantum computers, superconducting qubits,
topological quantum computers, and photonic quantum computers. In the
tutorial, we will cover both quantum annealers and gate-based models, which
are utilized in existing works (cf. Table I). Quantum annealers are designed
to solve optimization problems by finding the lowest energy state of a system,
which should correspond to the optimal solution. Quantum annealers can
currently be built with more qubits than other existing types of quantum
computers, e.g., 5000-qubit D-Wave Advantage quantum annealing processor [32].
Gate-based models are universal, i.e., they are in theory capable of
performing any computational task that can be executed on a classical
computer, but potentially more efficient for certain problems.

Open-source libraries. For developing applications on quantum computers, key
resources include open-source toolkits like IBM’s Qiskit333
https://qiskit.org/, Microsoft’s QDK444https://learn.microsoft.com/en-
us/azure/quantum/overview-what-is-qsharp-and-qdk, and Python libraries such as
Google’s Cirq555https://github.com/quantumlib/Cirq, Amazon’s OQpy666
https://github.com/openqasm/oqpy, TU Delft’s
OpenQL777https://openql.readthedocs.io/en/latest/, and
Qibo888https://github.com/qiboteam/qibo.

##  III Data management using quantum computers

When it comes to quantum computing applied to data management, we are still in
the nascent stages. Pioneering efforts have been made in both the theoretical
design and early prototyping of database problems for quantum computers, which
we briefly explain in Sec. III-A.

In Table I, more recent works cover essential data management topics such as
query optimization [20, 21, 22, 23, 24, 25, 26, 27], data integration [28],
and transaction management [29, 31, 30]. The general methodology is to map a
data management problem to a mathematical formulation solvable by a quantum
computer. These works, despite solving different problems each, are mostly
mapped a so-called _quadratic unconstrained binary optimization_ (QUBO)
problem. For quantum computing, currently, QUBO is one of the most widely
applied optimization models [33]. During the tutorial, we will elaborate on
the existing attempts summarized in Table I. In Sec. III-B, we discuss the
query optimization problem, which is one of the cornerstones of database
research.

###  III-A Quantum database search and query complexity

A _database_ is a collection of data stored electronically in a computer
system [34, 35]. In the context of data management, we discuss data
complexity, and combined complexity of evaluating database queries [36, 37],
e.g., conjunctive queries, in terms of the sizes of input database instances
and queries.

In the context of quantum computing, a “quantum database” is a conceptual
framework for processing and searching data using quantum algorithms. These
algorithms leverage quantum mechanics to address specific problems more
efficiently than classical approaches. In this context, a key metric for
comparing the computational efficiency of quantum and classical algorithms is
_query complexity_ [38]. Consider a database with $N=2^{n}$ records, in which
each record is identified by an $n$-bit integer label (e.g., “010” for a 3-bit
label). The goal is to find a target record $x_{0}$ using a binary function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, where

$\displaystyle\vspace{-0.6cm}\begin{split}f(x)=\begin{cases}1,&\text{if
$x=x_{0}$ }\\\ 0,&\text{otherwise}\end{cases}\end{split}\vspace{-0.2cm}$

A quantum algorithm’s efficiency can be measured by its query complexity,
i.e., how many times it queries this function $f(x)$. One of the most well-
known algorithms demonstrating quantum speedup is _Grover’s algorithm_ [19].
To search a specific record in an unsorted database of $N$ records, classical
algorithms require $O(N)$ operations, while Grover’s algorithm achieves this
in $O(\sqrt{N})$ operations. Grover’s algorithm has inspired early research
into quantum algorithms for searching databases [39, 40, 41, 42, 43, 44].
Moreover, efforts have been made to develop quantum query languages akin to
SQL for classical databases, covering basic operations: join and set
operations (intersection, union, difference) [45, 46, 47, 48, 49, 50], and
data manipulation operations (insert, update, delete) [46, 51, 49].

###  III-B Query optimization

Recent quantum-related works mainly tackled two subproblems of query
optimization: multiple query optimization (MQO) and join ordering (JO).

Multiple query optimization studies how to choose query plans given a set of
queries [52], which is NP-hard. As one of the earliest attempts to study the
MQO problem with modern quantum computers, Trummer et al. proposed in 2016 a
method using the D-Wave 2X annealing-based quantum computer [20]. The proposed
method includes logical and physical mapping. At the logical level, it
transforms the MQO problem to a QUBO formulation, guaranteeing each query has
one query plan selected while minimizing the time-wise efficiency. At the
physical level, the logical formula of QUBO is further transformed to the
energy formula coherent with the physical design of the quantum computer [53].
The experiments demonstrated 1000x speedup on quantum annealer compared to
state-of-the-art MQO solutions at that time, although only for a limited
subset of MQO problems. Annealing-based quantum computers can reach a larger
number of qubits. However, the gate-based model is a more general
architecture. Subsequent works [21, 22] tackled the MQO problem on gate-based
models using the Quantum Approximate Optimization Algorithm (QAOA) [54], which
is a hybrid quantum-classical algorithm.

Join ordering studies how to identify the optimal ordering of join operations
between relations for an efficient query plan [55, 56, 57]. To find optimal
left-deep join trees, Schönberger et al. [23, 24] defined the intermediate
formulation based on mixed integer linear programming (MILP), followed by
binary integer linear programming (BILP) models, which are eventually
transformed to QUBO. Recent works also expanded the problem to bushy join
trees [25, 26]. In [27], Winker et al. provided a different angle: treating
join ordering as a _learning_ problem, then apply quantum machine learning
techniques based on a variational quantum circuit (VQC) algorithm [58].

Figure 2: Roadmap for solving data management problems on quantum computers.

###  III-C Opportunities for data management using quantum computers

We outline a few near-term research directions in the following.
1) _Database problem reformulation._ Illustrated in Fig. 2, the general
methodology to solve data management problems on quantum computers includes
two steps. First, we need to reformulate the data management problem (e.g.,
MQO or schema matching) to a problem which can be solved on quantum computers
(e.g., QUBO). Besides QAOA, there are many more algorithms for quantum
computers, e.g., variational quantum eigensolver (VQE), quantum phase
estimation (QPE), and Grover’s algorithm. Therefore, the main research
opportunities are to explore _which_ data management problems can be
formalized into problems solvable by quantum computers and provide better or
faster solutions compared to classical solutions.
2) _Hybrid approach using classical and quantum computers._ Most works in
Table I require additional steps on classical computers. For instance, in [20]
a prior step is to cluster the queries sharing intermediate results, which
significantly reduces the required number of qubits. Many research challenges
emerge regarding how to design a hybrid approach using classical and quantum
computers.
3) _Optimization given quantum computer constraints._ Despite the compelling
computation power of quantum computers, to design data management systems that
make use of quantum computers, we still face many practical constraints such
as the restricted number of qubits as well as noisy operations [59]. For a
foreseeable period of time, such limitations will coexist while developing
data management systems that utilize quantum computers. It poses technical
challenges and research opportunities to achieve optimal performance (e.g.,
time-wise efficiency, accuracy, or completeness of the results), given the
physical properties and constraints of quantum computers.

##  IV Opportunities: Data Management via Quantum Internet

Quantum internet promises unprecedented new capabilities beyond our internet
today [60]. The applications include distributed systems [4], quantum cloud
computing [61], quantum key distribution [62]. One of the most fundamental
theories enabling these new capabilities is _quantum nonlocality_ [63].
Intuitively, we can understand quantum nonlocality as: in a distributed
system, we have two computers in different locations; when we change a file on
one computer, the corresponding file on the other computer would change
immediately. It bypasses our usual assumptions about network distance and
speed limitations to transfer data.

The study of quantum nonlocality is at subatomic level, i.e., entangled
particles. During the tutorial, we will explain representative nonlocality
problems (e.g., CHSH [64] and GHZ [65] games) using logical operators, e.g.,
AND ($\wedge$), OR ($\vee$). This shares a unified mathematical foundation
with data management problems. For example, for query optimization, a query
plan can be expressed as relation predicates connected by logical operators
[66].

###  IV-A Quantum nonlocality

In Sec. II, we mentioned superposition and entanglement. To explain the
phenomenon of nonlocality, we introduce one of the most well-known states for
entanglement, _Bell’s state_.

######  Example IV.1.

(Bell’s state) We extend the one-qubit state in Example II.1 to a two-qubit
state as follows:

$\ket{\Psi}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$

Nonlocal games. To make it simple, we consider only two players, Alice and
Bob. A two-player nonlocal game is a game that consists of two players and a
referee. During the game, each player receives an input (like a question or a
number) from the referee. Two players, Alice and Bob, however, cannot
communicate once the game starts. The intriguing aspect of nonlocal games is
that if Alice and Bob share an entangled quantum state, e.g., Bell’s state
from Example IV.1, they sometimes can win the game with a higher probability
than classical strategies. We give an example:

######  Example IV.2.

(Clauser-Horne-Shimony-Holt (CHSH) game [64]) In this game, Alice receives
input $x$ and outputs one-bit answers $a$, while Bob receives $y$ and outputs
$b$. The players win the game if the questions and the answers satisfy
$x\wedge y=a\oplus b$, where $\wedge$ is the logical AND operator and $\oplus$
is XOR. We omit the calculations here, but show results. The two players win
optimally with score $\approx 0.85$ using an entangled Bell’s state, and every
pair of players who do not share entangled states can succeed with probability
of at most $0.75$.

The CHSH game demonstrates an example of entanglement winning over classical
strategies by a higher success probability (0.85 vs. 0.75). During the
tutorial, we will give another example, the three-player Greenberger-Horne-
Zeilinger (GHZ) game [65]. In the GHZ game, the entangled state achieves a
probability of 1, while classical resources can only achieve a probability of
0.75. That is, with entanglement, we can achieve a task that is _not_ possible
with classical resources.

###  IV-B Future research directions of data management via quantum internet

Quantum nonlocality serves as the theoretical foundation of protocols for
secure communication and key distribution [62]. Naturally, it is an
interesting direction to explore secure data management via quantum internet.
Next, we discuss new design challenges and research opportunities, which are
not discussed in the existing literature.
1) _New data structures._ We face the fundamental challenge of data
representation, since communicating quantum information is fundamentally
different from classical information. Take the famous _no-cloning theorem_ [1]
for example. Existing database theory and systems are built upon the fact that
we can freely read and copy data, e.g., duplicate a data tuple, or replicate a
dataset (e.g., a CSV file) on another computer in the network. However, the
no-cloning theorem states that we cannot make an exact copy of an arbitrary
quantum state. Thus: How to design data models, when quantum data cannot be
copied without destroying the original version?
2) _New architectures of distributed data management systems._ Distributed
database systems traditionally manage distributed, fragmented, and replicated
data over classical computer networks. Facing quantum properties such as
entanglement, nonlocality, and no-cloning theorem, we need new system
architectures to ensure reliability, availability, and scalability. The
question arises, for instance, how to design distributed data management
systems based on protocols used in quantum internet [4]? Given the quantum
hardware or network failures [67], how to design fault tolerance and recovery
strategies?

##  V Presenters

Rihan Hai is an assistant professor at TU Delft, The Netherlands. Her research
focuses on data lakes, data management for machine learning, and quantum data
management.

Shih-Han Hung is a postdoc at Academia Sinica. His research aims to better
understand the power and the limit of quantum computers.

Sebastian Feld is an assistant professor at TU Delft, The Netherlands. He and
his group are working on Quantum Machine Learning.

## References

  * [1] M. A. Nielsen and I. L. Chuang, _Quantum computation and quantum information_. Cambridge university press, 2010.
  * [2] A. Broadbent, J. Fitzsimons, and E. Kashefi, “Universal blind quantum computation,” in _2009 50th Annual IEEE Symposium on Foundations of Computer Science_ , 2009, pp. 517–526.
  * [3] N. H. Nickerson, J. F. Fitzsimons, and S. C. Benjamin, “Freely scalable quantum technologies using cells of 5-to-50 qubits with very lossy and noisy photonic links,” _Physical Review X_ , vol. 4, no. 4, p. 041041, 2014.
  * [4] S. Wehner, D. Elkouss, and R. Hanson, “Quantum internet: A vision for the road ahead,” _Science_ , vol. 362, no. 6412, p. eaam9288, 2018.
  * [5] S. P. Neumann, A. Buchner, L. Bulla, M. Bohmann, and R. Ursin, “Continuous entanglement distribution over a transnational 248 km fiber link,” _Nature Communications_ , vol. 13, no. 1, p. 6134, 2022.
  * [6] J. Yin, Y. Cao, Y.-H. Li, S.-K. Liao, L. Zhang, J.-G. Ren, W.-Q. Cai, W.-Y. Liu, B. Li, H. Dai _et al._ , “Satellite-based entanglement distribution over 1200 kilometers,” _Science_ , vol. 356, no. 6343, pp. 1140–1144, 2017.
  * [7] E. F. Codd, “A relational model of data for large shared data banks,” _Communications of the ACM_ , vol. 13, no. 6, pp. 377–387, 1970.
  * [8] M. Qszu and P. Valdureiz, “Principles of distributed database system,” 1991.
  * [9] M. Atkinson, D. Dewitt, D. Maier, F. Bancilhon, K. Dittrich, and S. Zdonik, “The object-oriented database system manifesto,” in _Deductive and object-oriented databases_. Elsevier, 1990, pp. 223–240.
  * [10] D. Abadi, R. Agrawal, A. Ailamaki, M. Balazinska, P. A. Bernstein, M. J. Carey, S. Chaudhuri, J. Dean, A. Doan, M. J. Franklin _et al._ , “The beckman report on database research,” _Communications of the ACM_ , vol. 59, no. 2, pp. 92–99, 2016.
  * [11] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell _et al._ , “Quantum supremacy using a programmable superconducting processor,” _Nature_ , vol. 574, no. 7779, pp. 505–510, 2019.
  * [12] H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu _et al._ , “Quantum computational advantage using photons,” _Science_ , vol. 370, no. 6523, pp. 1460–1463, 2020.
  * [13] Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan _et al._ , “Strong quantum computational advantage using a superconducting quantum processor,” _Physical review letters_ , vol. 127, no. 18, p. 180501, 2021.
  * [14] L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Rortais, T. Vincent, J. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins _et al._ , “Quantum computational advantage with a programmable photonic processor,” _Nature_ , vol. 606, no. 7912, pp. 75–81, 2022.
  * [15] R. van der Heijden, “The first european cloud quantum computer is in delft,” https://www.nemokennislink.nl/publicaties/eerste-europese-cloudquantumcomputer-staat-in-delft, accessed: 2024-02-23.
  * [16] A. Einstein, B. Podolsky, and N. Rosen, “Can quantum-mechanical description of physical reality be considered complete?” _Physical review_ , vol. 47, no. 10, p. 777, 1935.
  * [17] E. Schrödinger, “Discussion of probability relations between separated systems,” in _Mathematical Proceedings of the Cambridge Philosophical Society_ , vol. 31, no. 4. Cambridge University Press, 1935, pp. 555–563.
  * [18] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” _SIAM review_ , vol. 41, no. 2, pp. 303–332, 1999.
  * [19] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ , 1996, pp. 212–219.
  * [20] I. Trummer and C. Koch, “Multiple query optimization on the D-Wave 2X adiabatic quantum computer,” _Proceedings of the VLDB Endowment_ , vol. 9, no. 9, 2016.
  * [21] T. Fankhauser, M. E. Solèr, R. M. Füchslin, and K. Stockinger, “Multiple query optimization using a hybrid approach of classical and quantum computing,” _arXiv preprint arXiv:2107.10508_ , 2021.
  * [22] T. Fankhauser, M. E. Soler, R. M. Füchslin, and K. Stockinger, “Multiple query optimization using a gate-based quantum computer,” _IEEE Access_ , 2023.
  * [23] M. Schönberger, “Applicability of Quantum Computing on Database Query Optimization,” in _Proceedings of the 2022 International Conference on Management of Data_ , ser. SIGMOD ’22. New York, NY, USA: Association for Computing Machinery, 2022, pp. 2512–2514.
  * [24] M. Schönberger, S. Scherzinger, and W. Mauerer, “Ready to leap (by co-design)? join order optimisation on quantum hardware,” _Proceedings of the ACM on Management of Data_ , vol. 1, no. 1, pp. 1–27, 2023.
  * [25] M. Schönberger, I. Trummer, and W. Mauerer, “Quantum Optimisation of General Join Trees,” in _Joint Workshops at 49th International Conference on Very Large Data Bases (VLDBW’23)—International Workshop on Quantum Data Science and Management (QDSM’23), August 28-September 1, 2023, Vancouver, Canada (CEUR Workshop Proceedings)_ , 2023.
  * [26] N. Nayak, J. Rehfeld, T. Winker, B. Warnke, U. Çalikyilmaz, and S. Groppe, “Constructing Optimal Bushy Join Trees by Solving QUBO Problems on Quantum Hardware and Simulators,” in _Proceedings of the International Workshop on Big Data in Emergent Distributed Environments_ , ser. BiDEDE ’23. New York, NY, USA: Association for Computing Machinery, 2023.
  * [27] T. Winker, U. Çalikyilmaz, L. Gruenwald, and S. Groppe, “Quantum Machine Learning for Join Order Optimization Using Variational Quantum Circuits,” in _Proceedings of the International Workshop on Big Data in Emergent Distributed Environments_ , ser. BiDEDE ’23. New York, NY, USA: Association for Computing Machinery, 2023.
  * [28] K. Fritsch and S. Scherzinger, “Solving hard variants of database schema matching on quantum computers,” _Proceedings of the VLDB Endowment_ , vol. 16, no. 12, pp. 3990–3993, 2023.
  * [29] T. Bittner and S. Groppe, “Avoiding blocking by scheduling transactions using quantum annealing,” in _Proceedings of the 24th Symposium on International Database Engineering and Applications_ , 2020.
  * [30] Tim Bittner and Sven Groppe, “Hardware accelerating the optimization of transaction schedules via quantum annealing by avoiding blocking,” _Open Journal of Cloud Computing (OJCC)_ , vol. 7, no. 1, pp. 1–21, 2020.
  * [31] S. Groppe and J. Groppe, “Optimizing transaction schedules on universal quantum computers via code generation for grover’s search algorithm,” in _Proceedings of the 25th International Database Engineering & Applications Symposium_, 2021, pp. 149–156.
  * [32] A. D. King, J. Raymond, T. Lanting, R. Harris, A. Zucca, F. Altomare, A. J. Berkley, K. Boothby, S. Ejtemaee, C. Enderud _et al._ , “Quantum critical dynamics in a 5,000-qubit programmable spin glass,” _Nature_ , pp. 1–6, 2023.
  * [33] F. Glover, G. Kochenberger, and Y. Du, “A tutorial on formulating and using qubo models,” _arXiv preprint arXiv:1811.11538_ , 2018.
  * [34] S. Abiteboul, R. Hull, and V. Vianu, _Foundations of databases_. Addison-Wesley Reading, 1995, vol. 8.
  * [35] R. Ramakrishnan, J. Gehrke, and J. Gehrke, _Database management systems_. McGraw-Hill New York, 2003, vol. 3.
  * [36] M. Y. Vardi, “The complexity of relational query languages,” in _Proceedings of the fourteenth annual ACM symposium on Theory of computing_ , 1982, pp. 137–146.
  * [37] C. H. Papadimitriou and M. Yannakakis, “On the complexity of database queries,” in _Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems_ , 1997, pp. 12–19.
  * [38] A. Ambainis, “Understanding quantum algorithms via query complexity,” in _Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018_. World Scientific, 2018, pp. 3265–3285.
  * [39] B. M. Terhal and J. A. Smolin, “Single quantum querying of a database,” _Physical Review A_ , vol. 58, no. 3, p. 1822, 1998.
  * [40] M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” _Fortschritte der Physik: Progress of Physics_ , vol. 46, no. 4-5, pp. 493–505, 1998.
  * [41] A. Patel, “Quantum database search can do without sorting,” _Physical Review A_ , vol. 64, no. 3, p. 34303, 2001.
  * [42] I.-M. Tsai, S.-Y. Kuo, and D. S. L. Wei, “Quantum Boolean circuit approach for searching an unordered database,” in _Proceedings of the 2nd IEEE Conference on Nanotechnology_. IEEE, 2002, pp. 315–318.
  * [43] S. Imre and F. Balázs, “The generalized quantum database search algorithm,” _Computing_ , vol. 73, pp. 245–269, 2004.
  * [44] Y.-L. Ju, I.-M. Tsai, and S.-Y. Kuo, “Quantum circuit design and analysis for database search applications,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 54, no. 11, pp. 2552–2563, 2007.
  * [45] P. Cockshott, “Quantum relational databases,” _arXiv preprint quant-ph/9712025_ , 1997.
  * [46] A. Gueddana, R. Chatta, and N. Boudriga, “Optimized methods for inserting and deleting records and data retrieving in quantum database,” in _2010 12th International Conference on Transparent Optical Networks_. IEEE, 2010, pp. 1–5.
  * [47] T. Salman and Y. Baram, “Quantum set intersection and its application to associative memory,” _The Journal of Machine Learning Research_ , vol. 13, no. 1, pp. 3177–3206, 2012.
  * [48] C.-Y. Pang, R.-G. Zhou, C.-B. Ding, and B.-Q. Hu, “Quantum search algorithm for set operation,” _Quantum information processing_ , vol. 12, no. 1, pp. 481–492, 2013.
  * [49] A. Gueddana, R. Chatta, and M. Attia, “CNOT-based design and query management in quantum relational databases,” _International Journal of Quantum Information_ , vol. 12, no. 04, p. 1450023, 2014.
  * [50] S. Jóczik and A. Kiss, “Quantum Computation and Its Effects in Database Systems,” in _European Conference on Advances in Databases and Information Systems_. Springer, 2020, pp. 13–23.
  * [51] A. Younes, “Database Manipulation Operations on Quantum Systems,” _Quantum Information Review_ , vol. 1, pp. 9–17, 2013.
  * [52] T. K. Sellis, “Multiple-query optimization,” _ACM Transactions on Database Systems (TODS)_ , vol. 13, no. 1, pp. 23–52, 1988.
  * [53] C. C. McGeoch and C. Wang, “Experimental evaluation of an adiabiatic quantum system for combinatorial optimization,” in _Proceedings of the ACM International Conference on Computing Frontiers_ , 2013, pp. 1–11.
  * [54] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” _arXiv preprint arXiv:1411.4028_ , 2014.
  * [55] M. Steinbrunn, G. Moerkotte, and A. Kemper, “Heuristic and randomized optimization for the join ordering problem,” _The VLDB journal_ , vol. 6, pp. 191–208, 1997.
  * [56] V. Leis, A. Gubichev, A. Mirchev, P. A. Boncz, A. Kemper, and T. Neumann, “How good are query optimizers, really?” _Proc. VLDB Endow._ , vol. 9, no. 3, pp. 204–215, 2015. [Online]. Available: http://www.vldb.org/pvldb/vol9/p204-leis.pdf
  * [57] I. Trummer and C. Koch, “Solving the join ordering problem via mixed integer linear programming,” in _Proceedings of the 2017 ACM International Conference on Management of Data_ , 2017, pp. 1025–1040.
  * [58] S. Y.-C. Chen, C.-H. H. Yang, J. Qi, P.-Y. Chen, X. Ma, and H.-S. Goan, “Variational quantum circuits for deep reinforcement learning,” _IEEE Access_ , vol. 8, pp. 141 007–141 024, 2020.
  * [59] A. A. Clerk, M. H. Devoret, S. M. Girvin, F. Marquardt, and R. J. Schoelkopf, “Introduction to quantum noise, measurement, and amplification,” _Reviews of Modern Physics_ , vol. 82, no. 2, p. 1155, 2010.
  * [60] W. Kozlowski and S. Wehner, “Towards large-scale quantum networks,” in _Proceedings of the sixth annual ACM international conference on nanoscale computing and communication_ , 2019, pp. 1–7.
  * [61] D. Castelvecchi, “Ibm’s quantum cloud computer goes commercial,” _Nature_ , vol. 543, no. 7644, 2017.
  * [62] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” _Theoretical computer science_ , vol. 560, pp. 7–11, 2014.
  * [63] H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, “Nonlocality and communication complexity,” _Rev. Mod. Phys._ , vol. 82, pp. 665–698, Mar 2010. [Online]. Available: https://link.aps.org/doi/10.1103/RevModPhys.82.665
  * [64] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, “Proposed experiment to test local hidden-variable theories,” _Physical review letters_ , vol. 23, no. 15, p. 880, 1969.
  * [65] D. M. Greenberger, M. A. Horne, and A. Zeilinger, “Going beyond bell’s theorem,” in _Bell’s theorem, quantum theory and conceptions of the universe_. Springer, 1989, pp. 69–72.
  * [66] F. Kastrati and G. Moerkotte, “Generating optimal plans for boolean expressions,” in _2018 IEEE 34th International Conference on Data Engineering (ICDE)_. IEEE, 2018, pp. 1013–1024.
  * [67] Y. Dulek, A. B. Grilo, S. Jeffery, C. Majenz, and C. Schaffner, “Secure multi-party quantum computation with a dishonest majority,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2020, pp. 729–758.