論文の概要: Shor's Factoring Algorithm and Modular Exponentiation Operators
- arxiv url: http://arxiv.org/abs/2306.09122v3
- Date: Mon, 18 Sep 2023 13:18:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-19 23:28:47.235306
- Title: Shor's Factoring Algorithm and Modular Exponentiation Operators
- Title（参考訳）: shorの因子分解アルゴリズムとモジュラー指数演算子
- Authors: Robert L Singleton Jr
- Abstract要約: Shorの分解アルゴリズムは、非常に大きな数(数百から数千ビット)を時間で分解する量子アルゴリズムである。
因数分解問題に対する既知のすべての古典的アルゴリズムは、多数の因数分解に指数関数的な時間を要する。
これらのノートでは、ショアのアルゴリズムについて、量子コンピューティングの回路モデルに精通した基礎的知識以上の事前知識は仮定しない。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: These are pedagogical notes on Shor's factoring algorithm, which is a quantum
algorithm for factoring very large numbers (of order of hundreds to thousands
of bits) in polynomial time. In contrast, all known classical algorithms for
the factoring problem take an exponential time to factor large numbers. In
these notes, we assume no prior knowledge of Shor's algorithm beyond a basic
familiarity with the circuit model of quantum computing. The literature is
thick with derivations and expositions of Shor's algorithm, but most of them
seem to be lacking in essential details, and none of them provide a pedagogical
presentation. We develop the theory of modular exponentiation (ME) operators in
some detail, one of the fundamental components of Shor's algorithm, and the
place where most of the quantum resources are deployed. We also discuss the
post-quantum processing and the method of continued fractions, which is used to
extract the exact period of the modular exponential function from the
approximately measured phase angles of the ME operator. The manuscript then
moves on to a series of examples. We first verify the formalism by factoring
N=15, the smallest number accessible to Shor's algorithm. We then proceed to
factor larger numbers, developing a systematic procedure that will find the ME
operators for any semi-prime $N = p \times q$ (where $q$ and~$p$ are prime).
Finally, we factor the numbers N=21, 33, 35, 143, 247 using the Qiskit
simulator. It is observed that the ME operators are somewhat forgiving, and
truncated approximate forms are able to extract factors just as well as the
exact operators. This is because the method of continued fractions only
requires an approximate phase value for its input, which suggests that
implementing Shor's algorithm might not be as difficult as first suspected.
- Abstract（参考訳）: これらはショアの分解アルゴリズムに関する教育的ノートであり、多項式時間で非常に大きな数(数百から数千ビット)を分解する量子アルゴリズムである。
対照的に、因数分解問題に対する既知のすべての古典的アルゴリズムは指数関数時間で大量の因数分解を行う。
これらのノートでは、量子コンピューティングの回路モデルに対する基本的な親和性以上のshorのアルゴリズムの事前知識を仮定する。
文学はショアのアルゴリズムの導出と解説で厚くなっているが、それらの多くは本質的な詳細に欠けており、教育的なプレゼンテーションを提供していない。
モジュラー指数(me)作用素の理論を,shorのアルゴリズムの基本成分の1つであり,量子資源のほとんどが展開される場所として,ある程度詳細に展開する。
また,me演算子の近似位相角からモジュラー指数関数の正確な周期を抽出するために,量子後処理と継続分数法についても検討した。
その後、写本は一連の例に移行した。
まず,shor のアルゴリズムでアクセス可能な最小数 n=15 を因子として定式化を検証する。
次に、より大きい数を分解し、任意の半素数$N = p \times q$(ここで$q$と~$p$は素数)の ME 演算子を見つける体系的な手順を開発する。
最後に、Qiskitシミュレータを用いて、N=21, 33, 35, 143, 247 を分解する。
ME演算子は幾分保留であり、切り詰められた近似形式は正確な演算子と同様に因子を抽出することができる。
これは、継続分数法が入力に近似位相値のみを必要とするためであり、これはショアのアルゴリズムの実装が最初に疑ったほど難しくないことを示唆している。
関連論文リスト
- 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) - Reverse That Number! Decoding Order Matters in Arithmetic Learning [49.5504492920404]
本研究は,最少の桁から出力を優先順位付けすることで,桁順を再評価する新たな戦略を導入する。
従来のSOTA法と比較すると,通常のトレーニングで使用するトークンの3分の1しか必要とせず,精度の全体的な改善が見られた。
論文 参考訳（メタデータ） (2024-03-09T09:04:53Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - Factoring integers with sublinear resources on a superconducting quantum
processor [11.96383198580683]
Shorのアルゴリズムは、公開鍵暗号システムに基づく情報セキュリティに深刻な挑戦をしている。
広く使われているRSA-2048スキームを破るためには、数百万の物理量子ビットが必要である。
本稿では,古典的格子削減法と量子近似最適化アルゴリズムを組み合わせることで,整数分解のための普遍量子アルゴリズムについて報告する。
論文 参考訳（メタデータ） (2022-12-23T14:45:02Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - CNOT-count optimized quantum circuit of the Shor's algorithm [8.88308897530269]
整数分解のためのShorアルゴリズムにおいて最も高価な演算である定数のモジュラー指数化のための改良された量子回路を提案する。
CNOTゲートの数に応じて、イオントラップ量子コンピュータ上でShorのアルゴリズムの実行時間と実現可能性を分析する。
論文 参考訳（メタデータ） (2021-12-21T16:56:22Z) - Efficient Floating Point Arithmetic for Quantum Computers [1.189955933770711]
量子コンピューティングの大きな約束の1つは、重ね合わせ現象を用いたSIMD(単一命令 - 複数のデータ)演算の実現である。
我々は、符号なし整数量子回路を便利に生成できる半ブールと呼ばれる符号化形式を導入している。
我々は、このタイプの評価を、アンシラのないインプレース乗算や整数係数評価などの追加機能で拡張する。
論文 参考訳（メタデータ） (2021-12-20T14:00:36Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - An integer factorization algorithm which uses diffusion as a
computational engine [0.0]
我々は、素数でも素数でもないと仮定される整数$N$の因子を計算するアルゴリズムを開発する。
比較すると、ショアのアルゴリズムは量子コンピュータ上での最大$O(log N)2log (log N) log (log log N)$quantum stepsで使用されることが知られている。
論文 参考訳（メタデータ） (2021-04-23T14:11:33Z) - Demonstration of Shor's factoring algorithm for N=21 on IBM quantum
processors [0.0]
本稿では、整数21を分解する量子オーダーフィニングアルゴリズムの概念実証を示す。
5量子ビットのみを用いて,IBM量子プロセッサ上にアルゴリズムを実装した。
私たちが採用している手法は、より大きい整数や、ノイズの多い量子ビット数に制限のあるシステムにおいて、ショアのアルゴリズムを実行するのに有用かもしれない。
論文 参考訳（メタデータ） (2021-03-25T14:11:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。