# Block encoding of a diagonal matrix with equidistant eigenvalues

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.

• I'm not sure about block encoding unitaries, but you should be able to recognize $\mathrm{diag}(1,2)^{\otimes{n}}=\mathrm{diag}(1,2,2^2,\cdots,2^n)$ and do something useful Mar 8 at 20:20

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.

• I'm confused: none of these are unitary Mar 9 at 13:51
• What do you mean? Each Pauli operator is unitary. The final matrix is not unitary, and not supposed to be. Mar 9 at 19:13
• @mavzolej I did not realize the final matrix need not be unitary, that helps! Mar 9 at 21:01