Grover’s Algorithm: II

Hiu Yung Wong

Yulun Wang, Predrag Krstić

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.

Ri Qu, Juan Wang, Zong-shang Li +3 more

We firstly investigate the multipartite entanglement features of the quantum states, including the iteration states achieved by repeated application of Grover iteration and the Oracle ones into which the above iteration states evolve by applying single Oracle operation, employed in Grover's search algorithm by means of the separable degree and the entanglement measure. Then we give the quantitative and qualitative descriptions of the entanglement dynamics in Grover's search algorithm. Our results show that for most instances (i) the separable degrees of these states and ranges of their maximum Schmidt numbers are invariable by following the dynamics of Grover's search algorithm; (ii) the dynamics of Grover's search algorithm is almost "filled" by the fully entangled states.

Hiu Yung Wong

Gerardo G. Fogel

This thesis studies multiobjective optimization problems in the context of quantum computing. Quantum computing is a computational paradigm based on the laws of quantum physics as superposition, interference and entanglement. New quantum algorithms have emerged that proved to be more efficient than classical algorithms. Particularly, Grover’s search algorithm can find a specific element out of a set of N elements with complexity O(√N). Applications of Grover’s algorithm to optimization problems are currently being studied by other researchers, and in this thesis, a new adaptive search method based on Grover’s algorithm applied to several biobjective optimization problems is introduced. This new algorithm is compared against one of the most cited multiobjective optimization algorithms known as NSGA-II. Experimental evidence suggests that the quantum optimization method proposed in this work is at least as effective as NSGA-II in average, considering an equal number of executions. The proposed quantum algorithm, however, only requires approximately the square root of the number of evaluations executed by NSGA-II. Also, two different types of oracles with regard to the proposed algorithm were considered and the experimental results have shown that one of this oracles has requiered less iterations for similar performance.

Hiu Yung Wong