Factoring integers with sublinear resources on a superconducting quantum processor

[gyu-don]

一言でいうと

Nビット整数の素因数分解を、O(logN/loglog N)量子ビットでのQAOAで行うアルゴリズムを提案した。また、超伝導型の実機で、10量子ビットを使って、48ビット整数261980999226229を素因数分解した。これは、(D-Waveも含めた)量子コンピュータ実機による素因数分解としては最大のもの。また、この手法は既存の量子アルゴリズムよりも少ない量子ビット数で素因数分解が行える。

このアルゴリズムは、古典コンピュータでの素因数分解アルゴリズムであるSchnorrのアルゴリズムの一部を量子アルゴリズムであるQAOAに置き換えたもの。Schnorrのアルゴリズムは素因数分解問題を格子の最近ベクトル問題(Closest Vector Problem, CVP)に帰着させて、BabaiのアルゴリズムによりCVPを解くが、Babaiのアルゴリズムの中で、サンプリングを行っていた部分をQAOAに置き換えることをこの論文では提案している。また、実機による実験により、ランダムにサンプリングするよりも良い結果が得られることを示している。

論文リンク

https://arxiv.org/abs/2212.12372

著者/所属機関

Bao Yan,1, 2, ∗ Ziqi Tan,3, ∗ Shijie Wei,4, ∗ Haocong Jiang,5 Weilong Wang,1 Hong Wang,1 Lan Luo,1 Qianheng Duan,1
Yiting Liu,1 Wenhao Shi,1 Yangyang Fei,1 Xiangdong Meng,1 Yu Han,1 Zheng Shan,1 Jiachen Chen,3 Xuhao Zhu,3
Chuanyu Zhang,3 Feitong Jin,3 Hekang Li,3 Chao Song,3 Zhen Wang,3, † Zhi Ma,1, ‡ H. Wang,3 and Gui-Lu Long2, 4, 6, 7, §
1State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China
2State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China
3School of Physics, ZJU-Hangzhou Global Scientific and Technological Innovation Center, Interdisciplinary Center for Quantum Information,
and Zhejiang Province Key Laboratory of Quantum Technology and Device, Zhejiang University, Hangzhou 310000, China
4Beijing Academy of Quantum Information Sciences, Beijing 100193, China
5Institute of Information Technology, Information Engineering University, Zhengzhou 450001, China
6Beijing National Research Center for Information Science and Technology
and School of Information Tsinghua University, Beijing 100084, China
7Frontier Science Center for Quantum Information, Beijing 100084, China

投稿日付(yyyy/MM/dd)

2022/12/23