Exact search algorithm to factorize large biprimes and a triprime on IBM
  quantum computer
Factoring large integers using a quantum computer is an outstanding research
problem that can illustrate true quantum advantage over classical computers.
Exponential time order is required in order to find the prime factors of an
integer by means of classical computation. However, the order can be
drastically reduced by converting the factorization problem to an optimization
one and solving it using a quantum computer. Recent works involving both
theoretical and experimental approaches use Shor's algorithm, adiabatic quantum
computation and quantum annealing principles to factorize integers. However,
our work makes use of the generalized Grover's algorithm as proposed by Liu,
with an optimal version of classical algorithm/analytic algebra. We utilize the
phase-matching property of the above algorithm for only amplitude amplification
purposes to avoid an inherent phase factor that prevents perfect implementation
of the algorithm. Here we experimentally demonstrate the factorization of two
bi-primes, 4088459 and 966887 using IBM's 5- and 16-qubit quantum processors,
hence making those the largest numbers that have been factorized on a quantum
device. Using the above 5-qubit processor, we also realize the factorization of
a tri-prime integer 175, which had not been achieved to date. We observe good
agreement between experimental and theoretical results with high fidelities.
The difficulty of the factorization experiments has been analyzed and it has
been concluded that the solution to this problem depends on the level of
simplification chosen, not the size of the number factored. In principle, our
results can be extended to factorize any multi-prime integer with minimum
quantum resources.
Avinash Dash Deepankar Sarmah Bikash K. Behera Prasanta K. Panigrahi