论文标题
量子缓解算法
Quantum Relief Algorithm
论文作者
论文摘要
Relief算法是Kira和Rendell提出的二进制分类中使用的特征选择算法，其计算复杂性随着样本的规模和特征数量而显着增加。为了降低复杂性，提出了一种基于浮雕算法（也称为量子救济算法）的量子特征选择算法。在该算法中，每个样品的所有特征都是通过\ emph {cmp}和\ emph {rotation}操作的特定量子状态超级构的，然后将\ emph {swap test}应用于此状态，以获得两个样品之间的相似性。之后，通过计算最大相似性来获得\ emph {近击}和\ emph {接近{接近}，并进一步应用以更新功能vector $ wt $以获取$ wt'$，以确定与阈值$τ$的相关功能。为了验证我们的算法，执行了基于IBM Q的模拟实验，并进行了一个简单的示例。效率分析表明，我们提出的算法的计算复杂性为\ emph {o（m）}，而原始救济算法的复杂性为\ emph {o（nm）}，其中$ n $是每个样品的特征数，而$ m $是样品集的大小。显然，我们的量子缓解算法比经典算法具有较高的加速度。
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 $τ$. 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.
