AI summaryⓘ
The authors study pseudorandom unitaries (PRUs), which are quantum operations that look random but are generated by a fixed method. They focus on the challenge of making PRUs whose security can scale independently of their size, a problem nobody has solved yet. The authors show that if such scalable PRUs exist under current analysis methods, it would solve a major open question in quantum computing about implementing arbitrary quantum operations efficiently. They also connect these PRUs to other concepts like unitary designs and the unitary synthesis problem, proving that any approach must use a classical oracle with input length close to twice the logarithm of the unitary's dimension. This result rules out many existing PRU proposals and suggests that their idealized model, ROM-PRUs, is valuable for future research.
pseudorandom unitariesquantum complexity theoryrandom oracle modelunitary synthesis problemapproximate unitary designsepsilon-netsquantum cryptographysecurity parameterclassical oraclequantum dimension
Authors
Zvika Brakerski, Henry Yuen
Abstract
We consider the task of constructing pseudorandom unitaries (PRUs) with scalable security, i.e. families in which the security parameter may vary independently of the dimension (or input bit-length). It is not known whether scalable PRUs can be constructed. In this work we show that if scalable PRUs can be constructed via the prevailing paradigm for analyzing PRUs, then there would be a positive solution to the Aaronson-Kuperberg unitary synthesis problem, a longstanding question in quantum complexity theory about whether implementing arbitrary unitaries can be efficiently reduced to computing a Boolean function. Specifically, we formalize the notion of ROM-PRUs, which are statistically secure PRUs in the random oracle model (ROM). All prior known constructions of cryptographically secure PRUs are based on a ROM-PRU construction. We prove novel connections between ROM-PRUs, approximate unitary designs, epsilon-nets over the unitary group, and the unitary synthesis problem. In particular, we prove that any unitary synthesis algorithm (and thus any ROM-PRU) must use a classical oracle with input length (2 - o(1)) log d bits, where d is the dimension of the unitary to be implemented. This bound rules out all existing candidates for scalable PRUs in the literature. Together, these connections indicate that ROM-PRUs provide a fruitful idealized model for studying pseudorandom unitaries.