Quantum algorithm for learning secret strings and its experimental demonstration

Abstract

In this paper, we consider the secret-string-learning problem in the teacher-student setting: the teacher has a secret string s ∈ { 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 ) ∈ { 0 , 1 } n × { 0 , 1 , · · · , 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 (cid:100) n/ 2 (cid:101) 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.