International Association for Cryptologic Research

International Association
for Cryptologic Research


Omri Shmueli


Scalable Pseudorandom Quantum States 📺
Zvika Brakerski Omri Shmueli
Efficiently sampling a quantum state that is hard to distinguish from a truly random quantum state is an elementary task in quantum information theory that has both computational and physical uses. This is often referred to as pseudorandom (quantum) state generator, or PRS generator for short. In existing constructions of PRS generators, security scales with the number of qubits in the states, i.e.\ the (statistical) security parameter for an $n$-qubit PRS is roughly $n$. Perhaps counter-intuitively, $n$-qubit PRS are not known to imply $k$-qubit PRS even for $k<n$. Therefore the question of \emph{scalability} for PRS was thus far open: is it possible to construct $n$-qubit PRS generators with security parameter $\secp$ for all $n, \secp$. Indeed, we believe that PRS with tiny (even constant) $n$ and large $\secp$ can be quite useful. We resolve the problem in this work, showing that any quantum-secure one-way function implies scalable PRS. We follow the paradigm of first showing a \emph{statistically} secure construction when given oracle access to a random function, and then replacing the random function with a quantum-secure (classical) pseudorandom function to achieve computational security. However, our methods deviate significantly from prior works since scalable pseudorandom states require randomizing the amplitudes of the quantum state, and not just the phase as in all prior works. We show how to achieve this using Gaussian sampling.
(Pseudo) Random Quantum States with Binary Phase
Zvika Brakerski Omri Shmueli
We prove a quantum information-theoretic conjecture due to Ji, Liu and Song (CRYPTO 2018) which suggested that a uniform superposition with random binary phase is statistically indistinguishable from a Haar random state. That is, any polynomial number of copies of the aforementioned state is within exponentially small trace distance from the same number of copies of a Haar random state.As a consequence, we get a provable elementary construction of pseudorandom quantum states from post-quantum pseudorandom functions. Generating pseudorandom quantum states is desirable for physical applications as well as for computational tasks such as quantum money. We observe that replacing the pseudorandom function with a (2t)-wise independent function (either in our construction or in previous work), results in an explicit construction for quantum state t-designs for all t. In fact, we show that the circuit complexity (in terms of both circuit size and depth) of constructing t-designs is bounded by that of (2t)-wise independent functions. Explicitly, while in prior literature t-designs required linear depth (for $$t > 2$$), this observation shows that polylogarithmic depth suffices for all t.We note that our constructions yield pseudorandom states and state designs with only real-valued amplitudes, which was not previously known. Furthermore, generating these states require quantum circuit of restricted form: applying one layer of Hadamard gates, followed by a sequence of Toffoli gates. This structure may be useful for efficiency and simplicity of implementation.


Zvika Brakerski (2)