  We improve the number of $T$ gates needed for a $b$-bit approximation of a
multiplexed quantum gate with $c$ controls applying $n$ single-qubit arbitrary
phase rotations from $4n b+\mathcal{O}(\sqrt{cn b})$ to $2n
b+\mathcal{O}(\sqrt{cn b})$, and reduce the number of qubits needed by up to a
factor of two. This generic quantum circuit primitive is found in many quantum
algorithms, and our results roughly halve the cost of state-of-art electronic
structure simulations based on qubitization of double-factorized or
tensor-hypercontracted representations. We achieve this by extending recent
ideas on stochastic compilation of quantum circuits to classical data and
discuss space-time trade-offs and concentration of measure in its
implementation.
