shor_algorithm

Functionality

The goal of Shor’s algorithm is, given coprime integers \(N\) and \(1<a<N\), to find the order \(r\) of \(a\) modulo \(N\), the smallest positive integer \(r\) such that \(a^{r}\equiv 1{\pmod {N}}\).

To achieve this, Shor’s algorithm uses a quantum circuit involving two registers. The second register uses \(n\) qubits, where \(n\) is the smallest integer such that \(N \leq 2^n\), i.e., \(n = \lceil \log_2 N \rceil\). The size of the first register determines how accurate of an approximation the circuit produces. It can be shown that using \(2n\) qubits gives sufficient accuracy to find \(r\). The exact quantum circuit depends on the parameters \(a\) and \(N\), which define the problem.

---

shor.py

Callee: Shor

Implements Shor’s algorithm for integer factorization.

The algorithm consists of two main steps:

1. Use quantum phase estimation with unitary matrix \(U\) representing the operation of multiplying by \(a\) (modulo \(N\)), and input state \(\ket{0}_{n+2}\ket{1}_n\ket{0}_{2n}\), where this state preparation is included in the benchmark algorithm. The eigenvalues of this \(U\) encode information about the period, and \(\ket{1}_n\) can be seen to be writable as a sum of its eigenvectors. Thanks to these properties, the quantum phase estimation stage gives as output a random integer \(c \approx \frac{j}{r}2^{2n}\) for random \(j \in \{0, \cdots, r-1\}\) upon measuring the \(2n\)-qubit state.

2. Use the continued fractions algorithm to extract the period \(r\) from the measurement outcomes obtained in the previous stage. This is a procedure to post-process (with a classical computer) the measurement data obtained from measuring the output quantum states, and retrieve the period.

Test expectations:

Upon measurement, the \(2n\) phase qubits produced by quantum phase estimation will yield a random integer

\[ c \approx \frac{j}{r}2^{2n}, j \in \{0, \cdots, r-1\} \]

where \(r\) is the order of \(a\) mod \(N\). Consequently, the probability distribution over the measurement outcomes of the phase register should concentrate around the peak locations

\[ c_j \approx round(\frac{j2^{2n}}{r}) \]

near each \(c_j\) corresponding to \(j \in \{0, \cdots, r-1\}\).

Supplementary material:

More details about Shor’s algorithm can be found in the following resource: [44] [45] [46] [47]

Post-processing

We retain a function of post-process to return the result in desired classical format in shor_postprocessing.py.

The original code is sourced from: https://quantum.cloud.ibm.com/docs/en/tutorials/shors-algorithm.

---

Function: shor_classical_postprocess(counts: dict[str, int], a: int, N: int, num_control: int)

Implements the classical post-processing stage of Shor’s algorithm.

This function processes the measurement outcomes produced by the quantum phase estimation (QPE) circuit and attempts to recover the order \(r\) of \(a\) modulo \(N\). Once a valid order is obtained, it computes a non-trivial factor of \(N\) using classical number-theoretic methods.

The algorithm consists of the following steps:

1. Phase extraction
   Each measured bitstring from the phase register is interpreted as a binary integer \(c\), yielding a phase

   \[ \theta = \frac{c}{2^{\text{num\_control}}} \approx \frac{k}{r}. \]

2. Order estimation via continued fractions
   The continued fractions algorithm is applied to \(\theta\) to obtain a rational approximation \(\frac{k}{r}\), where the denominator \(r\) is taken as a candidate order of \(a \mod N\).

3. Factor extraction
   If the estimated order \(r\) is even, the algorithm computes

   \[ \gcd\left(a^{r/2} - 1,\, N\right), \]

   and checks whether the result is a non-trivial factor of \(N\).

The procedure iterates over measurement outcomes until a valid factor is found or no further candidates remain.

API

qolumbina.programs.shor_algorithm.shor

Shor benchmark definition.

class Shor(to_be_factored_number, a)

Bases: QuantumCircuit

Shor’s algorithm implementation.

Parameters:

• to_be_factored_number (int) – The integer to be factored, denoted as \(N\).

• a (int) – An integer coprime to \(N\), denoted as \(a\).

controlled_multiple_mod_n(num_bits_necessary, to_be_factored_number, a, c_phi_add_n, iphi_add_n, qft, iqft)

Implements modular multiplication by a as an instruction.

Parameters:

• num_bits_necessary (int)

• to_be_factored_number (int)

• a (int)

• c_phi_add_n (QuantumCircuit)

• iphi_add_n (QuantumCircuit)

• qft (QuantumCircuit)

• iqft (QuantumCircuit)

Return type:

QuantumCircuit

double_controlled_phi_add_mod_n(angles, c_phi_add_n, iphi_add_n, qft, iqft)

Creates a circuit which implements double-controlled modular addition by a.

Parameters:

• angles (NDArray[np.float64] | ParameterVector)

• c_phi_add_n (QuantumCircuit)

• iphi_add_n (QuantumCircuit)

• qft (QuantumCircuit)

• iqft (QuantumCircuit)

Return type:

QuantumCircuit

static get_angles(a, n)

Calculates the array of angles to be used in the addition in Fourier Space.

Parameters:

• a (int)

• n (int)

Return type:

NDArray[np.float64]

static phi_add_gate(angles)

Gate that performs addition by a in Fourier Space.

Parameters:

angles (NDArray[np.float64] | ParameterVector)

Return type:

QuantumCircuit

power_mod_n(num_bits_necessary, to_be_factored_number, a)

Implements modular exponentiation a^x as a quantum circuit.

Parameters:

• num_bits_necessary (int)

• to_be_factored_number (int)

• a (int)

Return type:

QuantumCircuit

synth_qft_full(num_qubits, do_swaps=True, approximation_degree=0, insert_barriers=False, inverse=False, name=None)

Construct a circuit for the Quantum Fourier Transform using all-to-all connectivity.

Note

With the default value of do_swaps = True, this synthesis algorithm creates a circuit that faithfully implements the QFT operation. This circuit contains a sequence of swap gates at the end, corresponding to reversing the order of its output qubits. In some applications this reversal permutation can be avoided. Setting do_swaps = False creates a circuit without this reversal permutation, at the expense that this circuit implements the “QFT-with-reversal” instead of QFT. Alternatively, the ElidePermutations transpiler pass is able to remove these swap gates.

Parameters:

• num_qubits (int) – The number of qubits on which the Quantum Fourier Transform acts.

• do_swaps (bool) – Whether to synthesize the “QFT” or the “QFT-with-reversal” operation.

• approximation_degree (int) – The degree of approximation (0 for no approximation). It is possible to implement the QFT approximately by ignoring controlled-phase rotations with the angle beneath a threshold. This is discussed in more detail in https://arxiv.org/abs/quant-ph/9601018 or https://arxiv.org/abs/quant-ph/0403071.

• insert_barriers (bool) – If True, barriers are inserted for improved visualization.

• inverse (bool) – If True, the inverse Quantum Fourier Transform is constructed.

• name (str | None) – The name of the circuit.

Returns:

A circuit implementing the QFT operation.

Return type:

QuantumCircuit

static validate_input(to_be_factored_number, a)

Check parameters of the algorithm.

Parameters:

• to_be_factored_number (int) – The odd integer to be factored, has a min. value of 3.

• a (int) – Any integer that satisfies 1 < a < N and gcd(a, N) = 1.

Raises:

ValueError – Invalid input

Return type:

None

create_instance(choice)

Returns the number to be factorized and the integer a for the Shor’s algorithm.

Parameters:

choice (str)

Return type:

list[int]

qolumbina.programs.shor_algorithm._common.shor_postprocessing

shor_classical_postprocess(counts, a, N, num_control)

Classical post-processing stage of Shor’s algorithm.

Parameters:

• counts (dict[str, int]) – Qiskit backend measurement counts of the phase register. Format: {bitstring: shots}

• a (int) – The base used in modular exponentiation. Must be coprime to \(N\).

• N (int) – The integer \(N\) to be factorized

• num_control (int) – Number of control (phase) qubits.

Returns:

A non-trivial factor of N if found, otherwise None.