Quantum algorithm for learning secret strings and its experimental demonstration

• URL: http://arxiv.org/abs/2206.11221v1
• Date: Wed, 22 Jun 2022 17:15:45 GMT
• Title: Quantum algorithm for learning secret strings and its experimental demonstration
• Authors: Yongzhen Xu, Shihao Zhang, Lvzhou Li
• Abstract summary: We consider the secret-string-learning problem in the teacher-student setting. We present an optimal classical deterministic algorithm learning any $s$ using $n$ queries. We obtain a quantum algorithm learning the $n$-bit secret string $s$ with certainty.
• Score: 2.924463125497859
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Learning low-degree quantum objects [5.2373060530454625]
  We show how to learn low-degree quantum objects up to $varepsilon$-error in $ell$-distance. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely boundedpolynomials.
  arXiv  Detail & Related papers  (2024-05-17T17:36:44Z)
• A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
  We present an algorithm that learns the edges of $G$ in at most $tildeO(d2m3/4)$ quantum queries. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $tildeO(sqrtm)$ quantum queries.
  arXiv  Detail & Related papers  (2024-02-28T21:23:40Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Quantum Algorithms for Identifying Hidden Strings with Applications to Matroid Problems [8.347058637480506]
  We present a quantum algorithm consuming $O(1)$ queries to the max inner product oracle for identifying the pair $s, s'$. Also, we present a quantum algorithm consuming $fracn2+O(sqrtn)$ queries to the subset oracle, and prove that any classical algorithm requires at least $n+Omega(1)$ queries.
  arXiv  Detail & Related papers  (2022-11-19T11:14:19Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2021-11-09T16:50:18Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  We show a quantum algorithm with complexity $widetilde O(T_Dn)$, where $T_D D+1$. While the best known classical algorithm is $textpoly(m,n)log n T_Dn$, the time complexity of our quantum algorithm is $textpoly(m,n)log n T_Dn$.
  arXiv  Detail & Related papers  (2021-04-29T14:50:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)
• Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
  Goldreich-Levin algorithm was originally proposed for a cryptographic purpose and then applied to learning. It takes a $poly(n,frac1epsilonlogfrac1delta)$ time to output the vectors $w$ with Walsh coefficients $S(w)geqepsilon$ with probability at least $1-delta$. In this paper, a quantum algorithm for this problem is given with query complexity $O(fraclogfrac1deltaepsilon4)$, which is independent of $n$.
  arXiv  Detail & Related papers  (2019-12-31T14:52:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.