Many classical computer algorithms can be paralyzed efficiently; what about quantum computers? An algorithm can be described as having layers, one composed with another, with  the depth n of the circuit being the number of layers. An algorithm might be presented as having n simple layers, but if we are able to build more complicated layers, can we construct an equivalent algorithm with a few layers? This  is an issue, which goes back to the early days when people became enthusiastic about the possibility of quantum computers.

One of the most straightforward test cases is called the quantum waterfall or quantum staircase. It is a tensor product analog of a matrix of 2 x 2 blocks supported on the diagonal and the first diagonal below it. It was conjectured in the late 90s that an n layer  quantum waterfall cannot be produced with an algorithm having fewer than order n layers.

This conjecture (Moore-Nillson 1998) turns out to be way too pessimistic and the talk describes recent work with Adam Bene  Watts, Joe Slote, Charlie Chen on a theorem constructing a parallelization of any n layer quantum waterfall which yields  (asymptotically) log n layers.  Gratifying to  operator theorists is that a substantial ingredient is a matrix decomposition originating with Chandler Davis.