論文の概要: Distributed Quantum-classical Hybrid Shor's Algorithm

• arxiv url: http://arxiv.org/abs/2304.12100v1
• Date: Mon, 24 Apr 2023 13:52:05 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-25 14:42:46.446655
• Title: Distributed Quantum-classical Hybrid Shor's Algorithm
• Title（参考訳）: 分散量子古典ハイブリッドショールアルゴリズム
• Authors: Ligang Xiao, Daowen Qiu, Le Luo, Paulo Mateus
• Abstract要約: ショアのアルゴリズムは、ノイズ中間量子時代の最も重要な量子アルゴリズムの1つであると考えられている。 Shorのアルゴリズムに必要なリソースを削減するために、我々は新しい分散量子古典ハイブリッド順序決定アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 1.7396274240172125
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shor's algorithm, which was proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134], is considered as one of the most significant quantum algorithms. Shor's algorithm can factor large integers with a certain probability of success in polynomial time. However, Shor's algorithm requires an unbearable amount of qubits and circuit depth in the NISQ (Noisy Intermediate-scale Quantum) era. To reduce the resources required for Shor's algorithm, we propose a new distributed quantum-classical hybrid order-finding algorithm for Shor's algorithm. The traditional order-finding algorithm needs to obtain an estimation of some $\dfrac{s}{r}$, where $r$ is the ``order'' and $s\in\{0,1,\cdots,r-1\}$. In our distributed algorithm, we use $k$ computers to estimate partial bits of $\dfrac{s}{r}$ separately. In order to reduce the errors of measuring results of these computers, we use classical programs to correct the measuring results of each computer to a certain extent. Compared with the traditional Shor's algorithm, our algorithm reduces nearly $(1-\dfrac{1}{k})L-\log_2k$ qubits for each computer when factoring an $L$-bit integer. Also, our algorithm reduces gate complexity and circuit depth to some extent for each computer. The communication complexity of our algorithm is $O(kL)$.
• Abstract（参考訳）: peter shor (proceeds of the 35th annual symposium on foundations of computer science, 1994, pp. 124--134) によって提唱されたshorのアルゴリズムは、最も重要な量子アルゴリズムの一つであると考えられている。 ショアのアルゴリズムは多項式時間で成功する確率で大きな整数を分解することができる。 しかし、Shor のアルゴリズムは NISQ (Noisy Intermediate-scale Quantum) 時代において、相当量の量子ビットと回路深さを必要とする。 shorのアルゴリズムに必要なリソースを減らすために、shorのアルゴリズムのための新しい分散量子古典ハイブリッド順序探索アルゴリズムを提案する。 従来の順序探索アルゴリズムは、$\dfrac{s}{r}$ の推定値を得る必要があり、ここで $r$ は ``order'' と $s\in\{0,1,\cdots,r-1\}$ である。 分散アルゴリズムでは、$k$コンピュータを用いて、$\dfrac{s}{r}$の部分ビットを別々に推定する。 これらのコンピュータの計測結果の誤差を低減するために,従来のプログラムを用いて,各コンピュータの計測結果のある程度の補正を行う。 従来のショアのアルゴリズムと比較して、我々のアルゴリズムは1-\dfrac{1}{k})L-\log_2k$ qubits を約 1-\dfrac{1}{k}) に還元する。 また,本アルゴリズムはゲートの複雑度と回路深度をコンピュータ毎にある程度低減する。 我々のアルゴリズムの通信複雑性は$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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。