Distributed Shor's algorithm
- URL: http://arxiv.org/abs/2207.05976v1
- Date: Wed, 13 Jul 2022 06:00:03 GMT
- Title: Distributed Shor's algorithm
- Authors: Ligang Xiao, Daowen Qiu, Le Luo, Paulo Mateus
- Abstract summary: Shor's algorithm is one of the most important quantum algorithms proposed by Peter Shor.
We use two quantum computers separately to estimate partial bits of $dfracsr$ for some $sin0, 1, cdots, r-1$.
Compared with the traditional Shor's algorithm that uses multiple controlling qubits, our algorithm reduces nearly $dfracL2$ qubits and reduces the circuit depth of each computer.
- Score: 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.
Related papers
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al.
A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$.
We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Grover's algorithm is capable of finding $k$ elements in an unordered database with $N$ elements using $O(sqrtN/k)$ steps.
This work tackles the problem of using the quantum counting algorithm for estimating the value $k$ of marked elements in other graphs.
arXiv Detail & Related papers (2023-12-05T21:15:09Z) - Do you know what q-means? [50.045011844765185]
Clustering is one of the most important tools for analysis of large datasets.
We present an improved version of the "$q$-means" algorithm for clustering.
We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
arXiv Detail & Related papers (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
Shor's algorithm is considered as one of the most significant quantum algorithms of the Noisy Intermediate Quantum era.
To reduce the resources required for Shor's algorithm, we propose a new distributed quantum-classical hybrid order-finding algorithm.
arXiv Detail & Related papers (2023-04-24T13:52:05Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
General tools for designing efficient private estimation algorithms.
First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
arXiv Detail & Related papers (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - An integer factorization algorithm which uses diffusion as a
computational engine [0.0]
We develop an algorithm which computes a divisor of an integer $N$, which is assumed to be neither prime nor the power of a prime.
By comparison, Shor's algorithm is known to use at most $O(log N)2log (log N) log (log log N)$ quantum steps on a quantum computer.
arXiv Detail & Related papers (2021-04-23T14:11:33Z) - Well Separated Pair Decomposition and power weighted shortest path
metric algorithm fusion [0.0]
We consider an algorithm that computes all $s$-well separated pairs in certain point sets in $mathbbRn$, $n$ $>$ $1$.
We also consider an algorithm that is a permutation of Dijkstra's algorithm, that computes $K$-nearest neighbors using a certain power weighted shortest path metric in $mathbbRn$, $n$ $>$ $1$.
arXiv Detail & Related papers (2021-03-20T17:38:13Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
We design and analyze two new low depth algorithms for amplitude estimation (AE)
These algorithms bring quantum speedups for Monte Carlo methods closer to realization.
arXiv Detail & Related papers (2020-12-06T18:39:20Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.