Exponentiating a tensor product of operators acting on disjoint qubit registers

Question

Consider a problem of implementing $\operatorname{e}^{i\bigotimes_j O_j}$, where all the $O_j$ terms act on disjoint sets of qubits. Assume that efficient circuits implementing individual $\operatorname{e}^{i\ O_j}$ are known. Moreover, if necessary, one can also assume that the corresponding registers are relatively small so that efficient circuits $U_j$ for diagonalizing $O_j$ are known (different definitions of "small" or any other assumptions on $O_j$ are welcome too).

Is there a way to efficiently and exactly implement $\operatorname{e}^{i\bigotimes_j O_j}$?

My question is driven by the desire to generalize a well-known procedure for exponentiating Pauli terms $\operatorname{e}^{iXYZ\ldots}$, which is achieved by first rotating to eigenbases of individual qubits, and then using the cascade of $\text{CNOT}$s as in Fig 4.19 of Nielsen&Chuang.

Answer 1

I think the following would work:

1. Perform phase estimation individually against each $O_j$, creating phase estimate registers $a_j$.
2. Compute the superposed product $t = \prod_j a_j$.
3. Phase by an amount proportional to $t$.
4. Uncompute $t$.
5. Uncompute each $a_j$.

For the Pauli operator case it's easy to see why this works. Each operator has an eigenvalue of -1 or +1, and computing the product $t$ accumulates the -1 factors into one spot, so that when you phase by an amount proportional to $t$ you are phasing forward if there's an even number of -1s and backward if there's an odd number.