Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era

In order to understand the bounds of utilization of Grover's search algorithm for large unstructured data in the presence of quantum computer noise, we undertake a series of simulations by inflicting various types of noise, modeled by the IBM qiskit. We apply three forms of Grover's algorithm: (i) the standard one, with 4–10 qubits; (ii) a recently published modified Grover's algorithm, set to reduce the circuit depth; and (iii) the algorithms in (i) and (ii) with multicontrol Toffoli's gates modified by the addition of an ancilla qubit. Based on these simulations, we find the upper bound of noise for these cases, establish its dependence on the quantum depth of the circuit, and provide comparison among them. By extrapolation of the fitted thresholds, we predict what would be the typical gate error bounds when applying Grover's algorithms for the search of data in a data set as large as 32 000.

Figure 1

The 4-qubit Grover's search of 0011 in a set of 16 data on IBM's latest quantum computer “ibmq_paris.” The ideal probability to measure “0011” is 96.7%; however, the measured one is only 6.6% due to the quantum noise and the specific topology of the machine.

Figure 2

Threshold error probabilities for (a) bit flip (BF), phase flip (PF), and depolarizing (DEP) and for (b) threshold damping parameters of amplitude damping (AD) and phase damping (PD), with various numbers of qubits in the GA search. The hollow symbols and solid symbols are for SGA and SGAA, respectively. Dashed (SGA) and solid (SGAA) lines are fitting curves with extrapolation, as described in the text.

Figure 3

Selectivity thresholds for the thermal relaxation times of the SGA and the SGAA with various numbers of qubits.

Figure 4

Fitting curve of selectivity thresholds for the error probability vs the number of qubits for various types of errors [BF, PF, and DEP in panel (a) and AD and PD in panel (b)] applied at the two-stage depth-reduced GA [12] with the use of MCTs (M2GA) and of MCTAs (M2GAA). Figure S3 in the Supplemental Material [11] shows the calculated data for the one-stage depth-reduced GA.

Figure 5

Selectivity thresholds for thermal noise of two-stage modified Grover's searches [12] (M2GA and M2GAA). Similar results calculated for the one-stage algorithm are shown in Fig. S4 of the Supplemental Material [11].

Figure 6

Comparison of the selectivity thresholds due to various quantum circuits errors in the standard GA (SGA and SGAA when MCTA are used), the one-stage depth-reduced GA (M1GA and M1GAA), and the two-stage depth-reduced GA (M2GA and M2GAA) for (a) 4, 6, and 8 qubits and (b) 10 and 15 qubits. The 15-qubit case was obtained by extrapolation of the fitting curves in Secs. 3 and 4. Higher-resolution figures are presented in Fig. S6 of the Supplemental Material [11].

Figure 7

Error threshold of BF, PF, DEP, AD, and PD with noise channels applied only on single qubit gates and 2-qubit gates for (a) the 8-qubit SGA and (b) the 8-qubit SGAA. Simulated results with only 1 noisy qubit are also shown, as well as contributions of all error channels.