Are controlled unitaries helpful?

Understand

Many quantum algorithms, to compute some property of a unitary $U$, require access not just to $U$, but to $cU$, the unitary with a control qubit.

• We show that having access to $cU$ does not help for a large class of quantum problems.
• For a quantum circuit which uses $cU$ and $cU^\dagger$ and outputs $|\psi(U)\rangle$, we show how to "decontrol" the circuit into one which uses only $U$ and $U^\dagger$ and outputs $|\psi(\varphi U)\rangle$ for a uniformly random phase $\varphi$, with a small amount of time and space overhead.
• When we only care about the output state up to a global phase on $U$, then the decontrolled circuit suffices.