[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Qurzon: A Prototype for a Divide and Conquer-Based Quantum Compiler for Distributed Quantum Systems

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

When working with algorithms on quantum devices, quantum memory becomes a crucial bottleneck due to low qubit count in NISQ-era devices. In this context, the concept of ‘divide and compute’, wherein a quantum circuit is broken into several subcircuits and executed separately, while stitching the results of the circuits via classical post-processing, becomes a viable option, especially in NISQ-era devices. This paper introduces Qurzon, a proposed novel quantum compiler that incorporates the marriage of techniques of divide and compute with the state-of-the-art algorithms of optimal qubit placement for executing on real quantum devices. A scheduling algorithm is also introduced within the compiler that can explore the power of distributed quantum computing while paving the way for quantum parallelism for large algorithms. Several benchmark circuits have been executed using the compiler, thereby demonstrating the power of the divide and compute when working with real NISQ-era quantum devices.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Data availability

Not applicable.

Code availability

https://github.com/LegacYFTw/qurzon.

References

  1. Nielsen MA, Chuang IL. Quantum computation and quantum information: 10th anniversary edition. 10th ed. USA: Cambridge University Press; 2011.

    MATH  Google Scholar 

  2. Preskill J. Quantum computing in the nisq era and beyond. Quantum 2, 79 (2018). https://doi.org/10.22331/q-2018-08-06-79

  3. Steane A. Quantum computing. Rep Progress Phys. 1998;61(2):117.

    Article  MathSciNet  Google Scholar 

  4. Williams C.P. Explorations in Quantum Computing. Springer, ??? (2010)

  5. Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S. Quantum machine learning. Nature. 2017;549(7671):195–202.

    Article  Google Scholar 

  6. Schuld M, Sinayskiy I, Petruccione F. An introduction to quantum machine learning. Contemporary Phys. 2015;56(2):172–85.

    Article  Google Scholar 

  7. Cao Y, Romero J, Olson JP, Degroote M, Johnson PD, Kieferová M, Kivlichan ID, Menke T, Peropadre B, Sawaya NP, et al. Quantum chemistry in the age of quantum computing. Chem Rev. 2019;119(19):10856–915.

    Article  Google Scholar 

  8. Dasgupta S, Humble TS. Characterizing the stability of nisq devices. In: 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 419–429 (2020). IEEE

  9. Cowtan A, Dilkes S, Duncan R, Krajenbrink A, Simmons W, Sivarajah S. On the qubit routing problem. arXiv preprint arXiv:1902.08091 (2019)

  10. Ferrari D, Cacciapuoti AS, Amoretti M, Caleffi M. Compiler design for distributed quantum computing. IEEE Trans Quantum Eng. 2021;2:1–20. https://doi.org/10.1109/tqe.2021.3053921.

    Article  Google Scholar 

  11. Ferrari D, Nasturzio S, Amoretti M. A software tool for mapping and executing distributed quantum computations on a network simulator

  12. Cuomo D, Caleffi M, Cacciapuoti AS. Towards a distributed quantum computing ecosystem. IET Quantum Commun. 2020;1(1):3–8. https://doi.org/10.1049/iet-qtc.2020.0002.

    Article  Google Scholar 

  13. Gyongyosi L, Imre S. Distributed quantum computation for near-term quantum environments. In: Quantum Information Science, Sensing, and Computation XIII, vol. 11726, p. 117260 (2021). International Society for Optics and Photonics

  14. Preskill J. Fault-tolerant quantum computation. In: Introduction to Quantum Computation and Information, pp. 213–269. World Scientific, ??? (1998)

  15. Shor PW. Fault-tolerant quantum computation. In: Proceedings of 37th conference on foundations of computer science, pp. 56–65 (1996). IEEE

  16. Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput. 1997;26(5):1484–509. https://doi.org/10.1137/s0097539795293172.

    Article  MathSciNet  MATH  Google Scholar 

  17. Harrow AW, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Phys Rev Lett. 103(15) (2009). https://doi.org/10.1103/physrevlett.103.150502

  18. et. al., X.M.: Observation of time-crystalline eigenstate order on a quantum processor (2021)

  19. Arute F, Arya K, Babbush R, Bacon D, Bardin JC, Barends R, Biswas R, Boixo S, Brandao FG, Buell DA, et al. Quantum supremacy using a programmable superconducting processor. Nature. 2019;574(7779):505–10.

    Article  Google Scholar 

  20. Harrow AW, Montanaro A. Quantum computational supremacy. Nature. 2017;549(7671):203–9.

    Article  Google Scholar 

  21. Bremner MJ, Montanaro A, Shepherd DJ. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum. 2017;1:8.

    Article  Google Scholar 

  22. Yetis H, Karakoes M. Investigation of noise effects for different quantum computing architectures in ibm-q at nisq level. In: 2021 25th International Conference on Information Technology (IT), pp. 1–4 (2021). https://doi.org/10.1109/IT51528.2021.9390130

  23. Experience, IQ. IBM. https://quantum-computing.ibm.com/

  24. Saleem ZH, Tomesh T, Perlin MA, Gokhale P, Suchara M. Quantum divide and conquer for combinatorial optimization and distributed computing (2021)

  25. Cuomo D, Caleffi M, Krsulich K, Tramonto F, Agliardi G, Prati E, Cacciapuoti AS. Optimized compiler for distributed quantum computing. arXiv (2021). arXiv:2112.14139

  26. Preskill, J. Ph219/CS219 Quantum computation 2018-19 (2015)

  27. Tang W, Tomesh T, Suchara M, Larson J, Martonosi M. CutQC: Using small quantum computers for large quantum circuit evaluations. In: Proceedings of the 26th ACM International conference on architectural support for programming languages and operating systems, pp. 473–486 (2021)

  28. Peng T, Harrow AW, Ozols M, Wu X. Simulating large quantum circuits on a small quantum computer. Phys Rev Lett. 2020;125(15): 150504.

    Article  Google Scholar 

  29. Ayral T, Régent F-ML, Saleem Z, Alexeev Y, Suchara M. Quantum divide and compute: Exploring the effect of different noise sources. SN Comput Sci. 2(3) (2021). https://doi.org/10.1007/s42979-021-00508-9

  30. Tyagi R, Gupta SK. A survey on scheduling algorithms for parallel and distributed systems. In: Mishra A, Basu A, Tyagi V, editors. Silicon photonics & high performance computing. Singapore: Springer; 2018. p. 51–64.

  31. Siraichi MY, Santos VFd, Collange S, Pereira FMQ. Qubit allocation. In: Proceedings of the 2018 international symposium on code generation and optimization, pp. 113–125 (2018)

  32. Zulehner A, Paler A, Wille R. An efficient methodology for mapping quantum circuits to the ibm qx architectures. IEEE Trans Comput-Aided Design Integrated Circ Syst. 2018;38(7):1226–36.

    Article  Google Scholar 

  33. Wille R, Burgholzer L, Zulehner A. Mapping quantum circuits to ibm qx architectures using the minimal number of swap and h operations. In: 2019 56th ACM/IEEE Design Automation Conference (DAC), pp. 1–6 (2019). IEEE

  34. Nash B, Gheorghiu V, Mosca M. Quantum circuit optimizations for nisq architectures. Quantum Sci Technol. 2020;5(2): 025010.

    Article  Google Scholar 

  35. Tan B, Cong J. Optimal layout synthesis for quantum computing. In: 2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD), pp. 1–9 (2020). IEEE

  36. Cowtan A, Simmons W, Duncan R. A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz (2020)

  37. Cowtan A, Dilkes S, Duncan R, Simmons W, Sivarajah S. Phase gadget synthesis for shallow circuits. Electron Proc Theoretical Comput Sci. 2020;318:213–28. https://doi.org/10.4204/eptcs.318.13.

    Article  MathSciNet  MATH  Google Scholar 

  38. et. al., M.S.A.: Qiskit: An Open-source Framework for Quantum Computing (2021). https://doi.org/10.5281/zenodo.2573505

  39. Bernstein E, Vazirani U. Quantum complexity theory. SIAM J Comput. 1997;26(5):1411–73. https://doi.org/10.1137/S0097539796300921.

    Article  MathSciNet  MATH  Google Scholar 

  40. Perlin MA, Saleem ZH, Suchara M, Osborn JC. Quantum Circuit Cutting with Maximum Likelihood Tomography (2021)

  41. ...Chen Y, Neill C, Roushan P, Leung N, Fang M, Barends R, Kelly J, Campbell B, Chen Z, Chiaro B, Dunsworth A, Jeffrey E, Megrant A, Mutus JY, O’Malley PJJ, Quintana CM, Sank D, Vainsencher A, Wenner J, White TC, Geller MR, Cleland AN, Martinis JM. Qubit architecture with high coherence and fast tunable coupling. Phys Rev Lett. 2014;113: 220502. https://doi.org/10.1103/PhysRevLett.113.220502.

    Article  Google Scholar 

  42. Yan F, Krantz P, Sung Y, Kjaergaard M, Campbell DL, Orlando TP, Gustavsson S, Oliver WD. Tunable coupling scheme for implementing high-fidelity two-qubit gates. Phys Rev Appl. 2018;10: 054062. https://doi.org/10.1103/PhysRevApplied.10.054062.

    Article  Google Scholar 

  43. Mundada P, Zhang G, Hazard T, Houck A. Suppression of qubit crosstalk in a tunable coupling superconducting circuit. Phys Rev Appl. 2019;12: 054023. https://doi.org/10.1103/PhysRevApplied.12.054023.

    Article  Google Scholar 

  44. Li X, Cai T, Yan H, Wang Z, Pan X, Ma Y, Cai W, Han J, Hua Z, Han X, Wu Y, Zhang H, Wang H, Song Y, Duan L, Sun L. Tunable coupler for realizing a controlled-phase gate with dynamically decoupled regime in a superconducting circuit. Phys Rev Appl. 2020;14: 024070. https://doi.org/10.1103/PhysRevApplied.14.024070.

    Article  Google Scholar 

  45. Han XY, Cai TQ, Li XG, Wu YK, Ma YW, Ma YL, Wang JH, Zhang HY, Song YP, Duan LM. Error analysis in suppression of unwanted qubit interactions for a parametric gate in a tunable superconducting circuit. Phys Rev A. 2020;102: 022619. https://doi.org/10.1103/PhysRevA.102.022619.

    Article  Google Scholar 

Download references

Funding

Not applicable.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Calcutta Institute of Engineering and Management, Maulana Abul Kalam Azad University of Technology, Chandi Ghosh Road, Kolkata, 700040, West Bengal, India

    Turbasu Chatterjee

  2. A.K. Choudhury School of I.T., University of Calcutta, Technology Campus, Kolkata, 700106, West Bengal, India

    Turbasu Chatterjee, Amit Saha & Amlan Chakrabarti

  3. Department of Computer Science, B.B. College, Kazi Nazrul University, G.T. Road, Ushagram, Asansol, 713303, West Bengal, India

    Arnav Das

  4. Department of Chemistry, University of Dhaka, Dhaka, 1000, Bangladesh

    Shah Ishmam Mohtashim

  5. Quantum Computing Lab, Atos, Pune, Maharashtra, India

    Amit Saha

Authors
  1. Turbasu Chatterjee
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arnav Das
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shah Ishmam Mohtashim
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Amit Saha
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Amlan Chakrabarti
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Not applicable.

Corresponding author

Correspondence to Turbasu Chatterjee.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Ethics approval

Not applicable.

Consent to participate

Not applicable.

Consent for publication

Not applicable.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Quantum Computing: Circuits Systems Automation and Applications” guest edited by Himanshu Thapliyal and Travis S. Humble.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chatterjee, T., Das, A., Mohtashim, S.I. et al. Qurzon: A Prototype for a Divide and Conquer-Based Quantum Compiler for Distributed Quantum Systems. SN COMPUT. SCI. 3, 323 (2022). https://doi.org/10.1007/s42979-022-01207-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-022-01207-9

Keywords

Search

Navigation