Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An exact qubit allocation approach for NISQ architectures

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

The noisy intermediate-scale quantum (NISQ) devices that have just emerged in recent years provide an opportunity for the physical realization of quantum circuits. As the first step of mapping quantum circuits to these devices, qubit allocation imposes a great impact on the number of additional quantum operations required throughout the mapping. The global optimization of qubit allocation is NP-hard, but since many current NISQ devices have very few qubits, it is possible to solve this problem exactly. In this paper, we propose an exact approach for qubit allocation, which takes advantage of the branch and bound algorithm as the basic framework. In order to further prune the considerably huge state space, three techniques have been proposed and integrated into the exact approach, including an optimized lower bound for quadratic assignment problem, prioritization of logical qubits, and branch pruning by structural symmetry of physical qubits. Moreover, based on the multiple optimal solutions obtained by the exact approach, we give an error-aware qubit allocation method. For problems that are too large to be solved by the exact approach, we also give a heuristic qubit allocation approach with polynomial time complexity. Experimental evaluations show that the exact approach proposed in this paper is feasible for the qubit allocation of current NISQ architectures. For all benchmarks considered, this exact approach can find multiple optimal solutions to the qubit allocation problem on IBM Melbourne, a 16-qubit NISQ architecture, in no more than 20 min. It can serve as a evaluation baseline of any heuristic approach. Experimental evaluations also show that the proposed heuristic approach is near-optimal in terms of routing cost. Both the exact approach and the heuristic approach can be integrated into existing quantum circuit mapping approaches.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

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
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

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

References

  1. Abdelbasset, M., Manogaran, G., Rashad, H., Zaied, A.N.H.: A comprehensive review of quadratic assignment problem: variants, hybrids and applications. J. Ambient Intell. Humaniz. Comput. (2018). https://doi.org/10.1007/s12652-018-0917-x

  2. Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boixo, S., Brandao, F.G.S.L., Buell, D.A., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505–510 (2019)

    Article  ADS  Google Scholar 

  3. Ash-Saki, A., Alam, M., Ghosh, S.: Qure: Qubit re-allocation in noisy intermediate-scale quantum computers. In: Proceedings of the 56th Annual Design Automation Conference 2019, pp. 1–6 (2019)

  4. Chiesa, A., Tacchino, F., Grossi, M., Santini, P., Tavernelli, I., Gerace, D., Carretta, S.: Quantum hardware simulating four-dimensional inelastic neutron scattering. Nat. Phys. 15(5), 455–459 (2019)

    Article  Google Scholar 

  5. Ganzhorn, M., Egger, D., Barkoutsos, P., Ollitrault, P., Salis, G., Moll, N., Roth, M., Fuhrer, A., Mueller, P., Woerner, S., et al.: Gate-efficient simulation of molecular eigenstates on a quantum computer. Phys. Rev. Appl. 11(4), 044092 (2019)

    Article  ADS  Google Scholar 

  6. Hahn, P., Grant, T.: Lower bounds for the quadratic assignment problem based upon a dual formulation. Oper. Res. 46(6), 912–922 (1998)

    Article  MathSciNet  Google Scholar 

  7. Havlicek, V., Corcoles, A., Temme, K., Harrow, A.W., Kandala, A., Chow, J.M., Gambetta, J.M.: Supervised learning with quantum-enhanced feature spaces. Nature 567(7747), 209–212 (2019)

    Article  ADS  Google Scholar 

  8. IBM: Defining the future of computing, again. https://www.ibm.com/quantum-computing/technology/systems. Accessed 20 April 2020

  9. IBM: Quantum experience. https://quantum-computing.ibm.com/. Accessed: 20 April 2020

  10. Kissinger, A., De Griend, A.M.: CNOT circuit extraction for topologically-constrained quantum memories. (2019). arXiv:1904.00633

  11. Kole, A., Datta, K., Sengupta, I.: A heuristic for linear nearest neighbor realization of quantum circuits by swap gate insertion using \(n\) -gate lookahead. IEEE J. Emerg. Sel. Topics Circuits Syst. 6(1), 62–72 (2016)

    Article  ADS  Google Scholar 

  12. Kole, A., Datta, K., Sengupta, I.: A new heuristic for n-dimensional nearest neighbor realization of a quantum circuit. IEEE Trans. Comput.-Aided. Des. Integr. Circuits Syst. 37(1), 182–192 (2018)

    Article  Google Scholar 

  13. Lao, L., Manzano, D.M., van Someren, H., Ashraf, I., Almudever, C.G.: Mapping of quantum circuits onto NISQ superconducting processors. (2019). arXiv:1908.04226

  14. Lao, L., Wee, Bv, Ashraf, I., Someren, Jv, Khammassi, N., Bertels, K., Almudever, C.G.: Mapping of lattice surgery-based quantum circuits on surface code architectures. Quantum Sci. Technol. 4(1), 015005 (2018)

    Article  ADS  Google Scholar 

  15. Li, G., Ding, Y., Xie, Y.: Tackling the qubit mapping problem for nisq-era quantum devices. In: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (2019)

  16. Loiola, E.M., De Abreu, N.M.M., Boaventuranetto, P.O., Hahn, P.M., Querido, T.: A survey for the quadratic assignment problem. Eur. J. Oper. Res. 176(2), 657–690 (2007)

    Article  MathSciNet  Google Scholar 

  17. Mautor, T., Roucairol, C.: A new exact algorithm for the solution of quadratic assignment problems. Discrete Appl. Math. 55(3), 281–293 (1994)

    Article  MathSciNet  Google Scholar 

  18. Murali, P., Baker, J.M., Javadi-Abhari, A., Chong, F.T., Martonosi, M.: Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In: Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 1015–1029 (2019)

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

    Article  ADS  Google Scholar 

  20. Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information, 10th edn. Cambridge University Press, Cambridge (2011)

    MATH  Google Scholar 

  21. Nishio, S., Pan, Y., Satoh, T., Amano, H., Meter, R.V.: Extracting success from ibm’s 20-qubit machines using error-aware compilation. ACM J. Emerg. Technol. Comput. Syst. (JETC) 16(3), 1–25 (2020)

    Article  Google Scholar 

  22. Paler, A.: On the influence of initial qubit placement during nisq circuit compilation. Lecture Notes in Computer Science, pp. 207–217 (2019)

  23. Preskill, J.: Quantum computing in the nisq era and beyond. Bull. Am. Phys. Soc. 2, 79–98 (2018)

    Google Scholar 

  24. Siraichi, M.Y., Santos, V.F.D., Collange, S.: Qubit allocation. In: Proceedings of the 2018 International Symposium on Code Generation and Optimization, pp. 113–125 (2018)

  25. Wikipedia: Branch and bound. http://en.wikipedia.org/wiki/Branch_and_bound. Accessed 23 April 2020

  26. Wille, R., Lye, A., Drechsler, R.: Exact reordering of circuit lines for nearest neighbor quantum architectures. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 33(12), 1818–1831 (2014)

    Article  Google Scholar 

  27. Zhou, X., Li, S., Feng, Y.: Quantum circuit transformation based on simulated annealing and heuristic search. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. (2020). https://doi.org/10.1109/TCAD.2020.2969647

  28. Zhu, P.: Resources of exact qubit allocation. https://github.com/joyofly/ExactQubitAllocation. Accessed 23 April 2020

  29. Zhu, P., Guan, Z., Cheng, X.: A dynamic look-ahead heuristic for the qubit mapping problem of nisq computers. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. (2020). https://doi.org/10.1109/TCAD.2020.2970594

  30. Zulehner, A., Paler, A., Wille, R.: An efficient methodology for mapping quantum circuits to the ibm qx architectures. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 38(7), 1226–1236 (2019)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Information Science and Technology, Nantong University, Nantong, 226019, China

    Pengcheng Zhu, Xueyun Cheng & Zhijin Guan

  2. Department of Computer Science and Technology, Suqian College, Suqian, 223800, China

    Pengcheng Zhu

Authors
  1. Pengcheng Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xueyun Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhijin Guan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhijin Guan.

Additional information

Publisher's Note

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

This work was supported by the National Natural Science Foundation of China under Grant 61402244, in part by Jiangsu Province Natural Science Foundation of China under Grant BK20151274, in part by Suqian Science and Technology Foundation under Grant H201721.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhu, P., Cheng, X. & Guan, Z. An exact qubit allocation approach for NISQ architectures. Quantum Inf Process 19, 391 (2020). https://doi.org/10.1007/s11128-020-02901-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-020-02901-4

Keywords

Search

Navigation