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$ Commented Mar 8, 2023 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$ Commented Mar 9, 2023 at 13:51
  • 1
    $\begingroup$ What do you mean? Each Pauli operator is unitary. The final matrix is not unitary, and not supposed to be. $\endgroup$
    – mavzolej
    Commented Mar 9, 2023 at 19:13
  • $\begingroup$ @mavzolej I did not realize the final matrix need not be unitary, that helps! $\endgroup$ Commented Mar 9, 2023 at 21:01

Your Answer

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

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