Factorization of large tetra and penta prime numbers on IBM quantum processor

Ritu Dhaulakhandi; Bikash K. Behera; Felix J. Seo

doi:10.1063/5.0194993

journal article Open Access Jun 01, 2024

Factorization of large tetra and penta prime numbers on IBM quantum processor

Ritu Dhaulakhandi

Bikash K. Behera

Felix J. Seo

APL Quantum Vol. 1 No. 2 · AIP Publishing

View at Publisher Save 10.1063/5.0194993

Abstract

The factorization of large digit integers in polynomial time is a challenging computational task to decipher. The development of Shor’s algorithm sparked a new resolution for solving the factorization problem. However, putting Shor’s algorithm into use in real-world situations presents major difficulties. The algorithm largely depends on the availability of large-scale, fault-tolerant quantum computers, which are not available at present. The need for qubit coherence and error correction makes the algorithm susceptible to noise and decoherence, hindering its practical realization. Therefore, exploring alternative quantum factorization algorithms and investing in quantum computing hardware advancements are vital steps toward overcoming these drawbacks and harnessing the full potential of quantum computing for factorization tasks. This article explores an alternative method of converting the factorization problem into an optimization problem using appropriate analytic algebra. The generalized Grover’s protocol is used to increase the amplitude of the necessary states and, in turn, help in the execution of the quantum factorization of tetra and penta primes as a proof of concept for different integers, including 875, 1 269 636 549 803, and 4375, using three and four qubits of IBMQ Perth (a seven-qubit processor). The fidelity of the quantum factorization protocol with the IBMQ Perth qubits was near unity. A generalization of the method is provided at the end for implementing factorization problems in various cases.

Topics

No keywords indexed for this article. Browse by subject →

References

36

[1]

(2014)

[2]

"Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines" Chaos (2017) 10.1063/1.4975761

[3]

"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer" SIAM J. Comput. (1997) 10.1137/s0097539795293172

[4]

"Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance" Nature (2001) 10.1038/414883a

[5]

"Experimental realization of Shor’s quantum factoring algorithm using qubit recycling" Nat. Photonics (2012) 10.1038/nphoton.2012.259

[6]

"Oversimplifying quantum factoring" Nature (2013) 10.1038/nature12290

[7]

N. S. Dattani and N.Bryans, “Quantum factorization of 56153 with only 4 qubits,” arXiv:1411.6758v3 (2014).

[8]

(2015)

[9]

"Quantum adiabatic algorithm for factorization and its experimental implementation" Phys. Rev. Lett. (2008) 10.1103/physrevlett.101.220405

[10]

C. J. C. Burges , “Factoring as optimization,” Technical Report No. MSR-TR-2002-83, 2002.

[11]

"Prime factorization using quantum annealing and computational algebraic geometry" Sci. Rep. (2017) 10.1038/srep43048

[12]

"Factoring with qutrits: Shor’s algorithm on ternary and metaplectic quantum architectures" Phys. Rev. A (2017) 10.1103/physreva.96.012306

[13]

"Research on quantum annealing integer factorization based on different columns" Front. Phys. (2022) 10.3389/fphy.2022.914578

[14]

"Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system" Phys. Rev. Lett. (2012) 10.1103/physrevlett.108.130501

[15]

Z. Li , “High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311,” arXiv:1706.08061 (2017).

[16]

"Experimental adiabatic quantum factorization under ambient conditions based on a solid-state single spin system" Phys. Rev. Lett. (2017) 10.1103/physrevlett.118.130504

[17]

"Prime factorization using quantum variational imaginary time evolution" Sci. Rep. (2021) 10.1038/s41598-021-00339-x

[18]

"Factoring larger integers with fewer qubits via quantum annealing with optimized parameters" Sci. China: Phys., Mech. Astron. (2019) 10.1007/s11433-018-9307-1

[19]

A. Dash , D.Sarmah, B. K.Behera, and P. K.Panigrahi, “Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer,” arXiv:1805.10478 (2018).

[20]

"An exact quantum search algorithm with arbitrary database" Int. J. Theor. Phys. (2014) 10.1007/s10773-014-2055-3

[21]

"Phase matching in Grover’s algorithm" Phys. Lett. A (2007) 10.1016/j.physleta.2007.02.029

[22]

(2008)

[23]

"A method for obtaining digital signatures and public-key cryptosystems" Commun. ACM (1978) 10.1145/359340.359342

[24]

"New directions in cryptography" IEEE Trans. Inf. Theory (1976) 10.1109/tit.1976.1055638

[25]

"Design and implementation of Rivest Shamir Adleman’s (RSA) cryptography algorithm in text file data security" J. Phys.: Conf. Ser. (2020) 10.1088/1742-6596/1641/1/012042

[26]

"RSA public keys with inside structure: Proofs of key generation and identities for web-of-trust" J. Inf. Secur. Appl. (2019) 10.1016/j.jisa.2018.12.006

[27]

"Comment on ‘An enhanced and secured RSA key generation scheme (ESRKGS)’" J. Inf. Secur. Appl. (2016) 10.1016/j.jisa.2016.03.006

[28]

"Quantum cryptography" Rev. Mod. Phys. (2002) 10.1103/revmodphys.74.145

[29]

"Quantum cryptography for internet of things security" J. Electron. Sci. Technol. (2019) 10.11989/jest.1674-862x.90523016

[30]

"Quantum annealing for prime factorization" Sci. Rep. (2018) 10.1038/s41598-018-36058-z

[31]

"Prime factorization algorithm based on parameter optimization of Ising model" Sci. Rep. (2020) 10.1038/s41598-020-62802-5

[32]

See https://en.wikipedia.org/wiki/Quantum_tomography for Wikipedia page link to quantum tomography.

[33]

"Measurement of qubits" Phys. Rev. A (2001) 10.1103/physreva.64.052312

[34]

See https://docs.microsoft.com/en-us/azure/quantum/concepts-pauli-measurements\#multiple-qubit-measurements for Multiple qubit measurements.

[35]

See https://github.com/RituDhaulakhandi/Quantum-Factorization for Github link to supplementary materials.

[36]

"Simulation of electronic structure Hamiltonian using quantum computers" Mol. Phys. (2010) 10.1080/00268976.2011.552441

Cited By

4

FedQCNN: A Privacy‐Preserving Federated Quantum Convolutional Neural Network for Retinal Image Classification

Mahua Nandy Pal, Debashis De · 2025

IET Quantum Communication

Metrics

4

Citations

36

References

Details

Published: Jun 01, 2024
Vol/Issue: 1(2)
License: View

Authors

R

Ritu Dhaulakhandi

Department of Physics, Indian Institute of Science Education and Research 1 , Pune 411008, Maharastra, India

B

Bikash K. Behera

Bikash’s Quantum (OPC) Private Limited 2 , Balindi, Mohanpur 741246, Nadia, West Bengal, India

F

Felix J. Seo

Department of Physics, Hampton University 3 , Hampton, Virginia 23668, USA

Funding

National Aeronautics and Space Administration Award: NNX15AQ03A

Association for Research in Otolaryngology Award: W911NF-15-1-0535

Cite This Article

Ritu Dhaulakhandi, Bikash K. Behera, Felix J. Seo (2024). Factorization of large tetra and penta prime numbers on IBM quantum processor. APL Quantum, 1(2). https://doi.org/10.1063/5.0194993

Factorization of large tetra and penta prime numbers on IBM quantum processor

You May Also Like