Scholarlink

<p>With the growing interest in quantum machine learning, the perceptron, a fundamental building block in traditional machine learning, has emerged as a valuable model for exploring the potential of quantum algorithms. In this work, we make two principal contributions. First, we revisit the <i>quantum version space perceptron</i> algorithm proposed by Kapoor et al. (2016), by identifying and correcting a flawed complexity assumption. We show that the query complexity of the algorithm is dimension-dependent, which has significant implications for its behaviour in high-dimensional regimes under worst-case scenarios. Second, we propose and analyse two <i>quantum-enhanced</i> cutting-plane algorithms for perceptron learning. Specifically, we leverage established quantum subroutines such as <i>Grover’s search</i> and <i>quantum walk search</i>, and provide detailed algorithmic constructions together with query and arithmetic complexity analyses. Our results establish improved complexity bounds under an idealised implementation framework and noise-free quantum computational models, offering insights into the trade-offs between margin dependence, dimensional dependence, and quantum resources. These findings provide a refined understanding of quantum perceptron models and their theoretical computational complexity properties.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On quantum perceptron learning via quantum search

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年6月19日

查看全文
  • Xiaoyu Sun,
  • Mathieu Roget,
  • Giuseppe Di Molfetta,
  • Hachem Kadri

摘要

With the growing interest in quantum machine learning, the perceptron, a fundamental building block in traditional machine learning, has emerged as a valuable model for exploring the potential of quantum algorithms. In this work, we make two principal contributions. First, we revisit the quantum version space perceptron algorithm proposed by Kapoor et al. (2016), by identifying and correcting a flawed complexity assumption. We show that the query complexity of the algorithm is dimension-dependent, which has significant implications for its behaviour in high-dimensional regimes under worst-case scenarios. Second, we propose and analyse two quantum-enhanced cutting-plane algorithms for perceptron learning. Specifically, we leverage established quantum subroutines such as Grover’s search and quantum walk search, and provide detailed algorithmic constructions together with query and arithmetic complexity analyses. Our results establish improved complexity bounds under an idealised implementation framework and noise-free quantum computational models, offering insights into the trade-offs between margin dependence, dimensional dependence, and quantum resources. These findings provide a refined understanding of quantum perceptron models and their theoretical computational complexity properties.