論文の概要: Distributed Phase Estimation Algorithm and Distributed Shor's Algorithm
- arxiv url: http://arxiv.org/abs/2304.12100v2
- Date: Fri, 13 Dec 2024 11:30:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-16 15:00:26.396077
- Title: Distributed Phase Estimation Algorithm and Distributed Shor's Algorithm
- Title（参考訳）: 分散位相推定アルゴリズムと分散ショアアルゴリズム
- Authors: Ligang Xiao, Daowen Qiu, Le Luo, Paulo Mateus,
- Abstract要約: Shorのアルゴリズムは、最も重要な量子アルゴリズムの1つである。
NISQ時代には相当量の量子ビットを必要とする。
分散位相推定アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 4.199844472131922
- License:
- Abstract: Shor's algorithm is one of the most significant quantum algorithms. Shor's algorithm can factor large integers with a certain success probability in polynomial time. However, Shor's algorithm requires an unbearable amount of qubits in the NISQ (Noisy Intermediate-scale Quantum) era. To reduce the resources required for Shor's algorithm, in this paper we first propose a new distributed phase estimation algorithm. Our distributed phase estimation algorithm does not require quantum communication and it reduces the number of qubits of a single node compared to the traditional phase estimation algorithm (non-iterative version). Then we apply our distributed phase estimation algorithm to form a distributed order-finding algorithm for Shor's algorithm. Compared with the traditional Shor's algorithm (non-iterative version), the maximum number of qubits required by a single node of our dristributed order-finding algorithm is reduced by $(2-\dfrac{2}{k})L-\log_2k-O(1)$ when factoring an $L$-bit integer ($k$ is the number of compute nodes). The communication complexity of our distributed order-finding algorithm is $O(kL)$.
- Abstract（参考訳）: Shorのアルゴリズムは、最も重要な量子アルゴリズムの1つである。
ショアのアルゴリズムは多項式時間である種の成功確率を持つ大きな整数を分解することができる。
しかしながら、Shorのアルゴリズムは、NISQ時代(ノイズ中間スケール量子)において、許容できない量の量子ビットを必要とする。
そこで本稿では,Shorのアルゴリズムに必要なリソースを削減するために,まず分散位相推定アルゴリズムを提案する。
分散位相推定アルゴリズムは量子通信を必要としないため,従来の位相推定アルゴリズムと比較して単一ノードの量子ビット数を減少させる。
次に、分散位相推定アルゴリズムを適用し、Shorアルゴリズムの分散順序決定アルゴリズムを構成する。
従来のShorのアルゴリズム(非定型バージョン)と比較すると、計算ノード数で$L$-bitの整数(k$は計算ノード数)を分解した場合、Dristributedのオーダーフィニングアルゴリズムの単一ノードで要求されるキュービットの最大数は$(2-\dfrac{2}{k})L-\log_2k-O(1)$に削減される。
分散順序決定アルゴリズムの通信複雑性は$O(kL)$である。
関連論文リスト
- Distributed exact quantum algorithms for Bernstein-Vazirani and search
problems [9.146620606615889]
我々は、$t$の計算ノードを持つ分散Bernstein-Vaziraniアルゴリズム(DBVA)と、未順序データベースの1つのターゲット項目で探索問題を解決する分散型Grover'sアルゴリズム(DEGA)を提供する。
我々は、MindQuantum(量子ソフトウェア)上でDBVAとDEGAの状況を提供し、我々の手法の正確性と実践性を検証する。
論文 参考訳（メタデータ） (2023-03-19T14:18:49Z) - An adaptive Bayesian quantum algorithm for phase estimation [0.0]
平均絶対誤差と平均二乗誤差の最適2次スケーリングを実現するためのコヒーレンスに基づく位相推定アルゴリズムを提案する。
ノイズの存在下で、我々のアルゴリズムは理論的な下界に近づく誤差を生成する。
論文 参考訳（メタデータ） (2023-03-02T19:00:01Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Distributed Shor's algorithm [1.7396274240172125]
ショアのアルゴリズムはピーター・ショアが提唱した最も重要な量子アルゴリズムの1つである。
2つの量子コンピュータを別々に使い、$dfracsr$を$sin0, 1, cdots, r-1$と見積もる。
複数の制御量子ビットを使用する従来のショアのアルゴリズムと比較して、我々のアルゴリズムは、約$dfracL2$ qubitsを減らし、各コンピュータの回路深さを減らしている。
論文 参考訳（メタデータ） (2022-07-13T06:00:03Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - 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) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳（メタデータ） (2020-12-06T18:39:20Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。