Convergence times for random walks on the unitary group

Series
Math Physics Seminar
Time
Wednesday, March 13, 2024 - 1:00pm for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Shivan Mittal – Department of Physics, The University of Texas at Austin – shivan@utexas.edu
Organizer
Federico Bonetto

Please Note: Available online at: https://gatech.zoom.us/j/98258240051

Consider the following question of interest to cryptographers: A message is encoded in a binary string of length n. Consider a set of scrambling operations S (a proper subset of permutations on n bits). If a scrambling operation is applied uniformly at random from S at each step, then after how many steps will the composition of scrambling operations look like a random permutation on all the bits? This question asks for the convergence time for a random walk on the permutation group. Replace the binary string with a quantum state and scrambling operations in S with Haar random quantum channels on two bits (qudits) at a time. Broadly speaking, we study the following question: If a scrambling operation is applied uniformly at random from S at each step, then after how many steps will the composition of scrambling operations (quantum channels) look like a Haar random channel on all qudits? This question asks about the convergence time for a random walk on the unitary group. Various protocols in quantum computing require Haar random channels, which motivates us to understand the number of operations one would require to approximately implement that channel.

More specifically, in our study, we add a connected-graph structure to scrambling operations (a step on the random walk), where qudits are identified by vertices and the allowed 2-qudit scrambling operations are represented by edges. We develop new methods for lower bounds on spectral gaps of a class of Hamiltonians and use those to derive bounds on the convergence times of the aforementioned random walk on the unitary group with the imposed graph structure. We identify a large family of graphs for which O(poly(n)) steps suffice and show that for an arbitrary connected graph O(n^(O(log(n))) steps suffice. Further we refute the conjectured O(n log(n)) steps for a family of graphs.