Quantum Circuit for Random Forest Prediction
This work addresses the challenge of efficient quantum implementation for machine learning algorithms, but it is incremental as it builds on previous methods for quantum prediction.
The authors tackled the problem of implementing random forest prediction on a quantum computer by designing a quantum circuit that reduces the number of CNOT gates from O(4^{|X|+n+h+2}) to O(2^{n+2h+1}), where n is the number of trees, h is tree height, and |X| is attribute length.
In this work, we present a quantum circuit for a binary classification prediction algorithm using a random forest model. The quantum prediction algorithm is presented in our previous works. We construct a circuit and implement it using qiskit tools (python module for quantum programming). One of our goals is reducing the number of basic quantum gates (elementary gates). The set of basic quantum gates which we use in this work consists of single-qubit gates and a controlled NOT gate. The number of CNOT gates in our circuit is estimated by $O(2^{n+2h+1})$ , when trivial circuit decomposition techniques give $O(4^{|X|+n+h+2})$ CNOT gates, where $n$ is the number of trees in a random forest model, $h$ is a tree height and $|X|$ is the length of attributes of an input object $X$. The prediction process returns an index of the corresponding class for the input $X$.