Quantum machine learning (QML) aims to effectively solve certain learning tasks that are challenging for classical methods [1]}, [2]}, [3]}. Theoretical studies have demonstrated that many QML algorithms, e.g., quantum perceptron [4]}, quantum support vector machine [5]}, and quantum differentially private sparse learning [6]}, outperform their classical counterparts in the measure of runtime complexity. Despite runtime advantages, the required resources to implement these algorithms are expensive and even unaffordable for noisy intermediate-scale quantum (NISQ) machines [2]}, [8]}. Meanwhile, experimental studies have confirmed the feasibility of using near-term devices to accomplish various QML tasks such as classification [9]} and image generation [10]}, [11]}, and drug design [12]}. However, theoretical results to guarantee quantum advantages of these NISQ-based QML algorithms are lacking. Therefore, an open question in the field of QML is `What QML algorithms can be executed on NISQ devices with evident advantages?'.
