论文标题
量子支持向量机的复杂性
The complexity of quantum support vector machines
论文作者
论文摘要
量子支持向量机采用量子电路来定义内核函数。已经表明，与某些数据集的任何已知经典算法相比，这种方法提供了可证明的指数加速。此类模型的训练对应于通过其原始公式或双重公式解决凸优化问题。由于量子力学的概率性质，训练算法受统计不确定性的影响，这对其复杂性产生了重大影响。我们表明，双重问题可以在$ o（m^{4.67}/\ varepsilon^2）$ Quantum电路评估中解决，其中$ m $表示数据集的大小和$ \ varepsilon $与确切期望值相比，解决方案的准确性与确切的预期值相比，仅在理论中可以获得。我们证明，可以在$ o（\ min \ {m^2/\ varepsilon^6，\，1/\ varepsilon^{10} {10} {10} \}）$评估中以$ o（\ min \ {m^2/\ varepsilon^6，\ {m^2/\ varepsilon^6，\ oc（min \ {m^2/\ varepsilon^6）$评估，可以通过$ o（\ min \ {m^2/\ varepsilon^6，\ ock {m^2/\ varepsilon^6，$ o）进行证明。伴随的经验结果表明这些分析复杂性基本紧密。此外，我们研究了量子支持向量机的变分近似，并表明他们的启发式训练在我们的实验中取得了更好的缩放。
Quantum support vector machines employ quantum circuits to define the kernel function. It has been shown that this approach offers a provable exponential speedup compared to any known classical algorithm for certain data sets. The training of such models corresponds to solving a convex optimization problem either via its primal or dual formulation. Due to the probabilistic nature of quantum mechanics, the training algorithms are affected by statistical uncertainty, which has a major impact on their complexity. We show that the dual problem can be solved in $O(M^{4.67}/\varepsilon^2)$ quantum circuit evaluations, where $M$ denotes the size of the data set and $\varepsilon$ the solution accuracy compared to the ideal result from exact expectation values, which is only obtainable in theory. We prove under an empirically motivated assumption that the kernelized primal problem can alternatively be solved in $O(\min \{ M^2/\varepsilon^6, \, 1/\varepsilon^{10} \})$ evaluations by employing a generalization of a known classical algorithm called Pegasos. Accompanying empirical results demonstrate these analytical complexities to be essentially tight. In addition, we investigate a variational approximation to quantum support vector machines and show that their heuristic training achieves considerably better scaling in our experiments.
