Generalized Inner Product Estimation with Limited Quantum Communication

In [3], they prove their lower bound using a very interesting connection to quantum cloning: in particular, they show that if one could solve a decision-version of DIPE, then one could have cloned the states “well-enough”. One of the main challenges in proving our lower bound was that the cloning-based lower bounds do not work when allowed even few qubits of communication in the cloning channel (which is the setting in which we would like lower bounds). Instead, here we showed that one could use the notion of robustness of entanglement, a concept from entanglement theory and split a protocol with a quantum channel into a sum of LOCC protocols. Proving this is a small technical lemma which we combine with the lower bound of [3] to obtain our overall lower bound of $\sqrt{2^{n-q}}$. In order to prove our upper bound, we use ideas from the celebrated Johnson-Lindenstrauss lemma. Our main idea is to perform projections onto random subspaces, i.e., Alice and Bob pick random subspaces and project their states onto these subspaces, maintaining the inner product between their states with high probability. Further, this protocol is completely agnostic to the states they started with. Now holding smaller-dimensional projections of their states, they can use classical communication to detect when their subspace-projections have collisions, use their shared quantum channel and perform $\mathrm{SWAP}$ tests to estimate the inner product within the subspace. With some analysis, we are able to show that the overall sample complexity for this scales as $\sqrt{2^{n-q}}$ as well, matching our lower bound.

For estimating bilinear forms, our protocol is fairly similar to the one in [3] except that we need to deal with some technicalities due to the Hermitian operator $M$. The key observation we first make is that ${|⟨\varphi |M|\psi ⟩|}^2$ and ${|⟨\varphi |M_{\epsilon }|\psi ⟩|}^2$ can only differ by at most $\epsilon /2$. So it suffices for Alice and Bob to restrict themselves to the support of $M_{\epsilon }$. Then, they can simultaneously measure the magnitude of the components of their states in this subspace as well as the weighted inner product of said components. The calculations here are similar to the one in [3] wherein one needs to compute the mean variance of the estimator, but a little bit more technical in order to bound all the terms in terms of ${\Vert M_{\epsilon }\Vert }_2$. The lower bound follows from realizing that $M_{\epsilon }$ when restricted to its support, is not too far off from identity and then we can invoke the lower bounds for inner product estimation can be applied. We remark that the lower bound here is much more subtle than the one in [3] since one needs to project onto the eigenspaces of $M$ carefully in order to get the optimal dependence on ${\Vert M_{\epsilon }\Vert }_2$.

A tantalizing open question left open by [3] and also this work is the analogue of DIPE in the mixed case setting. Here the goal is as follows: Alice has copies of $\rho$, Bob has copies of $\sigma$ and they engage in $\mathrm{𝖫𝖮𝖢𝖢}$. They need to distinguish if $\rho =\sigma$ or ${\Vert \rho -\sigma \Vert }_{tr}\ge \epsilon$, promised one of them is the case. Using the bounds obtained in [3], we have an upper bound of $O(d^2/{\epsilon }^4+d^{1.5}/{\epsilon }^2)$. As for lower bounds, [5] showed that if Alice also had copies of $\sigma$ (instead of Bob having them), then one can solve this property testing task using $𝒪(d/{\epsilon }^2)$ copies (this procedure requires a highly-entangling operation between copies of $\rho$ and $\sigma$). Furthermore, if we restricted the measurements to be single-copy measurements and if we fix $\sigma =𝕀/d$, then $\mathrm{\Omega }(d^{3/2})$ copies are necessary [12]. Despite several attempts in making progress on this question, we have not been able to obtain a lower bound better than $\mathrm{\Omega }(d)$ and believe that the sample complexity of mixed state DIPE should be $𝒪(d)$. We leave this as an open question.

Say that there exists a separable protocol $𝒜$ that uses $k$ copies of the states $|\varphi ⟩$ and $|\psi ⟩$ and the resource state $\sigma$ and returns an estimate of ${|⟨\psi |\varphi ⟩|}^2$ to accuracy $\epsilon$ with probability at least $3/4$. Because of anti-concentration of the Haar measure, Alice and Bob will be able to use this protocol to solve problem 9 with high probability. Let $B([\varphi ],\epsilon )$ be the ball of radius $\epsilon \le \pi /2$ around $[\varphi ]$ in $ℂ\mathbb{P}(d)$ with respect to the Fubini-Study metric, which we will denote as $d([\varphi ,\psi ])=\arccos |⟨\psi |\varphi ⟩|$. Then, it is known that, under the uniform distribution, the volume of $B([\varphi ],\epsilon )$ for $\epsilon \le \pi /2$ is given by ${\sin }^{2d-2}\epsilon$ [8]. If ${|⟨\psi |\varphi ⟩|}^2>\epsilon$, then $d([\psi ,\varphi ])\le \arccos \sqrt{\epsilon }$ (and $\arccos \sqrt{\epsilon }\le \pi /2$ for $\epsilon \in [0,1]$). Thus, for constant $\epsilon$ it follows that ${|⟨\varphi |\psi ⟩|}^2\le \epsilon$ with exponentially (in $d$) high probability in case two of 9. Thus, if Alice and Bob use the protocol $𝒜$, they will solve problem 9 with probability at least $2/3$ as well. This implies that there is some separable POVM $\{M,𝕀-M\}$ such that

We now show that the RHS of the inequality above can be upper bounded by $(1+2E(\sigma ))(e^{k^2/d}-1)$. To see this, split $\sigma$ into $\sigma =(1+E(\sigma )){\sigma }^{+}-E(\sigma ){\sigma }^{-}$, where ${\sigma }^{+}$ and ${\sigma }^{-}$ are both separable states. Then, it follows that

Note that the sign of ${\sigma }^{-}$ has been absorbed into the trace in the second term above. Now, because ${\sigma }^{\pm }$ are separable, each term above could be replaced by a separable measurement on ${\varphi }^{\otimes k}\otimes ({\varphi }^{\otimes k}-{\psi }^{\otimes k})$ without any reference state. To see this, decompose ${\sigma }^{+}$ into ${\sigma }^{+}={\sum }_i{p}_i{\rho }_i^A\otimes {\rho }_i^B$. Using spectral decompositions ${\rho }_i^A={\sum }_k{\lambda }_{i,k}|u_{i,k}⟩⟨u_{i,k}|$ and ${\rho }_i^B={\sum }_k{\nu }_{i,k}|v_{i,k}⟩⟨v_{i,k}|$, we arrive at

As a separable measurement, we have $M={\sum }_t{A}_t\otimes B_t$. Now define a new measurement

where $A_t={\sum }_{j,j^{\prime }}{A}_t^{i,j,j^{\prime }}\otimes |u_{i,j}⟩⟨u_{i,j^{\prime }}|$ and $B_t={\sum }_{k,k^{\prime }}{B}_t^{i,k,k}\otimes |v_{i,k}⟩⟨v_{i,k^{\prime }}|$. As a sum of positive operators, this is positive. As a convex combination of operators majorized by $𝕀$, this is also majorized by $𝕀$. It then follows that $M^{\prime }$ is a separable POVM. From Thm 12 it then follows that

The same proof shows that

Thus, we have that

Putting the above along with our lower bound in Eq.(5) shows

Rearranging, this implies that

So, if Alice and Bob share $q$ Bell pairs, then $E(\sigma )=2^q-1$ and we get the desired lower bound.

Using techniques similar to [3, Section 5.3], wherein they showed how to use standard concentration techniques to reduce the decision version of DIPE (for which we have a $\mathrm{\Omega }(\sqrt{d/q})$ lower bound) to prove a lower bound for estimating the inner product between $|\varphi ⟩$ and $|\psi ⟩$ with a factor of $1/\epsilon$. In particular, they prove that if there exists a protocol that solves the $\epsilon$-version of inner product estimation then it can be used to solve DIPE with high probability. Then, the lower bound on DIPE follows from their reduction. $◀$

Let $\psi =|\psi ⟩⟨\psi |$ and $\varphi =|\varphi ⟩⟨\varphi |$. Fix some unitary $U$. For convenience of notation we will assume that $r$ divides $d$ (working with qubits, if Alice and Bob may communicate $\log (r)$ qubits then this holds). Divide the $d$-dimensional Hilbert space into $d/r$ subspaces each of dimension $r$. Let this decomposition be given by a collection of orthogonal projectors ${\{P_i\}}_{i=1}^{d/r}$. Alice and Bob perform the protocol in Figure 1.

Our theorem will follow by repeating the protocol above constantly many times, each time by sending a $r$-dimensional quantum message. To see the correctness, we will require the following fact.

By linearity this extends to arbitrary vectors in ${ℂ}^d$, as the following corollary demonstrates.

This follows readily from Fact 14 via linearity. Apply Fact 14 to $\frac{u}{{\Vert u\Vert }_2}$ while multiplying both ${\Vert P_{i}Uu/{\Vert u\Vert }_2\Vert }_2$ and $(1\pm \mathrm{\Delta })\sqrt{\frac{r}{d}}$ by ${\Vert u\Vert }_2$. $◀$

For a fixed unitary $U$, let $|{\psi }_i^{\prime }⟩=\frac{P_{i}U|\psi ⟩}{|P_{i}U|\psi ⟩|}$ and $|{\varphi }_i^{\prime }⟩=\frac{P_{i}U|\varphi ⟩}{|P_{i}U|\varphi ⟩|}$ be the normalized projections of $|\psi ⟩$ and $|\varphi ⟩$ into the subspace given by $P_i$. We will now show that, with high probability over the choice of $U$, ${|⟨{\psi }_i|{\varphi }_i⟩|}^2\approx {|⟨\psi |\varphi ⟩|}^2$.

Using Fact 14, with probability at least $1-16\exp \{-\frac{{\mathrm{\Delta }}^{2}r}{16}\}$, the following four conditions hold

We now follow steps similar to those of [25, Theorem 1] to obtain

Let $x,y\in ℂ$ be such that $|x-y|\le \mathrm{\Delta }$. Then,

In our case, this implies that

Taking a union bound over all $d/r$ subspaces completes the proof. $◀$

Now, after receiving $m$ pairs of post-projected states, Bob then performs $m$ many $\mathrm{SWAP}$ tests. A $\mathrm{SWAP}$ test on the pair $|{\psi }_i^{\prime }⟩$ and $|{\varphi }_i^{\prime }⟩$ succeeds with probability $\frac{1}{2}+\frac{1}{2}{|⟨{\varphi }_i^{\prime }|{\psi }_i^{\prime }⟩|}^2\in \frac{1}{2}+\frac{1}{2}|⟨\varphi |\psi ⟩|\pm 8\mathrm{\Delta }$. The expected value of the sample average $s/m$ then satisfies

which implies $2𝔼\left[\frac{s}{m}\right]-1\in {|⟨\varphi |\psi ⟩|}^2\pm 16\mathrm{\Delta },$ and by a Hoeffding bound, we get

with probability at least $1-2\exp (-2m{\delta }^2)$. In this case, the total error of the estimator is at most $16\mathrm{\Delta }+\delta$. For constant error, $m=O(1)$ suffices.

It remains to determine $k$ needs to be to obtain $m=O(1)$ projected pairs with high probability. To this end, let $E_{a,b}$ be an indicator variable for if Alice’s $a$th projection falls into the same subspace as Bob’s $b$th projection. The expected number of collisions is given by

where the inequality follows from $\Vert P_{i}U|\psi ⟩\Vert ,\Vert P_{i}U|\varphi ⟩\Vert \ge (1-\mathrm{\Delta })\sqrt{\frac{r}{d}}$. By a Hoeffding bound, it suffices to take $k=\mathrm{\Omega }(\sqrt{d/r})$ to obtain a collision with high probability. As we only require a constant number of pairs, this can simply be repeated a constant number of times to obtain a constant number of collisions with high probability. Thus, the protocol succeeds for $k=\mathrm{\Omega }(\sqrt{d/r})$. It remains to pick $\mathrm{\Delta }$ and $\delta$ such that the claims go through: we require that $\frac{d}{r}\exp (-{\mathrm{\Delta }}^{2}r/16)=O(1)$, which can be achieved by letting $\mathrm{\Delta }=O(1)$ and $r=\mathrm{\Omega }(\log d)$. $◀$

Let $|0⟩$ be such that $M|0⟩=\pm 1$, which exists for since $\Vert M\Vert =1$ and the unit sphere is compact. Let $|1⟩$ be an eigenvector of $M$ orthogonal to $|0⟩$. Consider the states

Now, say that Alice is given $k$ copies of $|{\psi }_0⟩$ or $|{\psi }_1⟩$ and Bob is given $k$ copies of $|0⟩$. We have that

Thus, if Alice and Bob can estimate ${|⟨\psi |M|\varphi ⟩|}^2$ to accuracy $\epsilon$, they can distinguish between these two states. However, the fidelity between these states is given by

which implies that $k=\mathrm{\Omega }(1/{\epsilon }^2)$. $◀$

Before proving the second lower bound, we give some intuition. Say that $M\ge 0$.If $|\psi ⟩$ and $|\varphi ⟩$ are drawn independently from the Haar measure, then

If they are identical, that is $\psi =\varphi$ always, then instead the expected value is

The difference between these two is roughly $\mathrm{𝖳𝗋}{[M]}^2/d^2$. Thus, if Alice and Bob are able to estimate ${|⟨\psi |M|\varphi ⟩|}^2$ to this order, then they can solve DIPE (that we defined as Problem 9). However, $\mathrm{𝖳𝗋}{[M]}^2/d^2$ may be quite small. Restricted to the support of $M_{\epsilon }$, we instead have that ${\epsilon }^2/4\le \mathrm{𝖳𝗋}{[M_{\epsilon }]}^2/d_{\epsilon }^2\le 1$. We will show that if Alice and Bob can estimate ${|⟨\varphi |M_{\epsilon }|\psi ⟩|}^2$, then they can solve the following decision problem, which is known to require $k=\mathrm{\Omega }(\sqrt{dim\mathscr{H}}/\epsilon )$ samples [3] (when $\epsilon \le 0.01$).