Results 401 - 410 of 23740

In this talk we will see how to classically verify the correctness of any quantum computation without destroying the prover's initial quantum state, and without needing to clone it.  Previous approaches destroyed the prover's quantum state and required the prover to clone its state.  The soundness of our scheme is based on the post-quantum Learning With Errors (LWE) assumption.  

This talk is based on a joint work with Dakshita Khurana and Justin Raizes.  No prior quantum knowledge will be assumed. 
 

We propose an extension of Yao's standard two-party communication model, where Alice and Bob respectively hold probability distributions p and q over inputs to a function f, rather than singleton inputs. Their goal is to estimate E[f(x,y)] to within additive error eps where x is drawn from p and y is drawn (independently) from q. We refer to this as the distributed estimation problem for f. We motivate this problem by showing that communication problems that have been studied in sketching, databases and learning are instantiations of distributed estimation for various functions f. Our goal is to understand how the required communication scales with the communication complexity of f and the error parameter eps. 

The naive sampling protocol achieves communication that scales as O(1/eps^2). We design a new debiasing protocol for arbitrary bounded functions that requires communication only linear in 1/\eps, and gives better variance reduction than random sampling. We develop a novel spectral technique to show lower bounds for distributed estimation, and use it to show that the Equality function is the easiest full rank Boolean function for distributed estimation. This technique yields tight lower bounds for most functions, with set-disjointness being the exception that proves the rule.

Based on joint work with Raghu Meka (UCLA), Prasad Raghavendra (UC Berkeley), Mihir Singhal (UC Berkeley) and Avi Wigderson (IAS).