1. Introduction
Every update of quantum hardware (computer) attracts
the attention of countless people, expecting it to provide
more substantial computing power. The source of this
expectation is the fact verified by proposed quantum
algorithms: quantum computing, indeed, has the ability
to solve certain problems more efectively than
classical computing [
1, 2
]. Therefore, many researchers are
spending lots of energy exploring quantum computing’s
applications (of academic or commercial interest) that
can realistically be solved faster on a quantum computer
than on a classical one (e.g., cryptanalysis [
3, 4
], materials
science [
5
], and chemistry [
6
]). This is called practical
quantum advantage, or quantum practicality for short
[
7
]. One of the most promising applications is in the
realm of database management systems [
8
], giving rise
CEUR
htp:/ceur-ws.org
ISN1613-073
CEUR
Workshop Proceedings (CEUR-WS.org)
to the concept of quantum databases.
Quantum databases will be built upon the unique capa
bilities of quantum computing, which relies on the
principles of quantum mechanics to perform computations.
These principles allow quantum computers to process
information in parallel, enabling them to solve certain
problems more eficiently than classical computers. To fully
exploit the potential of quantum computing in database
management systems, researchers are currently
exploring novel approaches for implementing quantum data
structures and algorithms, as well as investigating
interdisciplinary collaborations between the fields of quantum
computing and database management. These eforts are
paving the way for innovative solutions in areas such as
quantum database search, database manipulation, query
optimization, and transaction management.
This paper aims to provide an analysis of the current
state of quantum databases by examining existing and
mostly researched areas (see Table 1). Additionally, it will
discuss the primary challenges that impede the growth
of quantum databases, including the necessity for mature
quantum computing hardware, limited coherence times,
and the absence of well-established query languages and
data models specifically tailored for quantum systems.
Lastly, this paper will present a visionary outlook on
quantum multi-modal databases, outlining their
potential benefits. By tackling these challenges and unlocking
the potential of quantum databases, our goal is to
enmanagement, and search functionalities, among others.
© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License hance database systems to support multi-modal storage,
Adiabatic quantum computation [
37
] is another
Query Optimization [23, 24, 25, 26, 27, 28] form of quantum computing. It works based on the
adiTransaction Management [29, 30, 31] abatic theorem. Eforts aimed at the realization of
adiabatic quantum computation employing quantum physical
systems are confronted with the challenge of non-ideal
The rest of the paper is organized as follows. Section 2 conditions, thereby impeding the fulfillment of the
adiapresents the current development of quantum hardware. batic theorem’s potential. Quantum annealing,
inhabitSection 3 introduces the quantum-based methods applied ing an intermediary realm between the idealized
assumpin databases. Section 4 discusses the open challenges and tions of universal adiabatic quantum computation and
vision. Section 5 concludes the paper. the unavoidable compromises arising from experimental
constraints, ofers an alternative approach to identifying
the minimum of an objective function without meeting
2. Quantum Hardware the rigorous prerequisites set forth by adiabatic quantum
computation [
38, 39
]. A quantum annealer uses a
proQuantum computing is a fast-growing technology. At the cess, quantum annealing, to solve a hard optimization
heart of it is quantum hardware, the physical devices, and problem, whose method is evolving a known initial
concomponents that allow quantum computers to function. figuration at non-zero temperature towards the ground
This hardware – from the quantum bits (qubits) that state of a Hamiltonian encoding a given problem [
40
].
hold and process quantum information to the circuits A famous example of the quantum annealer is D-Wave
and cooling systems that make these qubits function – [
41
].
is very diferent from the classical computers we know
well. Because of this diference, more attention is needed • D-Wave Corporation (Canada) launched the
to promote the development of quantum hardware, so world’s first commercial quantum computer,
“Das to provide a better ecological environment for the Wave One”, on May 11, 2011. In 2023, D-Wave
development of its applications (e.g., databases). The key launched a 5000+ qubit computer.
components of quantum hardware are:
Qubits [32] are the fundamental building blocks of Quantum Error Correction [
42
] is a set of techniques
quantum computers. Unlike classical bits, which can be used to correct errors in quantum computations. Because
either 0 or 1, qubits can be in a superposition of states qubits are extremely sensitive to noise and decoherence,
(denoted in the form | ⟩ = |0⟩ + |1⟩, a two-dimensional these techniques are essential for creating reliable
quanvector, where the coeficients and are called probabil- tum hardware.
ity amplitudes), empowering them to hold and process
more information than classical bits.
Quantum Gates [33] are the basic operations that are
performed on qubits. Since qubits are represented by
column vectors mathematically, a quantum gate is defined
as a unitary matrix. They are the quantum equivalent of
classical logic gates but with extra capabilities due to the
unique properties of quantum mechanics.
Quantum Circuits [
34
] include networks of qubits,
quantum gates, and measurements, which is the most
widely used model of quantum computation. Based on
the quantum circuit, we list two representative types of
quantum computers built in recent years.
1. In 2022, IBM [35] unveiled its most powerful quantum computer processor (Superconducting Circuits) to date, Osprey, a 433-qubit machine.
The advent of quantum computers has brought about
a transformative impact on applications in various fields,
ofering more eficient and expedient resolutions to
complex problems (e.g., Traveling Salesman Problem [
43
],
Subset Sum Problem [
44
], and Boolean Satisfiability
Problem [45]). Unfortunately, current quantum computers
are Noisy Intermediate Scale Quantum (NISQ) devices
[46], prone to substantial error rates and limited in size
by the number of qubits in the system. However, luckily,
NISQ computers are not our final goal. We firmly believe
the ongoing research eforts of developing large-scale,
fault-tolerant quantum computers indicate a bright
future for quantum databases. Furthermore, developing
eficient error correction mechanisms (e.g., surface code
[47]) will be a huge aid to the development of quantum
computing.
Databases
knowing . Besides, the algorithm could utilize the final
state of the index register as an input to another circuit
for extending the scale of quantum systems.
3.1. Quantum Database Search Ju et al. [
15
], an extension of [
14
], use the
quantum Boolean circuits to implement Grover’s algorithm.
The proposal of Grover’s algorithm [
1, 2
] could help peo- The implementation of Grover’s algorithm is made up of
ple know whether or not unsorted databases containing two parts: selective-inversion | 0⟩, and
inversion-aboutrecords have one satisfying particular property by ( √) average | 0⟂⟩. Besides, they summarize these problems
operations instead of checking records one by one until and ofer a template of quantum circuits for applying
ifnding the desired one. Based on this benefit of Grover’s in the following situation: Give a one-way function
algorithm, people have made the following eforts in the ∶ {0, 1} ⟶ {0, 1} and a -bit integer , the aim
hope of improving database query performance. is to find an -bit integer for satisfying () = .
Grover [
9
] proposes an algorithm to locate the marked
item in a single query. This algorithm is implemented by 3.2. Database Manipulation
using enough subsystems, where each subsystem has an
dimensional state space like the system of the original We all know that one of the abilities of database
manageGrover’s algorithm [
1, 2
], and the number of subsystems ment systems (DBMSs) is to manipulate data. The basic
(denoted as ) needs to be Ω( ) . processes in database systems involving data
manipula
Terhal and Smolin [
10
] propose quantum algorithms tion encompass a range of operations that include but
for a class of problems (e.g., binary search and coin- are not limited to insertion, deletion, selection, and
proweighing problems), which could retrieve a quantum jection. In this part, we will introduce current research
database in a single query. The proposal of the algorithms on applying quantum computing in this area.
is based on Bernstein and Vazirani’s parity problem. Cockshott [
16
] mentions that the basic operations
Boyer et al. [
11
] proposes an algorithm to find one (selection, projection, and join) could be implemented in
result item that appears more than once in an -items the quantum relational database. In detail, the primary
table, and the number of result items (denoted as ) is key selection could be achieved with the help of Grover’s
not known ahead of time. Besides, based on Grover’s algorithm [
1, 2
]. Relational database projection in the
algorithm, Boyer combines it with Shor’s algorithm [48] quantum database can be performed by only keeping the
to design an algorithm for approximately counting the qubits that encode the domains of the projected relation
number of solutions. and having the rest qubits discarded. The join operation
Patel [
12
] proposes a factorized quantum search algo- could be implemented by cooperation with a similarity
rithm to find the wanted object in an unsorted database operator, a combining operator, and Grover’s algorithm
by ( 4 ) queries, which is much similar to the as- [
1, 2
].
sembly process in DNA replication. This algorithm first Younes [
17
] defines some operations of a Quantum
digitizes the database with integer labels (i.e., a string of Query Language (QQL) used to manipulate a database
letters belonging to a finite alphabet), where the number ifle. Specifically, a way to insert records (one or several
of integer labels is and = (i.e., the alphabet has records) into the superposition in a single step is
preletters, the length of the string is letters, and set = 4). sented based on the tensor product. Then, a permutation
With digitization, the algorithm could check one letter of operator is defined to achieve updating records. Next, by
integer labels at a time. Next, this algorithm utilizes the utilizing Boolean functions and global conditions, certain
projection/measurement operator to remove from the sets of records can be selected and conditional
operaHilbert space all the states whose ℎ letter is not what we tions can be executed on the intersection of the selected
want, where could be denoted using identity operators. records. And finally, backing up and restoring a required
That is, = 1 ⊗ … ( ) ⊗ ⋯ ⊗ . One by one, the portion of the database file is given based on the oracle
algorithm looks over all the letters and finally locates the operator and partial difusion operator.
item with the wanted label. Liu and Long [
18
] propose a quantum algorithm to
Imre and Balázs [
13
] present a generalized Grover’s delete a marked item, with a single query, from an
unsearch algorithm to find the desired result with high ac- sorted database without knowing anything about the
curacy while letting the algorithm iterate as few times as marked state. This algorithm is made up of the following
possible. In detail, this algorithm replaces the Hadamard iterative process: (i) Take phase rotations with a fixed
transformation with an arbitrary unitary transformation. value of /3 to every basis state while the marked state
Then, the generalized Grover operator ( ) could preserve | ⟩ keeps unchanged; (ii) Do the -qubit Hadamard
transthe 2-dimensional vector space spanned by the refined formation; (iii) Take phase rotations with a fixed value
state vectors | ⟩ and | ⟩. Next, the algorithm derives the of /3 to the |0⟩ state; (iv) Do the -qubit Hadamard
optimal number of iterations during a search after transformation again. With this fixed phase angle /3 ,
the proposed deletion algorithm could nearly completely choose a combination of query plans for minimizing the
delete the marked state. Besides, this deletion operation cost of running a set of queries. To reach this purpose, the
is periodic, whose period is 3. algorithm first transforms an MQO problem instance into
Pang et al. [
19
] propose a quantum algorithm combin- a Quadratic Unconstrained Binary Optimization (QUBO)
ing Grover’s algorithm, classical memory, and classical problem instance. After that, the algorithm will use the
iterative computation for getting intersection. Specifi- quantum annealer to minimize the physical energy
forcally, the algorithm consists of two parts. The first part mula by finding an optimal value assignment. Then, the
is a subroutine finding an element in set = ⋂ , algorithm passes the solution returned by the quantum
similar to the algorithm [
11
]. The second part is for get- annealer back step by step. It uses the returned
soluting = ⋂ , which works by repeatedly calling the tion to obtain the answer and address the original MQO
subroutine until there is no output from the subroutine. problem.
Gueddana et al. [
20
] give a quantum database design. Fankhauser et al. [24] present an approach according
For the relational database, it consists of several relations to the Quantum Approximate Optimization Algorithm
(tables), where each table could be represented by a circuit (QAOA), which could find quasi-optimal solutions for
(e.g., a CNOT-based circuit). Then, a quantum database the MQO problem on a gate-based quantum computer.
associated with a relational database can be regarded The approach comprises two parts: one is to explore
as a collection of quantum circuits. Next, they design the search space by parametrized quantum computing,
circuits to implement table, insert (i.e., inserting records and the other is to optimize the parameters by classical
into a quantum table), delete, and select, respectively. computing with the heuristic strategies [49].
Here, they concentrate on selecting from naturally joined Schönberger [25] investigates solving the MQO
probquantum tables instead of retrieving records from a single lem with QAOA on the gate-based 27-qubit quantum
table. computer and analyses MQO problems with diferent
Salman and Baram [
21
] propose an algorithm to numbers of plans per query. Besides, a multi-step
reforpick any member of the intersection set = ⋂ , mulation is presented for the join ordering problem so
which is based on the oracle (i.e., () = 1, ∈ that it can run on the quantum circuit/annealer. And
, ℎ () = 0 ), the oracle () (i.e., () = ifnally, the related experiment results are given.
1, ∈ ), the intersection oracle ⋂ () , and a Tof- Schönberger et al. [26] present a quantum
implemenfoli gate. Then the algorithm obtains an element in the tation of join ordering optimization based on a
reformuintersection set by using Grover’s algorithm [
1, 2
]. lation to QUBO problem. According to insights gained
Jóczik and Kiss [
22
] propose four quantum algo- from the experimental analysis, authors identify design
rithms, for basic set operations (intersection, diference, criteria for shaping quantum processing units (QPU) as
union, projection), with the help of Grover’s algorithm. special-purpose devices tailored to specific applications
The first one is to define an appropriate oracle function (e.g., databases). Furthermore, the authors conduct
nu to determine the intersection set of set and . merical simulations for tailored custom QPU designs and
Then it uses the method of Grover’s algorithm to locate suggest minor architectural improvements on which the
. The second algorithm is to obtain the set diference, usefulness of custom co-designing QPUs for join ordering
which uses the previous intersection algorithm to obtain can be substantially enhanced.
the result. The third one is to get a union. The last algo- Nayak et al. [27] propose to formulate the join order
rithm is to obtain projection, which consists of two parts. optimization problem as a QUBO problem and then solve
One is to remove the duplicate attributes, whose main this QUBO problem to find the best solution for the more
idea is to convert a multiset to a set. The other one is general bushy join trees instead of the previous approach
to acquire the elements of the specific column, which is [26] finding the best solution among the left-deep join
implemented based on Grover’s algorithm. trees.
Winker et al. [28] develop a quantum machine
learn3.3. Database Query Optimization ing approach to predict eficient join orders by learning
from past join orders, which uses a variational
quantum circuit (VQC) [50]. It is worth noting that this
approach has been integrated into an open-source relational
database management system.
Query optimization is finding an optimal way to con
duct a provided query by considering the possible query
plans, which tends to explore large search spaces for
solving this problem. In this part, we will introduce
current research on applying quantum computing to the
optimization problem.
Trummer and Koch [23] propose an algorithm to
solve the problem of Multiple Query Optimization (MQO)
with an adiabatic quantum computer, where MQO aims to
3.4. Transaction Management with
Quantum Machine
Transaction management is a critical component in database systems, ensuring data integrity and consis
Video
Image
Music
Text
Transform
Search
Vector
Vector
Vector
Vector
Classical Data
Decoding
Quantum State
t
i
u
c
r
i
CInsert Delete Upadate
m
u
t
n
auQuery Vector Index
Q Operator
Quantum State
tency. However, the application of quantum technology vision, researchers need to overcome several challenges
and quantum computers in transaction processing is still related to quantum computing hardware and software,
in its nascent stages, with limited research conducted as well as develop new query languages and data models
in this domain [51]. Currently, the primary focus is on tailored for quantum systems.
modeling transaction processing as a general resource One of the main challenges in realizing the vision of
scheduling problem and leveraging quantum computing quantum databases is the development of mature
quantechniques to enhance its eficiency. This part introduces tum computing hardware. Although recent advances in
some techniques by quantum methods to speed up the quantum computing have led to the creation of several
transaction process of the concurrent controls. prototype quantum computers, these machines still sufer
Bittner et al. [29, 30] introduce an optimal quantum from issues such as limited coherence times, a lack of
eralgorithm by leveraging quantum annealing to optimally ror correction mechanisms, and I/O bandwidth. For one,
schedule transactions over a two-phase locking database when accessing classical data in databases, current
classisuch that the performance of a quantum annealer out- cal computers could do it faster than quantum computers.
performs traditional ones and isolation property is still That is to say, fundamental I/O bottleneck (bounds for
guaranteed. data input and output bandwidths) limits quantum
com
Groppe et al. [31], similar to [29, 30], leverage puters in their interaction with the classical world [
7
].
Grover’s search algorithm in solving combinatorial op- To enable practical quantum database applications,
retimization problems to optimally schedule transactions. searchers need to continue working on improving the
Firstly, concerning the transaction lengths and conflicts stability and reliability of quantum computing hardware,
between the transactions, the code generation modular as well as developing large-scale, fault-tolerant quantum
is proposed for the black box function of Grover’s search computers. Of course, people could also regard quantum
algorithm. And estimating the optimal solutions can fur- computing as a specialized hardware component of
clasther accelerate Grover’s search algorithm. The authors sical databases (e.g., [26]) to accelerate data processing.
also provide a detailed complexity analysis of the com- We call this quantum accelerated databases.
parison between a quantum method and traditional ones Another challenge lies in the development of query
in terms of preprocessing and execution time, space, and languages [52] and data models specifically designed for
code length. quantum database systems. Quantum databases require a
new set of tools and techniques to handle the unique
properties of quantum information, such as superposition and
4. Open Challenges and Vision entanglement. Researchers should focus on creating
intuitive query languages that can eficiently represent and
The core vision of quantum databases is to harness the manipulate quantum data, as well as designing data
modunique capabilities of quantum computing to revolution- els that can efectively store and organize quantum
inize the field of database management systems. In partic- formation. This calls for interdisciplinary collaborations
ular, quantum databases aim to ofer significant advan- between the fields of quantum computing and database
tages in terms of query processing speed. To achieve this management, which are crucial for realizing the vision
of quantum databases.
In this paper, we present a vision for the development
of a quantum multi-modal database, as illustrated in
Figure 1. This innovative approach aims to enable eficient
and precise similarity searches, as well as data retrieval
based on quantum vector distance or similarity. A vector
database is designed to store data in the form of
highdimensional vectors, which serve as mathematical
representations of various features or attributes. Vectors are
commonly used to encode multi-modal data,
encompassing diverse forms such as video, image, music, and text,
into numerical representations. Leveraging the power
of quantum circuits, the numerical values within these
vectors can be eficiently encoded using quantum
techniques. A straightforward approach is using multiple
qubits to encode the numerical value of the vector and
use controlled gates to determine the elements of the
vector. Then we may apply quantum multipliers or adders
on these vectors to accelerate processing. By combining
the principles of quantum computing with the concept
of vector databases, we anticipate advancements in the
ifelds of similarity search and data retrieval. This
approach holds the potential to revolutionize the way we
process and analyze multi-modal data in quantum
computing environments.
Additionally, it is crucial for this framework to
encompass an accessible interface, enabling operations such
as insertion, deletion, and updating of quantum data.
Furthermore, there is a need to develop a quantum
multimodal query algorithm capable of eficiently accessing
and processing multi-modal data. And it is feasible to
develop the corresponding operations and query
algorithms by building upon the extant works introduced in
the previous section (e.g., [
1, 20, 28, 30
]). For example,
we could use the following format to preserve the value
located at index in the -th vector:
| ⟩
_ | ⟩
_ |
⟩
,
where the three quantum registers storing qubits are used
to save the ID of the vector, the index ID of the vector,
and the value of the data, respectively. Next, we apply
CNOT gates on these quantum registers to store the -th
data’s value of the -th vector, with the third register
being the target qubits and the first two as control qubits.
Besides, it could be extended as the storage format of
relational tables. In summary, these could be
interesting attempts in the future. On top of it, the utilization
of Grover’s algorithm [
1
], amplitude amplification, or
quantum counting can be employed to perform various
forms of queries. With references [
18, 20
], we could
also attempt to design the corresponding deletion
operation. Of course, exploring the utilization of quantum
machine learning techniques within quantum databases
also presents an intriguing avenue for further
investigation [53]. Finally, as data is stored within quantum
1–8
vector databases, a compelling direction to explore is the
provision of multi-modal data services within a cloud
environment [54]. Investigating the feasibility and
effectiveness of deploying quantum vector databases in
the cloud can pave the way for scalable and accessible
multi-modal data management.