Please note: This seminar will take place in DC 2568 and online.
Vahid Asadi, PhD candidate
David R. Cheriton School of Computer Science
A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. In this talk, we will review two classes of NLQC, f-routing and f-BB84, which are of relevance to classical information-theoretic cryptography and quantum position verification, and we will show the first non-trivial lower bounds on entanglement in both settings but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function f(x,y) in terms of the rank of a matrix g(x,y) whose entries are zero when f(x,y)=0, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of f(x,y).
We also prove the number of quantum gates plus single qubit measurements needed to implement a function f is lower bounded linearly by the communication complexity of f in the simultaneous message-passing model with shared entanglement. Because of a relationship between f-routing and the conditional disclosure of secrets (CDS) primitive studied in information-theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS.
To attend this seminar in person, please go to DC 2568. You can also attend virtually on Zoom.