論文の概要: Quantum algorithm for learning secret strings and its experimental
demonstration
- arxiv url: http://arxiv.org/abs/2206.11221v1
- Date: Wed, 22 Jun 2022 17:15:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-08 09:36:37.035404
- Title: Quantum algorithm for learning secret strings and its experimental
demonstration
- Title（参考訳）: 秘密文字列学習のための量子アルゴリズムとその実験的実証
- Authors: Yongzhen Xu, Shihao Zhang, Lvzhou Li
- Abstract要約: 教師-学生設定における秘密弦学習問題について考察する。
我々は,$n$クエリを用いて任意の$s$を学習する古典的決定論的アルゴリズムを提案する。
我々は,n$-bit秘密文字列$s$を確実に学習する量子アルゴリズムを得る。
- 参考スコア（独自算出の注目度）: 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.
- 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.
私たちの貢献は以下の通りです。
(i)あらゆる古典的な決定論的アルゴリズムが、最悪のケースと平均ケースの両方において、n$-bitの秘密文字列を学習するために、oracle $f_{s}$に対して少なくとも$n$クエリを必要とすることを証明し、また$n$クエリを使用して$s$を学習する最適な古典的決定論的アルゴリズムを示す。
(ii) oracle $f_s$に対して$\left\lceil n/2\right\rceil$クエリを使用して、n$-bit の秘密文字列 $s$ を学習する量子アルゴリズムを得る。
(iii)ibm cloud quantum computer上での量子アルゴリズムの実験的な実証を行い、それぞれ$n=2$と$n=3$の全てのケースにおいて平均成功確率は85.3\%$と82.5\%$である。
関連論文リスト
- Learning low-degree quantum objects [5.2373060530454625]
低次量子オブジェクトを、$ell$-distanceで$varepsilon$-errorまで学習する方法を示す。
我々の主な技術的貢献は、量子チャネルと完全有界ポリリノミアルに対する新しいボネンブラスト・ヒル不等式である。
論文 参考訳（メタデータ） (2024-05-17T17:36:44Z) - A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。
特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-28T21:23:40Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
我々は、ペアの$s, s'$を特定するために、最大内部積のオラクルに$O(1)$クエリを消費する量子アルゴリズムを提案する。
また、サブセットのオラクルに$fracn2+O(sqrtn)$クエリを消費する量子アルゴリズムを提案し、任意の古典的アルゴリズムが少なくとも$n+Omega(1)$クエリを必要とすることを証明した。
論文 参考訳（メタデータ） (2022-11-19T11:14:19Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z) - Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。
ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。
本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
論文 参考訳（メタデータ） (2019-12-31T14:52:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。