A complexity theory for non-local quantum computation (2025)
Finds relations between a wide range of different NLQC tasks, including showing that $f$-routing and $f$-BB84 are equivalent, with a constant-overhead reduction between them.
- from
- Position-Based Quantum Cryptography
- added
- 2026-10-10
- likes
- 0
similar
-
Relating non-local quantum computation to information theoretic cryptography (2023) doi.org
Connects $f$-routing to topics in classical cryptography, in particular conditional disclosure of secrets. Shows a sub-exponential upper bound for attacks for any $f$ and finds an $f$ that is believed to be outside of $\mathsf{P}$ (with pre-processing), but efficiently attacked.
-
Complexity and entanglement in non-local computation and holography (2022) doi.org
Notes that the necessary attack resource requirements are controlled by the entangled part of the task unitary. Shows that for tasks where one side is classical input information, a doubly-logarithmic (later improved to logarithmic) lower bound and exponential upper bound (in…
-
Introduces a rooster of different QPV protocols like BB84 QPV, $f$-routing, $f$-BB84 QPV and variations of them. Mentions entanglement-based attacks on some of them.
-
Non-local computation of quantum circuits with small light cones (2022) arxiv.org
Provides a general attack on QPV based on the geometric structure of a circuit decomposition of the task unitary. Is more efficient for certain classes of unitaries than previous general attacks.
-
Code-routing: A new attack on position verification (2023) doi.org
Provides a new attack on $f$-routing, connecting attacks to secret-sharing schemes and span programs, and showing that any $f \in \mathsf{Mod}_p\mathsf{L}$ (with pre-processing), for $p$ prime, can be attacked efficiently.
-
Quantum Computing Q# Introduction 2018 github.com
Position-Based Quantum Cryptography › Towards Understanding NLQC: “Finds relations between a wide range of different NLQC tasks, including showing that $f$-routing and $f$-BB84 are equivalent, with a constant-overhead reduction between them.”