Fugu-MT 論文翻訳(概要): Simplified Quantum Algorithm for the Oracle Identification Problem

論文の概要: Simplified Quantum Algorithm for the Oracle Identification Problem

arxiv url: http://arxiv.org/abs/2109.03902v1
Date: Wed, 8 Sep 2021 19:48:27 GMT
ステータス: 処理完了
システム内更新日: 2021-09-11 09:40:32.736990
Title: Simplified Quantum Algorithm for the Oracle Identification Problem
Title（参考訳）: Oracleの同定問題に対する簡易量子アルゴリズム
Authors: Leila Taghavi
Abstract要約: oracleは未知の文字列のビットに$x$ of length$n$をアクセスし、既知のセットである$Csubseteq0,1n$に属することを約束する。目標は、できるだけ少数のオラクルへのクエリを使って$x$を識別することだ。この問題に対して,クエリ複雑性を$Oleft(sqrtfracnlog M log(n/log M)+1right)$,$M$は$C$である。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In the oracle identification problem we have oracle access to bits of an unknown string $x$ of length $n$, with the promise that it belongs to a known set $C\subseteq\{0,1\}^n$. The goal is to identify $x$ using as few queries to the oracle as possible. We develop a quantum query algorithm for this problem with query complexity $O\left(\sqrt{\frac{n\log M }{\log(n/\log M)+1}}\right)$, where $M$ is the size of $C$. This bound is already derived by Kothari in 2014, for which we provide a more elegant simpler proof.
Abstract（参考訳）: oracle の識別問題では、oracle は、未知文字列 $x$ of length $n$ のビットにアクセスでき、既知のセット $c\subseteq\{0,1\}^n$ に属することを約束しています。目標は,oracleへのクエリを可能な限り少なくして,$x$を識別することだ。我々は、クエリ複雑性を$O\left(\sqrt {\frac{n\log M }{\log(n/\log M)+1}}\right)$,$M$が$C$である場合、この問題に対する量子クエリアルゴリズムを開発する。この境界はすでに2014年にKothariによって導かれており、よりエレガントな単純な証明を提供する。

関連論文リスト

Quantum Search with Noisy Oracle [0.0]
すべてのオラクル呼び出しに対して、確率$p>0$はクエリレジスタを完全に非分極するが、そうでなければ適切に動作する。すべての$ple 0.99$に対して、非構造化検索の量子ノイズ-クエリの複雑さは$tildeTheta(maxnp,sqrtn)$であることを示す。下限の$Omega(maxnp,sqrt n)$は、デフォーカスノイズに対しても保持され、全てのオラクル呼び出しに対して、エラーが発生したかどうかを示すフラグが与えられる。
論文参考訳（メタデータ） (2023-09-26T14:00: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)
Optimal Clustering with Noisy Queries via Multi-Armed Bandit [19.052525950282234]
多くのアプリケーションによって動機づけられた私たちは、欠陥のあるオラクルでクラスタリングを研究します。我々は,$O(fracn)delta2 + textpoly(k,frac1delta, log n)$クエリを用いた新しい時間アルゴリズムを提案する。我々の主な要素は、我々の問題と多腕バンディットの興味深い関係である。
論文参考訳（メタデータ） (2022-07-12T08:17:29Z)
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)
The Sparse Vector Technique, Revisited [67.57692396665915]
我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-10-02T10:50:52Z)
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)
Fast Classical and Quantum Algorithms for Online $k$-server Problem on Trees [0.19573380763700712]
木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。 Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-08-01T14:21:45Z)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。