5
$\begingroup$

Consider a Haar random unitary $U$.

I am trying to compute the value (or put a bound on)

\begin{equation} \mathbb{E}\left[\left|\langle 0^{n} |U^{2} |0^{n}\rangle\right|^{2}\right]. \end{equation}

The expectation is taken over the choice of the circuit.


We know that \begin{equation} \mathbb{E}\left[\left|\langle 0^{n} |U |0^{n}\rangle \right|^{2}\right] = \frac{1}{2^{n}}. \end{equation}

Multiplication by another unitary $U$ should "scramble" the probability even more, but what might be a way to prove that?

$\endgroup$
3
  • $\begingroup$ "The expectation is taken over the choice of the circuit." Do you mean that you integrate over all Haar-random $U$? If so, are you familiar with unitary designs? $\endgroup$
    – JSdJ
    Jun 10, 2022 at 9:38
  • 2
    $\begingroup$ A wild guess- a Haar random unitary applied twice has the same distribution as another Haar random unitary. I would bet that there’s a one-one correspondence between the two, and applying a given unitary twice has the same expectation as applying it once. What would “more scrambled” even mean? $\endgroup$ Jun 10, 2022 at 12:01
  • $\begingroup$ I don’t think unitary designs talk of applying the same unitary twice. $\endgroup$
    – BlackHat18
    Jun 10, 2022 at 15:07

1 Answer 1

8
$\begingroup$

There is an explicit formula for the integral with respect to the Haar measure of any polynomial in the entries of a unitary and its conjugate, due to Collins and Śniady:

Benoît Collins and Piotr Śniady. Integration with Respect to the Haar Measure on Unitary, Orthogonal and Symplectic Group. Communications in Mathematical Physics 264: 773-795, 2006. [arXiv:math-ph/0402073]

I won't actually write down the formula in this answer, it can be found in the paper. For high-degree polynomials you need to know some things about the representation theory of the symmetric group to evaluate it, but for low-degree polynomials it's easy enough to just look up the required values.

Let me rewrite the question using notation that matches with Collins and Sniady: we'll assume the rows and columns of the unitary $U$ we're integrating over are indexed by the integers $1,\ldots,d$, so $d = 2^n$, and we'll denote the $(i,j)$ entry of $U$ by $U_{i,j}$. The question asks for the value $$ \int \bigl\vert \bigl(U^2\bigr)_{1,1} \bigr\vert^2 \mathrm{d}U $$ where the integral is with respect to Haar measure for $d\times d$ unitary matrices.

We need to rewrite the integrand. We have $$ \bigl(U^2\bigr)_{1,1} = \sum_{i=1}^d U_{1,i} U_{i,1} $$ and therefore $$ \bigl\vert \bigl(U^2\bigr)_{1,1} \bigr\vert^2 = \sum_{i=1}^d\sum_{j=1}^d U_{1,i} U_{i,1} \overline{U_{1,j}} \overline{U_{j,1}}. $$

From the formula of Collins and Sniady, we can conclude this: $$ \int U_{1,i} U_{i,1} \overline{U_{1,j}} \overline{U_{j,1}} \, \mathrm{d}U = \begin{cases} \frac{2}{d(d+1)} & i = j = 1\\ \frac{1}{d^2-1} & i = j \not= 1\\ 0 & i\not=j. \end{cases} $$ Therefore, the value we're looking for is $$ \int \bigl\vert \bigl(U^2\bigr)_{1,1} \bigr\vert^2 \mathrm{d}U = \frac{2}{d(d+1)} + (d-1) \frac{1}{d^2 - 1} = \frac{d+2}{d(d+1)}. $$

Switching back to the notation in the original question gives $$ \mathbb{E}\Bigl[ \bigl\vert \langle 0^n \vert U^2 \vert 0^n\rangle \bigr\vert^2\Bigr] = \frac{2^n + 2}{2^n(2^n+1)} = \frac{2^{n-1} + 1}{2^{n-1}(2^n+1)}, $$ which is ever-so-slightly larger than $1/2^n$.

So, unless I made a mistake in this calculation (which is a definite possibility — it should be checked carefully), the intuition that applying a unitary twice scrambles the probability more is wrong: it scrambles it slightly less. It's kind of like vitamins: taking twice as much as you need isn't better for you, it's actually a little bit worse.

$\endgroup$
2
  • 2
    $\begingroup$ maybe an intuitive way to understand this is to observe that unitaries equal/close to the identity are preserved by the squaring operation, while others are not, thus resulting in a distribution more skewed towards matrices close to the identity? At the very least, some quick numerics points in this direction, see i.stack.imgur.com/KFGA8.png $\endgroup$
    – glS
    Jun 14, 2022 at 15:27
  • $\begingroup$ Thanks, as always, for a great answer! :) @John Watrous $\endgroup$
    – BlackHat18
    Jun 14, 2022 at 22:13

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.