A complexity theory for non-local quantum computation
with Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, and Henry Yuen
Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. They include attacks on quantum position verification (QPV) protocols as special cases. 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, attacks on the two most promising QPV protocols, 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. Beyond this, we study a number of other examples of NLQC tasks and their relationships. [arXiv]
Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss
with Rene Allerstorfer, Harry Buhrman, Matthias Christandl, Llorenç Escolà-Farràs, Florian Speelman, and Philip Verduyn Lunel
A big challenge on the way towards practical protocols for secure quantum position-verification is the fact that in experimental setups e.g. using fiber optics, most of the photons sent get lost. That can compromise the security of protocols of interest. We prove that adding a commitment step, we can prove security for a large class of protocols against arbitrary photon loss, thereby exhibiting the first protocol that is both secure against photon loss, secure against entangled attackers, can allow the quantum information to travel slowly, and is simple for the honest parties. This makes the protocol an ideal candidate for experimental implementation. [arXiv]
A single-qubit position verification protocol that is secure against multi-qubit attacks
with Matthias Christandl and Florian Speelman
Imagine that you sit in front of a computer and look at a website that looks like the website of your bank. But how can you be sure that it is genuine? If you could verify that the server is indeed in the basement of the bank, you could stop worrying. This is the idea behind position-based cryptography: The position of a party is used as a credential. Unfortunately, secure position-verification, the fundamental building block of position-based cryptography, is classically impossible. However, quantum protocols for this task exist. We put forward the hitherto simplest such protocol and prove that it is secure as long as the attackers have at most an amount of qubits linear in the classical information sent during the protocol, while the honest parties only need a single qubit. Since classical bits are much easier to control than qubits, this makes the protocol secure in practice. [journal] [arXiv]