Figure 1

Schematic diagram of Grover’s quantum search algorithm over a space of $n$ qubits ($N=2^n$ entries). Initially, all qubits are prepared in the state ∣000…0⟩. (a) A global Hadamard gate prepares an equal superposition of all states. (b) The oracle (shaded in light gray) flips the sign of the amplitude corresponding to the marked element, represented by the $n$-bit binary number $\mathbf{x}$. (c) Two global Hadamard gates surround an additional phase gate (shaded in dark gray) that flips the sign of the amplitude corresponding to the initial state ∣000…0⟩, amplifying the weight of the marked state. Steps (b) and (c) are repeated in sequence a prescribed number of times, and finally (d) the qubits are measured. An example of the distributions of quantum amplitudes at each stage is depicted at the right.Reuse & Permissions

Figure 2

Quantum circuit to implement Grover’s searching algorithm for $N=4$ entries [1]. (a) Theoretical circuit using a third ancilla bit and standard gates including the Haddamard gate $\left(H\right)$, the generalized Toffoli gate, a bit flip $X$, and a controlled-NOT (CNOT) gate. The Toffoli gate implements the oracle (shaded in light gray), where the scheme to mark each of the four possibilities is shown below the circuit. The remainder of the circuit (shaded in dark gray) amplifies the weighting of the marked state. (b) The experimental circuit to implement the algorithm for $n=2$ qubits, where $R(\theta ,\varphi )$ is a rotation on the Bloch sphere [33], $R_z\left(\varphi \right)$ is a phase rotation about the $\widehat{z}$ axis, and $G_{\mathit{MS}}$ is the Mølmer-Sørensen entangling gate. The light gray shaded box identifies the oracle, where the value of the variables $\alpha$ and $\beta$ (given in the table), determine which state is marked [34]. The remainder of the circuit (shaded in dark gray) amplifies the weighting of the marked state.Reuse & Permissions

Figure 3

(a) Output of the algorithm. The conditional probability of measuring each of four output states given one was marked is shown in the sequence from top to bottom ∣00⟩, ∣01⟩, ∣10⟩, ∣11⟩. Each of the four data sets shows the distribution of measurements averaged over 500 trials. The marked state was recovered on average with 60(2)%, compared to unit probability for the ideal quantum algorithm and 50% for the best possible classical algorithm. (b) Output of the algorithm without the final entangling gate. This shows that the fidelity of the oracle is about 80%. Each of the four data sets was also averaged over 500 trials. The experimental average to recover the marked state is 41(2)% with the theoretical limit of 50%, both of which are less than the 60% from (a). The quoted errors are statistical.Reuse & Permissions