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.

  • 1
    $\begingroup$ 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 $\endgroup$ Mar 8 at 20:20

1 Answer 1


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


$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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.