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 |ψ1> 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 |ψ1> we get the result as follows

(7)

Define an angle θ as

(8)

where

(9)

We have

(10)

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

(11)

With increasing values ​​of k the vector Gk1> is more and more closer to |ψB>, which is the solution of the task. The state Gk1> 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 = 2n . The number k have to be a natural number, because the number represents the action of the operator G on the state | ψ1>. Given the function arcsin(x) and if we take in an account that arcsin (1/2) = π /6 we have N = 22 = 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

 

11 Comments on “Can be Grover’s quantum algorithm deterministic?”

  1. Once your customers are enticed and make an order, your next move is to collect psyments
    from your customer then transmit the transaction details to
    yyour supplier (wholesale dropshipper). In this type oof business the dropshipper oor the wholesaler supplier will
    be the one who will provide the products to you and delivers to the customers.

    When opened, a bifold wallet usually has one
    long pocket for keeping cash as well as a number off smaller pockets appropriate
    for keeping ccredit cards as well as oother small cards.

  2. How much do they know about your company or industry.

    If you are a self-employed small business, sole trader, individual who are looking for
    new waus to earn quick and easy money. The search engines like to see “Natural Links of Love”, a feew high quality links will go a lot further than many low qality links.

  3. While picking up the occasional discounted item won’t usually break-the-bank, buying just becase something is
    discounted really doesn’t make much sense. Since many are also making money out from it the devil way.

    Jewelry with a higher content of metfal components like sterling silver is more widely sold on the market compared to thhe fine
    type.

  4. A wholesale directory lisats thousands of suppliers and wholesalers in a website.
    Legitimate drop shippers will not charge you a single cent upfront, like monthly fees.

    To make the besat out of your customized armbands be sure that the
    logo you end up using as no fades and is fairly simple.

  5. When using a free dropshipper,they should allow you to look and choose from the variety of products they carry.

    With a one-stop shop, your customers need not go elsewhere to bbuy these things.
    These weddding dresses are usually products tnat aare overstocked, and thatt is why
    the wedding dresses are provided at verdy cheap rates.

  6. This is why thee inventory cycle is shortened and turnover improved.

    If you are retailing the clothes in the UK but they are made elksewhere
    then this isn’t a negative but just make sure you check with the wholesaler to see if they operate a supply source ethical policy.
    Geet a foot spa and pedicure before you slip your feet into those sexy
    shoes, though.

  7. hi!,I like your writing very so much! share we be in contact
    more about your article on AOL? I need a specialist on this
    area to unravel my problem. Maybe that is you! Taking a look forward to see you.

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *