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

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

• Have you seen this paper? arxiv.org/abs/0810.4331 Nov 18, 2019 at 7:30
• @DaftWullie: not for a while, no! Skimming though it once again, I am reminded that it is very interested in the geometric entanglement – essentially, the supremum of log-fidelity with some product state, as opposed to the expected value – of a typical state, as opposed to an arbitrary one. I don't immediately see what I should be looking for there, is there a particular Lemma or something which more transparently speaks to my question? –– Though using the log-fidelity is a reasonable way to try to bound the probability of deviating from the mean: I might have an idea of how to do that. Nov 18, 2019 at 9:27
• If I had thought it a perfect match for your question, I would have formulated an answer ;) I simply felt there were some similar elements. I suppose one statement that comes through is that almost every state is close to maximally entangled. Presumably, if the fidelity is due to the presence of entanglement, I guess you can infer something about the typical case rather than just the extremal case of separable basis choice (because presumably most local density matrices are close to maximally mixed). Nov 18, 2019 at 11:23
• @DaftWullie: fair enough, though sadly I'm not free to reformulate my question to use this idea in a direct way. But thinking superficially about Schmidt decompositions (and doing this recursively for $n > 2$), it does seem likely that the more entangled a state is, the less 'variance' (in some sense close to the technical sense) there will be in the fidelity. So the product state case is probably the one where deviation from the mean fidelity is most probable. Hopefully there is a simple argument along these lines, though of course I'd love to find that it's already in the literature. Nov 18, 2019 at 11:43

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.

• Hello, and thank-you! It looks to me as though your argument, about bounds on deviations applies for a unitary U which is Haar-distributed on a single system of dimension d, rather than to tensor tensor products of Haar-distributed unitaries on multiple systems of dimension d. I'm now looking into more general conditions for these bounds, so far without success: I have so far found out about bounds for random variables which are Gaussian, which doesn't even include the Haar-random case (though I see how an extension is plausible). Do you have a reference you would recommend about such bounds? Jul 1, 2021 at 10:25
• A further question: how can you be certain that the deviations are exponentially suppressed as $2^-n$ for multiple tensor factors? I don't see how this follows from your analysis. Jul 6, 2021 at 10:48

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: $$ = \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: $$ = \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: $$ = \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 $$ = \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}$$

• This looks quite thorough, but seems to address the question of the distribution of $F$ for a Haar-random $n$-qubit state, rather than an arbitrary one. I expect the distribution of $F$ to differ for different $n$-qubit states, so I wouldn't expect anyone to tell me what the distribution of $F$ is in general. However, perhaps it is easy to prove an upper bound on the variance, or some other means of showing how much the distribution spreads from the mean in the worst case. I expect that it will be easy to show that $n$-qubit states which are themselves product states will be the worst case. Dec 1, 2019 at 21:49