论文标题
用于学习秘密字符串及其实验演示的量子算法
Quantum algorithm for learning secret strings and its experimental demonstration
论文作者
论文摘要
在本文中，我们考虑在教师学生中的秘密学习问题：老师在{\ {\ {0,1 \}^{n}} $中有一个秘密字符串$ s \ $（x，q）\ in {\ {0,1 \}^{n}} \ times \ {0,1，\ cdots，n-1 \} $，老师返回的返回oracle $ f_ {s}（s s}（x，q）$，指示了$ quix of $ s $ s $和$ q $ quix of $ quix的长度是否更大。我们的贡献如下。 （i）我们证明，任何经典的确定性算法都至少需要$ n $ Queries对Oracle $ f_ {s} $进行$ n $ n $ n $ n $ - bit的秘密字符串$ s $在最坏情况和普通情况下，并且还提供了最佳的经典确定性算法，并呈现一种使用$ n $ queries的$ s $。 （ii）我们获得了一种量子算法，学习了$ n $ n $ necret $ s $，并使用$ \ left \ lceil n/2 \ right \ rceil $ queries to oracle $ f_s $确定性，从而证明了比经典配料的双重加速。 （iii）提出了我们在IBM云量子计算机上的量子算法的实验演示，分别分别为$ n = 2 $和$ n = 3 $的所有情况，平均成功概率为$ 85.3 \％\％\％\％\％$。
In this paper, we consider the secret-string-learning problem in the teacher-student setting: the teacher has a secret string $s\in {\{0,1\}^{n}}$, and the student wants to learn the secret $s$ by question-answer interactions with the teacher, where at each time, the student can ask the teacher with a pair $(x, q) \in {\{0,1\}^{n}}\times\{0,1,\cdots, n-1\}$ and the teacher returns a bit given by the oracle $f_{s}(x,q)$ that indicates whether the length of the longest common prefix of $s$ and $x$ is greater than $q$ or not. Our contributions are as follows. (i) We prove that any classical deterministic algorithm needs at least $n$ queries to the oracle $f_{s}$ to learn the $n$-bit secret string $s$ in both the worst case and the average case, and also present an optimal classical deterministic algorithm learning any $s$ using $n$ queries. (ii) We obtain a quantum algorithm learning the $n$-bit secret string $s$ with certainty using $\left\lceil n/2\right\rceil$ queries to the oracle $f_s$, thus proving a double speedup over classical counterparts. (iii) Experimental demonstrations of our quantum algorithm on the IBM cloud quantum computer are presented, with average success probabilities of $85.3\%$ and $82.5\%$ for all cases with $n=2$ and $n=3$ , respectively.
