题目：

Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer

作者：Avinash Dash, Deepankar Sarmah, Bikash K. Behera, Prasanta K. Panigrahi
单位：Department of Physical Sciences, Indian Institute of Science Education nd Research Kolkata, Mohanpur, 741246, West Bengal, India

摘要：

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 has 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.

简评：

质因子分解问题及相应的Shor算法是目前为止最有效地验证量子计算机优越性的办法。一方面，Shor算法大幅地减少了了大数分解质因子的计算时间；另一方面，由于质因子分解问题是RSA等现今流行的密钥体系的安全基础，Shor算法的实现便预示着部分经典密码学的应用将被量子的计算能力淘汰。然而，由于量子计算机在技术上难以实现，Shor算法一直以来很难得到有效的验证和运用。比如，几年前杜江峰老师组便利用核磁共振实验平台完成了143=13*11的Shor算法分解。

推荐这篇文章的原因不只是Shor算法的重要性及其在IBM量子处理器上的实现，更在于文章作者对于Shor算法应用的从设计到实现的连贯性。比如，一般来说，Shor算法的应用并非是输入一个大数便可以得到其公因子，而是加速经典寻找公因子算法中的寻找周期的计算过程。因此，一般的对于Shor算法的量子计算实现，严格来说只是实现了分解质因子过程中寻找周期这一子问题。再比如，针对这一子问题，如何设计相应的Hamiltonian（对应于退火量子计算）或者量子电路（对应于门量子计算）也是颇有技巧的。这篇论文至少在这两方面都可以作为一个参考。

总结来说，这篇文章非常有助于学习量子计算的基础问题和理清量子算法实现的思路。

[btn type=”” url=”https://arxiv.org/pdf/1805.10478.pdf”]论文下载[/btn]