Source code for qolumbina.programs.shor_algorithm._common.shor_postprocessing

from fractions import Fraction
from math import gcd



def shor_classical_postprocess(
    counts: dict[str, int],
    a: int,
    N: int,
    num_control: int
):
    r"""
    Classical post-processing stage of Shor's algorithm.

    Args:
        counts: Qiskit backend measurement counts of the phase register.
                Format: {bitstring: shots}
        a: The base used in modular exponentiation. Must be coprime to :math:`N`.
        N: The integer :math:`N` to be factorized
        num_control: Number of control (phase) qubits.

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

    FACTOR_FOUND = False
    num_attempt = 0

    while not FACTOR_FOUND:
        print(f"\nATTEMPT {num_attempt}:")
        # Here, we get the bitstring by iterating over outcomes
        # of a previous hardware run with multiple shots.
        # Instead, we can also perform a single-shot measurement
        # here in the loop.
        bitstring = list(counts.keys())[num_attempt]
        num_attempt += 1
        # Find the phase from measurement
        decimal = int(bitstring, 2)
        phase = decimal / (2**num_control)  # phase = k / r
        print(f"Phase: theta = {phase}")
    
        # Guess the order from phase
        frac = Fraction(phase).limit_denominator(N)
        r = frac.denominator  # order = r
        print(f"Order of {a} modulo {N} estimated as: r = {r}")
    
        if phase != 0:
            # Guesses for factors are gcd(a^{r / 2} +/- 1, N)
            if r % 2 == 0:
                x = pow(a, r // 2, N) - 1
                d = gcd(x, N)
                if d > 1:
                    FACTOR_FOUND = True
                    print(f"*** Non-trivial factor found: {x} ***")
                    return d