論文の概要: Minimizing CNOT-count in quantum circuit of the extended Shor's
algorithm for ECDLP
- arxiv url: http://arxiv.org/abs/2305.11410v1
- Date: Fri, 19 May 2023 03:41:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 16:20:58.016245
- Title: Minimizing CNOT-count in quantum circuit of the extended Shor's
algorithm for ECDLP
- Title（参考訳）: ECDLP用拡張ショアアルゴリズムの量子回路におけるCNOT数最小化
- Authors: Xia Liu, Huan Yang, Li Yang
- Abstract要約: イオントラップ量子コンピュータを用いて、改良された量子回路を用いてECDLPのクラックの可能性を分析する。
我々は、素体上の楕円曲線上の離散対数を計算するために、Shorのアルゴリズムを拡張するための正確な量子回路を与える。
イオントラップ量子コンピュータ上でのShorアルゴリズムの動作時間と実現可能性をCNOT数に応じて解析する。
- 参考スコア（独自算出の注目度）: 8.88308897530269
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Since the elliptic curve discrete logarithms problem (ECDLP) was proposed, it
has been widely used in cryptosystem because of its strong security. Although
the proposal of the extended Shor's algorithm offers hope for cracking ECDLP,
it is debatable whether the algorithm can actually pose a threat in practice.
From the perspective of the quantum circuit of the algorithm, we analyze the
feasibility of cracking ECDLP with improved quantum circuits using an ion trap
quantum computer.
We give precise quantum circuits for extended Shor's algorithm to calculate
discrete logarithms on elliptic curves over prime fields, including modulus
subtraction, three different modulus multiplication, modulus inverse, and
windowed arithmetic. Whereas previous studies mostly focused on minimizing the
number of qubits or the depth of the circuit, we minimize the number of CNOTs,
which greatly affects the time to run the algorithm on an ion trap quantum
computer. First, we give the implementation of the basic arithmetic with the
lowest known number of CNOTs and the construction of an improved modular
inverse, point addition, and the windowing technique. Then, we precisely
estimate the number of improved quantum circuits needed to perform the extended
Shor's algorithm for factoring an n-bit integer. We analyze the running time
and feasibility of the extended Shor's algorithm on an ion trap quantum
computer according to the number of CNOTs. Finally, we discussed the lower
bound of the number of CNOTs needed to implement the extended Shor's algorithm.
- Abstract（参考訳）: 楕円曲線離散対数問題 (ECDLP) が提案されて以来、強力なセキュリティのために暗号システムで広く使われている。
拡張Shorのアルゴリズムの提案はECDLPのクラックを期待するが、実際にそのアルゴリズムが脅威となるかどうかは議論の余地がある。
アルゴリズムの量子回路の観点から、イオントラップ量子コンピュータを用いて、改良された量子回路を用いてECDLPのクラックの可能性を分析する。
拡張ショアのアルゴリズムに対して高精度量子回路を与え、モジュラス減算、3つの異なるモジュラス乗算、モジュラス逆算術、ウィンドウ演算を含む素体上の楕円曲線上の離散対数を計算する。
従来の研究では、量子ビット数や回路深さの最小化に重点を置いていたが、CNOTの数を最小化することは、イオントラップ量子コンピュータ上でアルゴリズムを実行する時間に大きな影響を与える。
まず,最小数の CNOT を用いた基本演算の実装と,改良されたモジュラー逆数,点加算,ウィンドウ化技術の構築について述べる。
そこで我々は,nビット整数を分解するShorアルゴリズムの拡張に必要な改良量子回路の数を正確に推定する。
イオントラップ量子コンピュータ上で拡張されたshorアルゴリズムの実行時間と実行可能性について,cnot数に応じて解析する。
最後に、拡張されたshorアルゴリズムを実装するのに必要なcnotの数の下限について論じた。
関連論文リスト
- On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
格子ベースの暗号は、量子後暗号の主要な候補の1つである。
量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている
SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
論文 参考訳（メタデータ） (2024-10-17T16:54:41Z) - Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
CNOT回路は一般的な量子回路の共通構成ブロックである。
本稿では,CNOTゲート数を最適化するための最先端アルゴリズムを提案する。
シミュレーション評価により、提案手法はほとんど常に有用であることが示され、CNOTゲートの数を最大10%削減する。
論文 参考訳（メタデータ） (2024-08-07T19:51:22Z) - Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
我々は,所定の回路を実装するために必要なTゲート数を最小化する手法であるAlphaTensor-Quantumを開発した。
Tカウント最適化の既存の方法とは異なり、AlphaTensor-Quantumは量子計算に関するドメイン固有の知識を取り入れ、ガジェットを活用することができる。
注目すべきは、有限体における乗法であるカラツバの手法に似た効率的なアルゴリズムを発見することである。
論文 参考訳（メタデータ） (2024-02-22T09:20:54Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Reducing the Depth of Quantum FLT-Based Inversion Circuit [0.5735035463793008]
本稿では、二元有限体に対する既存の量子フェルマーのLittle Theorem(ゲート)ベースの反転回路の深さを削減することを提案する。
私たちのアプローチは、時間効率の実装の代替となることができます。
論文 参考訳（メタデータ） (2022-04-16T00:20:18Z) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
我々は、ノイズの多い量子デバイス上で分解可能な数値の範囲を拡大するステップを推し進めるShorのアルゴリズムの縮小版を導入する。
特に、ほとんどのケースで注目すべき結果が得られており、しばしば提案されたアルゴリズムの1つで与えられた数を分解できる。
論文 参考訳（メタデータ） (2021-12-23T15:36:59Z) - CNOT-count optimized quantum circuit of the Shor's algorithm [8.88308897530269]
整数分解のためのShorアルゴリズムにおいて最も高価な演算である定数のモジュラー指数化のための改良された量子回路を提案する。
CNOTゲートの数に応じて、イオントラップ量子コンピュータ上でShorのアルゴリズムの実行時間と実現可能性を分析する。
論文 参考訳（メタデータ） (2021-12-21T16:56:22Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
雑音二元線形問題(NBLP)の量子可解性について完全解析する。
NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
論文 参考訳（メタデータ） (2021-09-23T07:46:20Z) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。
本稿では,QAOAの回路深度依存性能について実験的に検討する。
この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
論文 参考訳（メタデータ） (2020-05-11T17:20:51Z) - Improved quantum circuits for elliptic curve discrete logarithms [6.058525641792685]
楕円曲線スカラー乗算のための改良された量子回路を提案する。
可逆整数やモジュラ演算などの低レベル成分を最適化する。
Q#量子プログラミング言語における点加算の完全な実装を提供する。
論文 参考訳（メタデータ） (2020-01-27T04:08:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。