Fugu-MT 論文翻訳(概要): Distributed Quantum-classical Hybrid Shor's Algorithm

論文の概要: 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)$である。

関連論文リスト

A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
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)
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)
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)
Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文参考訳（メタデータ） (2021-04-02T16:05:00Z)
Well Separated Pair Decomposition and power weighted shortest path metric algorithm fusion [0.0]
私たちは、あるポイントセットで$s$-wellの分離ペアを$mathbbrn$, $n$$$>$$1で計算するアルゴリズムを考えています。また、ダイクストラのアルゴリズムの置換であるアルゴリズムについても検討し、特定のパワー重み付き最短経路メトリックを用いてk$-nearestの隣人を計算し、$mathbbrn$,$n$$$$$$$$$$で計算する。
論文参考訳（メタデータ） (2021-03-20T17:38:13Z)

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

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