Ran Raz

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

Andris Ambainis, Joseph Emerson

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

Andrew Drucker, Ronald de Wolf

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 >>>Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner

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

Scott Aaronson, Guy Rothblum

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