A quantum algorithm based on entanglement measure for classifying Boolean multivariate function into novel hidden classes

Abstract In this paper, we propose a novel algorithm that solves a generalized version of the Deutsch-Jozsa problem. The proposed algorithm has the potential to classify an oracle U F , that represents an unknown Boolean function on n Boolean variables, to one of 2 n different classes instead of only two classes which are constant and balanced classes in the case of Deutsch-Jozsa algorithm. The proposed algorithm is based on the use of entanglement measure to explore 2 n - 2 additional classes compared to the standard Deutsch-Jozsa algorithm. In addition, the comparison between the proposed quantum algorithm and the classical one is investigated in details. The comparison shows that the proposed algorithm is faster when the number of Boolean variables exceed 14 variables.