Can be Grover’s quantum algorithm deterministic?

Abstract

In classical computation, searching an unsorted database cannot be done in less than linear time. Grover’s quantum algorithm illustrates that in the quantum model searching can be done faster than classical computation. It provides a quadratic speedup. Like many quantum algorithms, Grover’s algorithm is probabilistic in the sense that it gives the correct answer with high probability. This paper discusses deterministic and probabilistic properties of the Grover’s quantum algorithm.

1. Introduction

The real challence of optimization is to create algorithms than can solve realistically sized problems within a reasonable amount of computational time. Unfortunately, many problems require such huge computational resources, that brute force search methods take to much time to find the optimal answer.

In the 80’s and 90’s of the 20th century a new approach has appeared with potentially enormous consequences. The new approach is called quantum computing. It relies on the principles of quantum mechanics. In classical computation, there are a of number problems that cannot be solved with efficient algorithms. For example, the best classical algorithm for factoring a large integer increases exponentially with the size of the integer. In the searching problem where we have a target object in a database, the best classical algorithm increases directly as the size of the database.

Grover’s algorithm is probabilistic [1,2] in the sense that it gives the correct answer with high probability. Here is a difference in comparison with the Deutsch-Jozsa algorithm [3] which always produces the correct answer. In our publication we discuss why the Grover’s algorithm is probabilistic and whether we could set things so that the algorithm will be deterministic.

2. Grover’s algorithm as a probabilistic algorithm

Grover’s algorithm is a quantum algorithm for searching in an unsorted database with N entries. It was discovered by Lov Grover [1, 2]. Quantum circuitrepresentation of the Grover’s algorithm is shown in Fig. 1

Fig.1: The quantum circuit for the Grover’s quantum algorithm.

The algorithm used to search a specified item in the unsorted list quadratically faster than any classical algorithm.

How does Grover algorithm work? Consider n qubits, which are inicializated to the state

(1)

In the second step the state is changed by application of Hadamard operators

(2)

(The Hadamard operator H is defined as H|0> = 2^-1/2(|0> + |1>), H|1> = 2^-1/2(|0> – |1>) ).

This state represents a superposition of all the base states. In the next step the application the Grover’s operator on the state is done. The Grover’s operator define as follows

(3)

The operator O is such an operator that changes the sign of the vector state, if the vector is solution of the task, otherwise the vector do not changed

(4)

What will be the result the application of the operator G on the state ? Consider the case where we have listed just one item we are looking for a solution which corresponds to the task. Mathematical properties of the operator G is the basis for the implementation of the Grover‘s quantum algorithm. Divide |ψ₁> on the two parts

(5)

(6)

The vector |ψ_A> is not the solution task, while the state |ψ_B> is one. Applying the operator O on the state |ψ₁> we get the result as follows

(7)

Define an angle θ as

(8)

where

(9)

We have

(10)

Re-use of G on the state |ψ₁ > k times reads

(11)

With increasing values ​​of k the vector G^k|ψ₁> is more and more closer to |ψ_B>, which is the solution of the task. The state G^k|ψ₁> will by almost equals to |ψ_B>. We expect that there is the value of k that

(12)

If the expression (11) is valid then we have

(13)

and at the same time

(14)

Combination of these two terms gives the following expression for the number k

(15)

There are also N = 2ⁿ . The number k have to be a natural number, because the number represents the action of the operator G on the state | ψ₁>. Given the function arcsin(x) and if we take in an account that arcsin (1/2) = π /6 we have N = 2² = 4 and k = 1. There are a number of qubits namely n = 2, for which k = 1. In this case, the Grover‘s algorithm behaves like a deterministic algorithm. For n > 2 we do not find a solution in order to be non-negative integers.

3. Results and discussion

We have found that the Grover‘s algorithm can behave as a deterministic algorithm for the case of two qubits; then k = 1. This could serve for an experimental testing of the algorithm. Indeed, in paper [4] had a system of two qubits. As it was noted in the work, N = 4 is a special case, in which a single query would provide the marked element with unit probability. Classically, a single query of a four elements searchs space followed by a guess can only result in a successfull outcome with 50% probability.

For the case of n > 2, the number k is not an integer. If N >> 1 we can do an aproximation

(16)

a the expression (15) takes a form

(17)

We take then the nearest integer number to , and we get an integer value that represents the number of iterations in the Grover‘s algorithm. The algorithm is not longer deterministic, and we can not find a solution with P = 1 after iterations. However, P is usually close to the unit, therefore with a high probability we will find the right solution. For example, for n = 4 there is 16 items and the final state will be

(18)

The comma in (18) means there is not wanted item in the sum. The state | 7> represents the search item. Probability reads

(19)

4. Conclusions

Quantum computation is a new computational model that utilizes the principles of quantum mechanics. Its goal is to solve problems that cannot be solved classicaly efficiently. The Grover’s quantum algorithm for searching is more efficient than the best classical alternatives. The Grover’s algorithm does not attain the exponential speedup of Shor’s quantum algorithm [5]. However, it is more versatile and provides accelerating NP-complete problem through exhaustive search over possible solutions [6].

References

[1] Grover L.K., 1996. A fast quantum mechanical algorithm for database search.

In Proceedings of 28th ACM STOC (1996) pp. 212-219.

[2] Grover L. K., 1997. Quantum mechanics helps in searching for a needle in

a haystack. InPhys. Rev. Lett. 79 (1997) pp. 325-328.

[3] Deutsch D., Jozsa R., 1992. Rapid solution of problems by quantum

Computation. In Proceedings of the Royal Society, London, A 439 (1992)

pp. 553-558.

[4] Brickman K.-A. et al., 2005. Implementation of Grover’s quantum algorithm

in a scalable system. In Phys. Rev. A 72 (2005)p p. 050306(R)-050306-4.

[5] Shor P.W., 1997. Polynomial-time algorithms for prime factorization and

discrete logarithms on a quantum computer. In SIAM Journal on Computing,

26, (1997) pp. 1484-1509, Earlier version inFOCS’94, quant-ph/9508027.

[6] Gerf N. J., Grover L.K. and Williams C.P., 2000. Nested quantum search and

structured problems. InPhys. Rev. A 61 (2000) pp. (032303-1)-(032303-14).

Autor:

RNDr. Viliam Malcher, CSc.
Pracovisko: Fakulta managementu UK, Odbojárov 10, Bratislava

Recenzenti:

Ing. Jaroslav Vojtechovský, PhD.
Pracovisko: Fakulta managementu UK, Odbojárov 10, Bratislava

prof. RNDr. Michal Greguš, PhD.
Pracovisko: Fakulta managementu UK, Odbojárov 10, Bratislava

Vydanie:

Digital Science Magazine, Číslo 4, Ročník II