Top

Quantum Information Processing

Published in:

01-11-2023

An improved circuit for Shor’s factoring algorithm using \(2n+2\) qubits

Authors: Song Xiuli, Wen Liangsen

Published in: Quantum Information Processing | Issue 11/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Due to the existence of decoherence, researchers are limited in controlling large-scale qubits, which also prevents the application of Shor’s factoring algorithm in the case of large-scale qubits for the time being. To reduce the number of qubits required when using Shor’s factoring algorithm, by using borrowed ancilla qubits and reducing the number of gates in the constant addition circuit, a new quantum circuit for Shor’s factoring algorithm is proposed. The designed circuit works on \(2n+2\) qubits, in practice is about 35% and 40% less than the best circuit of Takahashi et al. (Quantum Inf Comput 5(6):440–448, 2005) and Haner et al. (Quantum Inf Comput 17(7 &8):673–684, 2017) in terms of depth and size, respectively. Also, the designed circuit is completely general, and it does not depend on any property of the composite number to be factorized. Finally, we use Python with Qiskit to implement and simulate our circuit.

previous article On reconstruction of states from evolution induced by quantum dynamical semigroups perturbed by covariant measures

next article XIRAC-Q: a near-real-time quantum operating system scheduling structure based on Shannon information theorem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Haner, T., Roetteler, M., Svore, K.M.: Factoring using 2n+2 qubits with Toffoli based modular multiplication. Quantum Inf. Comput. 17(7 &8), 673–684 (2017). https://doi.org/10.26421/QIC17.7-8-7MathSciNetCrossRef

Takahashi, Y., Kunihiro, N.: A quantum circuit for Shors factoring algorithm using 2n+2 qubits. Quantum Inf. Comput. 5(6), 440–448 (2005). https://doi.org/10.26421/QIC5.6-2MathSciNetCrossRefMATH

Liu, J., Wang, H., Ma, Z.: Optimization for Shors integer factorization algorithm circuit. Comput. Sci. (2022). https://doi.org/10.11896/jsjkx.210600149CrossRef

Cuccaro, S.A., Draper, T.G., Moulton, D.P., Kutin, S.A.: A new quantum ripple-carry addition circuit. Quantum Phys. (2004). https://doi.org/10.48550/arXiv.quant-ph/0410184CrossRef

Beauregard, S.: Circuit for Shors algorithm using 2n+3 qubits. Quantum Inf. Comput. 3(2), 175–185 (2003). https://doi.org/10.26421/QIC3.2-9MathSciNetCrossRefMATH

Draper, T.G.: Addition on a quantum computer. arXiv:quant-ph/0008033 (2000). Accessed 21 June 2023

Parker, S., Plenio, M.B.: Efficient factorization with a single pure qubit and \(log\)N mixed qubits. Phys. Rev. Lett. 85(14), 3049–3052 (2000). https://doi.org/10.1103/PhysRevLett.85.3049. arXiv:quant-ph/0001066CrossRefADS

Fu, X., Bao, W., Zhou, C.: Speeding up implementation for Shors factorization quantum algorithm. Chin. Sci. Bull 55(32), 3648–3653 (2010). https://doi.org/10.1007/s11434-010-3039-1CrossRef

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 351(6277), 1068–1070 (2016). https://doi.org/10.1126/science.aad9480MathSciNetCrossRefMATHADS

10.

Kitaev, A.Y.: Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph/9511026 (1995). Accessed 01 June 2023

11.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, 10th anniversary, ed Cambridge University Press, Cambridge; New York (2010)

12.

Cheung, D.: Improved bounds for the approximate QFT. arXiv:quant-ph/0403071 (2004). Accessed 20 April 2023

13.

Coppersmith, D.: An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph/0201067 (2002). Accessed 20 June 2023

14.

Barenco, A., Ekert, A., Suominen, K.-A., Trm, P.: Approximate quantum Fourier transform and decoherence. Phys. Rev. A 54(1), 139–146 (1996). https://doi.org/10.1103/PhysRevA.54.139MathSciNetCrossRefADS

15.

Fowler, A.G., Hollenberg, L.C.L.: Scalability of Shors algorithm with a limited set of rotation gates. Phys. Rev. A 70(3), 032329 (2004). https://doi.org/10.1103/PhysRevA.70.032329MathSciNetCrossRefMATHADS

16.

Nam, Y.S., Blümel, R.: Robustness and performance scaling of a quantum computer with respect to a class of static defects. Phys. Rev. A 88(6), 062310 (2013). https://doi.org/10.1103/PhysRevA.88.062310CrossRefADS

17.

Nam, Y.S., Blümel, R.: Analytical formulas for the performance scaling of quantum processors with a large number of defective gates. Phys. Rev. A 92(4), 042301 (2015). https://doi.org/10.1103/PhysRevA.92.042301CrossRefADS

18.

Maslov, D.: Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. Phys. Rev. A 76(5), 052310 (2007). https://doi.org/10.1103/PhysRevA.76.052310. arXiv:quant-ph/0703211CrossRefADS

19.

Takahashi, Y., Kunihiro, N., Ohta, K.: The quantum Fourier transform on a linear nearest neighbor architecture. Quantum Inf. Comput. 7(4), 383–391 (2007). https://doi.org/10.26421/QIC7.4-7MathSciNetCrossRefMATH

20.

Maslov, D., Nam, Y.: Use of global interactions in efficient quantum circuit constructions. New J. Phys 20(3), 033018 (2018). https://doi.org/10.1088/1367-2630/aaa398CrossRefADS

21.

Nam, Y., Su, Y., Maslov, D.: Approximate quantum Fourier transform with O(n log(n)) T gates. NPJ Quantum Inf 6(1), 26 (2020). https://doi.org/10.1038/s41534-020-0257-5CrossRefADS

22.

Nam, Y.S., Blümel, R.: Scaling laws for shor’s algorithm with a banded quantum Fourier transform. Phys. Rev. A 87, 032333 (2013). https://doi.org/10.1103/PhysRevA.87.032333CrossRefADS

23.

Ruiz-Perez, L., Garcia-Escartin, J.C.: Quantum arithmetic with the Quantum Fourier Transform. Quantum Information Processing 16(6), 152 (2017). https://doi.org/10.1007/s11128-017-1603-1. arXiv:1411.5949 [quant-ph]MathSciNetCrossRefMATHADS

24.

Dobsicek, M., Johansson, G., Shumeiko, V.S., Wendin, G.: Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark. Phys. Rev. A 76(3), 030306 (2007). https://doi.org/10.1103/PhysRevA.76.030306. arXiv:quant-ph/0610214CrossRefADS

Title: An improved circuit for Shor’s factoring algorithm using qubits
Authors: Song Xiuli
Wen Liangsen
Publication date: 01-11-2023
Publisher: Springer US
Published in: Quantum Information Processing / Issue 11/2023
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-023-04159-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 11/2023

High-speed train timetable optimization based on space–time network model and quantum simulator

Optimizing measurements sequences for quantum state verification

An orderly quantum multi-signature based on orthogonal product states for the multi-party transaction blockchain

Relaxation dynamics of an unlike spin pair system

New quantum surface codes from semi-regular tessellations

Efficient algorithm for full-state quantum circuit simulation with DD compression while maintaining accuracy