Abstract
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 speed-up 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 faster by a factor of 3.41 than 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.
I. INTRODUCTION
In recent decades, the quantum theory found another practical use in the field of quantum information processing: Quantum computation [1] [2] [3] and quantum information theory [4, 5] are extensively researched by several scientific communities. On one hand, the superposition principle of quantum mechanics speeds up the computation for important classes of computational problems. On the other hand, entanglement assists us in sending information from one place to another in a secure way. Both branches-quantum computation and quantum information theory-are interlinked and are growing rapidly.
I. INTRODUCTION
"Searching an item in a given database" is a wellknown computational problem which has been studied with different conditions in both classical [6] and quantum [7] contexts. When an unsorted database stored in the memory of a classical computer (CC) is given, then the average number of iterations required by the CC to complete this classical search grows linearly with the total number of items present in the database. But, if the items are already present in an order in the memory, then the average number of iterations scales up logarithmically with respect to the total number of items.
I. INTRODUCTION
Grover introduced a quantum search algorithm [7] for an analogous "quantum search problem:" A quantum computer (QC) searches a particular ket out of a set of kets from the computational basis. Or, more precisely, the quantum search finds which one of a set of unitary mappings-the oracles-is implemented by a black box. One can tackle this problem like its classical analog by testing for each oracle one by one in a sequence till the * email: jwilliams@example.org match is found. Alternatively, we can exploit the superposition principle and address all the oracles simultaneously, with Grover's search algorithm (GA). This gives a quadratic speedup to GA in comparison with the classical search.
I. INTRODUCTION
But the answer returned by GA is the correct one with a high probability only, not with certainty. It is, therefore, necessary to verify the answer. This verification is done with the aid of the test states that we introduce here, one test state for each oracle.
I. INTRODUCTION
The test states can also be used for a classical-type search of the quantum data set (that is, the set of oracles). Such a test-state search is deterministic-it will give the correct answer after a finite number of queriesand the average number of queries is proportional to the number of permissible oracles, but fewer by a factor of 3.41 than the average number of queries for the corresponding classical search of an unstructured classical database.
I. INTRODUCTION
A single iteration of the test-state approach is a threestep process. First, we prepare a test state, which is a certain superposition of all the kets of the set under search. Second, we pass it through the oracle-the very same oracle that is employed by GA. Finally, we retrieve the information by a measurement on the processed test state. As is the case in the classical search, this measurement says "yes" or "no" if the test state matches the oracle or not. In marked contrast to the classical search problem, however, there are different "no" answers depending on the actual oracle, and the measurement extract the available information. The choice of test state for the next round is then guided by this information, and this guidance leads to a substantial reduction of the average number of trials needed before successful termination of the search.
I. INTRODUCTION
The structure of this article is as follows. Section II comprises of the definitions and the algorithms for the search problem in both classical and quantum contexts. In Sec. III, a comprehensive description of the teststate approach to the quantum search problem is provided. GA with test-state verification is then discussed in Sec. IV, and Sec. V deals with alternative test-state search strategies. In Sec. VI, we describe the quantum circuit for the construction of the test state and for realizing the measurements. We conclude with a summary and discussion in Sec. VII, and two appendixes contain additional material.
II. SEARCH PROBLEM
Suppose someone gives us a list of one hundred names of different animals on a piece of paper, and ask where "Lion" appears on this list. If "Lion" appears exactly once on the list, and the list is not ordered in any obvious way, then we have to go through about fifty names on average before we find "Lion." For a search of this kind, neither a CC nor a QC can directly helps us, because the data (names) are given on a piece of paper.
II. SEARCH PROBLEM
In order to use a CC or a QC for this kind of database search, first we have to convert the data into an accessible format. For example, in case of a CC for such a search, first we have to load the data (the given list) into the memory of a CC. However, we can find the name Lion in the process of converting the list of names into an electronic format (in terms of strings of bits) and storing them in the memory. So, neither a CC nor a QC is very helpful for a search of this kind. In other words, a CC (QC) is helpful for a database search only when the database is given in an electronic format (quantum format).
II. SEARCH PROBLEM
Furthermore, a QC also cannot search a classical database without a "quantum addressing scheme" [8] where the classical database is converted into a quantum format (in terms of quantum kets). So, the process of searching a marked string of bits with a CC in a classical database which is stored in the memory of a computer is called as classical search. Similarly, quantum search is a process where a QC searches a marked quantum state (or, rather, a particular unitary operation) out of a set of quantum states (or, rather, a set of unitary operations). Classical and quantum searches are analogous but not the same, their detailed description is given in the following.
A. Classical search
Suppose we have an unsorted database as a set
A. Classical search
of a total of N items stored electronically in the memory of a CC. Each item is labeled by an index from 0 to N −1 and further represented by a n-bit string in binary representation. For convenience, we shall confine our attention to the case N = 2 n (0 ≡ 00 · · · 0, N − 1 ≡ 11 · · · 1), but the following algorithms and the test-state approach can be implemented for an arbitrary value of N .
A. Classical search
Throughout the article we shall consider only the case of a single matching item. The task of the search problem is to recover the corresponding index (n-bit string) to the marked item at the end of computation.
A. Classical search
The method employed by a CC to solve the search problem is by checking every element of S N C one by one in a sequence till a match is found [6] . A single iteration of this classical algorithm is a three-step process given as follows.
A. Classical search
Step 1: The CC picks a n-bit string at random from the set S N C as an input.
A. Classical search
Step 2: The CC checks whether or not this string matches with our query.
A. Classical search
Step 3: It produces an answer to the question in terms of "yes" or "no." If the answer is "yes," then the CC stops the computation and produces the string as the result, and the corresponding item will be the matching item. If the answer turns out to be "no," then the CC picks another string at random from the set S N C as an input, with items tested earlier excluded, and asks the same question. If the answer is again "no," then the CC repeats the above procedure until it hits the matching item. One of the main points in this classical algorithm is, "Every time the CC picks at random only one n-bit string, and its current guess does not depend on previous guesses" other than excluding them. In this way, a CC needs, on average, as many as
A. Classical search
queries of the database before it finds the matching item. This is an immediate consequence of the recurrence relation
A. Classical search
that commences with G C (1) = 0. Since G C (N ) ∝ N for N 1, this classical search algorithm is linear in the number of candidate items. If, rather than being unstructured, the data were sorted beforehand, then the problem could be completed by a binary search in approximately log 2 N iterations [6] .
B. Quantum search
In this section, an analogous quantum search problem to the classical one and a brief description of GA [7] is provided. Throughout the text we represent the single-qubit Pauli vector operator σ by (X, Y, Z) and the identity operator by I.
B. Quantum search
In the step from classical to quantum, bits are replaced by qubits. So, for each index (n-bit string) j of S N C defined by Eq. (1) there exist a n-qubit quantum ket |j , the so-called index ket. There is then a unitary operation O j -the jth oracle-which gives a conditional phase shift of π to the index ket |j only,
B. Quantum search
where I = I ⊗n is the identity operator in the Ndimensional Hilbert space.
B. Quantum search
One can define an analogous quantum search problem to the classical search problem of Sec. II A in the following way: Suppose someone gives us a quantum black box, which is implementing one of the N different oracles, and asks us to find out which of the oracles is the case without actually opening the box and looking inside. Clearly, we are not using QC to search a marked item in a classical database, but we are searching the index ket corresponding to the given oracle. The question of how many queries of the database are now needed, reads "How many times must one use the quantum black box to find out the correct result?"
B. Quantum search
The most efficient way of finding out which oracle is the actual one is GA [9] . GA begins by applying the Hadamard gate
B. Quantum search
to each qubit, after initially preparing the state with index ket |0 ≡ |0 ⊗n . The operation H ⊗n creates a superposition of all the index kets of S N Q with equal amplitude 1/ √ N . The next step is an application of the Grover iteration operator G, geometrically it is a rotation composed of two reflection operations as G = DO. The operator O is the same quantum oracle (black box) defined by Eq. (4), whose unknown index we have to find. The diffusion operator D gives an inversion about the average [7] ,
B. Quantum search
its central piece is the 0th oracle O 0 . GA is probabilistic in nature in the sense that, after applying G several times, the probability of the privileged index ket becomes significantly higher than the probabilities of the other index kets. Finally, we read out the output by performing projective measurements on each qubit, and so find one of the index kets. After k applications of G, we have [7] 
B. Quantum search
for the probability that the oracle associated with the final output state is the one which the black box is executing. Upon optimizing k, GA solves the quantum search problem by using the black box only
B. Quantum search
times when N 1; see Sec. IV below. The quadratic speedup of G Q (N ) ∝ √ N versus G C (N ) ∝ N is owed to the computational power of quantum physics; specifically, the superposition principle jwilliams@example.org. We emphasize that the outcome of GA is not guaranteed to be the correct answer; it can be incorrect with a probability that is very small but definitely nonzero.
B. Quantum search
In passing, we note the following. A general treatment of GA for multiple targets and for an arbitrary value of N is given in Ref. [10] . Moreover, GA is a special case of the quantum amplitude amplification [11] . In addition, one can get rid of the probabilistic nature of GA if one has the option of changing the structure of the diffusion operator D and the oracle O [12] . When one is only allowed to use the given black box, namely the oracles of Eq. (4), but not to look inside and change the setting, then GA remains probabilistic in nature.
B. Quantum search
So, one needs a confirmation step to be sure of the result obtained by GA. A single iteration of the teststate search introduced in the next section acts as a confirmation step for GA, where the verification matter is discussed after Eqs. (15) . Details of GA with test-state verification are given in Sec. IV.
III. TEST-STATE SEARCH
In this section, we introduce the test-state approach to the quantum search problem described in Sec. II Bwhere one has to identify the actual oracle which is implemented by the given black box. The features of both classical and quantum approaches are embodied in this approach. A single iteration in the test-state approach can be summarized in the following three steps.
III. TEST-STATE SEARCH
Step 1: We pick an index ket |j and prepare the corresponding test state.
III. TEST-STATE SEARCH
Step 2: We pass the test state through the given quantum black box which is executing one of the oracles of Eq. (4).
III. TEST-STATE SEARCH
Step 3: We extract the information with the help of a particular probabilityoperator measurement (POM) [13, 14] . Here, a "single iteration" comprises of these three steps, which are similar to the classical search algorithm of Sec. II A. The result of the POM gives an answer to the same question-whether or not the black box is executing the oracle O j -in terms of "yes" or "no." The answer "yes" tells us that the black box is executing the corresponding oracle to the index ket we picked, and we terminate the search.
III. TEST-STATE SEARCH
Even if the answer is "no," the result of the POM gives us some information about the actual oracle. This information facilitates an educated guess and a judicious choice of the test state for the next iteration.
III. TEST-STATE SEARCH
The correct result is obtained after a finite number of iterations. In other words, the test-state search is deterministic, rather than probabilistic. And, the systematic educated guessing makes the test-state search more efficient than a truly classical search, in which all test states would be chosen at random: For N 1, the test-state search needs fewer guesses by a factor of 3.41.
A. A single iteration in the test-state search
In this section, we construct the test states for verification of the outcome of GA and discuss the three steps of one iteration round in the test-state approach to determining the actual oracle of the quantum search problem. The narrative follows the steps in sequence.
A. A single iteration in the test-state search
Step 1-Preparing the test state: We pick an index ket |j from the set
A. A single iteration in the test-state search
of all index kets. For the very first round of iteration, the choice of |j is random, but for all subsequent rounds the choice is dictated by the result of the measurement in Step 3, as discussed in Sec. III B.
A. A single iteration in the test-state search
Then we prepare the corresponding test state |t j which is of the form
A. A single iteration in the test-state search
where a is the amplitude of the privileged index ket |j and b is the common amplitude of all other index kets. Both a and b are functions of N ; it suffices to consider only real positive values for a and b, but this is a restriction of convenience, not of necessity. In Sec. VI A, we present a quantum circuit for constructing the test state |t 0 . The test state |t 0 can be transformed into any other test state |t j by applying the X operations on the relevant qubits. In other words, each |t j is equivalent to |t 0 up to some single-qubit operations.
A. A single iteration in the test-state search
Step 2-Processing the test state: We pass the test state |t j through the given quantum black box. We recall that the black box is implementing one of the N different oracles of Eq. (4), but we do not know which oracle is the case. If the black box is implementing the jth oracle, then the resultant state is
A. A single iteration in the test-state search
If the black box is not implementing the jth oracle, but some other one, the kth oracle, say, then the resultant state is
A. A single iteration in the test-state search
Result |t j j says "yes, it is the jth oracle" whereas each |t k j with k = j says "no, it is not the jth oracle," and we note that there is one "yes" but N − 1 different "no"s.
A. A single iteration in the test-state search
We define the "no" set C N j to index ket |j as the collection of all N − 1 "no" states of Eq. (12) ,
A. A single iteration in the test-state search
In order to be able to distinguish the "yes" ket |t j j from the "no" kets in C N j , we demand that
A. A single iteration in the test-state search
so that the "yes" ket is orthogonal to all "no" kets. Together with the normalization of the test-state ket |t j j , this gives
A. A single iteration in the test-state search
for the amplitudes in Eq. (10) . The use of the test states for the verification of the outcome of GA, is quite obvious: After GA identifies the jth oracle, we prepare the jth test state |t j and let the oracle act on it. Then we perform a measurement that determines whether the resulting ket is proportional to the "yes" ket |t j j or resides in the orthogonal subspace spanned by the N − 1 "no" kets. If we find the "yes" ket, the search is over; otherwise, we have to execute GA another time. An alternative confirmation step for GA, where one has to use the black box at most two times, is described in Appendix A.
A. A single iteration in the test-state search
As Eqs. (15) show, there are test states for N > 2, but none for N = 2. This is as it should be. For, the two N = 2 oracles O 0 = |1 1|−|0 0| and O 1 = |0 0|−|1 1| are simply indistinguishable; they do not tell the index kets |0 and |1 apart.
A. A single iteration in the test-state search
Turning our attention to the "no" kets, we observe that they are the edges of a (N − 1)-dimensional pyramid,
A. A single iteration in the test-state search
with λ = (N −4)/(N −2). In the terminology of Ref. [15] , the pyramid is acute (λ > 0) for N > 4, orthogonal (λ = 0) for N = 4, and flat (λ = −1/(N − 2)) for N = 3. The case N = 4 is particular: We have a = b = 1/2 and all four test states are identical. The "no" states for one index ket are pairwise orthogonal; they are "yes" states for the other index kets. As a consequence, testing the oracle once with the one common test state will reveal its identity.
A. A single iteration in the test-state search
This observation is sometimes stated as "GA needs to query the oracle only once for N = 4." Indeed, we have p Step 3-Measuring the result: When measuring the state that results from applying the black-box oracle to the jth test state |t j , we not only need to distinguish between "yes" and "no" but also want to acquire information about which of the "no"s is the case, so that we can make a judicious choice for the next test state. Thanks to the pyramidal structure of the "no" kets, the POM that maximizes our odds of guessing right is the so-called square-root measurement (SRM) [15, 16] .
A. A single iteration in the test-state search
For N = 3, there is no useful POM of this kind because the two "no" states are the same, as is exemplified by
A. A single iteration in the test-state search
has the rank-1 outcomes Π
A. A single iteration in the test-state search
where
A. A single iteration in the test-state search
and a, b are the coefficients of Eqs. (10)- (12) and (15) . Since
A. A single iteration in the test-state search
the SRM is an orthogonal measurement, a standard von Neumann measurement, not a POM proper. Therefore, the SRM can be implemented by a unitary transformation followed by measuring the computational basis. One quantum circuit for such a unitary transformation is given in Sec. VI B.
B. Conditional probabilities
The probability of getting the lth outcome if the processed jth test state is |t k j is given by
B. Conditional probabilities
It follows from Eqs. (11), (12) , and (18) that there are three cases,
B. Conditional probabilities
where
B. Conditional probabilities
with the subscript N − 1 stating the number of different "no" outcomes. The first case in Eq. (22) is the affirmative "yes, it is the jth oracle" answer that terminates the search. The second and third cases both say "no, it is not the jth oracle." Thereby, the probability α N −1 of getting the kth outcome when the black box implements the kth oracle is larger than the probability β N −1 for all other "no" outcomes. Upon finding the lth outcome, we will therefore guess that the black box contains the lth oracle and choose |t l as the next test state. The choice of SRM maximizes the probability that this educated guess is right.
B. Conditional probabilities
After the first wrong guess |j , we exclude the index ket |j from the list of candidates, and have the set
B. Conditional probabilities
of the remaining N − 1 index kets for the next round.
B. Conditional probabilities
Having found SRM outcome Π l j , we repeat the iteration described in Sec. III A on the set S N −1 Q by taking the index ket |l as the next educated guess, for which the "no" probabilities are α N −2 and β N −2 . If this guess is also wrong, then the lth index ket can be excluded as well, and we are left with N −2 candidates and a new educated guess for the next test state with "no" probabilities α N −3 and β N −3 . And so forth, until we either get the "yes" answer, or we are left with four candidates only, having excluded N −4 index kets successively. The common test state for N = 4 will then surely give us the "yes" answer; in the present context, this is confirmed by α 3 = 1 and β 3 = 0 in Eqs. (22) and (23).
B. Conditional probabilities
In each round of iteration in the test-state search, we are using the black box once. Accordingly, the average number of oracle queries before a "yes" answer is obtained, is given by
B. Conditional probabilities
m is the probability that the search terminates after the mth round. For N > 4, these probabilities are
B. Conditional probabilities
Without the educated guesses provided by the SRM, one would have to resort to choosing the test state for the next iteration at random, just as one does in a purely classical search, which amounts to the replacement α L → 1/L and yields p 
B. Conditional probabilities
and the probabilities for early termination are substantially larger than 1/N . Equations (25) and (26) yield the recurrence relation
B. Conditional probabilities
which commences with G T (4) = 1 and reduces, as it should, to its G C analog in Eq. (3) for α N = β N = 1/N . With the aid of the large-L form of α L in Eq. (27) and the corresponding statement for β L , we then find that the average number of queries in the test-state search is given by
B. Conditional probabilities
The comparison with the classical search,
B. Conditional probabilities
shows that the judicious choice of the next test state has a substantial pay-off: We need much fewer queries. Since the test-state search and GA are both determining the actual oracle inside the quantum black box, the classical-type "yes/no" approach of the test-state search sets the benchmark for the quantum search with GA. It is true, that both G C (N ) and G T (N ) grow linearly with the number N of candidate items, whereas G Q (N ) grows proportional to √ N -and this quadratic speedup is, of course, the striking advantage of the quantum search algorithm-but the reduction of the average number of queries by the factor of 3.41 is truly remarkable by itself. It, too, is a benefit of the superposition principle. The three search strategies are compared in Fig. 1 , which shows G C (N ), G T (N ), and G Q (N ) as functions of N .
IV. GROVER'S ALGORITHM WITH TEST-STATE VERIFICATION
As recalled in Sec. II B above, a single GA cycle consists of the preparation of the initial state, k applications of G = DO, followed by a measurement in the computational basis that is composed of the index kets. After the measurement finds index ket |j , we apply the oracle to test state |t j , measure the resulting state with the SRM, and so decide whether the actual oracle is O j or not. The search terminates when this test says "yes." But if the reply is "no," we execute another GA cycle. The probability that a GA cycle finds the correct index state is p (N ) k of Eq. (7). It follows that the probability that the search terminates after the mth cycle is
IV. GROVER'S ALGORITHM WITH TEST-STATE VERIFICATION
for m = 1, 2, 3, . . . . Each cycle queries the oracle k times, once for each application of G, plus one more time during the test-state verification. The verification is only done, however, if the result of the GA cycle is not an index state to an oracle that is already known to be wrong from the verification step of an earlier cycle. If the search terminates after the mth cycle, the oracle has been queried as many as
IV. GROVER'S ALGORITHM WITH TEST-STATE VERIFICATION
times on average, where the last summand is the average number of wrong test states that are tried-out during the unsuccessful m − 1 preceding cycles. Accordingly, the average number that we need to query the oracle before we know which oracle is the actual one, is given by
IV. GROVER'S ALGORITHM WITH TEST-STATE VERIFICATION
This expression ignores the very small correction of no consequence that results from the possibility that the search can terminate after trying out N − 1 test states for wrong oracles and so learning that the one remaining oracle must be the actual one.
IV. GROVER'S ALGORITHM WITH TEST-STATE VERIFICATION
In G Q (N ; k) , k is the number of oracle queries per cycle, so that we can optimize GA by minimizing G Q (N ; k) with respect to k,
IV. GROVER'S ALGORITHM WITH TEST-STATE VERIFICATION
The asymptotic form of Eq. (8) is obtained from
IV. GROVER'S ALGORITHM WITH TEST-STATE VERIFICATION
where φ = 1.1656 is the smallest positive solution of 2φ = tan φ. For N 1, one needs (sin φ) −2 = 1.18 cycles on average before GA concludes successfully, and the optimal k value is k = 
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
The GA search of Sec. IV is consistently carried out in the full space spanned by all index kets, as requested by the standard form of GA that we accept as its definition. By contrast, the successive iteration rounds of the test-state search of Sec. III are conducted in the relevant subspace spanned by the remaining candidate index kets. As a consequence of this systematic shrinking of the searched space, the successive educated guesses get better from one iteration round to the next.
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
In actual implementations, however, it may not be practical to limit the search to the relevant subspace because it is usually much easier to realize the necessary operations in the full N = 2 n dimensional space; see Sec. VI. If all iteration rounds of the test-state search are indeed performed in the full space, we have
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
instead of G T (N ) of Eq. (28). The large-N form thereof is
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
(37) Compared with the classical search, the reduction is still by more than a factor of 3, but the full-space test-state search needs about 12% more queries than the relevantspace search.
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
One could wonder if there is a benefit in using the measurement for unambiguous discrimination (MUD) [17, 18] rather than the SRM, because the MUD gives a small chance of identifying the actual oracle with a wrong test state. The probability of finding the right one of N oracles with a randomly chosen test state is then
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
where 2/(N − 2) is the success probability for the MUD to the (N − 1)-edged pyramid of the |t k j kets with j = k [15] .
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
The price for this increase of the bare 1/N probability is paid by getting an inconclusive result from the MUD if it fails to identify the right state, so that we have no information that would facilitate an educated guess for the next test state. The resulting average number of oracle queries is
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
if we successively search in the relevant subspace only, and
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
if the search is consistently carried out in the full space.
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
The large-N forms
V. ALTERNATIVE TEST-STATE SEARCH STRATEGIES
show clearly that this price is high: The test-state search with MUD needs substantially more oracle queries than the search with SRM. In addition, the MUD is a proper POM and more difficult to implement than the SRM. One could also rely on the MUD rather than the SRM in the verification step of GA. There are then modifications in Eqs. (32) and (33), but the large-N statement of Eq. (35) remains the same.
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
While the test state |t 0 could be realized for any value of N , we deal only with the important case of N = 2 n when the oracles are unitary operators acting on n qubits. Then, the test states |t j of Eq. (10) are locally equivalent to |t 0 , in the sense that we can transform the test state |t 0 into any other test state by applying X operations on the relevant qubits. In Sec. VI A we describe a construction for |t 0 , and show how to realize the SRM of Eqs. (17)- (20) |t 0 (8) , the input register is initialized in the state |0 ⊗3 , and then the single-qubit gate
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
with tan
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
is performed on the first qubit. Thereafter, we perform the controlled gate
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
with tan
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
(43) on the second qubit by taking the first qubit as control (with the control set to |0 ) followed by the Hadamard gate H of Eq. (5). Subsequently, we perform the doublycontrolled gate
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
with tan
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
on the third qubit by taking the first and second qubits as controls (with both controls set to |0 ) followed by the Hadamard gate H. The over-all unitary operation u for the case of three qubits can be narrated as
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
and the corresponding quantum circuit is depicted in Fig. 2(a) . The quantum circuit displayed in Fig. 2(b) is for the construction of the four-qubit test state |t 0 (16) , where a = 13/28, b = 1/28, and a 2 + 15b 2 = 1. In this case,
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
with tan
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
and
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
with tan ϑ 2 = √ a 2 + 3b 2 − 2b √ a 2 + 3b 2 + 2b = 1 3 (47) as well as W 3 = V 2 and W 4 = V 3 .
VI. UNITARY OPERATIONS FOR REALIZING THE TEST-STATE APPROACH
The generalization to the n-qubit case is immediate. How to efficiently split a multi-qubit controlled unitary operation C n−1 (V ) (single-qubit gate V with n − 1 control qubits) in terms of universal gates with n − 1 work qubits is shown in Refs. [8, 19] , and its circuit complexity is of the order of n. Consequently, the circuit complexity for constructing the n-qubit test state with quantum circuits of the kind shown in Fig. 2 is O(n 2 ). In Appendix B, an alternative method for constructing the test state |t 0 is given, where the amplitudes a and b are complex numbers.
B. Realization of the SRM
In order to perform the SRM of Sec. III A in the laboratory, one needs a unitary transformation
B. Realization of the SRM
that turns each basis ket |T l 0 into the corresponding ket |l of the computational basis. With Eqs. (11) and (18) we have
B. Realization of the SRM
which has one eigenvalue +1 and N − 1 eigenvalues −1, so that the unitary operators −M and the n-qubitcontrolled-Z
B. Realization of the SRM
have the same set of eigenvalues, that is: they are unitarily equivalent. The eigenkets of M are with M|e 0 = |e 0 and M|e j =0 = −|e j =0 . In view of the degeneracy of M, the set of orthonormal eigenkets for eigenvalue −1 is not unique, but the choice of Eqs. (51) is particularly useful in the present context. For, the eigenket |e 0 has the same structure as the test state |t 0 of Eq. (10), and we know from Sec. VI A how to construct |t 0 .
B. Realization of the SRM
We relate M to C n−1 (Z) through the unitary operator U X ⊗n that diagonalizes M in the computational basis,
B. Realization of the SRM
The operator U itself is such that U|0 ⊗n = |e 0 or U X ⊗n |1 ⊗n = |e 0 , and we realize it by the circuit for u-see Fig. 2 -with the replacements
B. Realization of the SRM
while U † is implemented by the circuit that has the gates of Fig. 2 in reverse order and all respective θ angle parameters replaced by −θ. Accordingly, all unitary factors on the right-hand side of Eq. (52) have known realizations, as illustrated for N = 2 3 in Fig. 3 . With the SRM measurement thus implemented and the corresponding test states of Sec. VI A, we can verify the GA outcome and complete the quantum search as discussed in Sec. IV, and we can also perform the fullspace test-state search of Sec. V, for which Eqs. (36) and (37) apply. Of course, there are implementations as well of the test states in successively smaller spaces and of the corresponding SRM measurements, but we are not aware of economic implementations. The restriction to the subspaces of yet-to-probe index states is rather awkward in practice.
VII. SUMMARY AND DISCUSSION
We have introduced the test states that enable one to verify whether the outcome of a quantum search with the Grover's algorithm is the actual oracle or not. We thereby regard the search problem as defined by the set of possible oracles, which are those considered by Grover. Other search problems, such as the one studied by Høyer [12] , are not automatically covered as well; the corresponding test states-if they exist-have to be found for each search problem separately. That is also the case for Grover-type searches with more than one matching item, that is when the oracle is a product of two or more different unitary operators of the kind defined in Eq. (4).
VII. SUMMARY AND DISCUSSION
It is possible that there are no test states for some of these other search problems, in which case one may not be able to verify if the search was successful -neither by test states of some sort, nor by a method like the one described in Appendix A below, nor by another procedure. This should make one wonder if a search problem is wellposed in the first place, if it is not possible to verify the outcome. We leave this as a moot point.
VII. SUMMARY AND DISCUSSION
With the test states at hand, we have the option of solving the quantum search problem with a classical search strategy. But there is a twist: While there is one "yes" answer, each "no" answer is slightly different and, with the help of the square-root measurement, this difference can be exploited systematically for a judicious choice of the test state for the next round. This educated guessing is rewarded by much fewer queries of the oracle on average than what one needs for the simple "yes/no" search. A reduction by a factor of 3.41 is achievable in principle, and a practical scheme still gains a factor of more than three. In our view, the classical-search benchmark is set by the search that exploits the differences between the "no"s fully.
VII. SUMMARY AND DISCUSSION
The picture is completed by giving explicit circuits for the implementation of the n-qubit test states. The circuit complexity is of order n 2 , and a variant of the same circuit is the main ingredient in the realization of the square-root measurement. where
H H
so that j and j differ in the first bit value only.
H H
As indicated in Fig. 4 , we prepare qubit 1 in the state with ket |0 , and encode the χ part of the index state in qubits 2 through n. So, the ket of the n-qubit input state is
H H
We pass it through the quantum circuit of Fig. 4 , where the given black box is used only once. If the black box is implementing either oracle O j or oracle O j , then the output state will have ket |φ (yes) out = |1χ .
H H
If, however, the black box is implementing one of the other N − 2 oracles, the output state will have ket
H H
Finally, qubit 1 is measured in the computational basis. If we find 0, the "no" output is the case, and we can be sure that the actual oracle is neither O j nor O j . But when we find 1, we know that one of these oracles is inside the black box. We determine which one by pairing |j with a third index ket that also differs only by the value of one qubit, which then plays the role of the privileged qubit in the corresponding circuit of the kind depicted in Fig. 4 , where qubit 1 is singled out.
H H
So, we either get a definite "no" answer to the question "Is the jth or the jth oracle the case?" or we are told "yes, it is one of these two." In the latter situation, we know for sure which one it is after a second round. 
H H
where |+ = H|0 = |0 + |1 / √ 2 uses the Hadamard gate of Eq. (5), and the absolute values |a| and |b| are, of course, still those of Eq. (15) . As before, it is enough to show how |t 0 is made, the other test states are then available by applying some single-qubit X gates.
H H
We obtain a ket of this kind by applying the multiHadamard unitary operator 
H H
and one verifies that
H H
also has the absolute value required by Eq. (15) . So, if we set θ in accordance with Eq. (B4), then the output state of Eq. (B3) is the test state |t 0 of Eq. (B1). We note that θ = π for N = 4, and θ = π/2 + 2/N for N 1. One can execute the unitary operation U 12...n HH...H (θ) on the n-qubit input state |0
H H
⊗n by a similar method as the one given for the unitary operation U 12...n ZZ...Z (θ) in Sec. IIA of Ref. [20] . Here, the input quantum register of n qubits (circles in Fig. 5(i) ) and the ancilla qubit 'r' (diamond in Fig. 5(i) ) are initialized in the n-qubit input state with ket |0
H H
⊗n and the state with ket |+ r , respectively. Then, similar to the n cz operations in Sec. II A of Ref. [20] , here we perform the n controlled-Hadamard operations ch(n) = |0 0| r ⊗ I ⊗n + |1 1| r ⊗ H ⊗n
H H
between the ancilla qubit and each one of the n qubits. All the controlled-Hadamard operations represented by the bonds in Fig. 5 (i) can be carried out at the same

{'paper_id': '119288839', 'title': 'Test-State Approach to the Quantum Search Problem', 's2_url': 'https://api.semanticscholar.org/CorpusID:119288839', 'source': 'S2ORC'}