Where are we with Shor’s algorithm?

was proposed by Peter Shor in a seminal paper [1] in 1995 as an algorithm for factoring giant numbers utilizing quantum computing. In 2025, i.e. 30 years later, early quantum processors are produced and made obtainable to the general public, making it potential to check the algorithm for actual. Can we efficiently run Shor’s algorithm on giant numbers? The reply is well-known to be no, as a result of this might require quantum processors with hundreds of qubits and really low quantum noise, and we aren’t there but. However what about small numbers? And, by the best way, how will we implement Shor’s algorithm concretely?

On this submit we give a information to the implementation of Shor’s algorithm, with a particular emphasis on the realisation of the order-finding quantum circuit and the modular arithmetic computations which can be on the core of the algorithm. We hyperlink a git repository with the total implementation in Qiskit. Lastly we run some simulations and supply the outcomes of precise computations on IBM quantum {hardware}, as of 2025.

In an effort to observe this submit, it will be ultimate if some fundamentals of quantum computing, particularly qubit manipulations and normal unitary gate operations, and a little bit of linear algebra.

Disclaimer 1: Though I purpose at a scientific stage of rigorousness, this isn’t a tutorial paper and I don’t faux to be an skilled within the area.

Disclaimer 2: No synthetic intelligence was used to provide this submit.

A breakthrough algorithm for quantity factoring

Shor’s algorithm is an algorithm which goals at discovering a non-trivial issue of an integer N. Whereas it’s straightforward to discover a issue for a sufficiently small N, by making an attempt potential values as much as N^1/2 for example, the issue turns into impractical when N is admittedly large, like N ~ 2¹⁰⁰⁰, just because the search house turns into too large. A human lifetime wouldn’t suffice to discover a issue of such a big integer, utilizing a classical pc.

If we denote by n = ⌈log₂(N)⌉ the variety of digits to write down N in binary notation, the best known classical algorithm has time complexity exp(c n^1/3 (log n)^2/3), for some fixed c, i.e. exponential time complexity. By “classical” algorithm one means an algorithm which might be run on a standard pc, particularly an algorithm which is product of arithmetic operations on numbers. That is principally all algorithms, besides quantum algorithms.

Shor’s algorithm is a quantum algorithm, which signifies that it entails operations on a quantum system, on this case on qubits. Furthermore, it’s a probabilistic algorithm, which signifies that it’s assured to work with excessive chance, however often it will possibly fail. 

Shor’s algorithm is ready to discover a issue of N in time complexity O(n² log n) with excessive chance, in its most effective implementation, i.e. in polynomial time complexity. That is most likely essentially the most spectacular instance of a quantum algorithm beating classical algorithms, to date.

Furthermore, it occurs that the issue of factoring giant integers is on the coronary heart of public key cryptography and the RSA algorithm, which is broadly used as we speak to safe Web communications. Shor’s algorithm, if efficiently run on a quantum pc holding a number of thousand qubits, may break this encryption scheme. This makes it one of the vital fashionable functions in quantum computing.

Whereas we’re nonetheless considerably removed from having a quantum pc with the capability to run Shor’s algorithm on giant numbers, the present progress makes it potential to strive it on small numbers. So it’s about time to take a deeper have a look at Shor’s algorithm, see the way it works, how we will really implement it and run it on quantum {hardware}. 

Making the most of the IBM quantum platform, which permits for a restricted quantity of free entry to actual quantum processors (QPUs), I’ve carried out the total algorithm with the Qiskit SDK and tried it on small numbers. The complete implementation is out there on this qiskit-shor repository.

Let’s dive now into the algorithm.

The algorithm

Introductions to Shor’s algorithm are quite a few on the internet (see e.g. Wikipedia). We’ll solely write down the algorithm itself and clarify the concepts concerned, however we is not going to clarify why it really works, nor give a proof of each assertion.

Contemplate a composite integer N, i.e. an integer which admits non-trivial prime components. Additionally require that N is odd and isn’t the facility of a first-rate quantity (in these circumstances, we will simply discover a non-trivial issue). 

Then, the algorithm steps are:

1. Select a random integer 1 < A < N and compute gcd(A, N). If gcd(A, N) > 1, then gcd(A, N) is a non-trivial issue of N and we’re achieved (fortunate case). In any other case A and N are coprime (typical case).
2. Discover the order of A in Z_N, i.e. the smallest integer 1 < r < N such that A^r = 1 mod N, utilizing the section estimation quantum algorithm (see under).
3. If r is odd, return to step 1 and select one other A. In any other case, compute d = gcd(A^r/2 − 1, N). If d > 1, then d is a non-trivial issue of N. If not, begin once more in step 1.

Peter Shor proposed this algorithm in a seminal paper [1] and proved that it finds an element of N in polynomial time, with excessive chance.

Among the many steps listed above solely the order discovering step requires a quantum operation. The opposite steps are classical operations, that are simply carried out on a classical pc. 

The quantum algorithm consists in making use of unitary operations on a set of qubits representing numbers in binary notation. The integer

[ x = sum_{i=0}^{m-1} x_i 2^i, quad x_i in {0,1} ,,]

is represented by the m-qubit state

[ |xrangle = |x_0rangle |x_1rangle …|x_{m-1}rangle ]

As an illustration, the quantity 13 = 2⁰ +2² + 2³ in represented by the “quantum integer” (4-qubit state) |13⟩ = |1⟩|0⟩|1⟩|1⟩.

To seek out the order r of the integer A in Z_N, the thought of Shor’s algorithm is to leverage the truth that the unitary operator

[ U_A : x rightarrow Ax ,, text{mod} ,, N ]

admits eigenvalues of the shape exp(2πi j/r), with 0 ≤ j < r, and that the vector |1⟩ (the “quantum integer 1”) might be expressed as a linear mixture of the corresponding eigenvectors. The algorithm tries to estimate at the very least one of many fraction j/r. That is known as section estimation, as we estimate the section Φ = 2π j/r of an eigenvalue exp(iΦ) of the operator U_A.

We’ll present the precise quantum circuit that must be run within the subsequent part. The quantum algorithm consists in operating this circuit and measuring its m output bits, forming a quantity okay in binary notation. This quantity okay is such that okay/2^m must be near j/r for some 0 ≤ j < r , with excessive chance. Until we find yourself in some unfortunate case (like j=0), we will extract the worth of r by discovering the fraction of the shape a/b, with b < N, closest to okay/2^m and figuring out r=b (there are libraries doing this effectively). Usually, one would run the order discovering circuit and measure its outcomes many occasions to search out r with very giant chance. The expectation is that the distribution of outputs okay/2^m ought to have peaks (of similar magnitude) in any respect the values j/r, for 0 ≤ j < r.

All of the classical operations are straightforward to implement and they are often run in log N time, so we solely want to fret in regards to the realisation and operating of the order-finding quantum circuit. Let’s see the way it seems.

Order-finding quantum circuit

The order-finding circuit is depicted within the following determine. A number of modifications might be delivered to the circuit to enhance its effectivity, however let’s depart this for later.

There are two teams of qubits: one group of n qubits initialised to the quantum integer state |1⟩, i.e. |x⟩ with x=1, known as the goal qubits (decrease qubits within the determine), and one other group of 2n qubits, known as the management qubits (higher qubits within the determine). The management qubits are initialised to the superposition of all integer states, utilizing Hadamard gates,

[ (H|0rangle)^{otimes 2n} = left( frac0rangle + {sqrt 2}right)^{otimes 2n} = frac{1}{2^n} sum_{x =0}^{2^{2n}-1} |xrangle ]

and are then used as management qubits for unitary operations U_D performing on the goal qubits sequentially,

[
CU_{D}|brangle|xrangle = left{
begin{align}
& |0rangle , |xrangle & text{if $b = 0$}
& |1rangle , |Dx, text{mod}, Nrangle & text{if $b = 1$}
end{align}
right.
,,
]

with D taking values

[ D = A^{2^i} , text{mod} , N ,, quad i = 0, …, 2n-1, ]

Lastly the management qubits are remodeled by an inverse QFT gate and are all measured (indicated by circles with “m” within the determine).

One may substitute the variety of management qubits 2n by one other variety of management qubits m. The extra management qubits, the higher would be the estimated section okay/2^m of the U_A operator. The selection m=2n is a compromise between precision and circuit measurement.

Why this circuit performs section estimation is the subject of many introductions to Shor’s algorithm. The IBM lecture is an excellent place to check this subject. 

Within the above circuit, all elements are simply carried out within the Qiskit SDK, apart from the unitary operator U_A (and its managed model CU_A). That is the place all the issue stands. Nearly all of educational analysis on Shor’s algorithm revolves round optimising the implementation of U_A. The above depiction of the order discovering circuit means that 3n qubits are sufficient to implement the quantum algorithm, however the U_A gate itself really requires n + c further qubits, termed ancillary or ancilla qubits (the precise fixed c depends upon the chosen implementation). 

Earlier than discussing the circuit implementation of U_A, allow us to point out that there’s an essential simplification of the above circuit. The 2n management qubits might be changed by a single qubit (!), which undergoes a sequence of unitary gate actions, measurements and reset, resulting in a big discount within the variety of qubits required to run Shor’s algorithm, however on the worth of introducing management circulate operations, particularly gate actions relying on intermediate measurements. Whereas this may occasionally appear to be an affordable worth to pay in principle, in follow management circulate gates are operationally extra complicated to deal with than normal unitary operations. The “one-control-qubit” circuit is depicted within the following determine.

the place m_i ∈ {0, 1} are successive measurement values of the distinctive management qubit, and X^m is the X gate (= NOT gate) if m=1, or the identification gate if m=0. Making use of X^m resets the management qubit to |0⟩. The R_i are section gates (= RZ rotation gates) with section parameters relying on all of the earlier measurement values. The small print and the reasons for this simplification might be discovered, for example, in [3].

The U_A gate and quantum modular arithmetics

Observe: This part is extra technical. Some readers may need to skip this half on a primary learn and go on to the subsequent part.

Allow us to now deal with the circuit implementing the unitary motion

[ U_A : x rightarrow Ax ,, text{mod} ,, N ]

The insightful reader may ask whether or not that is actually a unitary operation, because the operation doesn’t look very bijective, as a result of modulo N operation. That is fairly an essential level, as, utilizing solely unitary gates, we will solely implement unitary operations. The very fact is that U_A, performing on the house of integers in [0, N), is a bijective function, if and only if A and N are coprime integers, which is true for the values considered in Shor’s algorithm. The inverse operation is U_B, with B the inverse of A in Z_N, i.e. B is an integer such that BA = 1 mod N. The fact that A and N are coprime guarantees the existence of B.

So it is theoretically possible to build a unitary operator U_A acting on the space S spanned by the vectors |x⟩, with 0 ≤ x < N. In the order-finding circuit, a sequence of (controlled) U_D operations, with various values of D, are applied to the initial state |1⟩, which is in S. The action of U_A on states |x⟩, with x ≥ N, does not matter, as this case will not occur. We can ignore how our U_A gate circuit acts on those larger integer states.

To keep the presentation short enough, we will only present the most important features of the implementation of U_A, leaving some pointers to relevant papers to the interested reader. 

The important building block that needs to be implemented is the modular addition:

[ text{add}(Y,N): quad |xrangle rightarrow |(x+Y) , text{mod} , N rangle ]

with 0 ≤ Y < N  a “classical” integer, i.e. a given parameter, and 0 ≤ x < N  a “quantum” integer, i.e. an integer represented by the quantum state |x⟩, as described in earlier sections. To implement this operation, we’d like at the very least n = ⌈log₂(N)⌉ qubits to signify quantum integers modulo N, so we are going to assume that n is the dimensions of the quantum register we work with, i.e. the variety of qubits holding x. This implies we will signify quantum integers between 0 and a pair ofⁿ-1.

There are two “faculties of thought” for implementing this operation. The “Clifford+T” method makes use of solely the gates NOT, H, S, S^-1, CNOT and Toffoli, whereas the “Quantum Fourier Rework” (QFT) method performs addition through parametrised section gates P(λ) on the Fourier house illustration of the enter integer (extra on this under).

The Clifford+T method primarily makes use of a considerably simple “school-boy” process, including the bits of two quantum numbers written in binary notation and holding observe of carry-over models in ancilla qubits. Within the implementation [6], the entire process requires round 10n gates and one ancilla qubit, and has depth roughly 2n (these notions are mentioned within the part on algorithm complexity under). This method might be tailored to including a classical and a quantum quantity.

The QFT method was proposed within the work of Draper [4]. It begins by performing on |x⟩ with a QFT gate, which consists of H and P(π/2^j) gates, producing a superposition of states

[ QFT|xrangle = frac{1}{2^{n/2}} sum_{y=0}^{2^n-1} e^{2ipi frac{xy}{2^n}} |yrangle ]

On this illustration, the addition of a classical quantity Y might be carried out with n section rotation gates performing on the n qubits of the register

[ prod_{i=0}^{n-1} Pleft(2pi Yfrac{2^i}{2^n}right) QFT|xrangle = QFT|(x + Y) , text{mod} , 2^n rangle ]

The technique is thus to sandwich section rotations between a QFT and a QFT^-1 to implement the addition

[ |(x + Y), text{mod}, 2^n rangle = QFT^{-1} prod_{i=0}^{n-1} Pleft(2pi Yfrac{2^i}{2^n}right) QFT |xrangle ]

The implementation of managed addition is obtained by changing section gates by managed section gates.

Whereas the variety of elementary gates within the QFT and QFT^-1 operations is giant, O(n²) really, the next addition in Fourier house requires solely n section gates which may function in parallel. A number of additions, or managed additions, might be carried out sequentially, alongside the execution of a quantum circuit, whereas the quantum integer x is represented in Fourier house, through a sequence of (managed) section rotations. Furthermore, the entire QFT-adder gate doesn’t require ancilla qubits. This makes the QFT method a most popular selection in lots of initiatives requiring quantum adder circuits.

A current evaluate by S. Wang et al [5] compares the totally different state-of-the-art algorithms for quantum arithmetics and gives an intensive bibliography on the subject.

You will need to word that the addition operation described above is all the time modulo 2ⁿ. That is as anticipated, since we will solely signify integers within the vary [0, 2ⁿ) with n qubits. So the operation that is implemented so far is

[ text{add}(Y): quad |xrangle_n rightarrow |x+Yrangle_n := |(x + Y), text{mod}, 2^n rangle_n ]

the place the subscript n signifies the variety of qubits within the quantum register.

The following step is to implement the “modulo N” half. That is considerably more durable and requires a sequence of (managed) additions and (managed) subtractions. The essential concepts have been described within the work of Beauregard [2].

The steps proposed by Beauregard, with 0 ≤ Y < N and 0 ≤ x < N, are:

• With n = ⌈log₂(N)⌉, take into account the n+1 qubit state |x⟩_n+1. That is yet one more qubit than needed to carry x, i.e. there’s one “overflow” qubit initialised to |0⟩.
• Add Y-N, utilizing the add(Y-N) operation. This yields |x+Y-N⟩_n+1 if x+Y-N≥ 0, or |2ⁿ⁺¹-x+N)⟩ if x+Y-N < 0 .
• Compute the signal of x+Y-N in an ancilla qubit |a⟩. That is achieved through a CNOT gate performing on |a⟩ and managed by essentially the most important bit (i.e. the overflow bit) of the n+1-qubit register. After this step |a⟩ = |0⟩ if x+Y ≥ N and |a⟩ = |1⟩ if x+Y < N.
• Add N again to n+1-qubit register, managed on |a⟩, utilizing a managed add(N) operation. The ensuing state is |(x + Y) mod N⟩|a⟩.

The next steps enable to reset the ancilla qubit to its preliminary state |0⟩:

• Add -Y utilizing an add(-Y) operation. After this step the n+1-register is within the state |x⟩ if x + Y < N, or within the state |2ⁿ⁺¹+x-N)⟩ if x+Y ≥ N.
• Reverse the ancilla bit managed on essentially the most important little bit of the n+1-qubit register with a CNOT gate. After this step the ancilla bit is all the time within the state |a⟩ = |1⟩. We reset it to |0⟩ by performing with a NOT gate: |a⟩ = NOT|1⟩ = |0⟩.
• Add Y again utilizing an add(Y) operation. This results in the ultimate state |(x + Y) mod N⟩|0⟩.

This may increasingly look a little bit concerned, however that is arguably the best quantum algorithm discovered to date to carry out modular addition. 

The final three steps, reverting the ancilla qubit |a⟩ again to its preliminary state |0⟩, are essential, if the ancilla qubit is to be re-used in subsequent modular addition operations, which is the case in Shor’s algorithm. Alternatively, one may use new ancilla qubits for every modular addition, decreasing the depths and gate counts of the total order-finding circuit, at the price of growing the variety of qubits. Minimising the variety of qubits is often the first goal, as present quantum processors have a restricted variety of qubits (extra on this under).

The implementation of the managed modular addition is obtained by changing every addition/subtraction of an element Y, by a managed addition/subtraction.

The following step is to implement the operation

[ |xrangle |yrangle -> |xrangle|(y+Ax) ,text{mod}, Nrangle ]

the place 0 ≤ y < N is one other quantum integer. That is achieved by decomposing the modular addition y ↦ (y + Ax) mod N right into a sequence of modular additions y ↦ (y + 2ⁱA) mod N, carried out as add(2ⁱA, N)|y⟩ = |(y + 2ⁱA) mod N⟩, managed on the i-th bit |x_i⟩ of x = Σ_i x_i 2ⁱ. As we noticed, the modular addition requires an overflow qubit and an ancilla qubit, so the true operation we implement with this prescription is

[ V_A: |xrangle_n |yrangle_{n+1} |0rangle rightarrow |xrangle_n |(y+Ax) , text{mod}, Nrangle_{n+1} |0rangle ]

with subscripts indicating the variety of qubits.

Lastly the U_A operation is realised with

[
begin{align}
U_A , : quad
|xrangle_n |0rangle_{n+1} |0rangle  &rightarrow |xrangle_n |Ax,text{mod}, Nrangle_{n+1} |0rangle
&rightarrow |Ax,text{mod}, Nrangle_n |xrangle_{n+1} |0rangle
&rightarrow |Ax,text{mod}, Nrangle_n |0rangle_{n+1} |0rangle
end{align}
]

Step one is the V_A operation. The second step makes use of SWAP gates to trade the 2 units of n qubits. Observe that the overflow qubit of the center state will not be swapped (it’s within the |0> state at this stage). The third step is the V_-B operation with B = A^-1, the inverse of A in Z_N, utilizing the truth that (x – BAx) mod N = (x – x) mod N = 0. That is the primary and solely place the place the situation that A and N are coprime integers is used (in any other case B doesn’t exist).

Counting the variety of qubits used, we see that the total U_A operation requires 2n+2 qubits.

Quantum complexity evaluation

The “complexity” of a quantum algorithm is often expressed when it comes to three portions: the variety of qubits used, the variety of gates used and the depth of the circuit. 

The variety of qubits used is a transparent notion. It’s important as quantum processors nonetheless have a restricted variety of qubits to work with (usually within the tons of as of 2025).

The variety of gates is a extra fuzzy notion and sometimes refers back to the variety of single-qubit and two-qubit gates similar to H, NOT, P, SWAP, CNOT. This may be misleading because the bodily implementation of these gates might require a number of “bodily” gates, representing qubit operations carried out on the {hardware} stage. Usually two-qubit gates, similar to SWAP and CNOT, between distant qubits require a series of bodily two-qubit gates performing on neighbouring qubits. The variety of bodily gates depends upon the “connectivity” of the quantum processors, particularly which two-qubit operations are allowed bodily. These correspond to operations on close by qubits. Even single-qubit gates, such because the Hadamard gate, might require a number of bodily single-qubit gates. 

For the reason that set of bodily gates and the {hardware} connectivity differ from one supplier to the opposite, most of educational analysis merely focuses on counting the variety of “primary” single-qubit and two-qubit gates. 

The depth of the quantum circuit refers back to the variety of sequential operations on the qubits needed to succeed in the ultimate measurement step. The extra parallelised operations on qubits there are, the decrease is the depth. The depth might be roughly visualised because the size of the circuit in a pictorial illustration. You will need to minimise the depth of a quantum circuit as a result of the quantum coherence of qubits diminishes with the depth. The extra sequential operations there are, the longer it takes to run the circuit earlier than measuring its outcomes and the extra time there’s for qubits to work together with the atmosphere and unfastened their coherence.

If we check out our implementation of U_A , we see that it requires (at the very least) 2n+2 qubits. The variety of gates we used is O(n³) (an element n² comes from utilizing the QFT gate) and the depth is O(n²) (an element n comes from utilizing the QFT gate).

The whole order-finding circuit requires yet one more ancilla qubit, if we use the 1-control qubit simplification, and performs O(n) sequential U_A operations, so the entire variety of qubits required is 2n+3 (4n+2 if we use the circuit with 2n management qubits), the entire variety of gates is O(n⁴) and the depth is O(n³).

There may be yet one more normal simplification, which is to make use of an approximate QFT transformation utilizing solely O(n log n) gates, as a substitute of O(n²). This makes the analysis of the order-finding fraction okay/2²ⁿ a bit much less exact, however nonetheless ok for operating Shor’s algorithm with excessive success chance. This brings down the variety of gates to O(n³ log n).

Many analysis papers have include small enhancements on these numbers, however no main breakthrough to my information.

Total the price of operating the algorithm, each when it comes to variety of qubits and variety of operations is polynomial in n, which was the promise of Shor’s algorithm, displaying a quantum benefit on the factoring process for very giant integers N.

Simulations and runs on IBM quantum {hardware}

Up to now the whole lot we mentioned was theoretical, and recognized 20 years in the past. As we speak a number of corporations try to develop quantum processors which may in precept run Shor’s algorithm. Particularly the IBM Quantum Platform gives the chance to carry out a restricted of variety of quantum computations at no cost on quantum processors (QPUs) with 128 qubits.

The Qiskit SDK gives a handy interface to implement quantum circuits, carry out simulations and run the circuits on IBM quantum {hardware}. The training platform gives an introduction to Qiskit for newcomers.

$ pip set up qiskit qiskit-ibm-runtime qiskit-aer qiskit[visualization]

To run Shor’s algorithm, we use the open-source qiskit-shor library, carried out by the writer of this submit. We invite any reader within the actual implementation to try the linked repository.

The qiskit-shor API has two features: find_order(A, N) operating the order-finding circuit and returning the order r of A in Z_N , along with the distribution of measured outputs, and find_factor(N) which runs Shor’s algorithm in full and returns an element of N, if one was discovered.

To extend the possibilities of success, we run the order-finding circuit many occasions, between 100 and 1000 occasions, and observe a distribution of measured outputs. From this distribution, we take into account the highest 10 most frequent values to try to extract the order.

The library implements each the order-finding circuit with 2n management qubits and the optimised model with one management qubit. Nonetheless, we largely use the much less optimum model with 2n management qubits, because the IBM platform has stricter utilization limitations for circuits utilizing management circulate operations.

Simulations

After cloning the qiskit-shor repository, we will begin with operating simulations, utilizing the qiskit Aer simulator. We run simulations with out noise, to check the code. We’ll work solely with small integers as simulating a quantum state of many qubits on a classical pc is computationally intensive and we solely need to illustrate the above presentation with easy examples.

from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit.visualization import plot_distribution
from qiskit_aer import AerSimulator
from qiskit_aer.primitives import SamplerV2 as AerSampler
from qiskit_shor.shor import find_order

aer_sim = AerSimulator()
pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
sampler = AerSampler()

# Discover the order of seven in Z_15.
r, dist = find_order(A=7, N=15, sampler=sampler, pass_manager=pm, num_shots=100)
plot_distribution(dist)

Begin seek for the order of seven in Z_15
Discovered worth 4 for order of seven in Z_15.

The perform returns the order 4, which is right, 7⁴ = 1 mod 15. The output distribution reveals 4 values for the returned integer okay: 00000000, 01000000, 1000000, 11000000, akin to the binary notation of the integers 0, 2⁶, 2⁷ and a pair of⁶+2⁷ respectively. The output has 2n=8 qubits, with n=⌈log₂(15)⌉=4. The distribution of approximate fractions okay/2⁸ has values 0, 1/4, 1/2, 3/4, with related variety of occurrences. These correspond to the anticipated phases estimates j/4, j=0, 1, 2, 3, of the operator U₇. The widespread denominator 4 of those fractions provides us the order of seven in Z₁₅ .

Allow us to have a look at a second instance and seek for the order of 5 in Z₂₁.

r, dist = find_order(A=5, N=21, sampler=sampler, pass_manager=pm, num_shots=500)
plot_distribution(dist)

Begin seek for the order of 5 in Z_21
Discovered worth 6 for the order of 5 in Z_21.

The quantum search returns the right worth 6. The distribution of outputs has extra outcomes and importantly reveals some peaks. Changing the histogram bin labels by the corresponding fractions okay/2¹⁰ (rounded to 4 decimals) the histogram turns into

We see that there are peaks at 0, 1/6, 1/3, 1/2, 2/3 and 5/6, that are all of the values of the shape j/6, j =0, 1, 2, 3, 4, 5 (the peaks don’t seem repeatedly spaced within the determine, attributable to bins with zero outcomes dropping). The values j/6 correspond to the eigenvalues of the unitary operator U₅, with 6 being the order of 5 in Z₂₁, as anticipated.

We are able to simulate the total algorithm for completeness and extract non-trivial components for N=15 and N=21. The next code runs Shor’s algorithm with a most of three trial values for A, stopping if an element of N is discovered. Every trial consists in operating 100 occasions the order-finding circuit.

from qiskit_shor.shor import find_factor

f = find_factor(
    N=15, sampler=sampler, pass_manager=pm, num_tries=3, num_shots_per_trial=100
)

Begin seek for the order of 4 in Z_15
Discovered worth 2 for the order of 4 in Z_15
Issue discovered: 3

The worth A=4 was randomly chosen, then the order 2 was discovered, lastly the issue 3 of N=15 was returned.

f = find_factor(
    N=21, sampler=sampler, pass_manager=pm, num_tries=3, num_shots_per_trial=100
)

Begin seek for the order of 17 in Z_21
Discovered worth 6 for the order of 17 in Z_21
Begin seek for the order of 19 in Z_21
Discovered worth 6 for the order of 19 in Z_21
Issue discovered: 3

The worth A=17 was tried first, getting the order 6, however gcd(A^r/2 – 1, N) = gcd(4912, 21) = 1, so this doesn’t give an element of 21. The worth 19 was tried subsequent, getting the order 6 once more. This time gcd(A^r/2 – 1, N) = gcd(6858, 21) = 3, giving the issue 3 of 21.

Quantum runs

Now that we’re satisfied that the order-finding circuit is appropriately carried out, we will attempt to run it on precise QPUs.

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

# For this to run, you want to setup an IBM Cloud account and generate 
# an API token. See https://cloud.ibm.com

# Load default saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False, min_num_qubits=127)
print(f"backend: {backend.title}")
pm = generate_preset_pass_manager(goal=backend.goal, optimization_level=1)
sampler = Sampler(mode=backend)

backend: ibm_brisbane

Allow us to now attempt to discover the order of seven in Z₁₅, as within the simulation above.

r, dist = find_order(A=7, N=15, sampler=sampler, pass_manager=pm, num_shots=1000)
plot_distribution(dist)

Begin seek for the order of seven in Z_15
Discovered worth 4 for order of seven in Z_15

The right order 4 of seven in Z₁₅ is returned, however the distribution of outcomes is way from the one within the simulation, which had solely 4 noticed values. Right here nearly all values between 0 and a pair of⁸-1 seem, making the plot reasonably unreadable. There are some small peaks, however the result’s largely dominated by noise. It’s considerably miraculous that from the ten most frequent values, the algorithm is ready to extract the right order.

Different runs for various values of A, for N=15 or N=21, produce related noisy information. It’s because the quantum {hardware} is topic to quantum noise interfering with unitary gate operations. The extra gates there are, the extra noise there’s. Within the N=15 order discovering circuit, our implementation has already 2482 gates. That is technique to a lot for the present quantum computation capacities.

from qiskit_shor.shor import order_finding_circuit

qc = order_finding_circuit(A=7, N=15)
print(f"Variety of qubits: {qc.num_qubits}")  # 4n+2 qubits, with n = ceil(log2(N)) = 4
print(f"Variety of gates: {qc.measurement()}")
print(f"Circuit depth: {qc.depth()}")

Variety of qubits: 18
Variety of gates: 2482
Circuit depth: 1632

We are able to strive a case with fewer qubits, by trying to find the order of 5 in Z₆, utilizing the one-control qubit optimised circuit.

from qiskit_shor.shor import order_finding_circuit_one_control

qc = order_finding_circuit_one_control(A=5, N=6)
print(f"Variety of qubits: {qc.num_qubits}")  # 2n+3 qubits, with n = ceil(log2(N)) = 3
print(f"Variety of gates: {qc.measurement()}")
print(f"Circuit depth: {qc.depth()}")

Variety of qubits: 9
Variety of gates: 1246
Circuit depth: 861

r, dist = find_order(A=5, N=6, sampler=sampler, pass_manager=pm, num_shots=1000, one_control_circuit=True)
plot_distribution(dist)

Begin seek for the order of 5 in Z_6
Discovered worth 2 for the order of 5 in Z_6

The right order 2 is returned, however the distribution remains to be dominated by the quantum noise.

Concluding ideas

We now have given a tentatively full presentation of the implementation of Shor’s algorithm, together with a considerably detailed description of the quantum modular arithmetic operations concerned. Utilizing the implementation of the qiskit-shor module, now we have run some simulations and a few precise quantum computations on the IBM Quantum platform. The quantum computations turned out to be dominated by quantum noise, making it inconceivable, in the meanwhile, to run Shor’s algorithm and extract significant outcomes.

The implementation we used was naive, within the sense that it didn’t embrace state-of-the-art optimisation. However the noticed noisy outputs of this naive implementation when operating Shor’s algorithm for very small values of N, signifies that related outcomes can be obtained, even with further circuit optimisations.

Sooner or later it’d turn out to be extra sensible to run Shor’s algorithm efficiently. The big progress in quantum {hardware} capacities within the current years depart us with respectable hopes to see this occur in a number of years time.

References

[1] Original paper: Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum pc. SIAM evaluate, 41(2), 303-332.

[2] S. Beauregard, Circuit for Shor’s algorithm utilizing 2n+ 3 qubits. arxiv: quant-ph/0205095.

[3] Parker, S., & Plenio, M. B. (2000). Environment friendly factorization with a single pure qubit and log N blended qubits. Bodily Assessment Letters, 85(14), 3049. arxiv: quant-ph/0001066.

[4] T. Draper, Addition on a Quantum Laptop, arxiv preprint: quant-ph/0008033

[5] S. Wang et al, A Complete Examine of Quantum Arithmetic Circuits, arxiv: quant-ph/2406.03867.

[6] S. Cuccaro et al, A brand new quantum ripple-carry addition circuit, arxiv: quant-ph/0410184.

---

Until in any other case famous, all pictures are by the writer.