Pseudorandom states, introduced by Ji, Liu and Song (Crypto'18), are efficiently-computable
quantum states that are computationally indistinguishable from Haar-random states. One …

We prove that random quantum circuits on any geometry, including a 1D line, can form
approximate unitary designs over $ n $ qubits in $\log n $ depth. In a similar manner, we …

While quantum state tomography is notoriously hard, most states hold little interest to
practically minded tomographers. Given that states and unitaries appearing in nature are of …

We construct a classical oracle relative to which P= NP yet single-copy secure
pseudorandom quantum states exist. In the language of Impagliazzo's five worlds, this is a …

In the classical model of computation, it is well established that one-way functions (OWF) are
minimal for computational cryptography: They are essential for almost any cryptographic …

We construct a quantum oracle relative to which $\mathsf {BQP}=\mathsf {QMA} $ but
cryptographic pseudorandom quantum states and pseudorandom unitary transformations …

Uniformly random unitaries, ie unitaries drawn from the Haar measure, have many useful
properties, but cannot be implemented efficiently. This has motivated a long line of research …

The existence of one-way functions is one of the most fundamental assumptions in classical
cryptography. In the quantum world, on the other hand, there are evidences that some …

One-way functions are central to classical cryptography. They are necessary for the
existence of non-trivial classical cryptosystems, and also sufficient to realize meaningful …

The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit
unitary U can be implemented by an efficient quantum algorithm A augmented with an …