Fugu-MT 論文翻訳(概要): Quantum Search with Noisy Oracle

論文の概要: Quantum Search with Noisy Oracle

arxiv url: http://arxiv.org/abs/2309.14944v1
Date: Tue, 26 Sep 2023 14:00:23 GMT
ステータス: 処理完了
システム内更新日: 2023-09-27 13:34:17.273155
Title: Quantum Search with Noisy Oracle
Title（参考訳）: 雑音の多いoracleによる量子検索
Authors: Ansis Rosmanis
Abstract要約: すべてのオラクル呼び出しに対して、確率$p>0$はクエリレジスタを完全に非分極するが、そうでなければ適切に動作する。すべての$ple 0.99$に対して、非構造化検索の量子ノイズ-クエリの複雑さは$tildeTheta(maxnp,sqrtn)$であることを示す。下限の$Omega(maxnp,sqrt n)$は、デフォーカスノイズに対しても保持され、全てのオラクル呼び出しに対して、エラーが発生したかどうかを示すフラグが与えられる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum $\mathrm{O}(\sqrt{n})$-query algorithms in this setting, even for constant $p$. We show that, for all $p\le 0.99$, the quantum noisy-query complexity of the unstructured search is $\tilde\Theta(\max\{np,\sqrt{n}\})$. The lower bound $\Omega(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.
Abstract（参考訳）: 我々は、全てのオラクルコールに対して、確率$p>0$でクエリレジスタを完全に非分極するが、それ以外は適切に機能するノイズの多いオラクルにアクセスする量子検索アルゴリズムを考える。以前の結果は、定数$p$であっても、この設定で量子$\mathrm{o}(\sqrt{n})$-queryアルゴリズムを除外していなかった。すべての$p\le 0.99$に対し、非構造化探索の量子ノイズクエリ複雑性は$\tilde\theta(\max\{np,\sqrt{n}\})$である。下限の$\Omega(\max\{np,\sqrt 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)
Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文参考訳（メタデータ） (2023-06-02T17:49:35Z)
On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文参考訳（メタデータ） (2023-03-20T08:17:32Z)
Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文参考訳（メタデータ） (2023-03-03T18:23:20Z)
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)
Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文参考訳（メタデータ） (2021-11-29T19:26:28Z)
Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文参考訳（メタデータ） (2021-05-18T06:51:11Z)
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)
Resonant Quantum Search with Monitor Qubits [0.0]
連続的ハミルトニアンと共振を利用した一般化探索問題($N$項目中$k$マークされた項目を探索する)のアルゴリズムを提案する。この共振アルゴリズムはGroverアルゴリズムと同じ時間複雑性$O(sqrtN/k)$を持つ。
論文参考訳（メタデータ） (2020-02-21T19:31:34Z)

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