論文の概要: The NISQ Complexity of Collision Finding
- arxiv url: http://arxiv.org/abs/2211.12954v2
- Date: Wed, 28 Feb 2024 11:00:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-29 19:35:14.688386
- Title: The NISQ Complexity of Collision Finding
- Title（参考訳）: 衝突発見のNISQ複雑さ
- Authors: Yassine Hamoudi, Qipeng Liu, Makrand Sinha
- Abstract要約: 現代の暗号における基本的なプリミティブである衝突耐性ハッシュは、同じハッシュ値を生成する入力を効率的に見つける方法がないことを保証している。
現在、量子敵はNISQのパワーを備えたフルスケールのコンピュータを必要とする。
本稿では, NISQアルゴリズムの3つの異なるモデルについて検討する。
- 参考スコア（独自算出の注目度）: 2.9405711598281536
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Collision-resistant hashing, a fundamental primitive in modern cryptography,
ensures that there is no efficient way to find distinct inputs that produce the
same hash value. This property underpins the security of various cryptographic
applications, making it crucial to understand its complexity. The complexity of
this problem is well-understood in the classical setting and $\Theta(N^{1/2})$
queries are needed to find a collision. However, the advent of quantum
computing has introduced new challenges since quantum adversaries
$\unicode{x2013}$ equipped with the power of quantum queries $\unicode{x2013}$
can find collisions much more efficiently. Brassard, H\"oyer and Tapp and
Aaronson and Shi established that full-scale quantum adversaries require
$\Theta(N^{1/3})$ queries to find a collision, prompting a need for longer hash
outputs, which impacts efficiency in terms of the key lengths needed for
security.
This paper explores the implications of quantum attacks in the
Noisy-Intermediate Scale Quantum (NISQ) era. In this work, we investigate three
different models for NISQ algorithms and achieve tight bounds for all of them:
(1) A hybrid algorithm making adaptive quantum or classical queries but with
a limited quantum query budget, or
(2) A quantum algorithm with access to a noisy oracle, subject to a dephasing
or depolarizing channel, or
(3) A hybrid algorithm with an upper bound on its maximum quantum depth;
i.e., a classical algorithm aided by low-depth quantum circuits.
In fact, our results handle all regimes between NISQ and full-scale quantum
computers. Previously, only results for the pre-image search problem were known
for these models by Sun and Zheng, Rosmanis, Chen, Cotler, Huang and Li while
nothing was known about the collision finding problem.
- Abstract（参考訳）: 近代暗号の基本原理である衝突耐性ハッシュは、同じハッシュ値を生成する異なる入力を見つける効率的な方法がないことを保証している。
この性質は、様々な暗号アプリケーションのセキュリティを支え、その複雑さを理解することが重要である。
この問題の複雑さは古典的な設定ではよく理解されており、衝突を見つけるには$\Theta(N^{1/2})$クエリが必要である。
しかし、量子コンピューティングの出現は、量子逆数$\unicode{x2013}$が量子クエリのパワーを持つので、より効率的に衝突を見つけることができるため、新しい課題をもたらした。
brassard氏、h\"oyer氏、tapp氏、aaronson氏、そしてshi氏は、完全な量子敵は衝突を見つけるために$\theta(n^{1/3})$クエリを必要とし、より長いハッシュ出力が必要となり、セキュリティに必要な鍵長の効率に影響を及ぼすことを示した。
本稿では,ノイズ・中間スケール量子(NISQ)時代における量子攻撃の影響について考察する。
本研究では,nisqアルゴリズムの3つの異なるモデルを調査し,それらすべてに対する厳密な境界を達成した。(1)適応型量子・古典型問合せを行うハイブリッドアルゴリズム,(2)ノイズの多いオラクルにアクセスする量子アルゴリズム,デ強調・非分極化チャネルに属する量子アルゴリズム,(3)最大量子深さに上限を持つハイブリッドアルゴリズム,すなわち低深さ量子回路によって支援される古典的アルゴリズムである。
実際、我々の結果は、NISQとフルスケール量子コンピュータの間の全ての状態を扱う。
これまでは、画像前探索問題の結果のみがsunとzheng、rosmanis、chen、cotler、huang、liのモデルで知られていたが、衝突発見問題については知られていない。
関連論文リスト
- A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
本稿では,Ising Model (HAWI) を用いた量子古典ハイブリッドアルゴリズムを提案し,LWE問題に対処する。
我々は、ハミルトンの低エネルギーレベルを同定して解を抽出し、現在のノイズの多い中間スケール量子(NISQ)デバイスの実装に適したものにする。
我々のアルゴリズムは反復であり、その時間複雑性はハミルトンの低エネルギーレベルを見つけるために使われる特定の量子アルゴリズムに依存する。
論文 参考訳（メタデータ） (2024-08-15T05:11:35Z) - Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。
我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
論文 参考訳（メタデータ） (2024-07-24T22:06:05Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Limitations of Noisy Quantum Devices in Computational and Entangling
Power [5.178527492542246]
回路深さが$O(log n)$以上のノイズ量子デバイスは、いかなる量子アルゴリズムにも利点がないことを示す。
また、ノイズ量子デバイスが1次元および2次元の量子ビット接続の下で生成できる最大エンタングルメントについても検討する。
論文 参考訳（メタデータ） (2023-06-05T12:29:55Z) - Making the cut: two methods for breaking down a quantum algorithm [0.0]
現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。
我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。
最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
論文 参考訳（メタデータ） (2023-05-17T18:00:06Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。
我々はQiskitでIQuCSを実装し、集中的な実験を行う。
その結果、量子ビットの消費を最大66.2%削減できることが示されている。
論文 参考訳（メタデータ） (2022-09-22T21:54:28Z) - 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) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。