論文の概要: A quantum algorithm for computing the Carmichael function
- arxiv url: http://arxiv.org/abs/2111.02488v1
- Date: Wed, 3 Nov 2021 19:30:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 06:30:22.920317
- Title: A quantum algorithm for computing the Carmichael function
- Title(参考訳): カルミケル関数計算のための量子アルゴリズム
- Authors: Juan Carlos Garcia-Escartin
- Abstract要約: 量子コンピュータは、多くの数理論問題を効率的に解くことができる。
本稿では,任意の整数$N$に対して,所望の 1 に近い確率でカーマイケル関数を計算するアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum computers can solve many number theory problems efficiently. Using
the efficient quantum algorithm for order finding as an oracle, this paper
presents an algorithm that computes the Carmichael function for any integer $N$
with a probability as close to 1 as desired. The algorithm requires $O((\log n
)^3n^3)$ quantum operations, or $O(\log\log n (\log n)^4 n^2)$ operations using
fast multiplication. Verification, quantum optimizations and applications to
RSA and primality tests are also discussed.
- Abstract(参考訳): 量子コンピュータは多くの数論問題を効率的に解くことができる。
本稿では, 順序探索のための効率的な量子アルゴリズムを用いて, 1 に近い確率で任意の整数 $N$ に対してカーマイケル関数を計算するアルゴリズムを提案する。
このアルゴリズムは、$O((\log n )^3n^3)$量子演算、または高速乗算を用いた$O(\log n)^4n^2)$演算を必要とする。
検証、量子最適化、RSAおよび予備性試験への応用についても論じる。
関連論文リスト
- Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳(メタデータ) (2023-11-19T00:06:11Z) - Integer Factorization by Quantum Measurements [0.0]
量子アルゴリズムは、古典的コンピュータでは解けない計算問題を解くために量子力学を使うことが進行中の努力の中心である。
既知の量子アルゴリズムの中で、特別な役割はShorアルゴリズム、すなわち整数分解のための量子時間アルゴリズムによって演じられる。
ここでは、別の真の量子特性(量子計測)に基づく整数分解の異なるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-19T17:00:01Z) - An Efficient Quantum Factoring Algorithm [0.27195102129094995]
我々は、$tildeO(n3/2)$の量子回路を独立に実行することで、$n$bit整数を分解できることを示した。
アルゴリズムの正しさは、指数的古典的因数分解アルゴリズムで使われるものに似た数論的な仮定に依存する。
論文 参考訳(メタデータ) (2023-08-12T13:57:38Z) - Quantum Complexity for Discrete Logarithms and Related Problems [9.092600296992922]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳(メタデータ) (2023-07-06T15:32:50Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳(メタデータ) (2023-05-09T20:53:27Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Asymptotically Optimal Circuit Depth for Quantum State Preparation and
General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。
本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。
我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文 参考訳(メタデータ) (2021-08-13T09:47:11Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳(メタデータ) (2021-05-18T06:51:11Z) - 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) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳(メタデータ) (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。