Abstract:

The unitary synthesis problem (Aaronson-Kuperberg CCC’07) asks whether an arbitrary n-qubit unitary U can be implemented by a polynomial size quantum circuit, given access to some classical oracle f_U that depends on U. Recently, it was proved (Lombardi-Ma-Wright STOC’24) that for a Haar-random unitary, this is impossible for any efficient synthesis algorithm that makes only one query (or polynomially many parallel queries) to an arbitrary classical oracle. 

In this work, we extend this line of lower bound for random unitaries to a finer structural understanding of one-query synthesis for natural explicit families. In particular, we prove one-query lower bounds for explicit families of unitaries that have efficient two-query synthesis algorithms, thereby separating the power of one-query and two-query synthesis algorithms. We also give a one-query algorithm for complex phase unitaries that achieves constant approximation, and prove a sharper separation between one-query unitary synthesis and quantum programs.