# QRLIT: Quantum Reinforcement Learning for Database Index Tuning
## 4 QRLIT: Quantum-Classical Implementation of Classical SMARTIX Algorithm  
This section describes the implementation of our QRLIT algorithm, a hybrid quantum-classical version of SMARTIX. Initially, we present a method for combining quantum computing (QC) with reinforcement learning (RL), which serves as the basis for the development of QRLIT. Then, we provide a description of the process used to identify the components that were converted. Finally, we demonstrate and compute the fundamental values necessary for the construction of the quantum circuit and conclude with the QRLIT flow diagram and pseudocode. Quantum reinforcement learning (QRL) is a method that combines the capabilities of QC and RL. Similarly to its classical counterpart, quantum reinforcement learning also includes a policy, a state space, an action space, and a reward function but is inspired by the superposition principle and quantum parallelism [33]. Based on the novel algorithm proposed in [33] for QRL, the authors of the paper [34] propose an algorithm called quantum Q-learning (QQRL) that stores the policy in a superposition state and uses [PERSON]'s algorithm as a strategy to amplify the probability amplitude of the best action based on the learned policy. [PERSON]'s algorithm exploits the natural behavior of superposition states and offers a good balance between exploration and exploitation. This balance can be achieved by controlling the number of Grover iterations L through the learning process of the agent. In other words, as the agent learns and the number of iterations increases, the capacity to explore decreases until reaching a number of iterations t (as defined in Equation (14)), which maximizes the probability of measuring the \"good\" action. The number of iterations L is determined by the formula in Equation (20) from [34], where k represents a rate that controls the proportion of policy and reward contributions and t denotes the maximum number of possible iterations. \[\mathrm{L}=\min\bigl{(}\mathrm{int}\bigl{(}\mathrm{k}\bigl{(}\mathrm{r}+ \mathrm{max}_{\mathrm{a}}\mathrm{Q}\bigl{(}\mathrm{s}^{\prime},\mathrm{a}^{ \prime}\bigr{)}\bigr{)}\bigr{)},\mathrm{t}\bigr{)} \tag{20}\]  
Our QRLIT implementation is based on the QQRL algorithm. Therefore, we identified that the Epsilon-greedy procedure is replaced by the Grover search algorithm, keeping the remaining elements in a classical system. With [PERSON]'s algorithm in QRLIT, we can not only determine the actions to be executed in the environment but also naturally balance the agent's duality between exploration and exploitation. As previously outlined in the Background Section, [PERSON]'s algorithm contains three distinct layers, namely State Preparation, Oracle, and Amplitude Amplification. In the State Preparation layer, we initiate the policy of the agent in a superposition state and in the Oracle, we encode the action with the highest Q-value in the current state of the environment. As the last layer, we implement the Amplitude Amplification, which amplifies the probability amplitude to measure the action encoded in the Oracle. To run and build [PERSON]'s algorithm, it is crucial to identify how many qubits are required in the quantum register to encode the actions. We calculate the number of qubits by using the formula \(\mathrm{N}_{\mathrm{a}}\leq 2^{\mathrm{n}}\leq 2\mathrm{N}_{\mathrm{a}}\), presented by the authors of the paper [33]. In this formula, \(\mathrm{N}_{\mathrm{a}}\) represents the size of the action space, while \(\mathrm{n}\) denotes the number of qubits required to encode an action. We apply and solve the formula for a space of 90 actions and round off the excess, so that \(\mathrm{n}\) is equal to seven (Equation (21)). We then define the maximum number of Grover iterations, \(\mathrm{t}\). As the number of qubits is already calculated, \(\mathrm{N}\) is equal to 128 and therefore, \(\mathrm{t}\) equals eight (Equation (22)).