We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$
by a single quantum state $|\Psi \rangle$ of size $O(n)$ qubits,
such that:
for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$,
the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved
from $|\Psi \rangle$ by a one-round Arthur-Merlin interactive ... more >>>

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t.

We then show that an ... more >>>

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas. In this paper we survey these results and the quantum toolbox they use.

more >>>

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>>

In differential privacy (DP), we want to query a database about $n$ users, in a way that "leaks at most $\varepsilon$ about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure $n$ quantum states, in a way that "damages the ... more >>>