Estimating the Number of Junta Variables for Optimizing Boolean Functions in Quantum Memories

Optimizing Boolean function components to have the minimum number of inputs in order to reduce the memory space required during these functions in computing devices is a significant demand. This paper proposes a quantum computation approach based on the degree-of-entanglement quantum computation model to estimate the number of junta variables of an unknown Boolean function presented through an oracle. The time complexity of the developed quantum approach is independent of the number of inputs and depends on an allowable assigned error ϵ. Thus, the time complexity of the developed algorithm is O(ϵ−2), compared to O(2n+1) in the traditional approach. Also, the memory space of the developed approach is linear, O(2n+4), in terms of the number of inputs compared to the exponential memory space O(2n+1) using the traditional approach. Therefore, the developed quantum approach has exponential supremacy in comparison to the traditional approach. The developed approach was implemented practically using both the Qiskit simulator and the IBM real quantum computer. The obtained results expose high statistical fidelities between the empirical and theoretical results.