Perfectly Recording Quantum Queries to Random Unitaries and Other Groups: A General Framework for Compressed Oracles
Barak Nehoran | Columbia University
A compressed/recording oracle is a stateful simulation that lazily samples responses to a randomly chosen function or unitary. Zhandry’19 first showed how to record quantum queries to a random function, and this technique has been very fruitful in showing cryptographic security and lower bounds in the random oracle model, since it allows inspecting what the algorithm has learned after t queries to the function. Ma and Huang’24 showed how to approximately record queries to a Haar random unitary, and used it to show the existence of pseudorandom unitaries, but their recording incurs an error of t^2/N for t queries to a unitary of dimension N, limiting its usefulness for lower bounds beyond √N.
We generalize these two techniques to give a generic framework for perfectly recording random unitary representations of any compact Lie group, including but not limited to random unitaries, orthogonal real matrices, and permutations. In fact, we show how to implement perfect recordings in two different but ultimately equivalent ways: The first records a pair of tableaux encoding the symmetries among the queries seen so far (with the tableaux originating from irreducible representations of the group). The second records the Feynman paths explored by the algorithm (encoding the input-output mappings for each query).
While both are perfect and equivalent recordings, the two perspectives allow different ways to interpret and bound the information learned by any quantum query algorithm.
Based on joint work with Alex Lombardi, Fermi Ma, and John Wright
Location
-
QNC 1201
-
-
Meeting ID: 940 9024 0234
-
Passcode: 938174
-