Effect of qubit losses on Grover's quantum search algorithm

We investigate the performance of Grover's quantum search algorithm on a register that is subject to a loss of particles that carry qubit information. Under the assumption that the basic steps of the algorithm are applied correctly on the correspondingly shrinking register, we show that the algorithm converges to mixed states with 50% overlap with the target state in the bit positions still present. As an alternative to error correction, we present a procedure that combines the outcome of different trials of the algorithm to determine the solution to the full search problem. The procedure may be relevant for experiments where the algorithm is adapted as the loss of particles is registered and for experiments with Rydberg blockade interactions among neutral atoms, where monitoring of atom losses is not even necessary.

Figure 1

(a) Illustration of physical loss of qubits from a quantum register. (b) Schematic representation of the block-diagonal density matrix, with population leaking from one two-dimensional subspace to the other caused by the loss of qubits.

Figure 2

Relative probability ${\mathcal{F}}_m\left(t\right)=\langle {\tilde{x}}_m|{\rho }_m|{\tilde{x}}_m\rangle /p_m\left(t\right)$ of the target-state component in subspaces with 12 (red, steepest rise), 14 (green, second steepest rise), and 19 (blue, third steepest rise at small $N_G$) remaining qubits (out of $n=24$), plotted as functions of the number of Grover steps $N_G$. The brown dashed line shows the weighted probability $\mathcal{F}\left(t\right)={\sum }_m{p}_m{\mathcal{F}}_m\left(t\right)$ that all bits match the target bit values. The results are shown for a loss rate of $\gamma \approx 4\times {10}^{-4}$ (per Grover step) leading to the average fraction of surviving qubits shown by the black line, while the target state probability in the ideal lossless case is shown by the gray line, reaching unity for $N_G\simeq 3217$.

Figure 3

Probability distribution of the number $n_c$ of correctly estimated qubits for an initial register size of $n=24$ qubits. In a given experiment we make ten trials to obtain the final bit string and we compare the cases where the bit values are obtained by (i) a simple majority vote on the raw data (blue circles) and (ii) the correlated data approach (red squares) using Eq. (14). To obtain the probability distributions shown, we have averaged the outcome of ${10}^4$ such experiments. The inset shows the upper left corner of the measurement table displaying the results for each trial. The dark (green) boxes indicate the lost qubits, represented by the numerical values $b_i^k=0.5$ in Eqs. (13) and (14).

Figure 4

Probability of obtaining all the bits correctly $P_n\left(K\right)$ plotted as a function of the number of trials $K$ for two different register sizes $n=24,36$. We have evaluated $P_n\left(K\right)$ when (i) the filtering is switched off, i.e., the final string is obtained by a simple majority vote (red filled circles and blue squares) and (ii) the filtering is switched on by the correlated data approach (red solid line and blue circles) using Eq. (14).