論文の概要: Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems
- arxiv url: http://arxiv.org/abs/2211.10667v1
- Date: Sat, 19 Nov 2022 11:14:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 02:00:19.502029
- Title: Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems
- Title（参考訳）: 隠れ文字列同定のための量子アルゴリズムとマトロイド問題への応用
- Authors: Xiaowei Huang, Shihao Zhang and Lvzhou Li
- Abstract要約: 我々は、ペアの$s, s'$を特定するために、最大内部積のオラクルに$O(1)$クエリを消費する量子アルゴリズムを提案する。
また、サブセットのオラクルに$fracn2+O(sqrtn)$クエリを消費する量子アルゴリズムを提案し、任意の古典的アルゴリズムが少なくとも$n+Omega(1)$クエリを必要とすることを証明した。
- 参考スコア（独自算出の注目度）: 8.347058637480506
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we explore quantum speedups for the problem, inspired by
matroid theory, of identifying a pair of $n$-bit binary strings that are
promised to have the same number of 1s and differ in exactly two bits, by using
the max inner product oracle and the sub-set oracle. More specifically, given
two string $s, s'\in\{0, 1\}^n$ satisfying the above constraints, for any
$x\in\{0, 1\}^n$ the max inner product oracle $O_{max}(x)$ returns the max
value between $s\cdot x$ and $s'\cdot x$, and the sub-set oracle $O_{sub}(x)$
indicates whether the index set of the 1s in $x$ is a subset of that in $s$ or
$s'$. We present a quantum algorithm consuming $O(1)$ queries to the max inner
product oracle for identifying the pair $\{s, s'\}$, and prove that any
classical algorithm requires $\Omega(n/\log_{2}n)$ queries. Also, we present a
quantum algorithm consuming $\frac{n}{2}+O(\sqrt{n})$ queries to the subset
oracle, and prove that any classical algorithm requires at least $n+\Omega(1)$
queries. Therefore, quantum speedups are revealed in the two oracle models.
Furthermore, the above results are applied to the problem in matroid theory of
finding all the bases of a 2-bases matroid, where a matroid is called $k$-bases
if it has $k$ bases.
- Abstract（参考訳）: 本稿では,最大内積オラクルとサブセットオラクルを用いて,同じ数1sを持つことを約束する$n$-bitバイナリ文字列のペアを正確に2ビットで識別する,マトロイド理論にインスパイアされたこの問題に対する量子スピードアップについて検討する。
具体的には、2つの文字列 $s, s'\in\{0, 1\}^n$ が上記の制約を満たすと、任意の$x\in\{0, 1\}^n$ の極大内積 oracle $O_{max}(x)$ は $s\cdot x$ と $s'\cdot x$ の間の最大値を返す。
量子アルゴリズムは最大内積オラクルに対して$O(1)$クエリを消費し、$\{s, s'\}$を識別し、任意の古典的アルゴリズムが$Omega(n/\log_{2}n)$クエリを必要とすることを証明する。
また、サブセットオラクルへの$\frac{n}{2}+o(\sqrt{n})$クエリを消費する量子アルゴリズムを示し、任意の古典的アルゴリズムが少なくとも$n+\omega(1)$クエリを必要とすることを示す。
したがって、量子スピードアップは2つのoracleモデルで明らかにされる。
さらに、上記の結果は、マトロイドが$k$塩基を持つ場合、マトロイドが$k$塩基と呼ばれる2塩基のマトロイドのすべての基底を見つけるという問題に適用される。
関連論文リスト
- Quantum Search with Noisy Oracle [0.0]
すべてのオラクル呼び出しに対して、確率$p>0$はクエリレジスタを完全に非分極するが、そうでなければ適切に動作する。
すべての$ple 0.99$に対して、非構造化検索の量子ノイズ-クエリの複雑さは$tildeTheta(maxnp,sqrtn)$であることを示す。
下限の$Omega(maxnp,sqrt n)$は、デフォーカスノイズに対しても保持され、全てのオラクル呼び出しに対して、エラーが発生したかどうかを示すフラグが与えられる。
論文 参考訳（メタデータ） (2023-09-26T14:00:23Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳（メタデータ） (2023-02-20T19:11:44Z) - 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 algorithm for learning secret strings and its experimental
demonstration [2.924463125497859]
教師-学生設定における秘密弦学習問題について考察する。
我々は,$n$クエリを用いて任意の$s$を学習する古典的決定論的アルゴリズムを提案する。
我々は,n$-bit秘密文字列$s$を確実に学習する量子アルゴリズムを得る。
論文 参考訳（メタデータ） (2022-06-22T17:15:45Z) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - 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) - Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
oracleは未知の文字列のビットに$x$ of length$n$をアクセスし、既知のセットである$Csubseteq0,1n$に属することを約束する。
目標は、できるだけ少数のオラクルへのクエリを使って$x$を識別することだ。
この問題に対して,クエリ複雑性を$Oleft(sqrtfracnlog M log(n/log M)+1right)$,$M$は$C$である。
論文 参考訳（メタデータ） (2021-09-08T19:48:27Z) - 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) - Query complexity of heavy hitter estimation [6.373263986460191]
我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。
それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。
それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-05-29T07:15:46Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。