論文の概要: Robust quantum minimum finding with an application to hypothesis
selection
- arxiv url: http://arxiv.org/abs/2003.11777v1
- Date: Thu, 26 Mar 2020 07:42:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-19 22:16:28.571342
- Title: Robust quantum minimum finding with an application to hypothesis
selection
- Title（参考訳）: ロバスト量子最小探索と仮説選択への応用
- Authors: Yihui Quek, Clement Canonne, Patrick Rebentrost
- Abstract要約: 雑音コンパレータを用いて長さ$N$の最小要素を求める問題を考える。
雑音のないケースの二次的なスピードアップを保った雑音量子最小化のための量子アルゴリズムを実証する。
我々は、コンパレータが分解能に制限されたり、不確実性がある場合に、ロバストな量子最小化がアルゴリズムの有用な構築ブロックになることを期待する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding the minimum element in a list of length
$N$ using a noisy comparator. The noise is modelled as follows: given two
elements to compare, if the values of the elements differ by at least $\alpha$
by some metric defined on the elements, then the comparison will be made
correctly; if the values of the elements are closer than $\alpha$, the outcome
of the comparison is not subject to any guarantees. We demonstrate a quantum
algorithm for noisy quantum minimum-finding that preserves the quadratic
speedup of the noiseless case: our algorithm runs in time $\tilde O(\sqrt{N
(1+\Delta)})$, where $\Delta$ is an upper-bound on the number of elements
within the interval $\alpha$, and outputs a good approximation of the true
minimum with high probability. Our noisy comparator model is motivated by the
problem of hypothesis selection, where given a set of $N$ known candidate
probability distributions and samples from an unknown target distribution, one
seeks to output some candidate distribution $O(\varepsilon)$-close to the
unknown target. Much work on the classical front has been devoted to speeding
up the run time of classical hypothesis selection from $O(N^2)$ to $O(N)$, in
part by using statistical primitives such as the Scheff\'{e} test. Assuming a
quantum oracle generalization of the classical data access and applying our
noisy quantum minimum-finding algorithm, we take this run time into the
sublinear regime. The final expected run time is $\tilde O(
\sqrt{N(1+\Delta)})$, with the same $O(\log N)$ sample complexity from the
unknown distribution as the classical algorithm. We expect robust quantum
minimum-finding to be a useful building block for algorithms in situations
where the comparator (which may be another quantum or classical algorithm) is
resolution-limited or subject to some uncertainty.
- Abstract（参考訳）: 我々は、ノイズの多いコンパレータを用いて長さ$n$のリストから最小要素を見つける問題を考える。
このノイズは以下のようにモデル化される: 比較するために2つの要素が与えられると、要素の値が要素に定義されたある計量によって少なくとも$\alpha$で異なる場合、その比較は正しく行われる。
ノイズのないケースの二次的なスピードアップを保存するノイズ量子最小探索のための量子アルゴリズムを実証する:我々のアルゴリズムは時間$\tilde o(\sqrt{n (1+\delta)})$で実行され、ここで$\delta$は区間$\alpha$内の要素数の上界であり、真の最小値のよい近似を高い確率で出力する。
我々のノイズコンパレータモデルは仮説選択の問題によって動機づけられ、未知のターゲット分布からn$の既知の候補確率分布とサンプルが与えられたとき、未知のターゲットに近いいくつかの候補分布$o(\varepsilon)$を出力しようとする。
古典的側面に関する多くの研究は、シェフ\'{e} テストのような統計的な原始的手法を用いて、古典的仮説の選択の実行時間を $o(n^2)$ から $o(n)$ に短縮することに費やされている。
古典的データアクセスの量子オラクル一般化を仮定し、ノイズの多い量子最小フィニングアルゴリズムを適用すると、この実行時間をサブ線形状態にします。
最終的な実行時間は$\tilde O( \sqrt{N(1+\Delta)})$で、古典的アルゴリズムと同じ未知の分布からO(\log N)$サンプルの複雑さを持つ。
我々は、ロバストな量子最小探索は、コンパレータ(量子アルゴリズムや古典アルゴリズム)が解像度制限されたり、不確かさの対象となるような状況において、アルゴリズムにとって有用な構築ブロックであると期待する。
関連論文リスト
- Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳（メタデータ） (2020-12-06T18:39:20Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
論文 参考訳（メタデータ） (2019-12-29T01:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。