Alexander Russell

We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access. In the case of simulating random states, the ideal object is an inputless oracle which outputs the same Haar-random n-qubit state whenever it is invoked. In the case of simulating random unitaries, the ideal object is an oracle which applies to its input the same Haar-random n-qubit unitary operator whenever it is invoked. This problem has only been previously considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs. In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error. These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.

This talk will survey some recent developments in the theory of quantum computation in groups, focusing on two primary research efforts: development of efficient quantum Fourier transforms and development of efficient solutions to hidden subgroup problems. Quantum Fourier transforms. The talk will describe a "quantization" of the successful separation of variables technique, the generic framework responsible for most known efficient classical Fourier transform algorithms. This results in a wide family of efficient quantum circuits for the quantum Fourier transform, recovering all known efficient quantum Fourier transforms and providing efficient transforms for many new groups. In addition, it gives the first subexponential quantum circuits for the Fourier transform over several interesting linear groups. Hidden subgroup problems. The talk will discuss some recent advances in our understand of the hidden subgroup problems, discussing new closure properties and solutions for families of groups which appear to require the strong standard method.