Where are we with Shor’s algorithm?

was proposed by Peter Shor in a seminal paper [1] in 1995 as an algorithm for factoring massive numbers utilizing quantum computing. In 2025, i.e. 30 years later, early quantum processors are produced and made accessible to the general public, making it attainable to check the algorithm for actual. Can we efficiently run Shor’s algorithm on massive 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 way in which, how will we implement Shor’s algorithm concretely?

On this put up 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 put up, it could be preferrred if you already know some fundamentals of quantum computing, particularly qubit manipulations and normal unitary gate operations, and a little bit of linear algebra.

Disclaimer 1: Though I intention at a scientific degree of rigorousness, this isn’t a tutorial paper and I don’t fake to be an knowledgeable within the area.

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

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 simple to discover a issue for a sufficiently small N, by attempting attainable values as much as N^1/2 for example, the issue turns into impractical when N is actually 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 jot 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 may be run on a conventional pc, particularly an algorithm which is product of arithmetic operations on numbers. That is mainly all algorithms, besides quantum algorithms.

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

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

Furthermore, it occurs that the issue of factoring massive integers is on the coronary heart of public key cryptography and the RSA algorithm, which is extensively used right this moment to safe Web communications. Shor’s algorithm, if efficiently run on a quantum pc holding a number of thousand qubits, might break this encryption scheme. This makes it one of the standard functions in quantum computing.

Whereas we’re nonetheless considerably removed from having a quantum pc with the capability to run Shor’s algorithm on massive numbers, the present progress makes it attainable 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 truly implement it and run it on quantum {hardware}. 

Profiting from 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 total implementation is offered 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 net (see e.g. Wikipedia). We are going to 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 elements. Additionally require that N is odd and isn’t the ability of a major quantity (in these instances, 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 accomplished (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 beneath).
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 example, 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 concept 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”) may be expressed as a linear mixture of the corresponding eigenvectors. The algorithm tries to estimate at the 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 are going to 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 needs to 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). Sometimes, one would run the order discovering circuit and measure its outcomes many occasions to search out r with very massive chance. The expectation is that the distribution of outputs okay/2^m ought to have peaks (of identical magnitude) in any respect the values j/r, for 0 ≤ j < r.

All of the classical operations are simple 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 appears.

Order-finding quantum circuit

The order-finding circuit is depicted within the following determine. A number of modifications may be dropped at 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 reworked by an inverse QFT gate and are all measured (indicated by circles with “m” within the determine).

One might change 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 matter. 

Within the above circuit, all substances are simply carried out within the Qiskit SDK, aside from the unitary operator U_A (and its managed model CU_A). That is the place all the issue stands. The vast majority 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 truly requires n + c further qubits, termed ancillary or ancilla qubits (the precise fixed c is determined by the chosen implementation). 

Earlier than discussing the circuit implementation of U_A, allow us to point out that there’s an necessary simplification of the above circuit. The 2n management qubits may be changed by a single qubit (!), which undergoes a collection 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 value of introducing management movement operations, particularly gate actions relying on intermediate measurements. Whereas this may increasingly appear like an inexpensive value to pay in concept, in apply management movement gates are operationally extra advanced 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 id 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 may be discovered, for example, in [3].

The U_A gate and quantum modular arithmetics

Notice: This part is extra technical. Some readers would possibly need to skip this half on a primary learn and go on to the following part.

Allow us to now give attention to the circuit implementing the unitary motion

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

The insightful reader would possibly 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 necessary 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 want at the least n = ⌈log₂(N)⌉ qubits to characterize quantum integers modulo N, so we are going to assume that n is the scale of the quantum register we work with, i.e. the variety of qubits holding x. This implies we will characterize quantum integers between 0 and a couple ofⁿ-1.

There are two “colleges 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 Remodel” (QFT) method performs addition by way of parametrised section gates P(λ) on the Fourier house illustration of the enter integer (extra on this beneath).

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 preserving observe of carry-over items 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 beneath). This method may 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 may 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 massive, O(n²) truly, the following addition in Fourier house requires solely n section gates which may function in parallel. A number of additions, or managed additions, may be carried out sequentially, alongside the execution of a quantum circuit, whereas the quantum integer x is represented in Fourier house, by way of 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 alternative in lots of tasks requiring quantum adder circuits.

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

You will need to notice that the addition operation described above is all the time modulo 2ⁿ. That is as anticipated, since we will solely characterize 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 subsequent step is to implement the “modulo N” half. That is considerably tougher and requires a collection of (managed) additions and (managed) subtractions. The fundamental 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)⌉, contemplate the n+1 qubit state |x⟩_n+1. That is yet one more qubit than mandatory to carry x, i.e. there may be 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 accomplished by way of a CNOT gate performing on |a⟩ and managed by probably 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 permit 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 probably 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 will look a bit of concerned, however that is arguably the best quantum algorithm discovered to this point to carry out modular addition. 

The final three steps, reverting the ancilla qubit |a⟩ again to its preliminary state |0⟩, are necessary, if the ancilla qubit is to be re-used in subsequent modular addition operations, which is the case in Shor’s algorithm. Alternatively, one might use new ancilla qubits for every modular addition, lowering 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 beneath).

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

The subsequent 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 accomplished 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. Notice that the overflow qubit of the center state is just not 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 by way of 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 is crucial as quantum processors nonetheless have a restricted variety of qubits to work with (sometimes within the lots of as of 2025).

The variety of gates is a extra fuzzy notion and infrequently refers back to the variety of single-qubit and two-qubit gates akin to H, NOT, P, SWAP, CNOT. This may be misleading because the bodily implementation of these gates could require a number of “bodily” gates, representing qubit operations carried out on the {hardware} degree. Sometimes two-qubit gates, akin to SWAP and CNOT, between distant qubits require a sequence of bodily two-qubit gates performing on neighbouring qubits. The variety of bodily gates is determined by 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, could require a number of bodily single-qubit gates. 

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

The depth of the quantum circuit refers back to the variety of sequential operations on the qubits mandatory to succeed in the ultimate measurement step. The extra parallelised operations on qubits there are, the decrease is the depth. The depth may 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 may be for qubits to work together with the atmosphere and free their coherence.

If we check out our implementation of U_A , we see that it requires (at the 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 entire 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 adequate 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 data.

Total the price of operating the algorithm, each by way of variety of qubits and variety of operations is polynomial in n, which was the promise of Shor’s algorithm, exhibiting a quantum benefit on the factoring activity for very massive integers N.

Simulations and runs on IBM quantum {hardware}

To date all the things we mentioned was theoretical, and recognized 20 years in the past. At present a number of firms try to develop quantum processors which might in precept run Shor’s algorithm. Specifically the IBM Quantum Platform presents the likelihood to carry out a restricted of variety of quantum computations without 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 educational platform presents 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 creator of this put up. We invite any reader within the precise implementation to try the linked repository.

The qiskit-shor API has two capabilities: 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 contemplate 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. Nevertheless, we principally use the much less optimum model with 2n management qubits, because the IBM platform has stricter utilization limitations for circuits utilizing management movement 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 are going to 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 operate returns the order 4, which is appropriate, 7⁴ = 1 mod 15. The output distribution reveals 4 values for the returned integer okay: 00000000, 01000000, 1000000, 11000000, similar to the binary notation of the integers 0, 2⁶, 2⁷ and a couple 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 offers 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 often spaced within the determine, because of 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 elements 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 accurately 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, it's essential 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.identify}")
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 much from the one within the simulation, which had solely 4 noticed values. Right here virtually all values between 0 and a couple of⁸-1 seem, making the plot relatively 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 may be. Within the N=15 order discovering circuit, our implementation has already 2482 gates. That is method 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’ve got 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, we now 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 not possible, in the interim, to run Shor’s algorithm and extract significant outcomes.

The implementation we used was naive, within the sense that it didn’t embody 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 would turn into extra reasonable to run Shor’s algorithm efficiently. The big progress in quantum {hardware} capacities within the current years depart us with first rate 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 Overview Letters, 85(14), 3049. arxiv: quant-ph/0001066.

[4] T. Draper, Addition on a Quantum Pc, 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 photographs are by the creator.