ShorFactor

QuICT.algorithm.quantum_algorithm.ShorFactor

ShorFactor(N: int, *, c_mod_multiplier: _ModMultiMethod = 'bea', qpe_method: _QpeMethod = 'normal')

Shor's factoring algorithm

References

[1]: "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer" by Peter W. Shor https://arxiv.org/abs/quant-ph/9508027.

[2]: Nielsen, M.A., & Chuang, I.L. (2010). Quantum Computation and Quantum Information, p.232.

Parameters:

• N (int) –

  The number to be factored.

• c_mod_multiplier (str, default: 'bea' ) –

  Modular multiplication method to be used when constructing the circuit for Shor's algorithm, choose from "bea" and "hrs".

• qpe_method (str, default: 'normal' ) –

  Quantum phase estimation implementation to be used when constructing the order finding circuit, choose from "normal" and "iterative".

Source code in QuICT/algorithm/quantum_algorithm/shor/shor_factor.py

def __init__(
    self,
    N: int,
    *,
    c_mod_multiplier: _ModMultiMethod = "bea",
    qpe_method: _QpeMethod = "normal"
):
    """
    Args:
        N (int): The number to be factored.
        c_mod_multiplier (str): Modular multiplication method to be used when constructing the
            circuit for Shor's algorithm, choose from "bea" and "hrs".
        qpe_method (str): Quantum phase estimation implementation to be used when constructing
            the order finding circuit, choose from "normal" and "iterative".
    """
    try:
        self.c_mod_multi = self._MOD_MULTIPLIER_METHODS[c_mod_multiplier]
    except:
        raise ValueError(f"{c_mod_multiplier} is not a valid modular multiplication option. ",
                         f"Please choose from {self._MOD_MULTIPLIER_METHODS}.")

    try:
        self.qpe_method = self._QPE_METHDOS[qpe_method]
    except:
        raise ValueError(f"{qpe_method} is not a valid option for quantum phase estimation. ",
                         f"Please choose from {self._QPE_METHDOS}.")

    self.N = N

    self.work_bits_num = int(np.ceil(np.log2(self.N + 1)))
    self.order_bits_num = int(np.ceil(2 * np.log2(self.N + 1)))
    self._qpe_cache = {}
    self.distribution = None

running_data property

running_data: Dict

Return historical data of all the qpe circuits that has been used by run in (base, qpe_algorithm) key and value pairs.

SRData

SRData()

For storing (s, r) pair when running order finding for multiple times.

Source code in QuICT/algorithm/quantum_algorithm/shor/shor_factor.py

def __init__(self) -> None:
    self.s_list = []
    self.r_list = []

    self.lcm_s = 1
    self.lcm_r = 1

add

add(new_s: int, new_r: int) -> None

Add new (s, r) pair.

Source code in QuICT/algorithm/quantum_algorithm/shor/shor_factor.py

def add(self, new_s: int, new_r: int) -> None:
    """ Add new (s, r) pair. """
    if not self.is_valid(new_s, new_r):
        raise ValueError(f"The (s = {new_s}, r = {new_r}) pair cannot be added. ")

    self.s_list.append(new_s)
    self.r_list.append(new_r)

    gcd_s = gcd(self.lcm_s, new_s)
    gcd_r = gcd(self.lcm_r, new_r)
    self.lcm_s = (self.lcm_s // gcd_s) * new_s
    self.lcm_r = (self.lcm_r // gcd_r) * new_r

is_valid

is_valid(new_s: int, new_r: int) -> bool

Return whether the incoming s-r pair can be added.

Source code in QuICT/algorithm/quantum_algorithm/shor/shor_factor.py

def is_valid(self, new_s: int, new_r: int) -> bool:
    """ Return whether the incoming s-r pair can be added. """
    return gcd(self.lcm_s, new_s) == 1 and (self.lcm_r % new_r) != 0

circuit

circuit(base: int = None) -> Circuit

Construct the order finding quantum circuit for Shor's algorithm,

Parameters:

• base (int, default: None ) –

  The base for calculating the order r mod N. Has to be coprime to N. If not provided, will choose randomly in [2, N - 1].

Returns:

• Circuit ( Circuit ) –

  An order finding circuit.

Source code in QuICT/algorithm/quantum_algorithm/shor/shor_factor.py

def circuit(self, base: int = None) -> Circuit:
    """ Construct the order finding quantum circuit for Shor's algorithm,

    Args:
        base (int): The base for calculating the order r mod N. Has to be coprime to N.
            If not provided, will choose randomly in [2, N - 1].

    Returns:
        Circuit: An order finding circuit.
    """
    if base is None:
        base = self._rand_coprime(self.N)
    elif gcd(base, self.N) != 1:
        raise ValueError(f"The given base:{base} is not co-prime to {self.N}.")

    sf_logger.info(f"Constructing shor's order finding circuit with base={base}.")

    qpe_alg = self.qpe_method(
        precision_bits=self.order_bits_num,
        work_bits=self.work_bits_num,
        control_unitary=self.c_mod_multi(modulus=self.N, multiple=base, qreg_size=self.work_bits_num),
        work_state_prep=CompositeGate(gates=[X & 0], name="X")
    )

    return qpe_alg.circuit()

reset

reset()

Clear all the historical qpe algorithm data generated from run.

Source code in QuICT/algorithm/quantum_algorithm/shor/shor_factor.py

def reset(self):
    """ Clear all the historical qpe algorithm data generated from run. """
    self._qpe_cache.clear()

run

run(base: int = None, *, max_it: int = 1, forced_quantum_approach: bool = False, backend=StateVectorSimulator(ignore_last_measure=False)) -> Tuple[int, int]

Run Shor's factoring algorithm.

Parameters:

• base (int, default: None ) –

  The base for calculating the order r mod N. Has to be coprime to N. If not provided, will choose randomly in [2, N - 1].

• max_it (int, default: 1 ) –

  The maximum number of order finding iteration.

• forced_quantum_approach (bool, default: False ) –

  If true, the order finding part is forced to use the quantum approach.

• backend (Any, default: StateVectorSimulator(ignore_last_measure=False) ) –

  Device to run the circuit.

Returns:

• Tuple[int, int] –

  Tuple[int, int]: The two factors that multiply to N.

Source code in QuICT/algorithm/quantum_algorithm/shor/shor_factor.py

def run(
    self,
    base: int = None,
    *,
    max_it: int = 1,
    forced_quantum_approach: bool = False,
    backend=StateVectorSimulator(ignore_last_measure=False)
) -> Tuple[int, int]:
    r""" Run Shor's factoring algorithm.

    Args:
        base (int, optional): The base for calculating the order r mod N. Has to be coprime to N.
            If not provided, will choose randomly in [2, N - 1].
        max_it (int, optional): The maximum number of order finding iteration.
        forced_quantum_approach (bool, optional): If true, the order finding part is forced to
            use the quantum approach.
        backend (Any, optional): Device to run the circuit.

    Returns:
        Tuple[int, int]: The two factors that multiply to N.
    """
    ## Eliminate trivial factoring cases
    c_fac1, c_fac2 = self._pre_processing(self.N)
    if c_fac1 != 0:
        return c_fac1, c_fac2

    ## Order finding for nontrivial case
    if base is None:
        base_run = random.randint(2, self.N - 1)
    else:
        base_run = base

    # classical order finding
    while True:
        gcd_bN = np.gcd(base_run, self.N)
        if gcd_bN == 1:
            break
        if not forced_quantum_approach:
            sf_logger.info(f"Shor succeed: randomly chosen base = {base_run}, "
                           f"which has common factor {gcd_bN} with N classically.")
            return gcd_bN, self.N // gcd_bN
        if base is not None:
            raise ValueError(f"The input base = {base} is not coprime to {self.N}, thus "
                             "cannot be used in forced-quantum mode")
        base_run = random.randint(2, self.N - 1)

    # quantum order finding
    sr_pair = self.SRData()
    for _ in range(max_it):
        s, r = self._quantum_order_finding(base_run, backend)

        if r < 2:
            sf_logger.info(f"Post: s/r is close to 0, not valid for post-processing.")
            continue

        # post-processing
        if self._is_order(self.N, base_run, r):
            if r % 2 == 1:
                sf_logger.info(f"Post: found odd order: r = {r}, for base = {base_run}. "
                               "Changing to a new base is recommended.")
                return 0, 0
            if self._is_trivial_order(self.N, base_run, r):
                continue
            sf_logger.info(f"Post: Found an even order: r = {r}.")
            q_fac1, q_fac2 = self._post_processing(self.N, base_run, r)
            if q_fac1 != 0:
                return q_fac1, q_fac2
        else:
            sf_logger.info("Fail finding a valid order in current iteration")
            if max_it > 1 and sr_pair.is_valid(s, r):
                sf_logger.info(f"Add pair (s = {s}, r = {r}) to cumulative data.")
                sr_pair.add(s, r)
                q_fac1, q_fac2 = 0, 0
                if len(sr_pair.s_list) > 1 and self._is_order(self.N, base_run, sr_pair.lcm_r):
                    sf_logger.info(f"Found order: r = {sr_pair.lcm_r}, "
                                   f"from cumulative r list: {sr_pair.r_list}.")
                    q_fac1, q_fac2 = self._post_processing(self.N, base_run, sr_pair.lcm_r)
                if q_fac1 != 0:
                    return q_fac1, q_fac2
    sf_logger.info(f"Fail finding factor for N = {self.N} with base = { base_run}.")
    return 0, 0