Pseudorandomness via Noisy Quantum devices

Abstract

Randomness has widespread applications in classical as well as quantum computing. Clas- sical computing entails random numbers, functions, permutations, etc. while the quantum analogue is the Haar random unitaries and random quantum states. Similar to the classical case, quantum randomness can’t be prepared efficiently thus leading to the requirement for a notion of pseudorandomness which is easy to prepare but at the same time, hard to dis- tinguish from true randomness. There has been recent progress in the direction of quantum pseudorandomness which involves constructions of pseudorandom states and variants of pseudorandom unitaries. The field of quantum pseudorandomness opens an area of a more general idea of computationally efficient quantum information. In this thesis, we briefly review the current understanding of quantum pseudorandom- ness and try to look at their existence in near-term quantum computers which can have significant noise. Furthermore, we look at new flavors of quantum pseudorandomness in- volving pseudorandom density matrices and pseudorandomness with new assumptions. We then look at the advantages these flavors provide, primarily looking at the advantage of noise robustness. We argue that for a complete understanding of computationally efficient quantum information, notions like pseudorandom density matrices, pseudorandom quan- tum channels etc. should be explored which can provide new light and approach to various fields like pseudo-resource theories, learning of mixed quantum states and CPTP channels etc in the same way as pseudorandom states has proven to be useful.