Entanglement and the power of one qubit

The “power of one qubit” refers to a computational model that has access to only one pure bit of quantum information, along with $n$ qubits in the totally mixed state. This model, though not as powerful as a pure-state quantum computer, is capable of performing some computational tasks exponentially faster than any known classical algorithm. One such task is to estimate with fixed accuracy the normalized trace of a unitary operator that can be implemented efficiently in a quantum circuit. We show that circuits of this type generally lead to entangled states, and we investigate the amount of entanglement possible in such circuits, as measured by the multiplicative negativity. We show that the multiplicative negativity is bounded by a constant, independent of $n$, for all bipartite divisions of the $n+1$ qubits, and so becomes, when $n$ is large, a vanishingly small fraction of the maximum possible multiplicative negativity for roughly equal divisions. This suggests that the global nature of entanglement is a more important resource for quantum computation than the magnitude of the entanglement.

Figure 1

(a) Average negativity of the state ${\rho }_{n+1}$ of Eq. (1.2) $(\alpha =1)$ for a randomly chosen unitary $U_n$ for two different bipartite splittings, ($n$, 1) and $(\lfloor n∕2\rfloor +1,\lceil n∕2\rceil )$. The ($n$, 1) splitting appears to reach an upper bound quickly, whereas the other splitting is still rising slowly at 10 qubits. (b) Semilog plot of the standard deviation in the negativity of the randomly chosen state ${\rho }_{n+1}$. The fit curves show that the standard deviation is decaying exponentially, so that for large numbers of qubits, almost all unitaries give the same negativity.

Figure 2

Average negativity of the state ${\rho }_{10}$ of Eq. (1.2) $(\alpha =1)$ for a randomly chosen unitary $U_9$ as a function of bipartite splitting number $k$ for bipartite splittings ($10-k$, $k$). The error bars give the standard deviations. The function attains a maximum when the bipartite split is made between half of the qubits on which the unitary acts.

Figure 3

Plot of the bounds on the negativity of states of the form (1.2), i.e., for a pure-state input in the zeroth register $(\alpha =1)$. The uppermost plot is the simple analytic bound ${\mathcal{M}}_{1,2}=\sqrt{2}$, obtained using the $s=1,2$ constraint equations; the next largest plot is the numerically constructed $s=1,2,3$ bound. One can see that the $s=1,2,3$ bound asymptotes to the $s=1,2$ bound. As noted in the text, these bounds are independent of the unitary $U_n$ and the bipartite division. The flat line shows the negativity $5∕4$ for the state constructed in Sec. 4, currently the state of the form (1.2) with the largest demonstrated negativity; notice that for $n+1=3$, this state attains the $s=1,2,3$ bound. The lowest two sets of data points display the expected negativities for a randomly chosen unitary using the bipartite splittings ($n$, 1) and $(\lfloor n∕2\rfloor +1,\lceil n∕2\rceil )$, which were also plotted in Fig. 1.