Quantum Information & Computation
Volume 25, Issue 5
RESEARCH ARTICLE Open access

Experimental Factoring Integers Using Fixed-Point-QAOA with a Trapped-Ion Quantum Processor

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

Author affiliations
  • Ilia V. Zalivako1
  • Andrey Yu. Chernyavskiy2
  • Anastasiia S. Nikolaeva3
  • Alexander S. Borisenko1
  • Nikita V. Semenin1
  • Kristina P. Galstyan1
  • Andrey E. Korolkov1
  • Sergey V. Grebnev2
  • Evgeniy O. Kiktenko4
  • Ksenia Yu. Khabarova1
  • Aleksey K. Fedorov3
  • Ilya A. Semerikov1
  • Nikolay N. Kolachevsky1
  1. P.N. Lebedev Physical Institute of the Russian Academy of Sciences, Moscow, Russia; Russian Quantum Center, Skolkovo, Moscow, Russia
  2. Russian Quantum Center, Skolkovo, Moscow, Russia
  3. P.N. Lebedev Physical Institute of the Russian Academy of Sciences, Moscow, Russia; Russian Quantum Center, Skolkovo, Moscow, Russia; Laboratory of Quantum Information Technologies, National University of Science and Technology “MISIS”, Moscow, Russia
  4. Russian Quantum Center, Skolkovo, Moscow, Russia; Laboratory of Quantum Information Technologies, National University of Science and Technology “MISIS”, Moscow, Russia

pp. 369-384 · 10.2478/qic-2025-0021

Read PDF View on Reference Global
On this page

Abstract

Factoring integers is considered as a computationally hard problem for classical methods, whereas there exists polynomial-time Shor’s quantum algorithm for solving this task. However, requirements for running Shor’s algorithm for realistic tasks, which are beyond the capabilities of existing and upcoming generations of quantum computing devices, motivate to search for alternative approaches. In this work, we experimentally demonstrate factoring of the integer with a trapped ion quantum processor using the Schnorr approach and a modified version of the quantum approximate optimization algorithm (QAOA). The key difference of our approach in comparison with the recently proposed QAOA-based factoring method is the use of the fixed-point feature, which relies on the use of universal parameters. We present experimental results on factoring 1591 = 37 × 43 using 6 qubits as well as simulation results for 74425657 = 9521 × 7817 with 10 qubits and 35183361263263 = 4194191 × 8388593 with 15 qubits. Although we present all the necessary details for reproducing our results and analysis of the performance of the factoring method, the scalability of this approach in both the classical and quantum domains still requires further studies.
Open accessCC BY-NC-ND 4.0

Keywords

  • Schnorr’s algorithm
  • fixed-point QAOA
  • trapped-ion processor

Suggested citation

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 (2025). Experimental Factoring Integers Using Fixed-Point-QAOA with a Trapped-Ion Quantum Processor. Quantum Information & Computation, 25(5), 369-384. https://doi.org/10.2478/qic-2025-0021

Download BibTeX

References (59)

  1. 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 700DOI: 10.1109/SFCS.1994.365700Google Scholar
  2. 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/S0036144598347011DOI: 10.1137/S0036144598347011Google Scholar
  3. 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.359342DOI: 10.1145/359340.359342Google Scholar
  4. Bernstein, D. J.; Lange, T. Post-quantum cryptography. Nature 2017, 549, 188–194. https://doi.org/10.1038/nature23461DOI: 10.1038/nature23461Google Scholar
  5. 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.DOI: 10.1140/epjqt/s40507-021-00104-zGoogle Scholar
  6. 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/nphys2385DOI: 10.1038/nphys2385Google Scholar
  7. 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.aad9480DOI: 10.1126/science.aad9480Google Scholar
  8. 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.250504DOI: 10.1103/PhysRevLett.99.250504Google Scholar
  9. 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.250505DOI: 10.1103/PhysRevLett.99.250505Google Scholar
  10. 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.259DOI: 10.1038/nphoton.2012.259Google Scholar
  11. 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-433DOI: 10.22331/q-2021-04-15-433Google Scholar
  12. 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.15917Google Scholar
  13. Coppersmith, D. An approximate Fourier transform useful in quantum factoring. arXiv preprint 2002, arXiv:quant-ph/0201067. https://arxiv.org/abs/quant-ph/0201067Google Scholar
  14. 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.012306DOI: 10.1103/PhysRevA.96.012306Google Scholar
  15. Regev, O. An efficient quantum factoring algorithm. arXiv preprint 2024, arXiv:2308.06572. https://arxiv.org/abs/2308.06572Google Scholar
  16. 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.DOI: 10.1007/978-3-030-14082-3_7Google Scholar
  17. 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-1DOI: 10.1007/s11433-018-9307-1Google Scholar
  18. 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-5DOI: 10.1038/s41598-020-62802-5Google Scholar
  19. 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-zDOI: 10.1038/s41534-021-00478-zGoogle Scholar
  20. 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.DOI: 10.1103/PhysRevA.111.042413Google Scholar
  21. 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.12372Google Scholar
  22. Schnorr, C.P. Fast factoring integers by SVP algorithms, corrected. Cryptology ePrint Archive 2021, Paper 2021/933. https://eprint.iacr.org/2021/933Google Scholar
  23. Farhi, E.; Goldstone, J.; Gutmann, S. A quantum approximate optimization algorithm. arXiv 2014, arXiv:1411.4028. https://arxiv.org/abs/1411.4028Google Scholar
  24. Farhi, E.; Harrow, A.W. Quantum supremacy through the quantum approximate optimization algorithm. arXiv 2019, arXiv:1602.07674. https://arxiv.org/abs/1602.07674Google Scholar
  25. 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.2006373117DOI: 10.1073/pnas.2006373117Google Scholar
  26. 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-yDOI: 10.1038/s41567-020-01105-yGoogle Scholar
  27. 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 15004DOI: 10.1103/RevModPhys.94.015004Google Scholar
  28. 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-9DOI: 10.1038/s42254-021-00348-9Google Scholar
  29. 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.3336989DOI: 10.1109/ACCESS.2023.3336989Google Scholar
  30. Khattar, T.; Yosri, N. A comment on ‘‘Factoring integers with sublinear resources on a superconducting quantum processor”. arXiv 2023, arXiv:2307.09651.Google Scholar
  31. Hegade, N.N.; Solano, E. Digitized-counterdiabatic quantum factorization. arXiv 2023, arXiv:2301.11005.DOI: 10.1103/PhysRevResearch.4.L042030Google Scholar
  32. Chernyavskiy, A.; Bantysh, B. A method to compute QAOA fixed angles. Russian Microelectronics 2023, 52, S352-S356.DOI: 10.1134/S1063739723600577Google Scholar
  33. 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.Google Scholar
  34. Yan, S. Y. Cryptanalytic attacks on RSA. Springer New York, NY 2008. https://doi.org/10.1007/978-0-387-48 742-7Google Scholar
  35. Babai, L. On Lovász’s lattice reduction and the nearest lattice point problem. Combinatorica 1986, 6, 1-13.DOI: 10.1007/BF02579403Google Scholar
  36. Lenstra, A. K.; Lenstra, H. W.; Lovász, L. Factoring polynomials with rational coefficients. Mathematische Annalen 1982, 261, 515–534.DOI: 10.1007/BF01457454Google Scholar
  37. Guerreschi, G. G.; Matsuura, A. Y. QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. Scientific Reports 2019, 9, 6903.DOI: 10.1038/s41598-019-43176-9Google Scholar
  38. 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.DOI: 10.1103/PhysRevX.10.021067Google Scholar
  39. 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.DOI: 10.1016/j.cam.2021.113388Google Scholar
  40. 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.DOI: 10.1109/QCE52317.2021.00034Google Scholar
  41. Wurtz, J.; Lykov, D. The fixed angle conjecture for QAOA on regular MaxCut graphs. arXiv 2021, arXiv:2107.00677.Google Scholar
  42. Chernyavskiy, A.Y. Calculation of quantum discord and entanglement measures using the random mutations optimization algorithm. arXiv 2013, arXiv:1304.3703.Google Scholar
  43. Bantysh, B.; Bogdanov, Y.I. Quantum tomography of noisy ion-based qudits. Laser Physics Letters 2020, 18, 015203.DOI: 10.1088/1612-202X/abca44Google Scholar
  44. 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/quantum7020019DOI: 10.3390/quantum7020019Google Scholar
  45. 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.DOI: 10.1103/PhysRevA.96.022330Google Scholar
  46. 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/nature01494DOI: 10.1038/nature01494Google Scholar
  47. 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.1835DOI: 10.1103/PhysRevLett.82.1835Google Scholar
  48. 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.1971DOI: 10.1103/PhysRevLett.82.1971Google Scholar
  49. 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.022311DOI: 10.1103/PhysRevA.62.022311Google Scholar
  50. 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.DOI: 10.1103/PhysRevLett.112.190502Google Scholar
  51. 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.DOI: 10.1134/S0021364021200108Google Scholar
  52. Magesan, E.; Gambetta, J.M.; Emerson, J. Characterizing quantum gates via randomized benchmarking. Physical Review A 2012, 85, 042311.DOI: 10.1103/PhysRevA.85.042311Google Scholar
  53. 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/nphys961DOI: 10.1038/nphys961Google Scholar
  54. Brown, K.R.; Harrow, A.W.; Chuang, I.L. Arbitrarily accurate composite pulse sequences. Physical Review A 2004, 70, 052318.DOI: 10.1103/PhysRevA.70.052318Google Scholar
  55. 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.DOI: 10.3367/UFNe.2024.12.039884Google Scholar
  56. Aboumrad, W.; Widdows, D.; Kaushik, A. Quantum and classical combinatorial optimizations applied to latticebased factorization. arXiv 2023, arXiv:2308.07804.Google Scholar
  57. Luan, L.; Gu, C.; Zheng, Y.; Shi, Y. Lattice enumeration with discrete pruning: Improvements, cost estimation and optimal parameters. Mathematics 2023, 11, 766.DOI: 10.3390/math11030766Google Scholar
  58. 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.DOI: 10.1126/sciadv.adm6761Google Scholar
  59. 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.08403DOI: 10.1088/2058-9565/ae4cc6Google Scholar