1
$\begingroup$

Let $|\psi\rangle \in \mathbb{C}^{2n}$ be a random quantum state such that $ |\langle z| \psi \rangle|^{2} $ is distributed according to a $\text{Dirichlet}(1, 1, \ldots, 1)$ distribution, for $z \in \{0, 1\}^{n}$.

Let $z_{1}, z_{2}, \ldots, z_{k}$ be $k$ samples from this distribution (not all unique). Choose a $z^{*}$ that appears most frequently.

  1. I am trying to prove:

$$\underset{|\psi\rangle}{\mathbb{E}}\big[|\langle z^{*}| \psi \rangle|^{2}\big] = \underset{|\psi\rangle}{\mathbb{E}}\bigg[\underset{m}{\mathbb{E}}\big[|\langle z^{*}| \psi \rangle|^{2} ~| ~m\big]\bigg] = \mathbb{E}\bigg[\frac{1+m}{2^{n}+k}\bigg],$$ where $m$ is a random variable that denotes the frequency of $z^{*}$.

  1. I am also trying to prove that for the collection $z_{1}, z_{2}, \ldots, z_{k}$ $$\sum_{i \neq j}\mathrm{Pr}[z_{i} = z_{j}] = {n \choose k}\frac{2}{2^{n} + 1}. $$

Basically, I am trying to trace the steps of Lemma $13$ (page 10) of this quantum paper. I realize that my questions have to deal with posteriors and priors of the chosen distribution (though I do not understand how they have been explicitly derived or used here. An explicit derivation will be helpful). Is there any resource where I can find quick formulas for calculating these for other distributions, like the Binomial distribution?

$\endgroup$
2
$\begingroup$

Let $ p_i = |\langle i | \phi \rangle|^2 \sim Dir(a_1, .., a_{2^n}) = Dir(1, .., 1) $ and $ m_i $ the occurences of outcome $ |i\rangle $ on samples $z_1, .. z_k$.

Since the Dirichlet distribution is the conjugate prior of the categorical (see here), meaning

$ \bf{p} $ $| Z, (1, .. 1), $ $\bf{m} $ $ \sim Dir(2^n, $ $\bf{m} + 1$)

and using the formula for the mean value of Dirichlet we get

$ \mathbb{E}[p_{z*} | m] = \frac{m+1}{\sum_{j=1}^{2^n} (m_j + 1)} = \frac{m+1}{2^n + k} $

For the second claim, take $ i \neq j $ and compute \begin{align*} \mathbb{P}[z_i = z_j] &= \int \mathbb{P}[z_i = z_j | (p_1, .. p_{2^n})] \cdot f(p_1, .. p_{2^n}) \\ &= \int \sum_{k=0}^{2^n} p_k^2 \cdot f(p_1, .. p_{2^n}) \\ &= \sum_{k=0}^{2^n} \mathbb{E}[p_k^2] \\ &= \sum_{k=0}^{2^n} \frac{2}{2^n(2^n + 1)} = \frac{2}{2^n + 1} \end{align*}

(the last equality holds since $ \bf{x} $ $ \sim Dir($$\bf{a}$) $ \implies \mathbb{E}[x_i^2] = \frac{a_i(a_i + 1)}{a_0(a_0 + 1)} $, $ a_0 = \sum_{i=1}^{N} a_i $.

This means that $ \sum_{i \neq j} \mathbb{P}[z_i = z_j] = {k \choose 2} \frac{2}{2^n + 1} $.

$\endgroup$
11
  • 1
    $\begingroup$ By $ Z $ i refer to the collections of all the samples $ z_1, .. z_k $. Also $ \sum_{j=1}^{2^n} (m_j + 1) = \sum_{j=1}^{2^n} m_j + \sum_{j=1}^{2^n}1 = k + 2^n $ since the first sum simply counts the number of samples. In general you need $2^n $ concentration paramaters $ a_i $ for the Dirichlet distribution to generate points in the $2^n-1$ simplex. Finally, i only used different parameters for the prior and the posterior distributions $\endgroup$ – tsgeorgios Oct 6 '20 at 9:34
  • 1
    $\begingroup$ I define $ m_i $ to be the number of occurences of $|i\rangle$ and then i write $m_{z*} = m $. $ \sum_{j=1}^{2^n} m_j = \sum_{j=1}^{2^n} \sum_{l=1}^{k} \delta_{z_l, j} = \sum_{l=1}^{k} \sum_{j=1}^{2^n} \delta_{z_l, j} = \sum_{l=1}^{k} 1 = k $ $\endgroup$ – tsgeorgios Oct 6 '20 at 10:12
  • 1
    $\begingroup$ $ \mathbb{P}[z_i = z_j | (p_1, .., p_{2^n})] = \sum_{k=0}^{2^n} \mathbb{P}[z_i = k | (p_1, .., p_{2^n}), z_j = k] \cdot \mathbb{P}[z_j = k | (p_1, .., p_{2^n})] = \sum_{k=0}^{2^n} p_k \cdot p_k = \sum_{k=0}^{2^n} p_k^2 $ since $z_i, z_j $ independent. For the integral sign i used that $ \int p_k^2 \cdot f(p_1, .. p_{2^n}) = \mathbb{E}[p_k^2] $ since $f $ is the p.d.f $\endgroup$ – tsgeorgios Oct 6 '20 at 10:21
  • 1
    $\begingroup$ Well, each $ z_k $ takes the value $ |i \rangle $ with probability $ p_i $. This means that $ z_k | $ $\bf{p}$ is distributed according to the categorical. The "valid" distributions for $(p_1, .. p_{2^n}) $ are multivariate distributions defined on a simplex, since it must hold that $ \sum_{i} p_i = 1 $. The binomial is not one of them. For other "valid" distributions, i don't believe that there are some nice formulas that you can write down but honestly, i don't know. $\endgroup$ – tsgeorgios Oct 6 '20 at 11:02
  • 1
    $\begingroup$ We are taking the expectation condtional on $\bf{m}$. If we know Z, then we know $\bf{m}$. $\endgroup$ – tsgeorgios Oct 6 '20 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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