Document Open Access Logo

Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits

Author Florian Speelman

PDF
Thumbnail PDF

File

LIPIcs.TQC.2016.9.pdf
  • Filesize: 0.58 MB
  • 24 pages

Document Identifiers

Author Details

Florian Speelman

Cite As Get BibTex

Florian Speelman. Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.TQC.2016.9

Abstract

Instantaneous non-local quantum computation requires multiple parties to jointly perform a quantum operation, using pre-shared entanglement and a single round of simultaneous communication. We study this task for its close connection to position-based quantum cryptography, but it also has natural applications in the context of foundations of quantum physics and in distributed computing. The best known general construction for instantaneous non-local quantum computation requires a pre-shared state which is exponentially large in the number of qubits involved in the operation, while efficient constructions are known for very specific cases only.

We partially close this gap by presenting new schemes for efficient instantaneous non-local computation of several classes of quantum circuits, using the Clifford+T gate set. Our main result is a protocol which uses entanglement exponential in the T-depth of a quantum circuit, able to perform non-local computation of quantum circuits with a (poly-)logarithmic number of layers of T gates with quasi-polynomial entanglement. Our proofs combine ideas from blind and delegated quantum computation with the garden-hose model, a combinatorial model of communication complexity which was recently introduced as a tool for studying certain schemes for quantum position verification. As an application of our results, we also present an efficient attack on a recently-proposed scheme for position verification by Chakraborty and Leverrier.

Subject Classification

Keywords
  • Quantum Cryptography
  • Quantum Communication

Metrics

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

References

  1. Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004. Google Scholar
  2. Matthew Amy, Dmitri Maslov, and Michele Mosca. Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 33(10):1476-1489, Oct 2014. URL: http://dx.doi.org/10.1109/TCAD.2014.2341953.
  3. Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. Trans. Comp.-Aided Des. Integ. Cir. Sys., 32(6):818-830, June 2013. URL: http://dx.doi.org/10.1109/TCAD.2013.2244643.
  4. Pablo Arrighi and Louis Salvail. Blind quantum computation. International Journal of Quantum Information, 4(05):883-898, 2006. Google Scholar
  5. Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 13(9):093036, 2011. Google Scholar
  6. HJ Briegel, DE Browne, W Dür, R Raussendorf, and M Van den Nest. Measurement-based quantum computation. Nature Physics, 5(1):19-26, 2009. Google Scholar
  7. Anne Broadbent. Delegating private quantum computations. Canadian Journal of Physics, 93(9):941-946, 2015. URL: http://dx.doi.org/10.1139/cjp-2015-0030.
  8. Anne Broadbent. Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation. arXiv preprint arXiv:1512.04930, 2015. Google Scholar
  9. Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 517-526. IEEE, 2009. Google Scholar
  10. Anne Broadbent and Stacey Jeffery. Quantum homomorphic encryption for circuits of low T-gate complexity. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015, volume 9216 of Lecture Notes in Computer Science, pages 609-629. Springer Berlin Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48000-7_30.
  11. H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, and F. Unger. New limits on fault-tolerant quantum computation. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 411-419, Oct 2006. URL: http://dx.doi.org/10.1109/FOCS.2006.50.
  12. Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages 429-446. Springer Berlin / Heidelberg, 2011. Google Scholar
  13. Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS'13, pages 145-158, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2422436.2422455.
  14. Kaushik Chakraborty and Anthony Leverrier. Practical position-based quantum cryptography. Phys. Rev. A, 92:052304, Nov 2015. URL: http://dx.doi.org/10.1103/PhysRevA.92.052304.
  15. Andrew M Childs. Secure assisted quantum computation. Quantum Information &Computation, 5(6):456-466, 2005. Google Scholar
  16. S R Clark, A J Connor, D Jaksch, and S Popescu. Entanglement consumption of instantaneous nonlocal quantum measurements. New Journal of Physics, 12(8):083034, 2010. URL: http://stacks.iop.org/1367-2630/12/i=8/a=083034.
  17. Yfke Dulek, Christian Schaffner, and Florian Speelman. Quantum homomorphic encryption for polynomial-sized circuits. arXiv preprint arXiv:1603.09717, 2016. Google Scholar
  18. Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Secure two-party quantum evaluation of unitaries against specious adversaries. In CRYPTO, pages 685-706, September 2010. http://arxiv.org/abs/1009.2096, URL: http://dx.doi.org/10.1007/978-3-642-14623-7_37.
  19. KAG Fisher, A Broadbent, LK Shalm, Z Yan, J Lavoie, R Prevedel, T Jennewein, and KJ Resch. Quantum computing on encrypted data. Nature communications, 5, 2014. Google Scholar
  20. Simon Forest, David Gosset, Vadym Kliuchnikov, and David McKinnon. Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets. Journal of Mathematical Physics, 56(8):-, 2015. URL: http://dx.doi.org/10.1063/1.4927100.
  21. Brett Giles and Peter Selinger. Exact synthesis of multiqubit Clifford+T circuits. Physical Review A, 87(3):032332, 2013. Google Scholar
  22. Daniel Gottesman. The Heisenberg representation of quantum computers. In Group theoretical methods in physics. Proceedings, 22nd International Colloquium, Group22, ICGTMP'98, Hobart, Australia, July 13-17, 1998, 1998. URL: http://arxiv.org/abs/quant-ph/9807006.
  23. Daniel Gottesman. Theory of fault-tolerant quantum computation. Phys. Rev. A, 57:127-137, Jan 1998. URL: http://dx.doi.org/10.1103/PhysRevA.57.127.
  24. Daniel Gottesman and Isaac L. Chuang. Quantum Teleportation is a Universal Computational Primitive. Nature, 402:390-393, August 1999. http://arxiv.org/abs/9908010, URL: http://dx.doi.org/10.1038/46503.
  25. Satoshi Ishizaka and Tohya Hiroshima. Asymptotic teleportation scheme as a universal programmable quantum processor. Phys. Rev. Lett., 101(24):240501, Dec 2008. URL: http://dx.doi.org/10.1103/PhysRevLett.101.240501.
  26. Satoshi Ishizaka and Tohya Hiroshima. Quantum teleportation scheme by selecting one of multiple output ports. Phys. Rev. A, 79(4):042306, Apr 2009. URL: http://dx.doi.org/10.1103/PhysRevA.79.042306.
  27. Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous. Matchgate and space-bounded quantum computations are equivalent. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, page rspa20090433. The Royal Society, 2009. Google Scholar
  28. Adrian Kent, William J. Munro, and Timothy P. Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Phys. Rev. A, 84:012326, Jul 2011. URL: http://dx.doi.org/10.1103/PhysRevA.84.012326.
  29. Hartmut Klauck and Supartha Podder. New bounds for the garden-hose model. In Venkatesh Raman and S. P. Suresh, editors, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), volume 29 of Leibniz International Proceedings in Informatics (LIPIcs), pages 481-492, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.481.
  30. Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates. Quantum Info. Comput., 13(7-8):607-630, July 2013. Google Scholar
  31. Hoi-Kwan Lau and Hoi-Kwong Lo. Insecurity of position-based quantum-cryptography protocols against entanglement attacks. Phys. Rev. A, 83(1):012322, Jan 2011. URL: http://dx.doi.org/10.1103/PhysRevA.83.012322.
  32. Gabriele Nebe, Eric M. Rains, and Neil J. A. Sloane. The invariants of the Clifford groups. Designs, Codes and Cryptography, 24(1):99-122, 2001. URL: http://dx.doi.org/10.1023/A:1011233615437.
  33. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge university press, 2000. Google Scholar
  34. Neil J Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of z-rotations. arXiv preprint arXiv:1403.2975, 2014. Google Scholar
  35. Peter Selinger. Quantum circuits of T-depth one. Physical Review A, 87(4):042302, 2013. Google Scholar
  36. Peter Selinger. Efficient Clifford+T approximation of single-qubit operators. Quantum Information &Computation, 15(1-2):159-180, January 2015. Google Scholar
  37. Florian Speelman. Position-based quantum cryptography and the garden-hose game. Master’s thesis, University of Amsterdam, 2011. Google Scholar
  38. Lev Vaidman. Instantaneous measurement of nonlocal variables. Phys. Rev. Lett., 90(1):010402, Jan 2003. URL: http://dx.doi.org/10.1103/PhysRevLett.90.010402.
  39. Li Yu. Fast controlled unitary protocols using group or quasigroup structures. arXiv preprint arXiv:1112.0307, 2011. Google Scholar
  40. Li Yu, Robert B Griffiths, and Scott M Cohen. Fast protocols for local implementation of bipartite nonlocal unitaries. Physical Review A, 85(1):012304, 2012. Google Scholar
  41. Bei Zeng, Xie Chen, and Isaac L Chuang. Semi-Clifford operations, structure of C_k hierarchy, and gate complexity for fault-tolerant quantum computation. Physical Review A, 77(4):042313, 2008. 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 About DROPS Imprint Privacy Contact