Document Open Access Logo

On the Robustness of Bucket Brigade Quantum RAM

Authors Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca, Priyaa Varshinee Srinivasan

PDF
Thumbnail PDF

File

LIPIcs.TQC.2015.226.pdf
  • Filesize: 1.03 MB
  • 19 pages

Document Identifiers

Author Details

Srinivasan Arunachalam
Vlad Gheorghiu
Tomas Jochym-O'Connor
Michele Mosca
Priyaa Varshinee Srinivasan

Cite AsGet BibTex

Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca, and Priyaa Varshinee Srinivasan. On the Robustness of Bucket Brigade Quantum RAM. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 226-244, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.TQC.2015.226

Abstract

We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti, Lloyd, and Maccone [Phys. Rev. Lett., 2008]. Due to a result of Regev and Schiff [ICALP, 2008], we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order o(2^{-n/2}) (where N=2^n is the size of the memory) whenever the memory is used as an oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of "active" gates, since all components have to be actively error corrected.
Keywords
  • Quantum Mechanics
  • Quantum Memories
  • Quantum Error Correction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210-239, April 2007. Google Scholar
  2. Jonas T. Anderson, Guillaume Duclos-Cianci, and David Poulin. Fault-tolerant conversion between the steane and reed-muller quantum codes. Phys. Rev. Lett., 113:080501, Aug 2014. Google Scholar
  3. Srinivasan Arunachalam. Quantum speed-ups for boolean satisfiability and derivative-free optimization. Master’s Thesis, University of Waterloo, 2014. Google Scholar
  4. H. Bombin. Optimal transversal gates under geometric constraints. e-print arXiv:1311.0879 [quant-ph]. Google Scholar
  5. H. Bombin and M. A. Martin-Delgado. Topological quantum distillation. Phys. Rev. Lett., 97:180501, Oct 2006. Google Scholar
  6. Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. SIGACT News, 28(2):14-19, June 1997. Google Scholar
  7. Sergey Bravyi and Jeongwan Haah. Magic-state distillation with low overhead. Phys. Rev. A, 86:052329, Nov 2012. Google Scholar
  8. Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Phys. Rev. A, 71:022316, Feb 2005. Google Scholar
  9. Harry Buhrman, Ilan Newman, Hein Roehrig, and Ronald de Wolf. Robust polynomials and quantum algorithms. e-print arXiv:quant-ph/0309220. Google Scholar
  10. A. R. Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Phys. Rev. A, 54:1098-1105, Aug 1996. Google Scholar
  11. Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC'03, pages 59-68, New York, NY, USA, 2003. ACM. Google Scholar
  12. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Architectures for a quantum random access memory. Phys. Rev. A, 78:052310, Nov 2008. Google Scholar
  13. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett., 100:160501, Apr 2008. Google Scholar
  14. Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. e-print arXiv:quant-ph/0208112. Google Scholar
  15. Fang-Yu Hong, Yang Xiang, Zhi-Yan Zhu, Li-zhen Jiang, and Liang-neng Wu. Robust quantum random access memory. Phys. Rev. A, 86:010306, Jul 2012. Google Scholar
  16. Peter Høyer, Michele Mosca, and Ronald de Wolf. Quantum search on bounded-error inputs. In JosC.M. Baeten, JanKarel Lenstra, Joachim Parrow, and GerhardJ. Woeginger, editors, Automata, Languages and Programming, volume 2719 of Lecture Notes in Computer Science, pages 291-299. Springer Berlin Heidelberg, 2003. Google Scholar
  17. R. C. Jaeger and T. N. Blalock. Microelectronic Circuit Design. McGraw-Hill, Dubuque, 2003. Google Scholar
  18. Tomas Jochym-O'Connor and Raymond Laflamme. Using concatenated quantum codes for universal fault-tolerant quantum gates. Phys. Rev. Lett., 112:010505, Jan 2014. Google Scholar
  19. Phillip Kaye, Raymond Laflamme, and Michele Mosca. An Introduction to Quantum Computing. Oxford University Press, 2007. Google Scholar
  20. Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput., 35(1):170-188, July 2005. Google Scholar
  21. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. e-print arXiv:1307.0411 [quant-ph]. Google Scholar
  22. Michele Mosca and Phillip Kaye. Quantum networks for generating arbitrary quantum states. In Optical Fiber Communication Conference and International Conference on Quantum Information, page PB28. Optical Society of America, 2001. Google Scholar
  23. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (Cambridge Series on Information and the Natural Sciences). Cambridge University Press, 1 edition, January 2004. Google Scholar
  24. Adam Paetznick and Ben W. Reichardt. Universal fault-tolerant quantum computation with only transversal gates and error correction. Phys. Rev. Lett., 111:090505, Aug 2013. Google Scholar
  25. Oded Regev and Liron Schiff. Impossibility of a quantum speed-up with a faulty oracle. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part I, ICALP'08, pages 773-781, Berlin, Heidelberg, 2008. Springer-Verlag. Google Scholar
  26. A. S. Sedra and K. C. Smith. Microelectronic Circuits. Oxford Press, New York, 1998. Google Scholar
  27. Peter W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52:R2493-R2496, Oct 1995. Google Scholar
  28. A. M. Steane. Error correcting codes in quantum theory. Phys. Rev. Lett., 77(5):793-797, Jul 1996. Google Scholar
  29. Andrew M. Steane. Multiple-particle interference and quantum error correction. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452(1954):2551-2577, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact