On the distribution of the fidelity of a random product state with an arbitrary many-qubit state

Question

Consider an arbitrary $n$-qubit state $\lvert \psi \rangle$. How much do we understand about the probability distribution of the fidelity of $\lvert \psi \rangle$ with a tensor product $\lvert \alpha \rangle = \lvert \alpha_1 \rangle \lvert \alpha_2 \rangle \cdots \lvert \alpha_n \rangle$ of Haar-random pure states $\lvert \alpha_j \rangle$?

It seems to me that the mean fidelity will be $1/2^n$ (taking fidelity to be measured in units of probability, i.e., $F(\lvert\alpha\rangle,\lvert\psi\rangle) = \lvert \langle \alpha \vert \psi \rangle \rvert^2$). For instance, we can consider the fidelity instead of $\lvert \psi \rangle$, subject to a tensor product of Haar-random single-qubit unitaries, with the state $\lvert 00\cdots0 \rangle$. It seems to me that, up to phases, the Haar-random unitaries on $\lvert \psi \rangle$ will in effect randomise the weights of the components of $\lvert \psi \rangle$ over the standard basis. The expected fidelity with any particular standard basis state would then be the same over all standard basis states, i.e. $1/2^n$.

Question.

What bounds we can describe on the probability, that the fidelity will will differ much from $1/2^n$ (either in absolute or relative error) — without making any assumptions about the amount of entanglement or any other features of $\lvert \psi \rangle$?

Answer 1

All you need are simple tools from measure concentration. The setup is as follows (repeated from the question above for completeness): $| \psi \rangle$ is an $n$-qubit state and $| \alpha \rangle := | \alpha_{1} \rangle \otimes | \alpha_{2} \rangle \otimes \cdots \otimes | \alpha_{n} \rangle$ is an $n$-qubit product state where each $| \alpha_{j} \rangle$ is Haar-randomly distributed.

Let $\mathbb{E}_{U}$ denote Haar-averaging, for example, $\mathbb{E}_{U} \left[ UXU^{\dagger} \right] \equiv \int dU U X U^{\dagger} = \operatorname{Tr}\left[ X \right] \frac{\mathbb{I}}{d}$, which is a simple lemma that follows immediately from the left/right invariance of the Haar measure. In fact, this simple lemma is all we'll need to compute the mean.

Let's assume each $| \alpha_{j} \rangle$ is independently Haar-distributed, that is, for each $j$ we have, $| \alpha_{j} \rangle \langle \alpha_{j} | = U_{j} | j \rangle \langle j | U^{\dagger}_{j}$ where the $U_{j}$ is Haar-distributed. Namely, I'm assuming each qubit product state to be a random Haar qubit state. Then, for the case of $n=1$, we have, \begin{align} F(| \psi \rangle, | \alpha_{1} \rangle) = \left| \left\langle \psi | \alpha_{1} \right\rangle \right|^{2} = \operatorname{Tr}\left[ \left( | \psi \rangle \langle \psi | \right) \left( | \alpha_{1} \rangle \langle \alpha_{1} | \right) \right] = \operatorname{Tr}\left[ \left( | \psi \rangle \langle \psi | \right) U_{1} | 1 \rangle \langle 1 | U^{\dagger}_{1} \right], \end{align} where $U_{1}$ is Haar-distributed. Using the lemma above, we have, \begin{align} \mathbb{E}_{U} \left[ F(| \psi \rangle, | \alpha_{1} \rangle) \right] = \frac{1}{2} \operatorname{Tr}\left[ | \psi \rangle \langle \psi | \right] \operatorname{Tr}\left[ | 1 \rangle \langle 1 | \right] = \frac{1}{2}. \end{align}

Similarly, for the $n$-qubit case, (again, assuming each $| \alpha_{j} \rangle$ is i.i.d according to the Haar measure), \begin{align} \mathbb{E}_{\{ U_{j} \}} F(| \psi \rangle, | \alpha \rangle) = \mathbb{E}_{\{ U_{j} \}} \operatorname{Tr}\left[ | \psi \rangle \langle \psi | \left( \otimes_{j=1}^{n} U_{j} | j \rangle \langle j | U^{\dagger}_{j} \right)\right] = \frac{1}{2^{n}}, \end{align} since we can apply the above single-qubit result repeatedly to each of the $n$ product states, each of which gives us a factor of $\frac{1}{2}$. Therefore, yes, the expected value of the fidelity is $\frac{1}{2^{n}}$.

As for the bounds on deviations from this average, notice that, using measure concentration, the probability of a single instance of the fidelity between $| \psi \rangle$ and $| \alpha \rangle$ deviating from the mean is exponentially suppressed. More precisely, using Levy's lemma, let $U$ be Haar-distributed and $f:U(d) \rightarrow \mathbb{R}$ be a Lipschitz continuous function (here $U(d)$ is the unitary group on a single tensor factor), then, for any $\epsilon >0$, \begin{align} \mathrm{Prob} \{ \left| f(U) - \overline{f} \right| \geq \epsilon \} \leq \exp \left[ - \frac{d \epsilon^{2}}{4 K^{2}} \right], \end{align} where $\overline{f}$ is the Haar-averaged value of $f$ and $K$ the Lipschitz constant that depends on the function $f$. Recall that, a function $f:U(d) \rightarrow \mathbb{R}$ is said to be Lipschitz continuous with constant $K$ if \begin{align} \left| f(V) - f(W) \right| \leq K \left\Vert V - W \right\Vert_{2}, ~~\forall V,W \in U(d). \end{align} For the case of fidelity, we now need to think of the states $| \psi \rangle$ and $\otimes_{j=1}^{n}| j \rangle$ as fixed and $U$ as an input and compute $K$ for this function. Using a sequence of simple bounds, one can show that $K=2$ suffices (see a short proof at the end). Therefore, deviations from the $\frac{1}{2^{n}}$ are exponentially suppressed in the dimension $d = 2^{n}$ and double-exponentially suppressed in the number of qubits $n$.

Hints for computing the Lipschitz constant for a unitary acting on a single tensor factor: I'm sure there are easier ways to compute this, but I find the following calculation more elegant. Let's consider the following, $f(U):= f(U, | \psi \rangle, | j \rangle)= \operatorname{Tr}\left[ | \psi \rangle \langle \psi | U | j \rangle \langle j | U^{\dagger} \right]$. Notice that I'm not going to assume $U$ is a single-qubit unitary rather an $d$-dimensional one. Then, define $\rho = | \psi \rangle \langle \psi | , \Pi_{j} = | j \rangle \langle j |$ and we can rewrite $f(U) = \operatorname{Tr}\left[ \left( \rho \otimes \Pi_{j} \right) \left( U \otimes U^{\dagger} \right) \mathbb{S}\right]$, where $\mathbb{S}$ is the swap operator between the two copies of the Hilbert space. Now, \begin{align} \left| f(V) - f(W) \right| = \left| \operatorname{Tr}\left[ \left( \rho \otimes \Pi_{j} \right) \left( V \otimes V^{\dagger} - W \otimes W^{\dagger} \right) \mathbb{S} \right] \right| \leq \left\Vert \rho \otimes \Pi_{j} \right\Vert_{1}^{} \left\Vert \left( V \otimes V^{\dagger} - W \otimes W^{\dagger} \right) \mathbb{S} \right\Vert_{\infty}^{}, \end{align} where we have used the Cauchy-Schwarz inequality, $\left| \operatorname{Tr}\left[ AB \right] \right| \leq \left\Vert A \right\Vert_{1}^{} \left\Vert B \right\Vert_{\infty}^{} $. Now, since $\rho \otimes \Pi_{j}$ is a state, $\left\Vert \rho \otimes \Pi_{j} \right\Vert_{1}^{} = 1$. And since $\mathbb{S}$ is a unitary, and using submultiplicativity of the $\left\Vert \cdot \right\Vert_{\infty}^{} $ we have, $\left| f(V) - f(W) \right| \leq \left\Vert \left( V \otimes V^{\dagger} - W \otimes W^{\dagger} \right) \right\Vert_{\infty}^{}$. Some simple algebra from this point onwards shows that $K = 2$ suffices.

Answer 2

The required fidelity $F$ is a function of the Cartesian product of the single $n$-qubit state space: $CP^{2^n-1}$ and $n$ copies of a single qubit state space: $CP^{1} \cong S^2$. The statistics of $F$ is computed for a sample space drawn uniformly from the state space regarded as a probability space with respect to its Fubini-Study measure.

An explicit expression of $F$ is given in coordinates, and the assumption of the average: $<F> = \frac{1}{2^n}$ is validated by a direct integration.

Next, the probability density function of $F$ is computed again by a direct integration (and found to be a beta distribution with parameters $\alpha = 1$, $\beta = 2^n-1$).

The computation results are compared to a numerical experiment with $n=4$.

Finally, the required probability is explicitly computed from the density function.

We can parametrize the complex projective space $CP^{N-1}$, almost everywhere with the coordinates $ \mathbb{C}^{N-1} \ni \mathbf{\zeta} = \{[\zeta_1, . . ., \zeta_{N-1}]^t\}$. A random $N$-dimensional normalized vector corresponding to the point $\mathbf{\zeta}$ is given by (as a column vector): $$|\psi(\mathbf{\zeta}, \mathbf{\bar{\zeta}})\rangle = \frac{[1, \zeta _1,.,.,., \zeta _{N-1}]^t}{\sqrt{1+\mathbf{\zeta}^{\dagger} \mathbf{\zeta} }}$$

(We will eventually take $N=2^n$ or $N=2$). The Fubini-Study volume element is given by: $$d{\mu}_{CP^{N-1}}(\mathbf{\zeta}, \mathbf{\bar{\zeta}}) = \frac{(N-1)!}{\pi^{N-1}}\frac{\prod_{k=1}^{N-1} d\zeta_k d\bar{\zeta}_k}{(1+\mathbf{\zeta}^{\dagger} \mathbf{\zeta})^N}$$ (The prefactor serves for normalizing the volume to a unit mass).

The following integral identities are valid: $$\int_{CP^{N-1}} \frac{\zeta_k } {(1+\mathbf{\zeta}^{\dagger} \mathbf{\zeta})^N} d{\mu}_{CP^{N-1}}(\mathbf{\zeta}, \mathbf{\bar{\zeta})} = 0$$ $$\int_{CP^{N-1}} \frac{\bar{\zeta}_k } {(1+\mathbf{\zeta}^{\dagger} \mathbf{\zeta})^N} d{\mu}_{CP^{N-1}}(\mathbf{\zeta}, \mathbf{\bar{\zeta})} = 0$$ $$\int_{CP^{N-1}} \frac{1} {(1+\mathbf{\zeta}^{\dagger} \mathbf{\zeta})^N} d{\mu}_{CP^{N-1}}(\mathbf{\zeta}, \mathbf{\bar{\zeta})} = \frac{1}{N}$$ $$\int_{CP^{N-1}} \frac{\zeta_k\bar{\zeta}_l } {(1+\mathbf{\zeta}^{\dagger} \mathbf{\zeta})^N} d{\mu}_{CP^{N-1}}(\mathbf{\zeta}, \mathbf{\bar{\zeta})} = \frac{1}{N}\delta_{kl}$$

The Fubini-Study volume element is invariant with respect to the following unitary transformation realized non-linearly on the coordinates: Let $U \in U(N)$ be given in the following block form: $$U = \begin{bmatrix} a & \mathbf{b}^t\\ \mathbf{c} & D \end{bmatrix}$$ ($a$ is a scalar, $b$ and $c$ are $N-1$ dimensional column vectors and $D$ is an $N-1\times N-1$ matrix). $$\begin{bmatrix} 1\\ \mathbf{\zeta} \end{bmatrix} \rightarrow \begin{bmatrix} 1\\ \mathbf{\zeta}' \end{bmatrix} = (a + \mathbf{b}^t \zeta)\, U \begin{bmatrix} 1\\ \mathbf{\zeta} \end{bmatrix}$$ The first factor is a multiplier (cocycle).

Similarly, the $k$-th single qubit complex projective line can be parametrized almost everywhere by: $$|\alpha_k(z_k, \bar{z}_k)\rangle = \frac{[1, z_k]^t}{\sqrt{1+\bar{z_k} z_k }}$$ And the corresponding volume element: $$d{\mu}_{CP^{1}}(z_k, \bar{z}_k) = \frac{1}{\pi}\frac{dz_k d\bar{z_k}}{(1+\bar{z_k} z_k)^2}$$ Denoting by $f$ the natural mapping from the power set of $\mathbb{Z}_{n} = \{0, .,.,., n-1\}$ to $\mathbb{Z}_{2^n}$: $$f(x) = \sum_{k \in x} 2^k$$ and using the shorthand notation: $$z^{ f(x) } = \prod_{ k\in x } z_k$$ (with the convention $\zeta_0 = z_0 = 1$) Tensoring the single qubit vectors and performing the inner product, we get: $$F(\mathbf{\zeta}, z_0, ., ., . z_{n-1}, \mathbf{\bar{\zeta}}, \bar{z}_0, ., ., . \bar{z}_{n-1})= \frac{|\sum_{x \in \mathcal{P}(\mathbb{Z}_{n})} \zeta_{f(x)} \bar{z}^{f(x)} |^2}{(1+\mathbf{\zeta}^{\dagger} \mathbf{\zeta}) \prod_{k \in \mathbb{Z}_{n}} (1+\bar{z_k} z_k)}$$ The average of $F$ is computed by means of the following integral: $$<F> = \int_{CP^{2^n-1}} d{\mu}_{CP^{N-1}}(\mathbf{\zeta}, \mathbf{\bar{\zeta}}) \prod_{k=0}^{N-1} d{\mu}_{CP^{1}}(z_k, \bar{z}_k) F(\mathbf{\zeta}, z_0, ., ., . z_{n-1}, \mathbf{\bar{\zeta}}, \bar{z}_0, ., ., . \bar{z}_{n-1})$$ Expanding the numerator of $F$, we get a quadratic polynomial in $\mathbf{\zeta}, \mathbf{\bar{\zeta}}$. Using the integration formulas, only $2^n$ terms survive, each contributing $\frac{1}{2^n}$. Thus, we are left with: $$<F> = \frac{1}{2^n} \prod_{k=0}^{N-1} d{\mu}_{CP^{1}}(z_k, \bar{z}_k) \frac{\sum_{x \in \mathcal{P}(\mathbb{Z}_{n})} z^{f(x)} \bar{z}^{f(x)} }{ \prod_{k \in \mathbb{Z}_{n}} (1+\bar{z_k} z_k)}$$ The numerator factors to the denominator, and we are left with a product of $2^n$ normalized volumes of $CP^1$, i.e. $1$, Thus $$<F> = \frac{1}{2^n}$$ Given the explicit expression of the function $F$ on a probability space; its probability density function can be written as: $$p_F(y) = \int_{CP^{2^n-1}} d{\mu}_{CP^{N-1}}(\mathbf{\zeta}, \mathbf{\bar{\zeta}}) \prod_{k=0}^{N-1} d{\mu}_{CP^{1}}(z_k, \bar{z}_k) \delta(F(\mathbf{\zeta}, z_0, ., ., . z_{n-1}, \mathbf{\bar{\zeta}}, \bar{z}_0, ., ., . \bar{z}_{n-1}) – y)$$ We observe that the numerator of $F$ can be written as: $$\begin{bmatrix}1 & \bar{\mathbf{\zeta}}\end{bmatrix} \begin{bmatrix}1 \\ \mathbf{z}\end{bmatrix} \begin{bmatrix}1 & \bar{\mathbf{z}}\end{bmatrix} \begin{bmatrix}1 \\ \mathbf{\zeta}\end{bmatrix}$$ The interior matrix (depending on $\mathbf{z}$ only) is of unit rank; thus it can be diagonalized by a unitary transformation to a matrix of the form:

$$ \mathrm{diag }\begin{bmatrix} 1+ \mathbf{z}^{\dagger} \mathbf{z}, & 0, & 0, & ... \end{bmatrix}$$ (Please notice that the scalar cocycles cancel between the numerator and the denominator and the Fubini-Study measure is invariant under the transformation).

As mentioned above, the nonvanishing first element just factors out to the denominator depending on $z$. Thus, we are left with $n$ integrations on the normalized volumes of $CP^1$ giving an overall result of $1$ with respect to the $z$ integration. As for the $\zeta$ dependent terms, we are left with only one term of $\begin{bmatrix}1 & \bar{\mathbf{\zeta}}\end{bmatrix} \begin{bmatrix}1 \\ \mathbf{\zeta}\end{bmatrix}$, which can be taken the first, i.e., $1$, thus the delta function term becomes: $$\delta(\frac{1}{(1+\mathbf{\zeta}^{\dagger} \mathbf{\zeta})}-y)$$ Performing the standard manipulations on the delta function, we obtain: $$\frac{1}{2y^{\frac{3}{2}}(1-y)^{\frac{1}{2}}}\delta(\sqrt{\mathbf{\zeta}^{\dagger} \mathbf{\zeta}}-\sqrt{\frac{1-y}{y}})$$ The constraint is a spherical surface of dimension $2N-3$ inside $CP^{N-1}$ and radius $\sqrt{\frac{1-y}{y}}$ Using the surface area formula for a $n-1$ sphere of unit radius: $$S_{n-1} = \frac{n \pi^{\frac{n}{2}}}{\Gamma(\frac{n}{2}+1)}$$ We arrive at: $$ p_F(y) = \frac{1}{2y^{\frac{3}{2}}(1-y)^{\frac{1}{2}}} \frac{(2N-2) \pi^{N-1}}{\Gamma(N)} \left(\sqrt{\frac{1-y}{y}}\right)^{2N-3} \frac{(N-1)!}{\pi^{N-1}} y^N = (N-1)(1-y)^{N-2}$$ Which is just the beta distribution, with the parameters $\alpha = 1$, $\beta = 2^n-1$).

Thus, for the $n$ qubit case, we have: $$ p_F(y) = = (2^n-1)(1-y)^{2^n-2}$$ A numerical experiment was performed with $n=4$ with $10^6$ draws. The following figure compares the computed probability density function to the experiment's histogram:

From the probability density function, we get asymptotically for n>>1 and $\epsilon>>\frac{1}{2^n}$: $$\mathrm{Pr}(y>\frac{1}{2^n}+\epsilon) = e^{-2^n\epsilon}$$