Quantum Computing Concepts – Quantum  Algorithms
Articles,  Blog

Quantum Computing Concepts – Quantum Algorithms


It is often said that the power of quantum
computers comes from quantum parallelism which means that instead of processing each input
one by one, quantum mechanics allows us to do operations on a super position of all the
possible inputs at the same time. So let me give you an example of a quantum algorithm
that uses quantum parallelism to arrive at the solution in a much smaller number of steps compared to a classical computer. It’s called the quantum search algorithm and it’s used every time I have a large database and I’m trying to recognise a certain entry within that database. Imagine I have a telephone number and I want to find out who it belongs to using an old telephone book. The names are in order, but the numbers are not. So in the classical world, the only option I have is to start checking all the entries in the book until I recognise my number and find the name associated with it. If there are one million names in the book, it will take me on average, half a million attempts before I find the one I’m looking for. A quantum computer can do much better than this. It will find the name I’m looking for using a number of steps that is only the square root
of the number of items in the list. So in this case, one thousand steps instead of half a million. Let’s see how it works. I will show a really simple example where I use three quantum bits to encode eight numbers, each one associated to a name in the telephone book. I want to find which name goes with the code 1-0-1. First of all, I create a quantum super position of all the possible combinations of values for the three qubits. In quantum mechanics, we assign to every part of the super position an amplitude that tells us how much of that particular code is included in the super position. The square of of the amplitude for each code is the probability that if I measure the qubits, I find them in that particular code. So in this case, all the amplitudes are 1 over the square root of 8 so that the probability to measure each one of the eight codes would be one eighth. Next thing we do is apply a global operation to all the qubits, such that the amplitude
of the code I’m looking for changes sign. Whereas all the others are left untouched. Then I apply another operation that amplifies the difference between each amplitude and
those of the equal super position states. Now you see that the amplitude of the 1-0-1
code is greatly amplified because it’s very far from the average, whereas the others are slightly reduced. If I repeat the sequence just one more time, the amplitude is almost completely concentrated on the 1-0-1 code so that if I measure my register of qubits
after these two steps, I will find the 1-0-1 code with about 95% probability. Classically, I would have needed four attempts to find that code with better than 50% probability. This simple example should give you a sense of what makes quantum algorithm special. They operate globally on a super position of quantum codes and they are designed in such a way
that at every step, the initial quantum super position converges towards the correct answer which is no longer a super position so we can actually measure it.

22 Comments

  • Maximilian Paradiz

    You set out with the mission of finding out which name is associated with the code 101. Then, you make it so that the amplitude of 101 is high enough so that you will measure that value with 95% probability… You perform a measurement and get the output "101".

    So… when do you find out that "Charlie" is associated with that number?

  • Noah Namey

    Ok… I have to come clean.
    I'm grokking somewhere around 20% of the content, but I'm 100% fascinated with that leopard skin shirt.

  • Khorzho

    HA! HAHAHAHAHAHA! How novel. Quantum computers will have the very nature of the universe tell us the answers to our questions.

    But what if the universe gets tired of our petty questions?

  • Tim

    At 2:10 you say a global operation is performed on all qubits such that the qubit we are looking for has a negative value. What is this operation? Correct me if I'm wrong, but in my opinion this is the crucial step of this whole calculation.

  • dirmajanse

    Thank you Andrea Morello, your videos about quantum computing helped me a lot! Really clear explanations. Best, Dirma

  • Gediz GÜRSU

    It is strange. Should I compute in same number of operations to have better percentage to reach to the correct result instead of 95% ?
    What if I want to be sure %99.999 that the result is correct ?
    Isn't it inferior to a classical computer If I want to be sure ?

    By the way, this explanation is by far the best I have ever seen. Another demonstration that what smart and wise is so correlated with simple and concrete …

  • rollaz

    Grandissimo professore, anche se questo è l'unico video dove indossa una camicia orrenda, rispetto alle altre.
    Oppure questa è una sovrapposizione quantica di tutte le altre indossate negli altri video.

  • Clark G

    I only got 19 sec's in, couldn't stop focusing on that shirt. If you want to impress someone with your words, don't distract them with your apparel. Get your priorities straight.

  • Amit Saxena

    If we know the number already ( charlie matches|101> ) the state we want to amplify how is the search working for unknown states.

  • Dylan Sheils

    So, considering I got confused by this video a first, I think it might be beneficial to add to the video's explanation.
    The following is the process:

    Consider f(x) – The function will return if the person is in the book according to the analogy.
    We assume that, for a specific x, a result(s) will differ from the rest.
    For example:
    f(1) = 0
    f(2) = 0
    f(3) = 1
    (For our qubits, 0 equals a positive version of the amplitude while 1 equals a negative version of the amplitude)
    Now, from the example, you can see that for x = 3 produces 1 which varies from the rest. According to the video which is very good, the qubits are entangled, which allow for all possibilities to be checked because the system can only be described using all that data in a classical sense. The operations allow the QFT formula to take place (it is an operation which allows for destructive interference to occur for the "wrong" answers while causing constructive interference for the correct one hence the increase in probability for the solution and decreased probability for the incorrect ones) that changes the probability based on the mean (considering -1 and 1 have quite a difference in mean that explains the ability for it to amplify the correct probability). At least, according to my combination of different resources and my understanding, I believe this is an accurate description of the algorithm. Think of Grover's algorithm as a universal solver for problems that involves searching with an unknown function to produce a certain result. It also has the sqrt(x) speedup which is nice.

  • JNCressey

    What's the point of measuring and getting '101'? '101' is the phone number we're taking as input. We want to find its position in the database, which is the 8th place or address '111', so we can read off the name of charlie.

  • rodrigo romero

    I get lost when he starts applying operations… , too distracted by the leopard shirt, or is he schrodinger's cat? ;-O

Leave a Reply

Your email address will not be published. Required fields are marked *