Experimental Factoring Integers Using Fixed-Point-QAOA with a Trapped-Ion Quantum Processor
References
- Shor, P. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science 1994, 124–134. https://doi.org/10.1109/SFCS.1994.365 700
- Shor, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review 1999, 41, 303–332. https://doi.org/10.1137/S0036144598347011
- Rivest, R. L.; Shamir, A.; Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 1978, 21, 120–126. https://doi.org/10.1145/359340.359342
- Bernstein, D. J.; Lange, T. Post-quantum cryptography. Nature 2017, 549, 188–194. https://doi.org/10.1038/nature23461
- Yunakovsky, S. E.; Kot, M.; Pozhar, N.; Nabokov, D.; Kudinov, M.; Guglya, A.; Kiktenko, E. O.; Kolycheva, E.; Borisov, A.; Fedorov, A. K. Towards security recommendations for public-key infrastructures for production environments in the post-quantum era. EPJ Quantum Technology 2021, 8, 14. https://doi.org/10.1140/epjqt/s4 0507–021-00104-z6.
- Lucero, E.; Barends, R.; Chen, Y.; Kelly, J.; Mariantoni, M.; Megrant, A.; O’Malley, P.; Sank, D.; Vainsencher, A.; Wenner, J.; White, T.; Yin, Y.; Cleland, A. N.; Martinis, J. M. Computing prime factors with a Josephson phase qubit quantum processor. Nature Physics 2012, 8, 719–723. https://doi.org/10.1038/nphys2385
- Monz, T.; Nigg, D.; Martinez, E. A.; Brandl, M. F.; Schindler, P.; Rines, R.; Wang, S. X.; Chuang, I. L.; Blatt, R. Realization of a scalable Shor algorithm. Science 2016, 351, 1068. https://doi.org/10.1126/science.aad9480
- Lu, C.-Y.; Browne, D. E.; Yang, T.; Pan, J.-W. Demonstration of a compiled version of Shor’s quantum factoring algorithm using photonic qubits. Physical Review Letters 2007, 99, 250504. https://doi.org/10.1103/PhysRevLett.99.250504
- Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A.; White, A. G. Experimental demonstration of a compiled version of Shor’s algorithm with quantum entanglement. Physical Review Letters 2007, 99, 250505. https://doi.org/10.1103/PhysRevLett.99.250505
- Martín-López, E.; Laing, A.; Lawson, T.; Alvarez, R.; Zhou, X.-Q.; O’Brien, J. L. Experimental realization of Shor’s quantum factoring algorithm using qubit recycling. Nature Photonics 2012, 6, 773. https://doi.org/10.1 038/nphoton.2012.259
- Gidney, C.; Ekera, M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 2021, 5, 433. https://doi.org/10.22331/q-2021-04-15-433
- Gidney, C. How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv preprint 2025, arXiv:2505.15917. https://arxiv.org/abs/2505.15917
- Coppersmith, D. An approximate Fourier transform useful in quantum factoring. arXiv preprint 2002, arXiv:quant-ph/0201067. https://arxiv.org/abs/quant-ph/0201067
- Bocharov, A.; Roetteler, M.; Svore, K. M. Factoring with qutrits: Shor’s algorithm on ternary and metaplectic quantum architectures. Physical Review A 2017, 96, 012306. https://doi.org/10.1103/PhysRevA.96.012306
- Regev, O. An efficient quantum factoring algorithm. arXiv preprint 2024, arXiv:2308.06572. https://arxiv.org/abs/2308.06572
- Anschuetz, E.; Olson, J.; Aspuru-Guzik, A.; Cao, Y. Variational quantum factoring. In Quantum Technology and Optimization Problems, Feld, S.; Linnhoff-Popien, C. (Eds.), Springer International Publishing: Cham, 2019; pp. 74–85.
- Peng, W.; Wang, B.; Hu, F.; Wang, Y.; Fang, X.; Chen, X.; Wang, C. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters. Science China Physics, Mechanics & Astronomy 2019, 62, 60311. https://doi.org/10.1007/s11433-018-9307-1
- Wang, B.; Hu, F.; Yao, H.; Wang, C. Prime factorization algorithm based on parameter optimization of Ising model. Scientific Reports 2020, 10, 7106. https://doi.org/10.1038/s41598-020-62802-5
- Karamlou, A.H.; Simon, W.A.; Katabarwa, A.; Scholten, T.L.; Peropadre, B.; Cao, Y. Analyzing the performance of variational quantum factoring on a superconducting quantum processor. npj Quantum Information 2021, 7, 156. https://doi.org/10.1038/s41534-021-00478-z
- Sobhani, M.; Chai, Y.; Hartung, T.; Jansen, K. Variational quantum eigensolver approach to prime factorization on IBM’s noisy intermediate scale quantum computer. Physical Review A 2025, 111, 042413.
- Yan, B.; Tan, Z.; Wei, S.; Jiang, H.; Wang, W.; Wang, H.; Luo, L.; Duan, Q.; Liu, Y.; Shi, W.; et al. Factoring integers with sublinear resources on a superconducting quantum processor. arXiv 2022, arXiv:2212.12372. https://arxiv.org/abs/2212.12372
- Schnorr, C.P. Fast factoring integers by SVP algorithms, corrected. Cryptology ePrint Archive 2021, Paper 2021/933. https://eprint.iacr.org/2021/933
- Farhi, E.; Goldstone, J.; Gutmann, S. A quantum approximate optimization algorithm. arXiv 2014, arXiv:1411.4028. https://arxiv.org/abs/1411.4028
- Farhi, E.; Harrow, A.W. Quantum supremacy through the quantum approximate optimization algorithm. arXiv 2019, arXiv:1602.07674. https://arxiv.org/abs/1602.07674
- Pagano, G.; Bapat, A.; Becker, P.; Collins, K.S.; De, A.; Hess, P.W.; Kaplan, H.B.; Kyprianidis, A.; Tan, W. L.; Baldwin, C.; et al. Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator. Proceedings of the National Academy of Sciences of the United States of America 2020, 117, 25396. https://doi.org/10.1073/pnas.2006373117
- Harrigan, M. P.; Sung, K. J.; Neeley, M.; Satzinger, K. J.; Arute, F.; Arya, K.; Atalaya, J.; Bardin, J. C.; Barends, R.; Boixo, S.; et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics 2021, 17, 332.https://doi.org/10.1038/s41567-020-01105-y
- Bharti, K.; Cervera-Lierta, A.; Kyaw, TH.; Haug, T; Alperin-Lea, S.; Anand, A.; Degroote, M.; Heimonen, H.; Kottmann, J.S.; Menke, T.; Mok, W.-K.; Sim, S.; Kwek, L.-C.; Aspuru-Guzik, A. Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics 2022, 94, 015004. https://doi.org/10.1103/RevModPhys.94.0 15004
- Cerezo, M.; Arrasmith, A.; Babbush, R.; Benjamin, S.C.; Endo, S.; Fujii, K.; McClean, J.R.; Mitarai, K.; Yuan, X.; Cincio, L.; Coles, PJ. Variational quantum algorithms. Nature Reviews Physics 2021, 3, 625. https://doi.org/10.1038/s42254-021-00348-9
- Grebnev, S.V.; Gavreev, M.A.; Kiktenko, E.O.; Guglya, A.P.; Efimov, A.R.; Fedorov, A.K. Pitfalls of the sublinear QAOA-based factorization algorithm. IEEE Access 2023, 11, 134760. https://doi.org/10.1109/ACCESS. 2023.3336989
- Khattar, T.; Yosri, N. A comment on ‘‘Factoring integers with sublinear resources on a superconducting quantum processor”. arXiv 2023, arXiv:2307.09651.
- Hegade, N.N.; Solano, E. Digitized-counterdiabatic quantum factorization. arXiv 2023, arXiv:2301.11005.
- Chernyavskiy, A.; Bantysh, B. A method to compute QAOA fixed angles. Russian Microelectronics 2023, 52, S352-S356.
- Brandao, F.G.; Broughton, M.; Farhi, E.; Gutmann, S.; Neven, H. For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances. arXiv 2018, arXiv:1812.04170.
- Yan, S. Y. Cryptanalytic attacks on RSA. Springer New York, NY 2008. https://doi.org/10.1007/978-0-387-48 742-7
- Babai, L. On Lovász’s lattice reduction and the nearest lattice point problem. Combinatorica 1986, 6, 1-13.
- Lenstra, A. K.; Lenstra, H. W.; Lovász, L. Factoring polynomials with rational coefficients. Mathematische Annalen 1982, 261, 515–534.
- Guerreschi, G. G.; Matsuura, A. Y. QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. Scientific Reports 2019, 9, 6903.
- Zhou, L.; Wang, S.-T.; Choi, S.; Pichler, H.; Lukin, M. D. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X 2020, 10, 021067.
- Fernández-Pendás, M.; Combarro, E.F.; Vallecorsa, S.; Ranilla, J.; Rúa, I.F. A study of the performance of classical minimizers in the quantum approximate optimization algorithm. Journal of Computational and Applied Mathematics 2022, 404, 113388.
- Galda, A.; Liu, X.; Lykov, D.; Alexeev, Y.; Safro, I. Transferability of optimal QAOA parameters between random graphs. In Proceedings IEEE International Conference on Quantum Computing and Engineering (QCE), IEEE: 2021; pp. 171–180.
- Wurtz, J.; Lykov, D. The fixed angle conjecture for QAOA on regular MaxCut graphs. arXiv 2021, arXiv:2107.00677.
- Chernyavskiy, A.Y. Calculation of quantum discord and entanglement measures using the random mutations optimization algorithm. arXiv 2013, arXiv:1304.3703.
- Bantysh, B.; Bogdanov, Y.I. Quantum tomography of noisy ion-based qudits. Laser Physics Letters 2020, 18, 015203.
- Zalivako, I.V.; Nikolaeva, A.S.; Borisenko, A.S.; Korolkov, A.E.; Sidorov, P.L.; Galstyan, K.P.; Semenin, N.V.; Smirnov, V.N.; Aksenov, M.A.; Makushin, K.M.; Kiktenko, E.O.; Fedorov, A.K.; Semerikov, I.A.; Khabarova, K. Y.; Kolachevsky, N.N. Towards a multiqudit quantum processor based on a 171Yb+ ion string: Realizing basic quantum algorithms. Quantum Reports 2025, 7, 19. https://doi.org/10.3390/quantum7020019
- McKay, D.C.; Wood, C.J.; Sheldon, S.; Chow, J.M.; Gambetta, J.M.; Efficient Z gates for quantum computing. Physical Review A 2017, 96, 022330.
- Schmidt-Kaler, F.; Häffner, H.; Riebe, M.; Gulde, S.; Lancaster, G.P.T.; Deuschle, T.; Becher, C.; Roos, C.F.; Eschner, J.; Blatt, R. Realization of the Cirac–Zoller controlled-NOT quantum gate. Nature 2003, 422, 408. https://doi.org/10.1038/nature01494
- Mølmer, K.; Sørensen, A. Multiparticle entanglement of hot trapped ions. Physical Review Letters 1999, 82, 1835. https://doi.org/10.1103/PhysRevLett.82.1835
- Sørensen, A.; Mølmer, K. Quantum computation with ions in thermal motion. Physical Review Letters 1999, 82, 1971. https://doi.org/10.1103/PhysRevLett.82.1971
- Sørensen, A.; Mølmer, K. Entanglement and quantum computation with ions in thermal motion. Physical Review A 2000, 62, 022311. https://doi.org/10.1103/PhysRevA.62.022311
- Choi, T.; Debnath, S.; Manning, T.; Figgatt, C.; Gong, Z.X.; Duan, L.M.; Monroe, C. Optimal quantum control of multimode couplings between trapped ion qubits for scalable entanglement. Physical Review Letters 2014, 112, 190502.
- Semenin, N.V.; Borisenko, A.S.; Zalivako, I.V.; Semerikov, I.A.; Khabarova, K.Y.; Kolachevsky, N.N. Optimization of the readout fidelity of the quantum state of an optical qubit in the 171 Yb+ ion. JETP Letters 2021, 114, 486.
- Magesan, E.; Gambetta, J.M.; Emerson, J. Characterizing quantum gates via randomized benchmarking. Physical Review A 2012, 85, 042311.
- Benhelm, J.; Kirchmair, G.; Roos, C.F.; Blatt, R. Towards fault-tolerant quantum computing with trapped ions. Nature Physics 2008, 4, 463–466. https://doi.org/10.1038/nphys961
- Brown, K.R.; Harrow, A.W.; Chuang, I.L. Arbitrarily accurate composite pulse sequences. Physical Review A 2004, 70, 052318.
- Zalivako, I.V.; Semenin, N.V.; Zhadnov, N.O.; Galstyan, K.P.; Kamenskikh, P.A.; Smirnov, V.N.; Evgenyevich, K. A.; Leonidovich, S.P.; Borisenko, A.S.; Anosov, Y.P. Quantum computing with trapped ions: principles, achievements, and prospects. Physics-Uspekhi 2025, 68.
- Aboumrad, W.; Widdows, D.; Kaushik, A. Quantum and classical combinatorial optimizations applied to latticebased factorization. arXiv 2023, arXiv:2308.07804.
- Luan, L.; Gu, C.; Zheng, Y.; Shi, Y. Lattice enumeration with discrete pruning: Improvements, cost estimation and optimal parameters. Mathematics 2023, 11, 766.
- Shaydulin, R.; Li, C.; Chakrabarti, S.; DeCross, M.; Herman, D.; Kumar, N.; Larson, J.; Lykov, D.; Minssen, P.; Sun, Y.; et al. Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem. Science Advances 2024, 10, eadm6761.
- Priestley, B.; Wallden, P. A practically scalable approach to the closest vector problem for sieving via QAOA with fixed angles. arXiv 2025, arXiv:2503.08403. https://arxiv.org/abs/2503.08403
Language: English
Page range: 369 - 384
Submitted on: Mar 28, 2025
Accepted on: Jul 29, 2025
Published on: Dec 31, 2025
Published by: Cerebration Science Publishing Co., Limited
In partnership with: Paradigm Publishing Services
Publication frequency: 1 issue per year
Related subjects:
© 2025 Ilia V. Zalivako, Andrey Yu. Chernyavskiy, Anastasiia S. Nikolaeva, Alexander S. Borisenko, Nikita V. Semenin, Kristina P. Galstyan, Andrey E. Korolkov, Sergey V. Grebnev, Evgeniy O. Kiktenko, Ksenia Yu. Khabarova, Aleksey K. Fedorov, Ilya A. Semerikov, Nikolay N. Kolachevsky, published by Cerebration Science Publishing Co., Limited
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.