論文の概要: A generalization of Bernstein-Vazirani algorithm with multiple secret
keys and a probabilistic oracle
- arxiv url: http://arxiv.org/abs/2301.10014v1
- Date: Sat, 21 Jan 2023 19:34:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-25 13:34:48.657374
- Title: A generalization of Bernstein-Vazirani algorithm with multiple secret
keys and a probabilistic oracle
- Title（参考訳）: 複数の秘密鍵と確率的オラクルを持つベルンシュタイン・ヴァジラニアルゴリズムの一般化
- Authors: Alok Shukla, Prakash Vedula
- Abstract要約: 問題は、量子オラクルを使って複数の秘密鍵の集合から1つ以上の秘密鍵を見つけることである。
提案した量子アルゴリズムは(a)確率オラクルへの単一のクエリを用いて任意のキー(確実に)を取得することができる。
古典的なアルゴリズムでは、秘密鍵の1ビットも確実に見つけることができません。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A probabilistic version of the Bernstein-Vazirani problem (which is a
generalization of the original Bernstein-Vazirani problem) and a quantum
algorithm to solve it are proposed. The problem involves finding one or more
secret keys from a set of multiple secret keys (encoded in binary form) using a
quantum oracle. From a set of multiple unknown keys, the proposed quantum
algorithm is capable of (a) obtaining any key (with certainty) using a single
query to the probabilistic oracle and (b) finding all keys with a high
probability (approaching 1 in the limiting case). In contrast, a classical
algorithm will be unable to find even a single bit of a secret key with
certainty (in the general case). Owing to the probabilistic nature of the
oracle, a classical algorithm can only be useful in obtaining limiting
probability distributions of $ 0 $ and $ 1 $ for each bit-position of secret
keys (based on multiple oracle calls) and this information can further be used
to infer some estimates on the distribution of secret keys based on
combinatorial considerations. For comparison, it is worth noting that a
classical algorithm can be used to exactly solve the original
Bernstein-Vazirani problem (involving a deterministic oracle and a single
hidden key containing $n$ bits) with a query complexity of $\mathcal{O}(n)$. An
interesting class of problems similar to the probabilistic version of the
Bernstein-Vazirani problem can be construed, where quantum algorithms can
provide efficient solutions with certainty or with a high degree of confidence
and classical algorithms would fail to do so.
- Abstract（参考訳）: ベルンシュタイン-ヴァジラニ問題(ベルンシュタイン-ヴァジラニ問題の一般化)の確率論的バージョンとそれを解く量子アルゴリズムを提案する。
問題は、量子オラクルを使って複数の秘密鍵群(バイナリ形式でコード化されている)から1つ以上の秘密鍵を見つけることである。
複数の未知鍵の集合から、提案された量子アルゴリズムは、
a)確率的オラクルへの単一の問い合わせを用いて(確実性のある)鍵を取得すること
(b)高い確率で全ての鍵を見つけること(制限ケース1を割り当てること)。
対照的に、古典的なアルゴリズムは(一般的な場合では)秘密鍵の1ビットでも見つけることができない。
オラクルの確率的性質から、古典的なアルゴリズムは(複数のオラクルの呼び出しに基づく)秘密鍵のビット配置ごとに 0 $ と 1 $ の制限確率分布を得るのにのみ有用であり、この情報は、組合せ的考察に基づいて秘密鍵の分布に関するいくつかの推定を推測するためにさらに使うことができる。
比較のために、古典的なアルゴリズムは、元のベルンシュタイン・ヴァジラニ問題(決定論的オラクルと$n$ビットを含む単一の隠れキーを含む)を$\mathcal{O}(n)$のクエリ複雑性で正確に解くのに使えることに注意する必要がある。
ベルンシュタイン-ヴァジラニ問題の確率的バージョンに似た興味深い問題クラスは、量子アルゴリズムが確実に、あるいは高い信頼度で効率的な解を提供し、古典的アルゴリズムがそれを行うことができないような問題である。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum Truncated Differential and Boomerang Attack [10.853582091917236]
本稿では,truncated differential と boomerang cryptanalysis に焦点をあてる。
まず、対称暗号の切り詰められた微分を求めるために設計された量子アルゴリズムを提案する。
我々は、圧倒的な確率で、我々のアルゴリズムによって出力される切り離された微分は、キー空間のキーの大部分に対して高い差分確率を持つ必要があることを証明した。
論文 参考訳（メタデータ） (2024-07-21T11:34:29Z) - Grover's oracle for the Shortest Vector Problem and its application in
hybrid classical-quantum solvers [0.38366697175402226]
格子内の最短ベクトルを見つけることは、古典コンピュータと量子コンピュータの両方にとって困難であると考えられている問題である。
SVPのための最も優れた古典的、量子的、あるいはハイブリッドな古典量子アルゴリズムを見つけるためには、十分なセキュリティレベルを提供する暗号系パラメータを選択する必要がある。
グロバーの探索量子アルゴリズムは、一般的な二次的なスピードアップを提供する。
我々はGroverの小さなSVPインスタンスの量子探索と最先端の古典的解法を組み合わせる方法について分析する。
論文 参考訳（メタデータ） (2024-02-21T16:05:49Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - The NISQ Complexity of Collision Finding [2.9405711598281536]
現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
論文 参考訳（メタデータ） (2022-11-23T13:55:28Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳（メタデータ） (2022-09-08T17:55:30Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。