  Relief algorithm is a feature selection algorithm used in binary
classification proposed by Kira and Rendell, and its computational complexity
remarkable increases with both the scale of samples and the number of features.
In order to reduce the complexity, a quantum feature selection algorithm based
on Relief algorithm, also called quantum Relief algorithm, is proposed. In the
algorithm, all features of each sample are superposed by a certain quantum
state through the \emph{CMP} and \emph{rotation} operations, then the
\emph{swap test} and measurement are applied on this state to get the
similarity between two samples. After that, \emph{Near-hit} and
\emph{Near-miss} are obtained by calculating the maximal similarity, and
further applied to update the feature weight vector $WT$ to get $WT'$ that
determine the relevant features with the threshold $\tau$. In order to verify
our algorithm, a simulation experiment based on IBM Q with a simple example is
performed. Efficiency analysis shows the computational complexity of our
proposed algorithm is \emph{O(M)}, while the complexity of the original Relief
algorithm is \emph{O(NM)}, where $N$ is the number of features for each sample,
and $M$ is the size of the sample set. Obviously, our quantum Relief algorithm
has superior acceleration than the classical one.
