論文の概要: Effects of noise on performance of Bernstein-Vazirani algorithm
- arxiv url: http://arxiv.org/abs/2305.19745v2
- Date: Mon, 12 Aug 2024 07:35:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 01:08:32.461792
- Title: Effects of noise on performance of Bernstein-Vazirani algorithm
- Title（参考訳）: Bernstein-Vaziraniアルゴリズムの性能に及ぼす雑音の影響
- Authors: Archi Gupta, Priya Ghosh, Kornikar Sen, Ujjwal Sen,
- Abstract要約: ベルンシュタイン・ヴァジラーニ回路で用いられるアダマール門の効果に様々なガラス障害を導入する。
その結果,全ての症例において障害強度の増加に伴い,アルゴリズムの有効性が低下することが判明した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Bernstein-Vazirani (BV) algorithm offers exceptional accuracy in finding the hidden bit string of a function. We explore how the algorithm performs in real-world situations where noise can potentially interfere with its performance. In order to assess the impact of imperfect equipments, we introduce various forms of glassy disorders into the effect of the Hadamard gates used in the Bernstein-Vazirani circuit. We incorporated disorders of five different forms, viz., Haar-uniform with finite cutoff, spherical Gaussian, discrete circular, spherical Cauchy-Lorentz, and squeezed. We find that the effectiveness of the algorithm decreases with increasing disorder strength in all cases. Additionally, we demonstrate that as the number of bits in the secret string increases, the success probability of correctly guessing the string becomes increasingly insensitive to the type of disorder and instead depends only on the mean and spread of the disorder. We compare our results with the performance of the analogous classical algorithm in the presence of similar noise. When the length of the secret string is small or moderate, the quantum BV algorithm is found to be more efficient compared to the classical algorithm for almost all types of disorders under consideration, unless the strength of the disorder is very high and the disorder follows a discrete circular distribution. However, if we move to extremely large secret strings, the success probability of the disordered BV algorithm merges with the success probability of the disordered classical algorithm for all considered disorders having arbitrary strengths. The limit on the length of the string after which the efficiency of the quantum algorithm becomes equivalent to the classical algorithm depends on the amount of disorder and not on the type of disorder.
- Abstract（参考訳）: ベルンシュタイン・ヴァジラニ(Bernstein-Vazirani, BV)アルゴリズムは、関数の隠れビット列を見つける際、例外的な精度を提供する。
実環境において、ノイズが性能を阻害する可能性のある状況において、アルゴリズムがどのように機能するかを考察する。
不完全な機器の影響を評価するため、ベルンシュタイン・ヴァジラーニ回路で用いられるアダマール門の効果に様々な形態のガラス障害を導入する。
我々は, 有限カットオフ, 球状ガウス, 離散円, 球状コーシーローレンツの5種類の障害を加味し, 圧縮した。
その結果,全ての症例において障害強度の増加に伴い,アルゴリズムの有効性が低下することが判明した。
さらに、秘密文字列のビット数が増加するにつれて、文字列を正しく推測する成功確率は、障害の種類に敏感になり、その代わりに、障害の平均と拡散にのみ依存することを示した。
この結果と類似した雑音の存在下での古典的アルゴリズムの性能を比較した。
秘密文字列の長さが小さい場合、量子BVアルゴリズムは、障害の強度が非常に高く、障害が離散円分布に従わない限り、考慮中のほとんど全ての障害に対して古典的なアルゴリズムよりも効率的である。
しかし、極端に大きな秘密文字列に移動すると、乱れたBVアルゴリズムの成功確率は、任意の強みを持つ全ての考察された障害に対して、乱れた古典的アルゴリズムの成功確率とマージされる。
量子アルゴリズムの効率が古典的アルゴリズムと等価になる文字列の長さの制限は、障害の種類ではなく、障害の量に依存する。
関連論文リスト
- Resilience-Runtime Tradeoff Relations for Quantum Algorithms [0.7371081631199642]
アルゴリズム設計における主要なアプローチは、アルゴリズムのコンパイルにおける操作数を最小化することである。
摂動雑音に対するアルゴリズムのレジリエンスを特徴付ける枠組みを開発する。
我々は、このフレームワークがどのようにして特定のノイズに耐えられるアルゴリズムのコンパイルを識別できるかを示す。
論文 参考訳（メタデータ） (2024-08-05T18:31:14Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Quantum Advantage of Noisy Grover's Algorithm [3.803244458097104]
グロバーの探索アルゴリズムは、古典的な探索アルゴリズムの可能性を証明した唯一の量子アルゴリズムである。
本稿では,Groverアルゴリズムの雑音閾値を指数関数的に改善する耐雑音性手法を提案する。
論文 参考訳（メタデータ） (2023-06-19T11:17:32Z) - An adaptive Bayesian quantum algorithm for phase estimation [0.0]
平均絶対誤差と平均二乗誤差の最適2次スケーリングを実現するためのコヒーレンスに基づく位相推定アルゴリズムを提案する。
ノイズの存在下で、我々のアルゴリズムは理論的な下界に近づく誤差を生成する。
論文 参考訳（メタデータ） (2023-03-02T19:00:01Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。
特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文 参考訳（メタデータ） (2023-02-13T19:57:17Z) - Better-than-classical Grover search via quantum error detection and
suppression [0.0]
グロバーの探索アルゴリズムは証明可能な量子優位性を示す最初の量子アルゴリズムの1つである。
本稿では,これまでに実証された最大規模のGrover検索アルゴリズムの古典的成功確率について報告する。
論文 参考訳（メタデータ） (2022-11-08T20:31:02Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Bregman divergence based em algorithm and its application to classical
and quantum rate distortion theory [61.12008553173672]
本稿では,Bregman分散系における指数サブファミリーと混合サブファミリー間のBregman分散の最小化問題に対処する。
このアルゴリズムを量子設定を含む歪みとその変種の評価に適用する。
論文 参考訳（メタデータ） (2022-01-07T13:33:28Z) - Tunable Tradeoff between Quantum and Classical Computation via
Nonunitary Zeno-like Dynamics [0.5249805590164902]
アルゴリズムは、その効率の厳密な解析的下界を導出することにより、純粋量子バージョンと同様のスケールを示す。
また、ノイズを受けるアルゴリズムの挙動を調べた結果、特定のオラクルと運用上のエラーの下では、測定に基づくアルゴリズムが標準アルゴリズムよりも優れていることがわかった。
論文 参考訳（メタデータ） (2020-11-22T00:57:17Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。