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 >>>