2019-01-03 | Zhengfeng Ji：Pseudorandom Quantum States and Quantum Money
We propose the concept of pseudo-random quantum states, which appear random to any quantum polynomial-time adversary. It offers a computational approximation to perfectly random quantum states analogous in spirit to cryptographic pseudo-random generators, as opposed to statistical notions of quantum pseudo-randomness that have been studied previously, such as quantum t-designs analogous to t-wise independent distributions.
Under the assumption that quantum-secure one-way functions exist, we present efficient constructions of pseudorandom states, showing that our definition is achievable. We then prove several basic properties of pseudo-random states, which show the utility of our definition. First, we show a cryptographic no-cloning theorem: no efficient quantum algorithm can create additional copies of a pseudo-random state, when given polynomially-many copies as input. Second, as expected for random quantum states, we show that pseudo-random quantum states are highly entangled on average. Finally, as a main application, we prove that any family of pseudo-random states naturally gives rise to a private-key quantum money scheme.
Zhengfeng Ji is currently a Professor of the Centre for Quantum Software and Information (QSI), Faculty of Engineering and Information Technology (FEIT), University of Technology Sydney. He received BEng and PhD from the Department of Computer Science and Technology, Tsinghua University, Beijing, China in 2002 and 2007. His current research interests include quantum algorithms, quantum complexity theory and (post-)quantum cryptography.