A no-signalling-based lifting of commitment techniques yields the first single-shot loss-tolerant QPV protocol with exponential security decay in the commitment threshold k and 3.7% noise robustness.
A complexity theory for non-local quantum computation
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
abstract
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.
fields
quant-ph 4years
2026 4verdicts
UNVERDICTED 4representative citing papers
New lower-bound techniques based on controllable correlation and entanglement yield non-trivial bounds for Haar-random two-qubit unitaries and the first known bounds for CNOT, DCNOT, sqrt(SWAP), and XX gates, with a tight result for CNOT.
Reductions link redirecting a quantum system to controlled measurements and Clifford-diagonal-Clifford unitaries, implying equivalent entanglement scaling for many position-verification protocols.
A review compiling upper and lower bounds on entanglement cost for non-local quantum computation and its connections to cryptography, complexity, communication, and quantum gravity.
citing papers explorer
-
Arbitrarily Loss-Tolerant Quantum Position Verification in a Single Execution
A no-signalling-based lifting of commitment techniques yields the first single-shot loss-tolerant QPV protocol with exponential security decay in the commitment threshold k and 3.7% noise robustness.
-
Lower bounds on non-local computation from controllable correlation
New lower-bound techniques based on controllable correlation and entanglement yield non-trivial bounds for Haar-random two-qubit unitaries and the first known bounds for CNOT, DCNOT, sqrt(SWAP), and XX gates, with a tight result for CNOT.
-
Equivalence of non-local computation tasks beyond Clifford operations
Reductions link redirecting a quantum system to controlled measurements and Clifford-diagonal-Clifford unitaries, implying equivalent entanglement scaling for many position-verification protocols.
-
Entanglement cost in non-local quantum computation
A review compiling upper and lower bounds on entanglement cost for non-local quantum computation and its connections to cryptography, complexity, communication, and quantum gravity.