Implementing the Grover algorithm in homomorphic encryption schemes

Abstract

We apply quantum homomorphic encryption (QHE) schemes suitable for circuits with a polynomial number of 𝑇+𝑇† gates to Grover's algorithm, performing a simulation in Qiskit of a Grover circuit that contains three qubits. The 𝑇+𝑇†-gate complexity of Grover's algorithm is also analyzed in order to show that any Grover circuit can be evaluated homomorphically in an efficient manner. We discuss how to apply these QHE schemes to allow for the efficient homomorphic evaluation of any Grover circuit composed of 𝑛 qubits using 𝑛−2 extra ancilla qubits. We also show how the homomorphic evaluation of the special case where there is only one marked item can be implemented using an algorithm that makes the decryption process more efficient compared with the standard Grover algorithm.