論文の概要: Distributed Shor's algorithm
- arxiv url: http://arxiv.org/abs/2207.05976v1
- Date: Wed, 13 Jul 2022 06:00:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-05 06:57:29.952267
- Title: Distributed Shor's algorithm
- Title（参考訳）: 分散ショアのアルゴリズム
- Authors: Ligang Xiao, Daowen Qiu, Le Luo, Paulo Mateus
- Abstract要約: ショアのアルゴリズムはピーター・ショアが提唱した最も重要な量子アルゴリズムの1つである。
2つの量子コンピュータを別々に使い、$dfracsr$を$sin0, 1, cdots, r-1$と見積もる。
複数の制御量子ビットを使用する従来のショアのアルゴリズムと比較して、我々のアルゴリズムは、約$dfracL2$ qubitsを減らし、各コンピュータの回路深さを減らしている。
- 参考スコア（独自算出の注目度）: 1.7396274240172125
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Shor's algorithm is one of the most important quantum algorithm proposed by
Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer
Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with
certain probability and costs polynomial time in the length of the input
integer. The key step of Shor's algorithm is the order-finding algorithm.
Specifically, given an $L$-bit integer $N$, we first randomly pick an integer
$a$ with $gcd(a,N)=1$, the order of $a$ modulo $N$ is the smallest positive
integer $r$ such that $a^r\equiv 1 (\bmod N)$. The order-finding algorithm in
Shor's algorithm first uses quantum operations to obtain an estimation of
$\dfrac{s}{r}$ for some $s\in\{0, 1, \cdots, r-1\}$, then $r$ is obtained by
means of classical algorithms. In this paper, we propose a distributed Shor's
algorithm. The difference between our distributed algorithm and the traditional
order-finding algorithm is that we use two quantum computers separately to
estimate partial bits of $\dfrac{s}{r}$ for some $s\in\{0, 1, \cdots, r-1\}$.
To ensure their measuring results correspond to the same $\dfrac{s}{r}$, we
need employ quantum teleportation. We integrate the measuring results via
classical post-processing. After that, we get an estimation of $\dfrac{s}{r}$
with high precision. Compared with the traditional Shor's algorithm that uses
multiple controlling qubits, our algorithm reduces nearly $\dfrac{L}{2}$ qubits
and reduces the circuit depth of each computer.
- Abstract（参考訳）: shorのアルゴリズムはpeter shorによって提案された最も重要な量子アルゴリズムの1つである(proceeds of the 35th annual symposium on foundations of computer science, 1994, pp. 124--134)。
ショアのアルゴリズムは、ある確率で大きな整数を分解し、入力整数の長さで多項式時間をかけることができる。
shorのアルゴリズムの鍵となるステップは順序探索アルゴリズムである。
具体的には、$L$-bit整数$N$が与えられたとき、まず$gcd(a,N)=1$の整数$a$をランダムに選択し、$a$ modulo $N$は$a^r\equiv 1 (\bmod N)$の最小の正整数$r$である。
shor のアルゴリズムにおける順序探索アルゴリズムは、まず量子演算を用いて、いくつかの $s\in\{0, 1, \cdots, r-1\}$ に対して $\dfrac{s}{r}$ の見積もりを得る。
本稿では,分散ショアアルゴリズムを提案する。
分散アルゴリズムと従来の順序探索アルゴリズムの違いは、2つの量子コンピュータを別々に使って、$s\in\{0, 1, \cdots, r-1\}$ で$\dfrac{s}{r}$の部分ビットを推定することです。
彼らの測定結果が同じ$\dfrac{s}{r}$に対応するためには、量子テレポーテーションを採用する必要がある。
測定結果を古典的後処理で統合する。
その後、高精度で$\dfrac{s}{r}$と推定される。
複数の制御量子ビットを使用する従来のshorのアルゴリズムと比較して、このアルゴリズムはおよそ$\dfrac{l}{2}$ qubitsを削減し、各コンピュータの回路深度を減少させる。
関連論文リスト
- 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) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
論文 参考訳（メタデータ） (2023-12-05T21:15:09Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
ショアのアルゴリズムは、ノイズ中間量子時代の最も重要な量子アルゴリズムの1つであると考えられている。
Shorのアルゴリズムに必要なリソースを削減するために、我々は新しい分散量子古典ハイブリッド順序決定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T13:52:05Z) - 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) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - 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) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳（メタデータ） (2020-12-06T18:39:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。