Unitary complexity in polynomial space

William Kretschmer, Ewin Tang

We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP}\ne \mathsf{NEXP}$. Thus, showing un…