2026-10-06T13:59:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6690 2024-03-06T09:38:40Z ddc:004 open_access

Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits Speelman, Florian Quantum Cryptography Quantum Communication 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Speelman 2016 Is Part Of LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2016.9 urn:nbn:de:0030-drops-66909 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.9 eng https://creativecommons.org/licenses/by/3.0/legalcode