Selecting appropriate index configurations that can minimize query processing costs is essential to database applications. This problem becomes more complicated when the database is replicated on multiple nodes. There have been divergent design index tuning algorithms utilizing either heuristic or optimization methods to solve this NP-Hard problem. However, this index selection problem becomes much more complex for large-scale replicated database applications and eficient algorithms are needed. While quantum computing has been investigated with promising results in several areas of database management, such as query optimization and transaction scheduling, no work exists that studies the divergent design index tuning problem for replicated databases. To fill this gap, in this paper, we provide our vision of a machine learning-based quantum divergent design index tuning algorithm for replicated databases. We first discuss the issues that should be handled when designing such an algorithm. We then describe an algorithm for classical computers that has been shown to perform better than other existing algorithms and present our vision of how to transform the algorithm to its quantum version.
1. Introduction
puter node, a workload of queries, and a space budget,
the Index Selection Problem (ISP) [
Divergent design index tuning is an NP-hard prob- and startups participating in quantum computing.
Howputers. However, for large-scale database applications in
[
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License index tuning problem, which is also NP-Hard [
The rest of the paper is organized as follows. Section 2 have been used to incorporate learning into the index discusses the related work on classical divergent design selection process. Various learned index advisors exist, index tuning and the quantum computing background. such as the cost-model reinforcement learning [29], DRLSection 3 describes the issues that a quantum divergent based index advisor [22], OpenGauss [23], document design index tuning algorithm using machine learning database index learning [26], SMARTIX [24], and DBA needs to handle. Section 4 presents our vision of such an Bandis [25]. However, all these machine learning-based algorithm. Finally, Section 5 concludes the paper with index selection algorithms are designed for a single node. future research directions. To deal with replicated databases on multiple nodes, DRLindex [30, 31] employs a DRL algorithm to select the index configurations for a cluster replicated database. Its 2. Related Work reward function considers the estimated processing cost of the workload and the replica load unbalance factor.
In this section, we review the existing work on divergent While DRLindex [31] shows that DRL is a promising
sodesign index tuning for classical computers and then lution for divergent index selection, it solely relies on the
provide the background on quantum computing. query optimizer and only handles single-column indices.
DRL Divergent Index Advisor (DINA) [4] is designed
2.1. Classical Divergent Design Index to address the limitations of DRLindex. To avoid
posTuning sible query cost estimation errors due to using a query
optimizer, DINA employs two training phases where it
There exist a good number of algorithms that have been learns the eficiency of various possible query workload
proposed to select an index configuration on a single node partitions and their index configurations by creating the
for the entire query workload [20, 21, 22, 23, 24, 25, 26]. indexes and observing the real execution times. It deals
They employ either heuristic, optimization, or machine with both single-column and multiple-column indices.
learning methods to carry out the index selection pro- All the above algorithms were designed for classical
cess for the entire query workload. For databases that computers. To the best of our knowledge, there is no
are replicated on multiple nodes, instead of selecting existing quantum algorithm for divergent design index
the same index configuration for every node, divergent tuning.
design index tuning algorithms [
As the superiority of quantum computers results from the special states that a system of qubits can assume, it is important to keep these states undisturbed until the end of the calculation. Unlike classical computers, the states are not discrete in a quantum computer. For qubits, the quantum state is represented by 2 complex values with norm 1 [33]. This makes a quantum state more susceptible to noise than a classical one. Environmental noise can cause decoherence in a quantum system, which will result in the loss of information [35].
The first studies on quantum algorithms have only focused on providing a speed-up for problems that are hard to solve on classical computers [36, 37, 38]. These studies ignored the possible limitations of the first generation of quantum computers. In recent years, with the invention of the first quantum computers, the focus of research has shifted to developing quantum algorithms that can work on modest hardware of our age. The first generation of quantum computers which are also called noisy-intermediate scale quantum (NISQ) computers [39], sufers from a small number of qubits and short coherence times. The main solution that has been proposed so far is to create quantum-classical hybrid algorithms that use quantum subroutines to solve smaller problems which are then used to solve the main problem using a classical computer. These algorithms are more suitable to work on NISQ devices.
Among the hybrid algorithms, the ones that depend on variational quantum circuits (VQCs) take up a big volume [40]. In these algorithms, quantum circuits that apply parameterized quantum gates are used. These circuits consist of a small number of qubits and quantum gates, and they are run many times during the course of a program. Depending on the outcome of a VQC, a classical optimizer tunes the parameters. The purpose is to find the optimal values of the parameters and to output the result obtained using these values. QAOA [41] and VQE [42] are the most famous examples of such algorithms. An application of these two algorithms to another database problem, namely join order optimization, has already been studied [43]
It has been shown that VQCs can be utilized for machine learning applications, which is not surprising since the best set of parameters can be learned for a given task. Additionally, it has been proven that the representation capacity of a VQC is higher than a classical neural network [44]. This results in VQCs obtaining the same solution quality as neural networks using fewer parameters. Quantum machine learning has already been used to solve join order optimization [45].
learning-based divergent design index tuning algorithm needs to address regardless of whether it is designed to run on a classical computer or on a quantum computer. These issues are due to the design requirements of indices, not due to the underlying hardware on which the algorithm runs. We then discuss the issues that exist due to the special characteristics of quantum computers. 3.1. Issues Common to Classical and
Quantum Computers
As a query predicate may contain more than one attribute, an index tuning algorithm that only deals with single attributes may not yield good performance.
However, dealing with multiple attributes requires index tuning algorithms to examine many combinations of attributes, which is a complex and expensive process. 2. Query Workload Analysis: The algorithm needs to be able to analyze the query workload to identify the query characteristics, such as the types, frequencies, and predicates of the queries, and take them into consideration in selecting appropriate indices. In addition, as the algorithm is designed for replicated databases on multiple nodes, it also needs to consider the current query workloads on the nodes in order to decide what index configurations should be selected to run which queries on which nodes. 3. Cost Evaluation: The cost of an index configuration consists of many components, such as time to create indices, time to perform I/Os, time to process queries on CPUs, time to update indices due to deletion/insertion/modification queries, and space to create indices. In addition, for replicated databases on multiple nodes, the cost in terms of the degree of load balancing should also be included. The algorithm design also needs to consider whether it should rely on the estimated costs produced by an existing query optimizer or it should rely on the actual query execution time. The former is simpler to use but the resulting costs may not be accurate due to the errors of the 3.2. Issues Specific to Quantum query optimizer. On the contrary, the latter is more Computers complicated as the algorithm will need to be designed in such a way that it can determine when and how 1. Data Loading and Encoding: As classical data are the actual query execution information is obtained stored as bit strings of 0s and 1s, to store and process and how to incorporate such information into its pro- them in a quantum computer, the first issue is how to cess to improve the next index selection round, even encode classical data into qubits representing quanthough it can avoid the errors made by the query tum states in such a way that would minimize the optimizer. numbers of qubits and the circuit depths. There are 4. Machine Learning Issues: When using machine learn- various encoding techniques [9, 45]: basic encoding ing to predict index configurations as a part of a di- encodes each classical bit into a qubit; angle encodvergent design index tuning algorithm, the following ing provides a denser encoding by encoding each real are some of the additional issues that should also be value into a qubit; and amplitude encoding, which investigated: provides the densest encoding but also generates the a) Type of machine learning algorithm: There are most complex circuit depth, encodes each real value diferent types of machine learning algorithms into the amplitudes of the quantum state, allowing 2 that can be used [46]: supervised machine learn- values to be encoded into qubits. As diferent ening such as decision tree and neural network; un- coding algorithms require diferent numbers of qubits supervised machine learning, such as clustering and create diferent circuit depths, the choice of which and association rule mining; and reinforcement algorithm to use should aim at the ability to store the learning. With supervised learning, a lot of la- necessary data using the minimum required quantum beled data (training data) must exist prior to be- resources in terms of qubits and gate operations. ing used to build a learning model for index pre- 2. Data Decoding: This process describes how to retrieve diction, which is often dificult to obtain in real and interpret the results from a quantum computer. applications. With unsupervised learning, a lot There may be diferent options like choosing the most of data still need to exist for the query patterns occurring bit pattern in the measurements, calculatdiscovered to be meaningful, even though no la- ing the probabilistic expected value of the quantum beled data are required. Reinforcement learning circuit, i.e., the expectation value, and the probability does not require labeled data to be available in distribution of the measured values. There may also advance because it learns as it goes, but a proper be cases where more qubits are measured in the outreward function must be designed to compute the put than needed for the representation of the results, rewards for the actions taken. A combination of such that these additional values may just be ignored these algorithms can also be used, such as deep or several measured values are mapped to single ones reinforcement learning where a neural network of the result domain. For example, an index tuning trained based on a sample set of labeled data is algorithm may retrieve the tuning parameters from a used inside the reinforcement learning process. quantum circuit. b) Data Representation, Collection, and Cleaning: 3. Quantum Circuit Design: The longer the depths of the What data are needed for the chosen machine quantum circuits implementing the quantum operalearning algorithm, how to represent them, and tions designed for the divergent design index tuning how to collect them? Data may include attributes algorithm, the more qubits, gates, and control operain the database, queries, database statistics, and tions are needed, the more errors are encountered due so on. Once they are collected, how to deal with to noise and decoherence of qubits, and the longer the data quality issues, such as data inconsistency, it takes to execute the algorithm. It is thus impordata missing, and outliers? tant to design the algorithm in such a way that the c) Dynamic data: as data in database applications circuit depths are minimized. Techniques that optichange over time, the machine learning model mize quantum circuits, such as gate cancellation, gate constructed before the data change may no longer merging, and gate synthesis should be investigated perform well for index selection, then how to de- [47, 48]. Gate cancellation removes redundant gates tect this phenomenon, and how to rebuild the such as those that cancel each other out; gate merging model incrementally to reflect the new data with- merges consecutive gates of the same operation into out having to rerun the machine learning algo- one single gate; and gate synthesis eficiently decomrithm from the beginning are among the issues poses complex gates into sequences of elementary that need to be handled. gates available on the hardware being used. While gate synthesis may increase circuit depth at first, its resulting elementary gate sequences may enable further circuit optimization via gate cancellation and gate merging. 4. Training Data Handling: Training data is used in the machine learning part of the machine learning-based divergent design index tuning algorithm. On classical computers, the amount of training data and its quality impact the accuracy of the machine learning model.
The same is true on quantum computers. However, with errors caused by noise and decoherence of qubits as discussed in the background Section 2.2, an important issue is to determine what would be the suficient amount and quality of training data to meet the required accuracy of the machine learning model, and subsequently, the accuracy of the divergent design index tuning algorithm, while taking such errors into account. 5. Quantum Machine Learning: As there already exists a good number of quantum machine learning algorithms in the literature [14, 15, 16], an issue to consider is whether one or more such algorithms can be incorporated into the divergent design index tuning algorithm, or whether any of those algorithms needs to be revised before adoption, or a new quantum machine learning algorithm should be developed. 6. Hybrid Algorithms: Due to the limitation in the number of qubits and the decoherence time available on current quantum computers, hybrid approaches that take advantage of both classical and quantum computers have been proposed in areas such as quantum machine learning [14, 15, 16] and quantum query optimization [9, 45], where a part of the algorithms are executed on a classical computer while another part is executed on a quantum computer. To adapt a hybrid approach in quantum machine learning-based divergent design index tuning, some key issues that need to be addressed are to decide which parts of the algorithm should be processed on a classical computer, which parts should be processed on a quantum computer, and how these parts should communicate with each other to produce the intermediate results and the final results, while taking advantage of classical parallelism and quantum parallelism as well as considering load balancing on each computer and the waiting time between diferent processes. 7. Algorithm Evaluation: To evaluate the quantum speedup in terms of query execution time, theoretical analyses and/or experimental evaluations should identify cases where quantum algorithms can outperform classical counterparts. They should study the impacts of the database size in terms of attributes and tuples, query workload, database update rate, number of nodes, number of qubits, number of gates, circuit depths, decoherence time, and error rate. 8. Properties of Quantum Computers: There is a rapid development and huge improvements in the development of quantum hardware in recent years and it is expected that this progress will continue in the future. However, in order to guide the development of quantum hardware and provide researchers with quantum hardware feedback for their development goals, it is a key point to investigate the following question: Which properties (such as latencies of the quantum gates, supported quantum circuit depths and noise rates) should a future quantum computer have to achieve a certain accuracy and performance improvement over classical hardware for our quantum approach?
In this section, we first briefly describe DINA [ 4], a divergent design index tuning algorithm using Deep Reinforcement Learning (DRL) for classical computers that has been shown to perform better than existing algorithms. We then provide our vision of how to extend this algorithm for quantum computers. 4.1. DINA: A DRL Divergent Design Index Tuning Algorithm for Classical Computers In [4], DINA (DRL Divergent Index Advisor) has been proposed to select indices for a database replicated on multiple nodes. The database copy on each node is called a replica. DINA works for both single-column indices and multiple-column indices. It uses DRL where its DRL agent learns as it goes by exploring diferent query workload partitioning alternatives among the replicas and the efectiveness of their index configurations. The DRL eficiently explores the large search space. To avoid relying solely on the query optimizer as the estimated costs generated by the query optimizer can be erroneous, it trains the DRL agents in two phases: pre-training using the estimated query cost generated by a query optimizer and the re-training phase using the actual query execution time. As shown in Fig. 1, the algorithm has the three following major steps: Step 1: Invoke the Workload Forecaster module which runs an algorithm that forecasts the coming query workload [49] to generate a set of query templates, and the query instances and the number of query instances for each query template. pre-training phase) or in the actual query execution cost (during the agent re-training phase), and the inverse of the total workload-skew of the replicas () .
= × ( ) + × () where and are the weights obtained by trial and error defining a trade-of between query cost reduction and load-balancing. The details of these functions can be found in [4]. In Deep Q-Learning, the value of each action in a state at each time step is computed using a Q-function. The action predicted for the agent to take is the one that has the highest Q value, which is the most rewarding action. In DINA, the Q-function used is the following Bellman equation [51]: ( , ) = ( , ) + [ +1 +
proper index configuration for each replica such that the overall query processing cost and the workload skew on the replicas are minimal. The DRL framework is composed of the environment and agent. The environment defines the states of the replicas based on their index configurations and the possible actions for each state that the agent can take and returns a reward value for each action. The current state is represented as a state matrix where rows are the replicas, columns are the candidate indices, and an entry is 1 if the agent has selected the corresponding index for the corresponding replica and 0 otherwise. The possible actions are which query templates to be executed on which replicas and which candidate indices can be used on which replicas. An action at time denoted as is to select a query template to be executed on a replica and to select an index for the queries of that template.
Step 2: Submit the query workload to the Pre-Processing +1 ( +1 , +1 ) − ( , )] module to derive a set of candidate indices which are the attributes in the WHERE and JOIN clauses where ( , ) is the Q-value for state and action in the query templates, and create a workload ma- , is the learning rate, is the reward value, is the trix where rows are the query templates, columns discount rate, and +1 ( +1 , +1 ) is the maximum are the candidate indices, and an entry has a value of the estimated future return for the next state. value of 1 if the candidate index is an attribute in Due to the large search space, the agent uses a neural the WHERE or JOIN clause of the corresponding network to predict the action to take at each state. The query template and 0 otherwise. network is trained during the agent pre-training and retraining phases using a random sample of the agent’s experience tuples ( , , , +1 ) stored in the memory.
Experiments using the TPC-H [52] and TPC-DS [53]
database benchmarks have shown that DINA performs
better than the existing algorithms, DivDesign [
Given a state at time denoted as , the agent takes the action predicted by Deep Q-learning [50], the state is then changed from to the new state +1 , and the agent receives a reward value . The reward of an action is computed using a reward function based on the query processing cost reduction ( ) calculated from the reduction in the estimated query processing cost generated by the query optimizer (during the agent
tify three possible components which can be replaced by a quantum approach. These are the Workload Forecaster, the Divergent Design Index Selection, and the Cost Estimation. We can choose to replace all with quantum approaches or keep some classical ones. We will use variational quantum circuits with their properties to potentially learn with fewer training data [17], such that our new architecture can adapt faster to changes in indices, queries, and data sets.
take advantage of the probabilistic nature of quantum computing to simulate uncertainty about the expected as = 1 . This will result in a value in the interval [0, ∞] query workload. We have two possible approaches of with = 20 for 1 = 0 and = ∞ for 2 = 0. The precision mapping quantum states to query templates. of this cost value depends on the number of shots of the
One approach is to assign a query template to each quantum circuit. quantum state and the probability of the quantum state The suggested encoding and decoding approaches are is the percentage of queries belonging to this template. not the only possible representations of the inputs and Many shots of the quantum circuits are required to get a outputs. Many other representations exist and an experigood approximation of all probabilities. mental evaluation is needed to find out which represen
Another approach is to assign a query template to each tation has the best learning performance while having a qubit and count how often each qubit is measured as 1. reasonable qubit requirement.
This allows the counting of multiple templates with each execution and thus requires fewer shots.
work of the classical agent with a VQC. This component has the task of choosing an action from a given state of In this paper, we aimed to provide our vision of a quanthe environment. It gets the state of the environment tum divergent design index tuning algorithm that makes and an action as input and returns a predicted reward. use of machine learning to select indices for large-scale
The state of the environment is a × matrix of binary replicated database applications. We discussed the issues variables. A basis encoding would require ∗ qubits that the algorithm needs to address. We then presented and is not feasible. Instead of looking at it as a matrix an algorithm for classical computers and our approaches of binary variables, we can interpret a row or column to how to transform it into a quantum algorithm. as an integer in binary code. This allows us to reduce For future research, we plan to formalize and implethe number of inputs to or integers. As we know the ment our quantum algorithm using one of the widelynumber of bits, we know the upper bound of the integer used open-source software development kits for quanvalue. This makes it suitable for the scaling required for tum computers like the popular qiskit [54]. We will then angle encoding. conduct experiments to evaluate the algorithm’s perfor
The action consists of selecting a replica for a query mance and compare the experimental results to those of template and choosing an index configuration. Each its classical counterpart. query template and each replica can be given an ID, such that we have two additional integers as input. The choice of an index configuration is a set of possible indices. As Acknowledgements we know all possible indices, this can be seen as a vector of binary variables, which in turn can again be inter- This work is funded by the German Federal Ministry preted as an integer. of Education and Research within the funding program
With this encoding approach, we get + 3 or + 3 quantum technologies - from basic research to market – integers as input, and, with angle encoding, we get the contract number 13N16090. same number of qubits.
Cost estimation The cost estimator gets a query template and an index configuration as input and returns the estimated cost for the execution of a query from the given template with the given index configuration. If we use the same encoding method as that used for the index solution, we will have 2 input values, which are the ID of the query template and the set of indices interpreted as an integer. With angle encoding, 2 qubits would be suficient for the input. As our output should be the estimated cost of the query execution on the replica with the given index, it should be a continuous value. By using the probabilities of a qubit being measured as 1, we can create a continuous output value. If 1 is the probability of 1 being measured for the first qubit and 2 the probability of 1 for the second qubit, we can define the cost [4] Z. Sadri, L. Gruenwald, A divergent index advisor 2109.01840.
using deep reinforcement learning, in: Interna- [17] M. Caro, H. Huang, M. Cerezo, K. Sharma, A. Sorntional Conference on Database and Expert Systems borger, L. Cincio, P. Coles, Generalization in quanApplications (DEXA), 2022, pp. 139–152,. tum machine learning from few training data, Nat. [5] S. Groppe, J. Groppe, U. Calikyilmaz, T. Winker, Commun 13 (2022).
L. Gruenwald, Quantum data management and [18] H. Huang, M. Broughton, M. Mohseni, R. Babbush, quantum machine learning for data management: S. Boixo, H. Neven, J. McClean, R., Power of data State-of-the-art and open challenges, in: The EAI in quantum machine learning, Nat. Commun 12 International Conference on Intelligent Systems (2021).
and Machine Learning (EAI ICISML), 2022. [19] P. Rebentrost, M. Mohseni, S. Lloyd, Quantum sup[6] Ericson, Ericson established quantum research hub port vector machine for big data classification, Phys. in canada, 2023. URL: https://www.ericsson.com/ Rev. Lett 113 (2014). en/press-releases/6/2023/ericsson-establishes- [20] S. Agrawal, S. Chaudhuri, L. Kollar, A. Marathe, quantum-research-hub-in-canada,. V. Narasayya, M. Syamala, Database tuning advisor [7] N. Liu, Cleveland clinic install world’s first quan- for microsoft sql server 2005, in: The ACM SIGMOD tum computer for healthcare research, SDXCentral International Conference on Management of Data (2023). URL: https://www.sdxcentral.com/articles/ (SIGMOD), 2005, pp. 930–932,.
news,. [21] D. Dash, N. Polyzotis, Ailamaki, A.: Cophy: a [8] National Quantum Initiative (2023). URL: https:// scalable, portable, and interactive index advisor for www.quantum.gov/,, accessed April 2023. large workloads, PVLDB 4 (2011) 362–372,. [9] U. Calikyilmaz, S. Groppe, J. Groppe, T. Winker, [22] H. Lan, Z. Bao, Y. Peng, An index advisor using S. Prestel, F. Shagieva, D. Arya, F. Preis, L. Gruen- deep reinforcement learning, in: Proceedings of the wald, Opportunities for quantum acceleration of 29th ACM International Conference on Information databases, in: Optimization of Queries and Trans- Knowledge Management, 2020, pp. 2105–2108,. action Schedules, Accepted for publication in the [23] G. Li, X. Zhou, J. Sun, X. Yu, Y. Han, L. Jin, W. Li, Proceedings of The International Conference on T. Wang, Li, S.: opengauss: An autonomous Very Large Data Bases (VLDB), 2023. database system, Proceedings of the VLDB En[10] Forrester, Key factors driving quantum dowment 14 (2021) 3028–3042,. computing into a new chapter, 2023. URL: [24] G. Paludo Licks, J. Colleoni Couto, P. Fátima Miehe, https://www.forbes.com/sites/forrester/2023/04/07/ R. Paris, D. Dubugras Ruiz, F. Meneguzzi, Smartix: key-factors-driving-quantum-computing-into-a- A database indexing agent based on reinforcement new-chapter. learning, Applied Intelligence 50 (2020) 2575–2588,. [11] M. Schönberger, S. Scherzinger, W. Mauerer, [25] R. Perera, B. Oetomo, B. Rubinstein, R. BorovicaK. Winter-sperger, H. Safi, M. Franz, L. Wolf, Gajic, Dba bandits: Self-driving index tuning under M. Periyasamy, C. Ufrecht, Ready to leap (by co- ad-hoc, analytical workloads with safety guarandesign)? join order optimisation on quantum hard- tees, in: IEEE 37th International Conference on ware, in: ACM SIGMOD/PODS International Con- Data Engineering (ICDE), 2021, pp. 600–611,. ference on Management of Data, 2023. [26] M. Schaarschmidt, A. Kuhnle, B. Ellis, K. Fricke, [12] I. Trummer, C. Koch, Multiple query optimization F. Gessert, E. Yoneki, Lift: Reinforcement learning on the d-wave 2x adiabatic quantum computer, 2015. in computer systems by learning from demonstraArXiv preprint arXiv:1510.06437,. tions, 2018. ArXiv preprint arXiv:1808.07903,. [13] T. Bittner, S. Groppe, Avoiding blocking by schedul- [27] S. Chaudhuri, V. Narasayya, Autoadmin what-if ing transactions using quantum annealing, in: The index analysis utility, ACM SIGMOD RECORD 27 24th Symposium on International Database Engi- (1998) 367–368,.
neering Applications (IDEAS), 2020. [28] S. Papadomanolakis, D. Dash, A. Ailamaki, Ef[14] Z. Abohashima, M. Elhosen, E. Houssein, M. W. M, ifcient use of the query optimizer for automated Classification with quantum machine learning: A physical design, in: The 33rd International Confersurvey, 2020. ArXiv, arXiv:2006.12270,. ence on Very Large Data Bases (VLDB), 2007, pp. [15] C. Ciliberto, M. Herbster, A. Ialongo, M. Pontil, 1093–1104,.
A. Rocchetto, S. Severini, L. Wossnig, Quantum [29] D. Basu, Q. Lin, W. Chen, H. Vo, Z. Yuan, P. Senellart, machine learning: a classical perspective, Proceed- S. Bressan, Cost-model oblivious database tuning ings of the Royal Society A: Mathematical, Physical with reinforcement learning, in: Proceedings of The and Engineering Sciences 474 (2018). International Conference on Database and Expert [16] R. Zhao, S. Wang, A review of quantum neural net- Systems Applications (DEXA), 2015, pp. 253–268,. works: Methods, models, dilemma, 2021. ArXiv, [30] Z. Sadri, L. Gruenwald, E. Leal, Online index selection using deep reinforcement learning for a cluster Quantum machine learning for join order optimizadatabase., in: Proceedings of The 36th IEEE Interna- tion using variational quantum circuits, in: Protional Conference on Data Engineering Workshops ceedings of the International Workshop on Big (ICDEW), 2020, pp. 158–161,. Data in Emergent Distributed Environments (BiD[31] Z. Sadri, L. Gruenwald, E. Leal, Drlindex: deep EDE), Seattle, WA, USA, 2023. URL: https://doi.org/ reinforcement learning index advisor for a cluster 10.1145/3579142.3594299. database, in: Proceedings of The 24th Symposium [46] P. N. Tan, M. Steinbach, A. Karpatne, V. Kumar, on International Database Engineering and Appli- Introduction to Data Mining, 2nd ed., Pearson, 2018. cations (IDEAS), 2020, p. 1–8. [47] Y. Nam, N. Ross, Y. Su, A. Childs, D. Maslov, Auto[32] R. P. Feynman, Simulating physics with computers, mated optimization of large quantum circuits with in: Feynman and computation, CRC Press, 2018, pp. continuous parameters, npj Quantum Information 133–153. 4 (2018) 1–12,. [33] M. A. Nielsen, I. Chuang, Quantum computation [48] O. Matteo, M. Mosca, Parallelizing quantum cirand quantum information, 2002. cuit synthesis, Quantum Science and Technology 1 [34] D. R. Simon, On the power of quantum computation, (2016) 015003.
SIAM journal on computing 26 (1997) 1474–1483. [49] L. Ma, D. Van Aken, A. Hefny, G. Mezerhane, [35] M. Schlosshauer, Quantum decoherence, Physics A. Pavlo, G. Gordon, Query-based workload fore
Reports 831 (2019) 1–57. casting for self-driving database management sys[36] P. W. Shor, Algorithms for quantum computation: tems, in: Proceedings of The ACM International discrete logarithms and factoring, in: Proceedings Conference on Management of Data (SIGMOD), 35th annual symposium on foundations of com- 2018, p. 631–645.
puter science, Ieee, 1994, pp. 124–134. [50] G. Li, X. Zhou, S. Li, B. Gao, Qtune: A query-aware [37] L. K. Grover, A fast quantum mechanical algorithm database tuning system with deep reinforcement for database search, in: Proceedings of the twenty- learning, in: Proceedings of The International Coneighth annual ACM symposium on Theory of com- ference on Very Large Data Bases (VLDB), 2019, pp. puting, 1996, pp. 212–219. 2118–2130,. [38] A. W. Harrow, A. Hassidim, S. Lloyd, Quantum [51] M. Wiering, M. Otterlo, Reinforcement Learning: algorithm for linear systems of equations, Physical State-of-the-Art, Springer, 2014.
review letters 103 (2009) 150502. [52] TPC, Tpc-h benchmark, 2023. URL: [39] J. Preskill, Quantum computing in the nisq era and http://www.tpc.org/tpch/.
beyond, Quantum 2 (2018) 79. [53] TPC, Tpc-ds benchmark, 2023. URL: http:// [40] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Ben- www.tpc.org/tpcds/.
jamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, [54] IBM, Qiskit: Open-source quantum development, X. Yuan, L. Cincio, et al., Variational quantum algo- 2023. URL: https://qiskit.org/.
rithms, Nature Reviews Physics 3 (2021) 625–644. [41] E. Farhi, J. Goldstone, S. Gutmann, A quantum approximate optimization algorithm, arXiv preprint arXiv:1411.4028 (2014). [42] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.
Q. Zhou, P. J. Love, A. Aspuru-Guzik, J. L. O’brien, A variational eigenvalue solver on a photonic quantum processor, Nature communications 5 (2014) 4213. [43] N. Nayak, J. Rehfeld, T. Winker, B. Warnke,
U. Çalıkyılmaz, 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 (BiDEDE), Seattle, WA, USA, 2023. URL: https://doi.org/10.1145/ 3579142.3594298. [44] Y. Du, M.-H. Hsieh, T. Liu, D. Tao, Expressive power of parametrized quantum circuits, Physical Review
Research 2 (2020) 033125. [45] T. Winker, U. Çalıkyılmaz, L. Gruenwald, S. Groppe,