A Scalable 5,6-Qubit Grover’s Quantum Search Algorithm

Quantum computing is a novel paradigm in computational science that has the potential to revolutionise the field [1]. Recently, quantum computing offers promising quantum advantages in various applications over classical counterparts due to the development of quantum hardware and inherent quantum entanglement characteristics [2, 3]. On quantum computers, conventional NP-hard tasks [4, 5, 6] can be solved in polynomial time, demonstrating a significant speedup over classical computers. Using Shor’s method [4] for factoring offers a super-polynomial speedup, whereas Grover’s quantum search [5] yields a polynomial speedup. The real-world applications of quantum computing and the speedups given by quantum algorithms will rely heavily on noisy intermediate-scale quantum (NISQ) devices [7], which can handle hundreds of quantum bits. The behaviour and viability of quantum algorithms, as well as their future applications as quantum computing advances, have been studied in the last few decades [8, 9]. However, the entire scope of classical issues that quantum computers can effectively handle has not yet been recognized [9]. In addition to this, with the growing data size, the computational science community has a rising demand to successfully deploy quantum algorithms on large scale applications [10].
Grover’s search algorithm is one of the most popular quantum computing algorithms that can search for an entity with a high probability in an unstructured list using only O($\sqrt{N}$) [11] evaluations. Grover’s algorithm finds an entity in an unstructured list in fewer steps than a classical system [12]. In quantum processing, the search entity is one of the states from among all possible superposition states. According to Grover’s quantum search algorithm [12], there are ${2^{n}}$ = $N$ states in an $n$-qubit network, and the probability of finding every state is $\frac{1}{N}$. Hence, the amplitude of each state is $\frac{1}{\sqrt{N}}$. The same problem takes maximum O($N$) [12] trials in the classical system. According to Bennett et al. [11], no quantum method can solve the database search problem in fewer than O($\sqrt{N}$) steps asymptotically. Later, Boyer et al. [13] have shown that there are no quantum algorithm can outperform Grover’s algorithm by more than a few percentage points with a $50\%$ probability of success. The applications of Grover’s search include solving collision problems, finding the mean and median [12] of a given dataset, and reverse-engineering cryptographic hash functions by allowing an attacker to find a victim’s password.
In the last few decades, a plethora of Grover’s quantum search algorithms have been explored, which includes theoretical proof of the efficiency of the algorithm [14] and its applications in various problem domains [15, 16, 17, 18, 19]. Of late, the experimental implementation of fast Grover’s quantum search algorithm has been extended to Nuclear Magnetic Resonance (NMR) [20] for a system of four states. Moreover, a generalized Grover’s search algorithm [13] is introduced to deal with more than one marked state and allow an arbitrary number of unitary transformations in the original quantum circuit [21]. It may be noted that the generalization of Grover’s quantum search algorithm leads to adiabatic quantum computing settings [22]. However, the NMR systems lack scalability and optimization during the presentation of their experimental results. Grover’s quantum search algorithm has been implemented for two to four qubits on IBM’s quantum computer, such as a 2-qubit implementation on the ibmqx2 architecture [23], a 3-qubit on a trapped-ion architecture [24], and a 4-qubit circuit on ibmqx5 architecture [25]. There is an implementation of Grover’s search on a 2-qubit, 4-state quantum computer by Brickman et al. [26], and their findings demonstrate an improvement over the corresponding classical search approach. Mandviwalla et al. [27] demonstrate the experiments of a single-pattern Grover’s search for up to four qubits on IBM’s quantum computer and present the accuracy and execution time results. Recently, a five-qubit Grover’s search is realised on the ibmqx4 quantum computer by Abhijith et al. [28], and their models suffer from a lower success rate. Moreover, FPGA-based emulation of Grover’s circuit was suggested by Lee et al. [29] and Mahmud et al. [19]; however, their hardware designs are also not scalable.
Recent years have witnessed the growing interest in hybrid quantum-classical variational algorithms to solve the scalability issues of Grover’s quantum search [30]. Using Grover’s quantum search algorithm as a test case for variational hybrid quantum-classical algorithms has been proven to be asymptotically optimal. However, the variational quantum algorithms are restricted to four qubits. It uses only one shared angle in the quantum settings, which is not applicable for five or more qubits. The Grover search circuit proposed in our study has been modified from the usual circuit and widened to allow dynamic single-pattern and multi-pattern searches. The number of entangled qubits simulated in our experiments is also larger than in earlier studies. The significant contribution of this article is as follows:

1. 1.

   This paper introduces a $C^{4}Z$ gate and a novel Oracle function for 5-qubit and 6-qubit circuits using the $C^{4}Z$ gate. Hence, a scalable Quantum Grover Search algorithm is proposed.

2. 2.

   Furthermore, we developed a V-shaped Oracle (V- Oracle) pattern, which uses fewer gates and would potentially lead to fewer gate errors. The V-Oracle architecture can be easily extended to a higher number of qubits. The diffusion function takes the form HX + Oracle + XH to increase the amplitude of the search state.

3. 3.

   Finally, the experiments presented here are performed on the IBM Q experience, with each circuit being iterated $1024$ times. The accuracy of the proposed 5-qubit and 6-qubit circuits is benchmarked against the state-of-the art implementations for 3-qubit and 4-qubit.

The rest of this article’s sections are arranged in the following fashion. Section II explains the proposed novel scalable Grover’s quantum search algorithm based on $5$ and $6$ qubits circuits, including an introduction to the gate construction. Grover’s quantum search algorithms in $5$ and $6$ qubit space and experimental results are provided in Section III. Section IV sheds light on the scalability and reusability of the proposed Grover’s quantum search model. Finally, the concluding remarks and future research directions with the opportunity for large-scale implementation of Grover’s quantum search are confabulated in Section V. The complete circuit to implement 5 and 6 -qubit Grover quantum search is provided in Appendix.

Searching an unstructured data array of $N$ items is the primary objective of Grover’s quantum search algorithm [5]. For Grover’s quantum search strategy to be successful, it must locate an element in the collection $A=A_{1},A_{2},A_{3},\ldots S_{N}$ where $N$ is the number of elements in the set $A$. The Boolean function $\delta$ must be able to find an element in the collection so that $\delta(x)\rightarrow[0,1]$ [19]. When iterating over each element one at a time, a classical computer would need an average of $\frac{N}{2}$ queries for an array of cardinality $N$ [31]. A quadratic speedup over conventional computers is achieved by utilising Grover’s technique on a quantum machine, which only requires $\sqrt{N}$ queries. Multiple entries in the same collection may be found using Grover’s quantum search technique [13]. Each of the target patterns is found with equal probability by the algorithm. An Hadamard gate is first applied to transform the input qubits into entanglement and superposition with equal coefficients. Phase inversion and inversion around the mean are performed on the initial quantum state [19]. The following gates are required for implementing Grover’s quantum search algorithm.

Controlled $T$-gate ($cT$): A T gate is a phase shift gate that shifts the phase of a qubit by $\frac{\pi}{4}$ around the Z-axis. The $cT$ or controlled T gate, is a two-qubit gate created by adding a control qubit to a $T$ gate. For example, if the control qubit equals to $|1\rangle$, a $T$ gate will be applied to the target qubit; otherwise, it will stay unaltered. The generic $c^{k}T$ gate, where $k$ is the number of control qubits, may be created by adding more control qubits. A controlled $T$-gate describes a rotation of $\frac{\pi}{4}$ around the Z-axis on the target qubit when the control qubit is true. ${T^{\dagger}}$, its conjugate transpose, describes a rotation of $-\frac{\pi}{4}$ around the same axis. The matrix representations of controlled $T$ gates can be found in [24, 19], as shown below.

Controlled $Z$-gate ($cZ$): If it needs to invert the phase of the input qubit (i.e., the $|1\rangle$ basis state) while keeping the $|0\rangle$ basis state unaltered, we use a $Z$ gate (or Phase Inversion gate) [31]. A controlled $Z$-gate describes a rotation of ${\pi}$ around the Z-axis on the target qubit when the control qubit is true. It is possible to generate a $c^{k}Z$ gate by adding several control qubits that are all equal to $|1\rangle$. When this occurs, a $Z$ gate is applied to the target qubit, which otherwise remains unaffected. We have used $cZ$ gate in our proposed model available in IBM Q. A $Z$ and $cZ$ gate matrix representation is shown below [24, 19].

A quantum computer can solve a type of decision problem called the bounded-error quantum polynomial time (BQP) problem in polynomial time with an error probability of at most $\frac{1}{3}$ in all cases [18]. The unstructured search problem in this instance becomes a BQP problem as Grover’s iteration, when applied O($\sqrt{N}$) times, finds the element with a probability greater than $\frac{2}{3}$ [32, 33].
The Grover iteration, or Grover operator, is a quantum circuit that is employed in the quantum search process. There are two phases in the Grover iteration [5]. At the outset, the oracle function flips the phase of a single amplitude in a marked state. Once the indicated state amplitude has been flipped over, the diffusion layer has completed its task. While the other states retain their original amplitude, the target state is in an inverted condition, causing the amplitude of the target state to rise significantly and the amplitude of the other states to fall somewhat.

This section presents the experimental results of Grover’s quantum search implementation in 5-qubit and 6- qubit space on the IBM Q simulator. By default, IBM Q had five qubits and we extended it by editing the code in the IBM Q composer to increase the number of qubits. E.g., increase the size of the variable qreg from “$q[4]$” to “$q[8]$” to add four more qubits in the circuit (the full circuit is presented in Appendix).

This paper presents a 5-qubit and 6-qubit implementations of Grover’s quantum search algorithm. It introduces a V-Oracle pattern that offers a standard and relatively feasible technique to implement an unstructured search for a higher number of qubits. When applied for fewer qubits (less than $5$), the V-Oracle model gives equivalent or outperforms the state-of-the-art approaches. All the experiments have been performed on the IBM Q simulator. The experiments suggest that future quantum systems can use the proposed scalable Grover’s search technique and technology for various large-scale applications. However, the ibmq_16_melbourne backend results are not promising, which indicates that the actual qubits still suffer from a lack of coherence. The authors are currently working in this direction.

This work was partially supported by the Center for Advanced Systems Understanding (CASUS), financed by Germany’s Federal Ministry of Education and Research (BMBF) and by the Saxon state government out of the State budget approved by the Saxon State Parliament. We also appreciate the usage of IBM Q in this project. The views expressed here belong entirely to the authors and not the IBM Q experience team or any other entity.