[go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Synthesis of quantum circuits for linear nearest neighbor architectures

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

While a couple of impressive quantum technologies have been proposed, they have several intrinsic limitations which must be considered by circuit designers to produce realizable circuits. Limited interaction distance between gate qubits is one of the most common limitations. In this paper, we suggest extensions of the existing synthesis flow aimed to realize circuits for quantum architectures with linear nearest neighbor interaction. To this end, a template matching optimization, an exact synthesis approach, and two reordering strategies are introduced. The proposed methods are combined as an integrated synthesis flow. Experiments show that by using the suggested flow, quantum cost can be improved by more than 50% on average.

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

Similar content being viewed by others

Explore related subjects

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

References

  1. Wille, R., Saeedi, M., Drechsler, R.: Synthesis of reversible functions beyond gate count and quantum cost. In: International Workshop on Logic Synthesis, pp. 43–49 (2009)

  2. Nielsen M., Chuang I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)

    MATH  Google Scholar 

  3. Mosca, M.: Quantum algorithms. Springer Encyclopedia of Complexity and Systems Science (to appear) (2008)

  4. Meter R.V., Oskin M.: Architectural implications of quantum computing technologies. J. Emerg. Technol. Comput. Syst. 2(1), 31–63 (2006)

    Article  Google Scholar 

  5. Ross M., Oskin M.: Quantum computing. Commun. ACM 51(7), 12–13 (2008)

    Article  Google Scholar 

  6. Knill E., Laflamme R., Milburn G.J.: A scheme for efficient quantum computation with linear optics. Nature 409, 46–52 (2001)

    Article  PubMed  CAS  ADS  Google Scholar 

  7. Fowler A.G., Devitt S.J., Hollenberg L.C.L.: Implementation of shor’s algorithm on a linear nearest neighbour qubit array. Quantum Information and Computation 4, 237–245 (2004)

    MATH  MathSciNet  Google Scholar 

  8. Häffner H., Hänsel W., Roos C.F., Benhelm J., Chek al kar D., Chwalla M., Körber T., Rapol U.D., Riebe M., Schmidt P.O., Becher C., Gühne O., Dür W., Blatt R.: Scalable multiparticle entanglement of trapped ions. Nature 438, 643–646 (2005)

    Article  PubMed  ADS  CAS  Google Scholar 

  9. Laforest M., Simon D., Boileau J.-C., Baugh J., Ditty M., Laflamme R.: Using error correction to determine the noise model. Phys. Rev. A 75, 133–137 (2007)

    Article  CAS  Google Scholar 

  10. Kane B.: A silicon-based nuclear spin quantum computer. Nature 393, 133–137 (1998)

    Article  CAS  ADS  Google Scholar 

  11. Maslov, D.: Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. Phys. Rev. A 76 (2007)

  12. Takahashi Y., Kunihiro N., Ohta K.: The quantum fourier transform on a linear nearest neighbor architecture. Quantum Information and Computation 7, 383–391 (2007)

    MATH  MathSciNet  Google Scholar 

  13. Kutin, S.A.: Shor’s algorithm on a nearest-neighbor machine. Asian Conference on Quantum Information Science (2007)

  14. Choi, B.-S., Van Meter, R.: Effects of Interaction Distance on Quantum Addition Circuits. ArXiv e-prints (September 2008)

  15. Fowler A.G., Hill C.D., Hollenberg L.C.L.: Quantum error correction on linear nearest neighbor qubit arrays. Phys. Rev. A 69, 042314.1–042314.4 (2004)

    Article  ADS  CAS  Google Scholar 

  16. Möttönen M., Vartiainen J.J.: Decompositions of General Quantum Gates. Chapter 7 in Trends in Quantum Computing Research. NOVA Publishers, New York (2006)

    Google Scholar 

  17. Shende V.V., Bullock S.S., Markov I.L.: Synthesis of quantum-logic circuits. IEEE Trans. on CAD 25(6), 1000–1010 (2006)

    Google Scholar 

  18. Cheung, D., Maslov, D., Severini, S.: Translation techniques between quantum circuit architectures. Workshop on Quantum Information Processing (December 2007)

  19. Chakrabarti A., Sur-Kolay S.: Nearest neighbour based synthesis of quantum boolean circuits. Eng. Lett. 15, 356–361 (2007)

    Google Scholar 

  20. Khan M.H.A.: Cost reduction in nearest neighbour based synthesis of quantum boolean circuits. Eng. Lett. 16, 1–5 (2008)

    ADS  Google Scholar 

  21. Hirata, Y., Nakanishi, M., Yamashita, S., Nakashima, Y.: An efficient method to convert arbitrary quantum circuits to ones on a linear nearest neighbor architecture. In: International Conference on Quantum, Nano and Micro Technologies, pp. 26–33 (2009)

  22. Lee, S., Lee, S.J., Kim, T., Lee, J.S., Biamonte, J., Perkowski, M.: The cost of quantum gate primitives. J. Multiple Value Logic Soft Comput. 12(5–6) (2006)

    Google Scholar 

  23. Barenco A., Bennett C., Cleve R., DiVincenzo D., Margolus N., Shor P., Sleator T., Smolin J., Weinfurter H.: Elementary gates for quantum computation. APS Phys. Rev. A 52, 3457–3467 (1995)

    CAS  ADS  Google Scholar 

  24. Maslov D., Dueck G.W., Miller D.M., Negrevergne C.: Quantum circuit simplification and level compaction. IEEE Trans. on CAD 27(3), 436–444 (2008)

    Google Scholar 

  25. Hung W.N.N., Song X., Yang G., Yang J., Perkowski M.: Optimal synthesis of multiple output boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE Trans. on CAD 25(9), 1652–1663 (2006)

    Google Scholar 

  26. Große, D., Wille, R., Dueck, G.W., Drechsler, R.: Exact synthesis of elementary quantum gate circuits for reversible functions with don’t cares. International Symposium on Multiple Valued Logic, pp. 214–219 (2008)

  27. Maslov D., Dueck G.W., Michael Miller D.: Toffoli network synthesis with templates. IEEE Trans. on CAD 24(6), 807–817 (2005)

    Google Scholar 

  28. Maslov D., Dueck G.W., Miller D.M.: Techniques for the synthesis of reversible toffoli networks. ACM Trans. Des. Autom. Electron. Syst. 12(4), 42 (2007)

    Article  Google Scholar 

  29. Saeedi, M., Sedighi, M., Saheb Zamani, M.: A novel synthesis algorithm for reversible circuits. IEEE/ACM International Conference on Computer-aided design, pp. 65–68 (2007)

  30. Gupta P., Agrawal A., Jha N.K.: An algorithm for synthesis of reversible logic circuits. IEEE Trans. on CAD 25(11), 2317–2330 (2006)

    Google Scholar 

  31. Große D., Wille R., Dueck G.W., Drechsler R.: Exact multiple control toffoli network synthesis with SAT techniques. IEEE Trans. on CAD 28(5), 703–715 (2009)

    Google Scholar 

  32. Wille, R., Drechsler, R.: BDD-based synthesis of reversible logic for large functions. In: DAC ’09: Proceedings of the 46th annual Design Automation Conference, pp. 270–275 (2009)

  33. Saeedi M., Sedighi M., Zamani M. Saheb: A library-based synthesis methodology for reversible logic. Elsevier Microelectron. J. 41(4), 185–194 (2010)

    Google Scholar 

  34. Saeedi, M., Zamani M., Saheb, Sedighi, M., Sasanian, Z.: Synthesis of reversible circuit using cycle-based approach. ACM J. Emerg. Technol. Comput. Syst. http://arxiv.org/abs/1004.4320 (2010)

  35. Miller, D. Michael, Maslov, Dmitri, Dueck, Gerhard W.: A transformation based algorithm for reversible logic synthesis. In: DAC ’03: Proceedings of the 40th annual Design Automation Conference, pp. 318–323. New York, NY: ACM (2003)

  36. Chakrabarti, A., Sur-Kolay, S.: Rules for synthesizing quantum boolean circuits using minimized nearest-neighbour templates. In: International Conference on Advanced Computing and Communications, pp. 183–189 (2007)

  37. Barenco A., Ekert A., Suominen K.-A., Törmä P.: Approximate quantum fourier transform and decoherence. Phys. Rev. A 54(1), 139–146 (1996)

    Article  PubMed  CAS  ADS  MathSciNet  Google Scholar 

  38. Wille, R., Große, D., Dueck, G.W., Drechsler, R.: Reversible logic synthesis with output permutation. In: VLSID ’09: Proceedings of the 2009 22nd International Conference on VLSI Design, pp. 189–194, Washington, DC, USA: IEEE Computer Society (2009)

  39. Wille, R., Große, D., Teuber, L., Dueck, G.W., Drechsler, R.: Revlib: An online resource for reversible functions and reversible circuits. International Symposium on Multiple Valued Logic, pp. 220–225 (May 2008)

Download references

Author information

Authors and Affiliations

  1. Computer Engineering Department, Amirkabir University of Technology, Tehran, Iran

    Mehdi Saeedi

  2. Institute of Computer Science, University of Bremen, Bremen, Germany

    Robert Wille & Rolf Drechsler

Authors
  1. Mehdi Saeedi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert Wille
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rolf Drechsler
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mehdi Saeedi.

Additional information

A preliminary version of this paper has been presented in [1].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Saeedi, M., Wille, R. & Drechsler, R. Synthesis of quantum circuits for linear nearest neighbor architectures. Quantum Inf Process 10, 355–377 (2011). https://doi.org/10.1007/s11128-010-0201-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11128-010-0201-2

Keywords

Search

Navigation