Demonstration of Shor’s factoring algorithm for N

Zhengjun Cao, Zhenfu Cao, Lihua Liu

An efficient quantum modular exponentiation method is indispensible for Shor's factoring algorithm. But we find that all descriptions presented by Shor, Nielsen and Chuang, Markov and Saeedi, et al., are flawed. We also remark that some experimental demonstrations of Shor's algorithm are misleading, because they violate the necessary condition that the selected number $q=2^s$, where $s$ is the number of qubits used in the first register, must satisfy $n^2 \leq q < 2n^2$, where $n$ is the large number to be factored.

Unathi Skosana, Mark Tame

We report a proof-of-concept demonstration of a quantum order-finding algorithm for factoring the integer 21. Our demonstration involves the use of a compiled version of the quantum phase estimation routine, and builds upon a previous demonstration. We go beyond this work by using a configuration of approximate Toffoli gates with residual phase shifts, which preserves the functional correctness and allows us to achieve a complete factoring of [Formula: see text]. We implemented the algorithm on IBM quantum processors using only five qubits and successfully verified the presence of entanglement between the control and work register qubits, which is a necessary condition for the algorithm's speedup in general. The techniques we employ may be useful in carrying out Shor's algorithm for larger integers, or other algorithms in systems with a limited number of noisy qubits.

Jonathan C. F. Matthews, Alberto Politi, Jeremy L. O’Brien

We report the realization of a compiled version of Shor’s quantum factoring algorithm on an integrated waveguide chip. This demonstration serves as an illustration to the importance of using integrated optics for quantum optical experiments.

Thomas Lawson