Block encoding of a diagonal matrix with equidistant eigenvalues

Question

What would be the simplest way to construct a block encoding circuit $U_A$ for a $2^n\times 2^n$ matrix $A$ proportional to $\operatorname{diag}(0,1,2,\ldots,2^n-1)$?

A couple of options I can imagine:

• Use quantum adder $|x, y\rangle\mapsto|x, y+x\rangle$. Requires a number of ancillas equal to $n$.
• Somehow first prepare a diagonal matrix $\operatorname{e}^{iA}$ (probably won't require ancillas) and then calculate its logarithm using QSP.

Due to a very particular form of $A$ I'm hoping that some efficient block encoding may exist, with a number of ancillas logarithmic in $n$ or even constant.

Answer 1

Assume that, $U_n = \operatorname{diag}(0,1,2,\ldots,2^n-1)$

Then,

$U_1 = \frac{1}{2}(I-Z)$

$U_2 = \frac{1}{2}(3II-2ZI-IZ)$

$U_3 = \frac{1}{2}(7III-4ZII-2IZI - IIZ)$

And in general,

$U_n = \frac{1}{2}((2^n - 1)I^{\otimes n}-2^{n-1}ZI^{\otimes (n-1)}-2^{n-2}IZI^{\otimes (n-2)} - ... -I^{\otimes (n-1)}Z$

That is, we can write $U_n$ as a linear combination of $n+1$ unitaries. Which means we can use LCU technique to build the circuit using $\lceil \log(n+1) \rceil$ ancillas.