License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2016.9
URN: urn:nbn:de:0030-drops-66909
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6690/
Go to the corresponding LIPIcs Volume Portal

Speelman, Florian

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

pdf-format:
LIPIcs-TQC-2016-9.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{speelman:LIPIcs:2016:6690,
  author =	{Florian Speelman},
  title =	{{Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{9:1--9:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Anne Broadbent},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6690},
  URN =		{urn:nbn:de:0030-drops-66909},
  doi =		{10.4230/LIPIcs.TQC.2016.9},
  annote =	{Keywords: Quantum Cryptography, Quantum Communication}
}

Keywords: Quantum Cryptography, Quantum Communication
Collection: 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Issue Date: 2016
Date of publication: 22.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI