Distributed Quantum-classical Hybrid Shor's Algorithm

• URL: http://arxiv.org/abs/2304.12100v1
• Date: Mon, 24 Apr 2023 13:52:05 GMT
• Title: Distributed Quantum-classical Hybrid Shor's Algorithm
• Authors: Ligang Xiao, Daowen Qiu, Le Luo, Paulo Mateus
• Abstract summary: 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.
• Score: 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)$.

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)
• 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)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Distributed exact quantum algorithms for Bernstein-Vazirani and search problems [9.146620606615889]
  We give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. We provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods.
  arXiv  Detail & Related papers  (2023-03-19T14:18:49Z)
• 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)
• Distributed Shor's algorithm [1.7396274240172125]
  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.
  arXiv  Detail & Related papers  (2022-07-13T06:00:03Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• 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)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  We introduce a new notion of well-separation to reduce the work and space of our algorithm for HDBSCAN$*$. We show that our algorithms are theoretically efficient: they have work (number of operations) matching their sequential counterparts, and polylogarithmic depth (parallel time) Our experiments on large real-world and synthetic data sets using a 48-core machine show that our fastest algorithms outperform the best serial algorithms for the problems by 11.13--55.89x, and existing parallel algorithms by at least an order of magnitude.
  arXiv  Detail & Related papers  (2021-04-02T16:05:00Z)
• 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)

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.