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.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.05976Quantum Information and ComputationJan 1, 202324 citations

Shor’s factorization algorithm with a single control qubit and imperfections

Ignacio García-Mata, Klaus M. Frahm, Dima L. Shepelyansky

We formulate and numerically simulate the single control qubit Shor algorithm for the case of static imperfections induced by residual couplings between qubits. This allows us to study the accuracy of Shor's algorithm with respect to these imperfections using numerical simulations of realistic quantum computations with up to ${n}_{q}=18$ computational qubits allowing to factor numbers up to $N=205\phantom{\rule{0.2em}{0ex}}193$ . We confirm that the algorithm remains operational up to a critical coupling strength ${ϵ}_{c}$ which drops only polynomially with ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ . The obtained numerical dependence of ${ϵ}_{c}$ on ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ is in a good agreement with the analytical estimates that allows to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.We formulate and numerically simulate the single control qubit Shor algorithm for the case of static imperfections induced by residual couplings between qubits. This allows us to study the accuracy of Shor's algorithm with respect to these imperfections using numerical simulations of realistic quantum computations with up to ${n}_{q}=18$ computational qubits allowing to factor numbers up to $N=205\phantom{\rule{0.2em}{0ex}}193$. We confirm that the algorithm remains operational up to a critical coupling strength ${ϵ}_{c}$ which drops only polynomially with ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$. The obtained numerical dependence of ${ϵ}_{c}$ on ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ is in a good agreement with the analytical estimates that allows to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.

arXiv:0809.4416Physical Review ADec 12, 200814 citations

Quantum Computing: A Mathematical Analysis of Shor's Algorithm

Stephen S. Clarke

Jan 1, 20200 citations

Quantum algorithms 1

Helmut Bez, Tony Croft

The quantum algorithms covered in this chapter, i.e., the Deutsch, Deutsch-Jozsa and Bernstein-Vazirani algorithms, have been chosen for their relative simplicity and theoretical interest. They do not address problems of real practical value, their purpose being to demonstrate, using simple examples, the great potential power of quantum computation relative to the digital case. The most significant breakthrough in quantum computing is Shor's integer factorisation algorithm. Shor's algorithm is beyond the scope of this introductory text, but its significance lies in the fact that it demonstrates the potential to factor large integers efficiently. No efficient digital algorithms for factoring large integers exist, and many current encryption algorithms rely on this being the case. Shor's algorithm therefore threatens current encryption methods, and is responsible for much of the recent accelerated interest in quantum computation.The quantum algorithms covered in this chapter, i.e., the Deutsch, Deutsch-Jozsa and Bernstein-Vazirani algorithms, have been chosen for their relative simplicity and theoretical interest. They do not address problems of real practical value, their purpose being to demonstrate, using simple examples, the great potential power of quantum computation relative to the digital case. The most significant breakthrough in quantum computing is Shor's integer factorisation algorithm. Shor's algorithm is beyond the scope of this introductory text, but its significance lies in the fact that it demonstrates the potential to factor large integers efficiently. No efficient digital algorithms for factoring large integers exist, and many current encryption algorithms rely on this being the case. Shor's algorithm therefore threatens current encryption methods, and is responsible for much of the recent accelerated interest in quantum computation.

Chapman & Hall/CRC eBooksJan 6, 20230 citations

Using Shor’s algorithm on near term Quantum computers: a reduced version

Martina Sofia Rossi, Luca Asproni, Davide Caputo +5 more

arXiv:2112.12647Quantum Machine IntelligenceJul 2, 202213 citations

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.

{n}_{q}=18

computational qubits allowing to factor numbers up to

N=205\phantom{\rule{0.2em}{0ex}}193

. We confirm that the algorithm remains operational up to a critical coupling strength

{ϵ}_{c}

which drops only polynomially with

{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N

. The obtained numerical dependence of

{ϵ}_{c}

{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N

is in a good agreement with the analytical estimates that allows to obtain the scaling for functionality of Shor's algorithm on realistic quantum computers with a large number of qubits.