Nothing Special   »   [go: up one dir, main page]
Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Review Article
  • Published:

Programming languages and compiler design for realistic quantum hardware

Nature volume 549, pages 180–187 (2017)Cite this article

Subjects

Abstract

Quantum computing sits at an important inflection point. For years, high-level algorithms for quantum computers have shown considerable promise, and recent advances in quantum device fabrication offer hope of utility. A gap still exists, however, between the hardware size and reliability requirements of quantum computing algorithms and the physical machines foreseen within the next ten years. To bridge this gap, quantum computers require appropriate software to translate and optimize applications (toolflows) and abstraction layers. Given the stringent resource constraints in quantum computing, information passed between layers of software and implementations will differ markedly from in classical computing. Quantum toolflows must expose more physical details between layers, so the challenge is to find abstractions that expose key details while hiding enough complexity.

Access through your institution
Buy or subscribe

This is a preview of subscription content, access via your institution

Access options

Access through your institution

Buy this article

  • Purchase on SpringerLink
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

Figure 1: Design tool flows and abstraction stacks.

Similar content being viewed by others

References

  1. Moore, G. E. Progress in digital integrated electronics. IEEE Solid-State Circ. Soc. News. 20(3), 11–13 (1975; reprinted 2006); available at http://ieeexplore.ieee.org/document/4804410/

    Google Scholar 

  2. De Micheli, G. Hardware synthesis from C/C++ models. In Proc. Conf. on Design Automation and Test in Europe (DATE ’99) 80 (ACM, 1999)

  3. Deschamps, J.-P ., Valderrama, E & Terés, L. Design Methods 171–177 (Springer, 2017)

  4. Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proc. 35th Ann. Symp. on Foundations of Computer Science (FOCS ’94) 124–134 (IEEE, 1994)

  5. Mosca, M. in Encyclopedia of Complexity and Systems Science (ed. Meyers, R. A. ) 7088–7118 (Springer, 2009)

  6. Ambainis, A., Childs, A. M., Reichardt, B. W., Spalek, R. & Zhang, S. Any AND-OR formula of size N can be evaluated in time N1/2+0(1) on a quantum computer. SIAM J. Comput. 39(6), 2513–2530 (2010)

    Article  MathSciNet  Google Scholar 

  7. Childs, A. M . et al. Exponential algorithmic speedup by a quantum walk. In Proc. 35th Ann. Symp. on Theory of Computing (STOC ’03) 59–68 (ACM, 2003)

  8. Hallgren, S. Fast quantum algorithms for computing the unit group and class group of a number field. In Proc. 37th Ann. Symp. on Theory of Computing (STOC ’05) 468–474 (ACM, 2005)

  9. Grover, L. K. A fast quantum mechanical algorithm for database search. In Proc. 28th Ann. Symp. on Theory of Computing (STOC ’96) 212–219 (ACM, 1996)

  10. Whitfield, J. D. et al. Simulation of electronic structure Hamiltonians using quantum computers. Mol. Phys. 109, 735–750 (2010)

    Article  ADS  Google Scholar 

  11. National Institute of Standards and Technology FIPS PUB 180–4: Secure Hash Standard (SHS) http://csrc.nist.gov/publications/fips/fips180-4/fips180-4.pdf (US Department of Commerce, 2012)

  12. Magniez, F ., Santha, M . & Szegedy, M. Quantum algorithms for the triangle problem. In Proc. 16th Ann. Symp. on Discrete Algorithms (SODA ’05) 1109–1117 (ACM-SIAM, 2005)

  13. Aspuru-Guzik, A., Dutoi, A. D., Love, P. J. & Head-Gordon, M. Simulated quantum computation of molecular energies. Science 309, 1704–1707 (2005)

    Article  ADS  CAS  Google Scholar 

  14. Jordan, S. P., Lee, K. S. M. & Preskill, J. Quantum algorithms for quantum field theories. Science 336, 1130–1133 (2012)

    Article  ADS  CAS  Google Scholar 

  15. McClean, J. R., Babbush, R., Love, P. L. & Aspuru-Guzik, A. Exploiting locality in quantum computation for quantum chemistry. J. Phys. Chem. Lett. 5, 4368–4380 (2014)

    Article  CAS  Google Scholar 

  16. Reiher, M., Wiebe, N., Svore, K. M., Wecker, D. & Troyer, M. Elucidating reaction mechanisms on quantum computers. Preprint at https://arxiv.org/abs/1605.03590 (2016)

  17. Peruzzo, A. et al. A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014)

    Article  ADS  CAS  Google Scholar 

  18. O’Malley, P. J. J . et al. Scalable quantum simulation of molecular energies. Phys. Rev. X 6, 031007 (2016). This paper is a good example of the emerging importance of classical-quantum co-processing.

    Google Scholar 

  19. Valiron, B. et al. Programming the quantum future. Commun. ACM 58, 52–61 (2015). This paper offers another perspective on quantum programming language design issues.

    Article  Google Scholar 

  20. Metodi, T. S ., Thaker, D. D ., Cross, A. W ., Chong, F. T . & Chuang, I. L. A quantum logic array microarchitecture:scalable quantum data movement and computation. In Proc. 38th Ann. Int. Symp. on Microarchitecture (MICRO) 305–318 (ACM/IEEE Computer Society, 2005)

  21. Thaker, D. D ., Metodi, T. S ., Cross, A. W ., Chuang, I. L . & Chong, F. T. Quantum memory hierarchies: efficient designs to match available parallelism in quantum computing. In Proc. 33rd Ann. Int. Symp. on Computer Architecture (ISCA) 378–390 (ACM/IEEE Computer Society, 2006)

  22. Balensiefer, S., Kregor-Stickles, L. & Oskin, M. An evaluation framework and instruction set architecture for ion-trap based quantum micro-architectures. SIGARCH Comput. Archit. News 33, 186–196 (2005)

    Article  Google Scholar 

  23. Schuchman, E. & Vijaykumar, T. N. A program transformation and architecture support for quantum uncomputation. SIGARCH Comput. Archit. News 34, 252–263 (2006)

    Article  Google Scholar 

  24. Isailovic, N ., Whitney, M ., Patel, Y . & Kubiatowicz, J. Running a quantum circuit at the speed of data. In Proc. 35th Ann. Int. Symp. on Computer Architecture (ISCA). 177–188 (2008)

  25. Whitney, M. G ., Isailovic, N ., Patel, Y . & Kubiatowicz, J. A fault tolerant, area efficient architecture for Shor’s factoring algorithm. In Proc. 36th Ann. Int. Symp. on Computer Architecture (ISCA) 383–394 (2009)

  26. Van Meter, R. & Horsman, C. A blueprint for building a quantum computer. Commun. ACM 56, 84–93 (2013)

    Article  Google Scholar 

  27. Metodi, T. S ., Faruque, A. I . & Chong, F. T. Quantum Computing for Computer Architects 2nd edn Synthesis Lectures on Computer Architecture (Morgan & Claypool, 2011)

  28. Kudrow, D . et al. Quantum rotations: a case study in static and dynamic machine-code generation for quantum computers. In Proc.40th Ann. Int. Symp. on Computer Architecture (ISCA) 166–176 (ACM, 2013)

    Article  Google Scholar 

  29. Heckey, J . et al. Compiler management of communication and parallelism for quantum computation. In Proc. 20th Int. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS) 445–456 (ACM, 2015). This paper describes the use of a software toolchain to explore architectural designs and optimizations.

    Article  Google Scholar 

  30. Devitt, S. J. Performing quantum computing experiments in the cloud. Phys. Rev. A 94, 032329 (2016)

    Article  ADS  Google Scholar 

  31. Debnath, S. et al. Demonstration of a small programmable quantum computer with atomic qubits. Nature 536, 63–66 (2016)

    Article  ADS  CAS  Google Scholar 

  32. Linke, N. M. et al. Fault-tolerant quantum error detection. Preprint at https://arxiv.org/abs/1611.06946 (2016)

  33. Kelly, J. et al. State preservation by repetitive error detection in a superconducting quantum circuit. Nature 519, 66–69 (2015)

    Article  ADS  CAS  Google Scholar 

  34. Lekitsch, B. et al. Blueprint for a microwave trapped-ion quantum computer. Preprint at https://arxiv.org/abs/1508.00420 (2015)

  35. Fowler, A. G. et al. Surface codes: towards practical large-scale quantum computation. Phys. Rev. A 86, 032324 (2012)

    Article  ADS  Google Scholar 

  36. Monroe, C. et al. Large-scale modular quantum-computer architecture with atomic memory and photonic interconnects. Phys. Rev. A 89, 022317 (2014)

    Article  ADS  Google Scholar 

  37. Hastings, M. B., Wecker, D., Bauer, B. & Troyer, M. Improving quantum algorithms for quantum chemistry. Preprint at https://arxiv.org/abs/1403.1539 (2014). This paper describes a software toolchain that improves the efficiency 100,000-fold in their quantum chemistry application.

  38. Omer, B. A Procedural Formalism for Quantum Computing: Qcl. Master’s thesis http://tph.tuwien.ac.at/~oemer/doc/qcldoc.pdf (Technical Physics, TU Vienna, 1998)

  39. Green, A. S . et al. Quipper: A scalable quantum programming language. In Proc. 34th SIGPLAN Conf. on Programming Language Design and Implementation (PLDI ’13) 333–342 (ACM, 2013). This paper describes a quantum programming language incorporating some of the best design practices of functional languages.

  40. Lapets, A . et al. Quafl: A typed dsl for quantum programming. In Proc. 1st Ann. Workshop on Functional Programming Concepts in Domain-specific Languages (FPCDSL ’13) 19–26 (ACM, 2013)

  41. JavadiAbhari, A . et al. ScaffCC: A framework for compilation and analysis of quantum computing programs. In Proc. 11th ACM Conf. on Computing Frontiers 1 (ACM, 2014)

  42. Lattner, C . & Adve, V. LLVM: A compilation framework for lifelong program analysis & transformation. In Proc. Int. Symp. on Code Generation and Optimization: Feedback-directed and Runtime Optimization 75–86 (IEEE Computer Society, 2004)

  43. Wecker, D. & Svore, K. Liquid: A Software Design Architecture And Domain-Specific Language For Quantum Computing. https://www.microsoft.com/en-us/research/project/language-integrated-quantum-operations-liqui/ (2014)

  44. Haner, T., Steiger, D. S., Svore, K. & Troyer, M. A software methodology for compiling quantum programs. Preprint at https://arxiv.org/abs/1604.01401 (2016). This is a good example of a quantum software stack.

  45. Steiger, D. S., Hner, T. & Troyer, M. ProjectQ: an open source software framework for quantum computing. Preprint at https://arxiv.org/abs/1612.08091 (2016)

  46. Ion Storage Group. ARTIQ (Advanced Real-Time Infrastructure for Quantum Physics) http://m-labs.hk/artiq/index.html (NIST, 2017)

  47. Smith, R. S., Curtis, M. J. & Zeng, W. J. A practical quantum instruction set architecture. Preprint at https://arxiv.org/abs/1608.03355 (2016)

  48. Figgatt, C. et al. Complete 3-qubit grover search on a programmable quantum computer. Preprint at https://arxiv.org/abs/1703.10535 (2017)

  49. Castelvecchi, D. IBM’s quantum cloud computer goes commercial. Nature 543, 159 (2017)

    Article  ADS  CAS  Google Scholar 

  50. Park, J ., Esmaeilzadeh, H ., Zhang, X ., Naik, M . & Harris, W. Flexjava: Language support for safe and modular approximate programming. In Proc. 10th Joint Meet. on Foundations of Software Engineering (ESEC/FSE 2015) 745–757 (ACM, 2015)

  51. Aho, A. V ., Lam, M. S ., Sethi, R . & Ullman, J. D. Compilers: Principles, Techniques, and Tools 2nd edn (Addison-Wesley Longman, 2006)

  52. Allen, F. E. Interprocedural data flow analysis. In International Federation for Information Processing (IFIP) Congress 398–402 (1974)

  53. Hall, M. W ., Murphy, B. R ., Amarasinghe, S. P ., Liao, S. W . & Lam., M. S. Interprocedural Analysis for Parallelization 61–80 (Springer, 1996)

  54. Dempster, J. M., Fu, B., Ferguson, D. G., Schuster, D. I. & Koch, J. Understanding degenerate ground states of a protected quantum circuit in the presence of disorder. Phys. Rev. B 90, 094518 (2014)

    Article  ADS  Google Scholar 

  55. Mavadia, S., Frey, F., Sastrawan, J., Dona, S. & Biercuk, M. J. Prediction and real-time compensation of qubit decoherence via machine learning. Nature Commun. 8, 14106 (2017)

    Article  ADS  CAS  Google Scholar 

  56. Kandala, A. et al. Hardware-efficient quantum optimizer for small molecules and quantum magnets. Preprint at https://arxiv.org/abs/1704.05018 (2017)

  57. McKay, D. C., Naik, R., Reinhold, P., Bishop, L. S. & Schuster., D. I. High-contrast qubit interactions using multimode cavity qed. Phys. Rev. Lett. 114, 080501 (2015)

    Article  ADS  Google Scholar 

  58. Homulle, H. et al. A reconfigurable cryogenic platform for the classical control of scalable quantum computers. Preprint at https://arxiv.org/abs/1602.05786 (2016)

  59. Likharev, K. K. & Semenov, V. K. Rsfq logic/memory family: a new Josephson-junction technology for sub-terahertz-clock-frequency digital systems. IEEE Trans. Appl. Supercond. 1, 3–28 (1991)

    Article  ADS  Google Scholar 

  60. Wecker, D., Bauer, B., Clark, B. K., Hastings, M. B. & Troyer, M. Gate-count estimates for performing quantum chemistry on small quantum computers. Phys. Rev. A 90, 022305 (2014)

    Article  ADS  Google Scholar 

  61. Smelyanskiy, M., Sawaya, N. P. D. & Aspuru-Guzik, A. qHiPSTER: the quantum high performance software testing environment. Preprint at https://arxiv.org/abs/1601.07195 (2016)

  62. Khammassi, N. The QX Simulatorhttp://www.xpu-project.net/qx/download.html (2017)

  63. Bravyi, S. & Gosset, D. Improved classical simulation of quantum circuits dominated by clifford gates. Phys. Rev. Lett. 116, 250501 (2016)

    Article  ADS  Google Scholar 

  64. Chiw, C ., Kindlmann, G ., Reppy, J ., Samuels, L . & Seltzer, N. Diderot: a parallel DSL for image analysis and visualization. In Proc. SIGPLAN Conf. on Programming Language Design and Implementation 111–120 (ACM, 2012)

  65. Alur, R . et al. in Dependable Software Systems Engineering. NATO Science for Peace and Security Series D: Information and Communication Security (eds Irlbeck, M ., Peled, D. A . & Pretschner, A. ) Vol. 40, 1–25 (IOS Press, 2015)

    Google Scholar 

  66. Selinger, P . & Valiron, B. in Foundations of Software Science and Computational Structures 81–96 (Springer Science & Business Media, 2008)

  67. Kielpinski, D., Monroe, C. & Wineland, D. J. Architecture for a large-scale ion-trap quantum computer. Nature 417, 709–711 (2002)

    Article  ADS  CAS  Google Scholar 

  68. Wineland, D. J. et al. Experimental primer on the trapped ion quantum computer. Fortschr. Phys. 46, 363–390 (1998)

    Article  CAS  Google Scholar 

  69. Amy, M., Roetteler, M. & Svore, K. M. Verified Compilation of Space-Efficient Reversible Circuits. In Proc. Computer Aided Verification: 29th Int. Conf. (CAV 2017) Part II, 3–21 (Springer International, 2017)

Download references

Acknowledgements

We thank the many collaborators who have helped shape our thinking over the years: K. Brown, I. Chuang, E. Chi, A. Faruque, A. Harrow, J. Heckey, A. Javadi-Abhari, J. Kubiatowicz, D. Kudrow, T. Metodi, M. Oskin, S. Patil, J. Reppy, D. Schuster, M. Suchara and D. Thaker. This work was funded in part by Los Alamos National Laboratory and the US Department of Defense under subcontract 431682, by NSF PHY grant 1660686, and by a research gift from Intel Corporation.

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Chicago, Chicago, USA

    Frederic T. Chong & Diana Franklin

  2. Department of Computer Science, Princeton University, Princeton, USA

    Margaret Martonosi

Authors
  1. Frederic T. Chong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Diana Franklin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Margaret Martonosi
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All three authors contributed equally to the survey and conclusions in this article.

Corresponding author

Correspondence to Frederic T. Chong.

Ethics declarations

Competing interests

The authors declare no competing financial interests.

Additional information

Reviewer Information Nature thanks B. Valiron and the other anonymous reviewer(s) for their contribution to the peer review of this work.

Publisher's note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

PowerPoint slides

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chong, F., Franklin, D. & Martonosi, M. Programming languages and compiler design for realistic quantum hardware. Nature 549, 180–187 (2017). https://doi.org/10.1038/nature23459

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/nature23459

Search

Advanced search

Quick links

Nature Briefing AI and Robotics

Sign up for the Nature Briefing: AI and Robotics newsletter — what matters in AI and robotics research, free to your inbox weekly.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing: AI and Robotics