Oral: Realization of quantum algorithms based on Rydberg atom system

In recent years, significant advancements have been made in quantum computing utilizing Rydberg atoms. In the experiment, arbitrary single-qubit gates and (multi-)controlled Z gates can now be realized with gate time around nanosecond level. This heralds a promising future for Rydberg atom-based quantum computing. However, limited attention has been given to the practical realization of algorithms within this system. In this article, we construct specific quantum circuits for NP-complete problems and specially tailor them to the non-decomposable form for Rydberg atom system. We also introduce specialized techniques like the partial parallel method and the controlled addition method to reduce space complexity—a critical issue for many NP-complete problems. To demonstrate theoretical quantum advantage, we optimize both space and time costs, comparing them with their classical counterparts to identify critical thresholds. The results yield applicable quantum circuits with optimized costs, laying the groundwork for practical quantum computing experiments based on Rydberg atoms. Furthermore, the quantum circuits we construct are universal and can be easily adapted for use with other quantum systems.