| Title: |
A complexity theory for non-local quantum computation |
| Authors: |
Bluhm, Andreas; Höfer, Simon; May, Alex; Stasiuk, Mikka; Verduyn Lunel, Philip; Yuen, Henry |
| Contributors: |
Calculs algorithmes programmes et preuves (CAPP); Laboratoire d'Informatique de Grenoble (LIG); Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP); Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP); Université Grenoble Alpes (UGA); Perimeter Institute for Theoretical Physics Waterloo; Institute for Quantum Computing Waterloo (IQC); University of Waterloo Waterloo; Information Quantique LIP6 (QI); LIP6; Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS); Columbia University New York; ANR-22-PETQ-0007,EPiQ,Etude de la pile quantique : Algorithmes, modèles de calcul et simulation pour l'informatique quantique(2022); ANR-24-CE47-3023,PraQPV,Vérification de position quantique adapté à la pratique(2024) |
| Source: |
https://hal.science/hal-05095776 ; 2025. |
| Publisher Information: |
CCSD |
| Publication Year: |
2025 |
| Subject Terms: |
Quantum Physics (quant-ph); FOS: Physical sciences; [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph] |
| Description: |
Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that $f$-measure and $f$-route, the two best studied NLQC tasks, are in fact equivalent under $O(1)$ overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to $f$-measure. For instance, we obtain sub-exponential upper bounds on $f$-measure for all functions, and efficient protocols for functions in the complexity class $\mathsf{Mod}_k\mathsf{L}$. Beyond this, we study a number of other examples of NLQC tasks and their relationships. |
| Document Type: |
report |
| Language: |
English |
| DOI: |
10.48550/arXiv.2505.23893 |
| Availability: |
https://hal.science/hal-05095776; https://hal.science/hal-05095776v1/document; https://hal.science/hal-05095776v1/file/2505.23893v1.pdf; https://doi.org/10.48550/arXiv.2505.23893 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.172B5F9B |
| Database: |
BASE |