research-article

Open access

Systems Architecture for Quantum Random Access Memory

Authors:

Connor T. Hann,

Steven M. Girvin,

Yongshan DingAuthors Info & Claims

MICRO '23: Proceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture

Pages 526 - 538

https://doi.org/10.1145/3613424.3614270

Published: 08 December 2023 Publication History

All formats PDF

Abstract

Operating on the principles of quantum mechanics, quantum algorithms hold the promise for solving problems that are beyond the reach of the best-available classical algorithms. An integral part of realizing such speedup is the implementation of quantum queries, which read data into forms that quantum computers can process. Quantum random access memory (QRAM) is a promising architecture for realizing quantum queries. However, implementing QRAM in practice poses significant challenges, including query latency, memory capacity and fault-tolerance.

In this paper, we propose the first end-to-end system architecture for QRAM. First, we introduce a novel QRAM that hybridizes two existing implementations and achieves asymptotically superior scaling in space (qubit number) and time (circuit depth). Like in classical virtual memory, our construction enables queries to a virtual address space larger than what is actually available in hardware. Second, we present a compilation framework to synthesize, map, and schedule QRAM circuits on realistic hardware. For the first time, we demonstrate how to embed large-scale QRAM on a 2D Euclidean space, such as a 2D square grid layout, with minimal routing overhead. Third, we show how to leverage the intrinsic biased-noise resilience of the proposed QRAM for implementation on either Noisy Intermediate-Scale Quantum (NISQ) or Fault-Tolerant Quantum Computing (FTQC) hardware. Finally, we validate these results numerically via both classical simulation and quantum hardware experimentation. Our novel Feynman-path-based simulator allows for efficient simulation of noisy QRAM circuits at a larger scale than previously possible. Collectively, our results outline the set of software and hardware controls needed to implement practical QRAM.

References

[1]

Matthew Amy, Dmitri Maslov, and Michele Mosca. 2014. Polynomial-time T-depth optimization of Clifford+ T circuits via matroid partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 10 (2014), 1476–1489.

[2]

Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. 2018. Encoding electronic spectra in quantum circuits with linear T complexity. Physical Review X 8, 4 (2018), 041015.

[3]

Debjyoti Bhattacharjee, Abdullah Ash Saki, Mahabubul Alam, Anupam Chattopadhyay, and Swaroop Ghosh. 2019. MUQUT: Multi-constraint quantum circuit mapping on NISQ computers. In 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 1–7.

[4]

Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. 2017. Quantum machine learning. Nature 549, 7671 (2017), 195–202.

[5]

J Pablo Bonilla Ataides, David K Tuckett, Stephen D Bartlett, Steven T Flammia, and Benjamin J Brown. 2021. The XZZX surface code. Nature communications 12, 1 (2021), 2172.

[6]

H-J Briegel, Wolfgang Dür, Juan I Cirac, and Peter Zoller. 1998. Quantum repeaters: the role of imperfect local operations in quantum communication. Physical Review Letters 81, 26 (1998), 5932.

[7]

Sally Anne Browning. 1980. The tree machine: A highly concurrent computing environment. California Institute of Technology.

[8]

Gregory T Byrd and Yongshan Ding. 2023. Quantum Computing: Progress and Innovation. Computer 56, 1 (2023), 20–29.

[9]

Adán Cabello. 2002. Bell’s theorem with and without inequalities for the three-qubit Greenberger-Horne-Zeilinger and W states. Physical Review A 65, 3 (2002), 032108.

[10]

Zhao-Yun Chen, Cheng Xue, Tai-Ping Sun, Huan-Yu Liu, Xi-Ning Zhuang, Meng-Han Dou, Tian-Rui Zou, Yuan Fang, Yu-Chun Wu, and Guo-Ping Guo. 2023. An Efficient and Error-Resilient Protocol for Quantum Random Access Memory with Generalized Data Size. arXiv preprint arXiv:2303.05207 (2023).

[11]

Frederic T Chong, Diana Franklin, and Margaret Martonosi. 2017. Programming languages and compiler design for realistic quantum hardware. Nature 549, 7671 (2017), 180–187.

[12]

Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca. 2020. Fault-tolerant resource estimation of quantum random-access memories. IEEE Transactions on Quantum Engineering 1 (2020), 1–13.

[13]

Yongshan Ding and Frederic T Chong. 2020. Quantum computer systems: Research for noisy intermediate-scale quantum computers. Synthesis lectures on computer architecture 15, 2 (2020), 1–227.

[14]

Yongshan Ding, Pranav Gokhale, Sophia Fuhui Lin, Richard Rines, Thomas Propson, and Frederic T Chong. 2020. Systematic crosstalk mitigation for superconducting qubits via frequency-aware compilation. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). IEEE, 201–214.

[15]

Yongshan Ding, Xin-Chuan Wu, Adam Holmes, Ash Wiseth, Diana Franklin, Margaret Martonosi, and Frederic T Chong. 2020. Square: Strategic quantum ancilla reuse for modular quantum programs via cost-effective uncomputation. In 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA). IEEE, 570–583.

Digital Library

[16]

Bertrand Ducourthial, G Constantinescu, and Alain Mérigot. 1998. Implementing image analysis with a graph-based parallel computing model. Springer.

[17]

Yvonne Y Gao, Brian J Lester, Kevin S Chou, Luigi Frunzio, Michel H Devoret, Liang Jiang, SM Girvin, and Robert J Schoelkopf. 2019. Entanglement of bosonic modes through an engineered exchange interaction. Nature 566, 7745 (2019), 509–512.

[18]

Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay. 2022. T-count and T-depth of any multi-qubit unitary. npj Quantum Information 8, 1 (2022), 141.

[19]

Craig Gidney. 2018. Halving the cost of quantum addition. Quantum 2 (2018), 74.

[20]

Craig Gidney and Martin Ekerå. 2021. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5 (2021), 433.

[21]

András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. 2019. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 193–204.

Digital Library

[22]

Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. 2008. Architectures for a quantum random access memory. Physical Review A 78, 5 (2008), 052310.

[23]

Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. 2008. Quantum random access memory. Physical review letters 100, 16 (2008), 160501.

[24]

Pranav Gokhale, Olivia Angiuli, Yongshan Ding, Kaiwen Gui, Teague Tomesh, Martin Suchara, Margaret Martonosi, and Frederic T Chong. 2019. Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families. arXiv preprint arXiv:1907.13623 (2019).

[25]

Daniel M Greenberger, Michael A Horne, and Anton Zeilinger. 1989. Going beyond Bell’s theorem. Bell’s theorem, quantum theory and conceptions of the universe (1989), 69–72.

[26]

Lov K Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 212–219.

Digital Library

[27]

Connor T Hann. 2021. Practicality of Quantum Random Access Memory. Ph. D. Dissertation. Yale University.

[28]

Connor T Hann, Gideon Lee, SM Girvin, and Liang Jiang. 2021. Resilience of quantum random access memory to generic noise. PRX Quantum 2, 2 (2021), 020311.

[29]

Aram Harrow. 2001. Quantum compiling. Ph. D. Dissertation. Massachusetts Institute of Technology, Department of Physics.

[30]

Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum algorithm for linear systems of equations. Physical review letters 103, 15 (2009), 150502.

[31]

Ralf Heckmann, Ralf Klasing, Burkhard Monien, and Walter Unger. 1992. Optimal embedding of complete binary trees into lines and grids. In Proc. 17th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG’91), Lecture Notes in Computer Science. 25–35.

[32]

Stefan Hillmich, Alwin Zulehner, and Robert Wille. 2021. Exploiting quantum teleportation in quantum circuit mapping. In Proceedings of the 26th Asia and South Pacific Design Automation Conference. 792–797.

Digital Library

[33]

Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. 2012. Surface code quantum computing by lattice surgery. New Journal of Physics 14, 12 (2012), 123011.

[34]

Richard C Jaeger, Travis N Blalock, and Benjamin Joseph Blalock. 1997. Microelectronic circuit design. McGraw-Hill New York.

[35]

Samuel Jaques and Arthur G Rattew. 2023. QRAM: A Survey and Critique. arXiv preprint arXiv:2305.10310 (2023).

[36]

Tom Kilburn, David BG Edwards, Michael J Lanigan, and Frank H Sumner. 1962. One-level storage system. IRE Transactions on Electronic Computers2 (1962), 223–235.

[37]

Gushu Li, Yufei Ding, and Yuan Xie. 2019. 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. 1001–1014.

Digital Library

[38]

Y-B Lin, Zevi Miller, Manley Perkel, Dan Pritikin, and Ivan Hal Sudborough. 2003. Expansion of layouts of complete binary trees into grids. Discrete applied mathematics 131, 3 (2003), 611–642.

[39]

Guang Hao Low and Isaac L Chuang. 2017. Optimal Hamiltonian simulation by quantum signal processing. Physical review letters 118, 1 (2017), 010501.

[40]

Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. 2018. Trading T-gates for dirty qubits in state preparation and unitary synthesis. arXiv preprint arXiv:1812.00954 (2018).

[41]

Dmitri Maslov, Sean M Falconer, and Michele Mosca. 2008. Quantum circuit placement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 4 (2008), 752–763.

Digital Library

[42]

Connie Miao, Gideon Lee, Liang Jiang, and David Schuster. 2023. Implementation of a Quantum Switch with Superconducting Circuits. Bulletin of the American Physical Society (2023).

[43]

Abtin Molavi, Amanda Xu, Martin Diges, Lauren Pick, Swamit Tannu, and Aws Albarghouthi. 2022. Qubit Mapping and Routing via MaxSAT. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO). IEEE, 1078–1091.

Digital Library

[44]

Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret Martonosi. 2019. 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. 1015–1029.

Digital Library

[45]

Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information.

[46]

Jaroslav Opatrny and Dominique Sotteau. 2000. Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1. Discrete Applied Mathematics 98, 3 (2000), 237–254.

Digital Library

[47]

Jian-Wei Pan, Dik Bouwmeester, Harald Weinfurter, and Anton Zeilinger. 1998. Experimental entanglement swapping: entangling photons that never interacted. Physical review letters 80, 18 (1998), 3891.

[48]

Koustubh Phalak, Junde Li, and Swaroop Ghosh. 2022. Approximate Quantum Random Access Memory Architectures. arXiv preprint arXiv:2210.14804 (2022).

[49]

Aditya K Prasad, Vivek V Shende, Igor L Markov, John P Hayes, and Ketan N Patel. 2006. Data structures and algorithms for simplifying reversible circuits. ACM Journal on Emerging Technologies in Computing Systems (JETC) 2, 4 (2006), 277–293.

Digital Library

[50]

John Preskill. 2018. Quantum computing in the NISQ era and beyond. Quantum 2 (2018), 79.

[51]

Oded Regev and Liron Schiff. 2008. Impossibility of a quantum speed-up with a faulty oracle. In Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I 35. Springer, 773–781.

[52]

Peter W Shor. 1994. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science. Ieee, 124–134.

Digital Library

[53]

Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. 2023. Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2023).

Digital Library

[54]

Swamit S Tannu and Moinuddin K Qureshi. 2019. Not all qubits are created equal: A case for variability-aware policies for NISQ-era quantum computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 987–999.

Digital Library

[55]

Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. 2020. Convex optimization using quantum oracles. Quantum 4 (2020), 220.

[56]

Rodney Van Meter. 2014. Quantum networking. John Wiley & Sons.

[57]

Xin-Chuan Wu, Dripto M Debroy, Yongshan Ding, Jonathan M Baker, Yuri Alexeev, Kenneth R Brown, and Frederic T Chong. 2021. Tilt: Achieving higher fidelity on a trapped-ion linear-tape quantum computing architecture. In 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, 153–166.

[58]

Sophia Xue, Stijn de Graaf, Benjamin Chapman, Yaxing Zhang, James Teoh, Jacob Curtis, Takahiro Tsunoda, Alec Eickbusch, Alexander Read, Akshay Koottandavida, 2023. A hybrid controlled-SWAP gate between two bosonic modes. Bulletin of the American Physical Society (2023).

[59]

Chi Zhang, Ari B Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Eddy Z Zhang. 2021. Time-optimal qubit mapping. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 360–374.

Digital Library

[60]

Jun Zhang, Jiri Vala, Shankar Sastry, and K Birgitta Whaley. 2004. Optimal quantum circuit synthesis from controlled-unitary gates. Physical Review A 69, 4 (2004), 042309.

Cited By

Rodriges Zalipynis R(2024)Quantum Tensor DBMS and Quantum Gantt Charts: Towards Exponentially Faster Earth Data EngineeringEarth10.3390/earth50300275:3(491-547)Online publication date: 14-Sep-2024
https://doi.org/10.3390/earth5030027
Tan SXiang DLu LLu JJiang QChen MYin JTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)MorphQPV: Exploiting Isomorphism in Quantum Programs to Facilitate Confident VerificationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651360(671-688)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651360
Khan MAman MSikdar B(2024)Beyond Bits: A Review of Quantum Embedding Techniques for Efficient Information ProcessingIEEE Access10.1109/ACCESS.2024.338215012(46118-46137)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3382150

Index Terms

Systems Architecture for Quantum Random Access Memory
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Quantum computing
2. Hardware
  1. Emerging technologies
    1. Quantum technologies

Recommendations

Integrable quantum computation

Integrable quantum computation is defined as quantum computing via the integrable condition, in which two-qubit gates are either nontrivial unitary solutions of the Yang---Baxter equation or the Swap gate (permutation). To make the definition clear, in ...
Contextuality Supplies the Magic for Quantum Computation
ISMVL '15: Proceedings of the 2015 IEEE 45th International Symposium on Multiple-Valued Logic

We know that quantum mechanics enables the performance of computational and cryptographic tasks that are impossible (or impracticable) using only classical physics. It seems natural to examine manifestations of inherently quantum behaviour as potential ...
Quantum walks: a comprehensive review

Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MICRO '23: Proceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture

October 2023

1528 pages

ISBN:9798400703294

DOI:10.1145/3613424

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 December 2023

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

MICRO '23

Sponsor:

SIGMICRO

MICRO '23: 56th Annual IEEE/ACM International Symposium on Microarchitecture

October 28 - November 1, 2023

ON, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Upcoming Conference

MICRO '24

Sponsor:
sigmicro

57th Annual IEEE/ACM International Symposium on Microarchitecture

November 2 - 6, 2024

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
708
Total Downloads

Downloads (Last 12 months)708
Downloads (Last 6 weeks)153

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rodriges Zalipynis R(2024)Quantum Tensor DBMS and Quantum Gantt Charts: Towards Exponentially Faster Earth Data EngineeringEarth10.3390/earth50300275:3(491-547)Online publication date: 14-Sep-2024
https://doi.org/10.3390/earth5030027
Tan SXiang DLu LLu JJiang QChen MYin JTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)MorphQPV: Exploiting Isomorphism in Quantum Programs to Facilitate Confident VerificationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651360(671-688)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651360
Khan MAman MSikdar B(2024)Beyond Bits: A Review of Quantum Embedding Techniques for Efficient Information ProcessingIEEE Access10.1109/ACCESS.2024.338215012(46118-46137)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3382150
Wang YAlexeev YJiang LChong FLiu J(2024)Fundamental causal bounds of quantum random access memoriesnpj Quantum Information10.1038/s41534-024-00848-310:1Online publication date: 23-Jul-2024
https://doi.org/10.1038/s41534-024-00848-3

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents