pyqpanda_alg.QLuoShu.Shor

Functions

fastExpMod(b, e, m)	Fast exponentiation modulo operation.
Shor(N, a)	Quantum Circuit for Shor's algorithm.

Module Contents

pyqpanda_alg.QLuoShu.Shor.fastExpMod(b, e, m)

Fast exponentiation modulo operation.

Parameters:

b (int): Base number. e (int): Exponent. m (int): Modulus.

Returns:

int: The result of (b^e) % m.

pyqpanda_alg.QLuoShu.Shor.Shor(N, a)

Quantum Circuit for Shor’s algorithm.

This function contains a quantum computing part and a classical post-processing part, which calculates the factorization of the semi-prime integer N. Given an integer ‘N’ and an integer ‘a’ coprime with ‘N’ as input, the two prime factors ‘p,q’ of N can be calculated by using the ‘Shor’ function.

Parameters:

\(N\) : int

a semi-prime integer

\(a\) : int

an integer coprime with ‘N’

Return:

factor_1, factor_2

Here, the shor algorithm we provide is a semiclassical shor algorithm, which can achieve a :math:’2n+1’-qubit quantum circuit by decomposing QFT with \(n=\lceil \log_{2}N \rceil\). By measuring the quantum circuit of the Shor algorithm, the measurement result :math:’m’ is obtained. Subsequently, we are going to expand :math:’m/2^n’ with consecutive fractions to obtain the period :math:’r’. Finally, we compute the factors of :math:’N’ by the period :math:’r’. If :math:’r’ is even, we can get \(p=\gcd(a^(r/2)+1,N),q=\gcd(a^(r/2)-1,N)\); If :math:’r’ is odd, we can check \(t=r+1\) or \(t=r-1\) and compute \(p=\gcd(a^(t+1/2)+1,N),q=\gcd(a^(t/2)-1,N)\). It means that we get the factorization of the integer \(N\) if \(p*q=N\).

Example:

If \(N=77,a=5\) , by the ‘Shor’ function, we can get the factors (7,11).

Note:

The integer \(a\) must be coprime with \(N\). On the 30-qubit quantum virtual machine, the ‘Shor’ function can only decompose semi-prime numbers of less than 14-bit.

from pyqpanda import *
import numpy as np
import math
from fractions import Fraction
import time
import itertools

if __name__ == "__main__":
     N = 77
     a = 5
     start_time = time.time()
     print(Shor(N, a))
     end_time = time.time()
     print("Times: {:.2f}s".format(end_time - start_time))

(7, 11)
Times: 1.86s

Note that: if \(N\) is a power of 2, we need to let \(n=\lceil \log_{2}N \rceil+1\) in the Example.