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

arXiv:2304.12100

Distributed Phase Estimation Algorithm and Distributed Shor's Algorithm

Ligang Xiao, Daowen Qiu, Le Luo, Paulo Mateus

Published Apr 24, 2023• 5 citations
arXivHTMLPDF

Abstract

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)$.

DOI
10.48550/arxiv.2304.12100

Related papers

Distributed Shor's algorithm

Ligang Xiao, Daowen Qiu, Le Luo +1 more

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, the quantum part of which is to estimate $s/r$, where $r$ is the ``order" and $s$ is some natural number that less than $r$. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of $s/r$.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly $L/2$ qubits for factoring an $L$-bit integer and reduces the circuit depth of each computer.

arXiv:2207.05976•Quantum Information and Computation•Jan 1, 2023•24 citations

Distributed quantum algorithm for discrete logarithm problem

Hao Li, Daowen Qiu

The quantum algorithm with polynomial time for discrete logarithm problem proposed by Shor is one of the most significant quantum algorithms, but a large number of qubits may be required in the Noisy Intermediate-scale Quantum (NISQ) era. The main contributions of this paper are as follows: (1) A distributed quantum algorithm for discrete logarithm problem is designed, and its space complexity and success probability exhibit certain advantages to some extent; (2) The classical error correction technique proposed by Xiao and Qiu et al. is generalized by extending three bits to more than three bits.

arXiv:2504.09595•Apr 13, 2025•0 citations

Distributed Shor’s Algorithm with Sequential Quantum Teleportation

Jehn‐Ruey Jiang, Ting-Yuan Wang, Wen‐Han Huang +1 more

A distributed Shor’s algorithm is used to factorize a semiprime with two quantum computers using quantum teleportation to transport quantum states of qubits in parallel. We propose another distributed Shor’s algorithm with sequential quantum teleportation to improve the existing one. It explores how to employ distributed quantum computing through a quantum entanglement pair of qubits to transport quantum states of qubits sequentially. We combined two quantum computers to perform the quantum phase estimation (QPE) of Shor’s algorithm. This reduced the required number of qubits for a single quantum computer, decreased quantum circuit depth, mitigated the impact of insufficient decoherence time, and accelerated the process of breaking cryptographic systems such as Rivest-Shamir-Adleman (RSA). The designed quantum circuit was executed on the IBM Quantum Lab platform to verify its correctness. We analyzed and compared the required numbers of qubits to run different versions of Shor’s algorithm for individual quantum computers, as well as the numbers of qubits required to break different RSA cryptographic systems.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 27, 2023•2 citations

Enhancing the Practical Reliability of Shor's Quantum Algorithm via Generalized Period Decomposition: Theory and Large-Scale Empirical Validation

Chih-Chen Liao, Chia-Hsin Liu, Yun-Cheng Tsai

This work presents a generalized period decomposition approach, significantly improving the practical reliability of Shor's quantum factoring algorithm. Although Shor's algorithm theoretically enables polynomial-time integer factorization, its real-world performance heavily depends on stringent conditions related to the period obtained via quantum phase estimation. Our generalized decomposition method relaxes these conditions by systematically exploiting arbitrary divisors of the obtained period, effectively broadening the applicability of each quantum execution. Extensive classical simulations were performed to empirically validate our approach, involving over one million test cases across integers ranging from 2 to 8 digits. The proposed method achieved near-perfect success rates, exceeding 99.998% for 7-digit numbers and 99.999% for 8-digit numbers, significantly surpassing traditional and recently improved variants of Shor's algorithm. Crucially, this improvement is achieved without compromising the algorithm's polynomial-time complexity and integrates seamlessly with existing quantum computational frameworks. Moreover, our method enhances the efficiency of quantum resource usage by minimizing unnecessary repetitions, making it particularly relevant for quantum cryptanalysis with noisy intermediate-scale quantum (NISQ) devices. This study thus provides both theoretical advancements and substantial practical benefits, contributing meaningfully to the field of quantum algorithm research and the broader field of quantum information processing.

quant-pharXiv:2512.11004•Dec 12, 2025•0 citations

Distributed quantum computing: A distributed Shor algorithm

Anocha Yimsiriwattana, Samuel J. Lomonaco Jr. A

We present a distributed implementation of Shor’s quantum factoring algorithm on a distributed quantum network model. This model provides a means for small capacity quantum computers to work together in such a way as to simulate a large capacity quantum computer. In this paper, entanglement is used as a resource for implementing non-local operations between two or more quantum computers. These non-local operations are used to implement a distributed factoring circuit with polynomially many gates. This distributed version of Shor’s algorithm requires an additional overhead of O((log N) 2) communication complexity, where N denotes the integer to be factored. Keywords: Shor’s algorithm, factoring algorithm, distributed quantum algorithms, quantum circuit. 1.

•Jan 1, 2004•52 citations

Distributed quantum computing: a distributed Shor algorithm

Anocha Yimsiriwattana, Samuel J. Lomonaco Jr.

We present a distributed implementation of Shor's quantum factoring algorithm on a distributed quantum network model. This model provides a means for small capacity quantum computers to work together in such a way as to simulate a large capacity quantum computer. In this paper, entanglement is used as a resource for implementing non-local operations between two or more quantum computers. These non-local operations are used to implement a distributed factoring circuit with polynomially many gates. This distributed version of Shor's algorithm requires an additional overhead of O((log N)^2) communication complexity, where N denotes the integer to be factored.

arXiv:quant-ph/0403146•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•106 citations
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).
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, the quantum part of which is to estimate s/rs/rs/r, where rrr is the ``order" and sss is some natural number that less than rrr. {{Shor's algorithm requires lots of qubits and a deep circuit depth, which is unaffordable for current physical devices.}} In this paper, to reduce the number of qubits required and circuit depth, we propose a quantum-classical hybrid distributed order-finding algorithm for Shor's algorithm, which combines the advantages of both quantum processing and classical processing. {{ In our distributed order-finding algorithm, we use two quantum computers with the ability of quantum teleportation separately to estimate partial bits of s/rs/rs/r.}} The measuring results will be processed through a classical algorithm to ensure the accuracy of the results. Compared with the traditional Shor's algorithm that uses multiple control qubits, our algorithm reduces nearly L/2L/2L/2 qubits for factoring an LLL-bit integer and reduces the circuit depth of each computer.
The quantum algorithm with polynomial time for discrete logarithm problem proposed by Shor is one of the most significant quantum algorithms, but a large number of qubits may be required in the Noisy Intermediate-scale Quantum (NISQ) era. The main contributions of this paper are as follows: (1) A distributed quantum algorithm for discrete logarithm problem is designed, and its space complexity and success probability exhibit certain advantages to some extent; (2) The classical error correction technique proposed by Xiao and Qiu et al. is generalized by extending three bits to more than three bits.
A distributed Shor’s algorithm is used to factorize a semiprime with two quantum computers using quantum teleportation to transport quantum states of qubits in parallel. We propose another distributed Shor’s algorithm with sequential quantum teleportation to improve the existing one. It explores how to employ distributed quantum computing through a quantum entanglement pair of qubits to transport quantum states of qubits sequentially. We combined two quantum computers to perform the quantum phase estimation (QPE) of Shor’s algorithm. This reduced the required number of qubits for a single quantum computer, decreased quantum circuit depth, mitigated the impact of insufficient decoherence time, and accelerated the process of breaking cryptographic systems such as Rivest-Shamir-Adleman (RSA). The designed quantum circuit was executed on the IBM Quantum Lab platform to verify its correctness. We analyzed and compared the required numbers of qubits to run different versions of Shor’s algorithm for individual quantum computers, as well as the numbers of qubits required to break different RSA cryptographic systems.
This work presents a generalized period decomposition approach, significantly improving the practical reliability of Shor's quantum factoring algorithm. Although Shor's algorithm theoretically enables polynomial-time integer factorization, its real-world performance heavily depends on stringent conditions related to the period obtained via quantum phase estimation. Our generalized decomposition method relaxes these conditions by systematically exploiting arbitrary divisors of the obtained period, effectively broadening the applicability of each quantum execution. Extensive classical simulations were performed to empirically validate our approach, involving over one million test cases across integers ranging from 2 to 8 digits. The proposed method achieved near-perfect success rates, exceeding 99.998% for 7-digit numbers and 99.999% for 8-digit numbers, significantly surpassing traditional and recently improved variants of Shor's algorithm. Crucially, this improvement is achieved without compromising the algorithm's polynomial-time complexity and integrates seamlessly with existing quantum computational frameworks. Moreover, our method enhances the efficiency of quantum resource usage by minimizing unnecessary repetitions, making it particularly relevant for quantum cryptanalysis with noisy intermediate-scale quantum (NISQ) devices. This study thus provides both theoretical advancements and substantial practical benefits, contributing meaningfully to the field of quantum algorithm research and the broader field of quantum information processing.
We present a distributed implementation of Shor’s quantum factoring algorithm on a distributed quantum network model. This model provides a means for small capacity quantum computers to work together in such a way as to simulate a large capacity quantum computer. In this paper, entanglement is used as a resource for implementing non-local operations between two or more quantum computers. These non-local operations are used to implement a distributed factoring circuit with polynomially many gates. This distributed version of Shor’s algorithm requires an additional overhead of O((log N) 2) communication complexity, where N denotes the integer to be factored. Keywords: Shor’s algorithm, factoring algorithm, distributed quantum algorithms, quantum circuit. 1.
We present a distributed implementation of Shor's quantum factoring algorithm on a distributed quantum network model. This model provides a means for small capacity quantum computers to work together in such a way as to simulate a large capacity quantum computer. In this paper, entanglement is used as a resource for implementing non-local operations between two or more quantum computers. These non-local operations are used to implement a distributed factoring circuit with polynomially many gates. This distributed version of Shor's algorithm requires an additional overhead of O((log N)^2) communication complexity, where N denotes the integer to be factored.