Quantum algorithms for factorization problem

4^th International Conference on Photonics & Laser Technology

July 28-29, 2016 Berlin, Germany

Xinhua Peng

University of Science and Technology of China, China

Scientific Tracks Abstracts: J Laser Opt Photonics

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.

Biography :

Xinhua Peng received her PhD degree in Atomic and Molecular Physics from Wuhan Institute of Physics and Mathematics, Chinese Academy of Sciences, in July 2003. After that, she arrived at the University of Dortmund, Germany, as an Alexander von Humboldt Fellow. Since 2008, she is Professor at University of Science and Technology of China. She was awarded National Science Fund for Distinguished Young Scholars. She has published more than 50 papers in reputed journals.

Email: rying@ustc.edu.cn