Quantum Relief algorithm

DOI10.1007/S11128-018-2048-XzbMATH Open1400.68178arXiv2002.00184OpenAlexW3098745869MaRDI QIDQ1994722FDOQ1994722

Authors: Wen-Jie Liu, Pei-Pei Gao, Wenbin Yu, Ching-Nung Yang, Zhiguo Qu 

Publication date: 1 November 2018

Published in: Quantum Information Processing (Search for Journal in Brave)

Abstract: 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 $W{T}^{\prime }$ that determine the relevant features with the threshold $au$. 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.

Full work available at URL: https://arxiv.org/abs/2002.00184

Recommendations

• Quantum-based feature selection for multiclassification problem in complex systems with edge computing
• Quantum-enhanced feature selection with forward selection and backward elimination
• Quantum \(K\) nearest neighbor algorithm
• Quantum \(K\)-nearest neighbor classification algorithm based on Hamming distance
• Quantum algorithm for \(k\)-nearest neighbors classification based on the metric of Hamming distance

zbMATH Keywords

feature selectionrotation operationCMP operationIBM qquantum Relief algorithmswap test

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cites Work

• Title not available (Why is that?)
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Title not available (Why is that?)
• Rapid solution of problems by quantum computation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Title not available (Why is that?)
• Foundations of machine learning
• Computational Methods of Feature Selection
• Quantum adiabatic machine learning
• Equivalences and Separations Between Quantum and Classical Learnability

Cited In (11)

• Quantum-based feature selection for multiclassification problem in complex systems with edge computing
• Quantum algorithm for classical multidimensional scaling
• Quantum privacy-preserving price E-negotiation
• Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms
• An efficient quantum private query protocol based on oracle and Grover iteration
• Continuous variable quantum steganography protocol based on quantum identity
• Effects of quantum noises on \(\chi\) state-based quantum steganography protocol
• A relative uncertainty measure for fuzzy rough feature selection
• A unitary operator construction solution based on Pauli group for maximal dense coding with a class of symmetric states
• Quantum transport on large-scale sparse regular networks by using continuous-time quantum walk
• Synthesis of Deutsch-Jozsa circuits and verification by IBM Q

Uses Software

• QISKit

This page was built for publication: Quantum Relief algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1994722)