Test-state approach to the quantum search problem

The search for “a quantum needle in a quantum haystack” is a metaphor for the problem of finding out which one of a permissible set of unitary mappings—the oracles—is implemented by a given black box. Grover’s algorithm solves this problem with quadratic speedup as compared with the analogous search for “a classical needle in a classical haystack.” Since the outcome of Grover’s algorithm is probabilistic—it gives the correct answer with high probability, not with certainty—the answer requires verification. For this purpose we introduce specific test states, one for each oracle. These test states can also be used to realize “a classical search for the quantum needle” which is deterministic—it always gives a definite answer after a finite number of steps—and 3.41 times as fast as the purely classical search. Since the test-state search and Grover’s algorithm look for the same quantum needle, the average number of oracle queries of the test-state search is the classical benchmark for Grover’s algorithm.

Figure 1

Average number $G(N)$ of oracle queries as a function of the total number $N$ of index kets. Curve “a” shows $G_C(N)$ of Eq. (2) for the classical search strategy. Curve “b” shows $G_Q(N)$ of Eq. (34) for Grover’s search algorithm, supplemented by test-state verification and optimized for least number of queries per search cycle. Curve “c” shows $G_T(N)$ of Eq. (28) for the test-state search.

Figure 2

Quantum circuit (a) is for preparing of the three-qubit test state $|t_0(8)\rangle$ and (b) is for the four-qubit test state $|t_0(16)\rangle$, respectively. Here, the input state is $|0\rangle {}^{\otimes n}$ ($n=3,4$), the Hadamard operations are depicted by $H$, and the explicit forms of the various controlled gates (the $V$s and $W$s) are given in the text, where all single-qubit operations are $Y$ rotations.

Figure 3

The quantum circuit for the implementation of $-\mathbf{M}$ in the case of three qubits. The operation $\mathbf{U}$ is implemented by the circuit shown in Fig. 2a after changing the parameters in accordance with Eq. (53). And, if we run the same circuit in the reverse order we can also implement ${\mathbf{U}}^{†}$. The quantum gate shown in the center of circuit is the $C^2(Z)$ given by Eq. (50).

Figure 4

A single iteration of the alternative confirmation is exhibited in terms of quantum circuit diagram. The input state with ket $|{\varphi }_{\mathrm{in}}\rangle =|0\chi \rangle$ of Eq. (A2) is passed through the sequence of the Hadamard gate $H$ of Eq. (5), the quantum black box, and another Hadamard gate. Finally, the first qubit of the output state $|{\varphi }_{\mathrm{out}}\rangle$ is measured in the computational basis.

Figure 5

(a) The “star graph” stands for the graph state with the ket $|\varphi \rangle {}_{(1+n)}$ of Eq. (B7). The (blue) circles represent the $n$ qubits which carry the input ket $|0\rangle {}^{\otimes n}$; the bonds are established by the controlled-Hadamard gates $\text{CH}(n)$ of Eq. (B6), and the ancilla qubit ‘$r$’ is represented by the (black) diamond. Plot (b) represents the net effect on the input ket $|0\rangle {}^{\otimes n}$, when the ancilla qubit is measured in an appropriately chosen basis.