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:2207.05976 · Quantum Information and Computation

Distributed Shor's algorithm

Ligang Xiao, Daowen Qiu, Le Luo, Paulo Mateus

Published Jan 1, 2023• 39 citations
arXivHTMLPDF

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, 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.

DOI
10.26421/qic23.1-2-3

Related papers

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

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•3 citations

Enhanced Security Algorithm for Integer Factorization in Quantum Computing: Optimizing Shor’s Algorithm

Rashmi Kuksal, Sumit Chaudhary, Ashish Bhatt

With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.

International Conference on Innovative Mechanisms for Industry Applications•Oct 1, 2026•0 citations

Circuit for Shor's algorithm using 2n+3 qubits

Stéphane Beauregard

We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored.

arXiv:quant-ph/0205095•Quantum Information and Computation•Mar 1, 2003•299 citations

Experimental Implementation of Shor's Quantum Algorithm to Break RSA

Aminah Albuainain, Jana Alansari, Samiyah Alrashidi +3 more

Nowadays, quantum computing is an important topic since it allows computations to be completed in a small amount of the time. The goal of using quantum computers (QC) is to solve an increasing number of problems that were previously intractable to address with traditional computing. The classical approaches work with bits, which are made up of 0s and 1s, whereas QC uses qubits. Classical computing is limited by storage capacity and speed of calculations, even when parallel computation is conducted on it. Compared to traditional methods, quantum parallelism allows the storage to be reduced exponentially with the potential of a shorter amount of time. Besides, Peter Shor's algorithm can solve the factorization problem used in RSA in polynomial time, whereas in a classical computer, factoring any big integer is intractable. The purpose of this research is to explore and implement quantum computing schemes and how Shor's algorithm can break RSA algorithms.

International Conference on Computational Intelligence and Communication Networks (CICN)•Dec 4, 2022•14 citations

Using Single Time of Quantum Computer for Shor's Factoring Algorithm

Yousef Alhammadi

Peter Shor's in 1994 developed a factoring algorithm that can factor a composite number$\boldsymbol{n}$in a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected number$a, a\in Z_{n}$. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.

International Conference on IT Innovation and Knowledge Discovery (ITIKD)•Mar 8, 2023•0 citations
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.
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).
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.
With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.
Nowadays, quantum computing is an important topic since it allows computations to be completed in a small amount of the time. The goal of using quantum computers (QC) is to solve an increasing number of problems that were previously intractable to address with traditional computing. The classical approaches work with bits, which are made up of 0s and 1s, whereas QC uses qubits. Classical computing is limited by storage capacity and speed of calculations, even when parallel computation is conducted on it. Compared to traditional methods, quantum parallelism allows the storage to be reduced exponentially with the potential of a shorter amount of time. Besides, Peter Shor's algorithm can solve the factorization problem used in RSA in polynomial time, whereas in a classical computer, factoring any big integer is intractable. The purpose of this research is to explore and implement quantum computing schemes and how Shor's algorithm can break RSA algorithms.
Peter Shor's in 1994 developed a factoring algorithm that can factor a composite numbern\boldsymbol{n}nin a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected numbera,a∈Zna, a\in Z_{n}a,a∈Zn​. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.