Xinhua Peng
University of Science and Technology of China, China
Title: Quantum algorithms for factorization problem
Biography
Biography: Xinhua Peng
Abstract
Factorization of large numbers is a computationally hard problem on a classical computer: the computational resources required to accomplish this task increase exponentially with the size of the problem. Quantum computer could be much faster than classical ones in solving the factoring problem. Shor's algorithm is the most famous one. There are other methods for this problem, for example, adiabatic quantum algorithm and the Gauss-sum algorithm using properties of Gauss sums. Based on the idea of adiabatic quantum computation, we implemented the factorization of 143 by adiabatic quantum computation using nuclear magnetic resonance techniques, which is, we believe, the largest number factored in quantum-computation realization. On the other hand, relied on the properties of Gauss sums, we propose an efficient and exact quantum algorithm for finding the square-free part of a large integer - a problem for which no efficient classical algorithm exists. This algorithm overcomes the challenge that how to reduce the computational complexity by combining quantum entanglement with Gauss sums, and the introduced new concepts and methods may be applicable to a wider class of problems.