Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Communications in computer and information science

Improved Estimation of Success Probability of the Shor’s Algorithm

P. Zawadzki

Published Jan 1, 2010• 0 citations
Publisher
DOI
10.1007/978-3-642-13861-4_5

Related papers

Improving the Success Probability for Shor’s Factorization Algorithm

Guoliang Xu, Daowen Qiu, Xiangfu Zou +1 more

Emergence, complexity and computation•Jan 1, 2018•6 citations

On the Complexity of Shor's Algorithm for Factorization

Zhengjun Cao, Lihua Liu

The complexity analysis of Shor's quantum algorithm for factorization consists of: 1) The probability p that we see any particular state\c, xk(mod n)) with {rc}q¿ r/2 is at least 1/3r2. 2) There are ¿(r) possible values of c, and r possible values of xk(mod n). 3) The success probability is at least ¿(r) · r · 1/3r2. That is, the inventor views p as the joint probability P(X = c, Y = xk(mod n)). In this paper, we show that the argument for the estimation of P(X = c, Y = xk(mod n)) is not sound. Therefore, the problem that Shor's algorithm takes polynomial time remains open.

International Symposium on Information Science and Engineering•Dec 1, 2009•8 citations

Distributed Phase Estimation Algorithm and Distributed Shor's Algorithm

Ligang Xiao, Daowen Qiu, Le Luo +1 more

Shor's algorithm is one of the most significant quantum algorithms. Shor's algorithm can factor large integers with a certain success probability in polynomial time. However, Shor's algorithm requires an unbearable amount of qubits in the NISQ (Noisy Intermediate-scale Quantum) era. To reduce the resources required for Shor's algorithm, in this paper we first propose a new distributed phase estimation algorithm. Our distributed phase estimation algorithm does not require quantum communication and it reduces the number of qubits of a single node compared to the traditional phase estimation algorithm (non-iterative version). Then we apply our distributed phase estimation algorithm to form a distributed order-finding algorithm for Shor's algorithm. Compared with the traditional Shor's algorithm (non-iterative version), the maximum number of qubits required by a single node of our dristributed order-finding algorithm is reduced by $(2-\dfrac{2}{k})L-\log_2k-O(1)$ when factoring an $L$-bit integer ($k$ is the number of compute nodes). The communication complexity of our distributed order-finding algorithm is $O(kL)$.

arXiv:2304.12100•Apr 24, 2023•17 citations

Peter Shor on the genesis of Shor’s algorithm

David Zierler, Ryan Dahn

Physics Today•Mar 10, 2025•4 citations

Simulations of Shor’s algorithm using matrix product states

D. S. Wang, Charles D. Hill, Lloyd C. L. Hollenberg

arXiv:1501.07644•Quantum Information Processing•Jun 3, 2017•27 citations

Quantum Phase Estimation Using Multivalued Logic

Vamsi Parasa, Marek A. Perkowski

Quantum phase estimation (QPE) is one of the most important quantum algorithms which is used as a subroutine for other important quantum algorithms like Shor's factoring algorithm, simulation of quantum systems, quantum counting and QFT on arbitrary Zp. In this paper we develop the theoretical framework for the multivalued quantum logic version of the QPE algorithm using d valued qudits and show a quantum circuit to implement QPE with a complexity of O(nlogn) single qudit operations. The multivalued QPE algorithm, when compared to the binary quantum logic version, turns out to be more robust and leads to a significant decrease in the number of qudits required along with drastic improvement in the precision and success probability. We derive the requirements to amplify the probability of success to a value very close to 1 (for a given precision), thereby generalizing the previously obtained result in the binary case. Also, we note that the failure probability of QPE algorithm decreases exponentially as d increases.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2011•13 citations
The complexity analysis of Shor's quantum algorithm for factorization consists of: 1) The probability p that we see any particular state\c, xk(mod n)) with {rc}q¿ r/2 is at least 1/3r2. 2) There are ¿(r) possible values of c, and r possible values of xk(mod n). 3) The success probability is at least ¿(r) · r · 1/3r2. That is, the inventor views p as the joint probability P(X = c, Y = xk(mod n)). In this paper, we show that the argument for the estimation of P(X = c, Y = xk(mod n)) is not sound. Therefore, the problem that Shor's algorithm takes polynomial time remains open.
Shor's algorithm is one of the most significant quantum algorithms. Shor's algorithm can factor large integers with a certain success probability in polynomial time. However, Shor's algorithm requires an unbearable amount of qubits in the NISQ (Noisy Intermediate-scale Quantum) era. To reduce the resources required for Shor's algorithm, in this paper we first propose a new distributed phase estimation algorithm. Our distributed phase estimation algorithm does not require quantum communication and it reduces the number of qubits of a single node compared to the traditional phase estimation algorithm (non-iterative version). Then we apply our distributed phase estimation algorithm to form a distributed order-finding algorithm for Shor's algorithm. Compared with the traditional Shor's algorithm (non-iterative version), the maximum number of qubits required by a single node of our dristributed order-finding algorithm is reduced by (2−2k)L−log⁡2k−O(1)(2-\dfrac{2}{k})L-\log_2k-O(1)(2−k2​)L−log2​k−O(1) when factoring an LLL-bit integer (kkk is the number of compute nodes). The communication complexity of our distributed order-finding algorithm is O(kL)O(kL)O(kL).
Quantum phase estimation (QPE) is one of the most important quantum algorithms which is used as a subroutine for other important quantum algorithms like Shor's factoring algorithm, simulation of quantum systems, quantum counting and QFT on arbitrary Zp. In this paper we develop the theoretical framework for the multivalued quantum logic version of the QPE algorithm using d valued qudits and show a quantum circuit to implement QPE with a complexity of O(nlogn) single qudit operations. The multivalued QPE algorithm, when compared to the binary quantum logic version, turns out to be more robust and leads to a significant decrease in the number of qudits required along with drastic improvement in the precision and success probability. We derive the requirements to amplify the probability of success to a value very close to 1 (for a given precision), thereby generalizing the previously obtained result in the binary case. Also, we note that the failure probability of QPE algorithm decreases exponentially as d increases.