Chapter 4.2 Fault-tolerant Quantum Perceptron

This content of this section corresponds to the Chapter 4.2 of our paper. Please refer to the original paper for more details.

The primary aim of advancing quantum machine learning is to harness the computational advantages of quantum mechanics to enhance performance across various learning tasks. These advantages manifest in several ways, including reduced runtime, lower query complexity, and improved sample efficiency compared to classical models. A notable example of this is the quantum perceptron model [@kapoor2016quantum]. As a [FTQC]{.sans-serif}-based QML algorithm grounded in the Grover search, quantum perceptron offers a quadratic improvement in the query complexity during the training over its classical counterpart. For comprehensiveness, we first introduce the Grover search algorithm, followed by a detailed explanation of the quantum perceptron model.

Grover search

Grover search [@grover1996fast] provides runtime speedups for unstructured search problems, which have broad applications in cryptography, quantum machine learning, and constraint satisfaction problems. Unlike classical search methods that require $\mathcal{O}(d)$ queries for a dataset with $d$ entries, Grover’s algorithm can identify the target element with high probability using only $\mathcal{O}(\sqrt{d})$ queries to a quantum oracle. Consequently, quantum algorithms incorporating Grover search have the potential to achieve a quadratic speedup over classical approaches.

In general, a search task can be abstracted as a function $f({x})$ such that $f({x})=1$ if ${x}$ belongs to the solution set of the search problem, and $f({x})=0$ otherwise. We consider a dataset consisting of $d=2^N$ elements, where each element is represented by the quantum state $|{x}>$ with $x=0,1,\cdots,d-1$. In this process, two key quantum oracles are introduced. The first oracle, $U_0 = 2\ket{0}\bra{0}-\mathbb{I}_{d}$, applies a phase shift of $e^{i\pi}=-1$ to all quantum states except $|0>$, which remains unchanged. The second oracle, $U_f$, operates in a similar manner: it applies a phase shift of $-1$ to quantum states that belong to the solution set while leaving all other states unaffected. The procedure for Grover search is described in Algorithm 2.

Online quantum perceptron

In classical approaches, identifying a sample that is misclassified by the current model may require up to $\mathcal{O}(d)$ queries, where $d$ denotes the size of the training dataset. In contrast, the quantum perceptron model [@kapoor2016quantum] can identify misclassified samples more efficiently by employing the Grover search algorithm, achieving a quadratic speed-up in the query complexity.

An online quantum perceptron procedure is given in Algorithm 3.