Mikka Stasiuk

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.

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.

Quantum key distribution (QKD) aims to extract secret keys from correlations between quantum systems. Most QKD research focuses on "device-dependent" protocols whose security is conditioned on their quantum devices operating within specified tolerances. These assumptions on device operation render device-dependent protocols vulnerable to attacks that exploit the differences in real devices and their models in security proofs, and hence threaten the security of such protocols. Alternatively, Device-independent (DI) QKD seeks to achieve security with minimal assumptions on quantum devices by relying on quantum correlations that violate Bell inequalities, overcoming this short-coming of device-dependent QKD. Our work is motivated by the following two observations. First, DIQKD is more secure but has worse noise and loss tolerances than device-dependent QKD. This point has motivated investigations into new techniques to improve these tolerance thresholds such as random key generation, random post-selection, noisy pre-processing and advantage distillation, the last of which we investigate, and which describes a two-way communication procedure in the error correction step of the protocol. Second, the precise circumstances in which DIQKD is possible are unclear, since not all correlations that violate Bell inequalities can be used to distill a secret key in DIQKD. Under the independent and identically distributed (IID) collective attacks framework, previous work sought to resolve both problems by implementing DIQKD with an advantage distillation protocol called the repetition-code protocol. The authors derived both a sufficient and a conjectured necessary condition for security based on the fidelity between some states in the protocol. However, the significance of their results was limited by a gap between the two security conditions, which prevented the calculation of tight noise tolerance bounds and suggested that the fidelity is not the right quantity to consider to characterize exactly when key distillation in DIQKD is possible. Furthermore, in our work we replace the fidelity in the security proofs with the quantum Chernoff divergence, a measure of distinguishability in symmetric hypothesis testing, and achieve equivalent sufficient and necessary conditions for security for the repetition-code DIQKD protocol under the i.i.d collective attacks framework. Consequently, our work strongly indicates that quantum Chernoff divergence is the relevant quantity to describe the security of the repetition-code DIQKD protocol. With our new security condition, we show that the noise tolerance thresholds of the repetition-code DIQKD protocol outperform even one-way DIQKD protocols implemented with noisy pre-processing and random key measurements.