What is an Algorithm?
You most probably have already heard the word "algorithm" and you may have a vague idea of what that means but let's dive deeper and see algorithms from a computer scientist's point of view!
Each algorithm includes an ordered set of well-defined instructions that should be followed step-by-step to give us the desired result. The important things that make an algorithm different from any other type of instruction set are:
Sequence is crucial and ordering should not be changed.
Each instruction should be well-defined and there is no place for ambiguity.
Input and output are known and the algorithm is supposed to give the correct answer for any input that has follows the desired format for the input. There is no guaranteed output for input that does not match the defined criteria.
Keep in mind that an algorithm is independent from a program that implements it. A program has to follow and algorithm but the algorithm has no dependency upon the program and can be implemented by many different programs written in different programming languages or programs written in the same language but differing in details.
The algorithm is the thing that determines how fast we will solve the problem. Different algorithms may be offered for the exact same problem and some may solve the problem faster than the others. An active and interesting area of computer science research is designing algorithms that are able to solve specific problems faster. Let's see an example to understand this better.
A very well-known algorithm that can be used for sorting an array of n integers is called bubble sort.
For doing bubble sort on an array we start from the first element of the list and check if it is smaller than its next adjacent number. If it was smaller we do nothing and if it was larger we swap the 2 numbers so the larger one would be after the smaller one. Then we move to the next number on our list and do the same thing and keep doing that until we have checked the whole list.
At this stage, the very last element of the list is the largest one in the list so we have at least 1 element sorted out and n-1 elements left. If we repeat scanning the whole list for n-1 more times, we can know for sure that the whole list is sorted. Check the animation below to get a better idea of how bubble sort works:
Computational Complexity
In the algorithm design world, whenever we talk about an arbitrary number denoted as 'n', our assumption is that 'n' is a large number. 'n' can be anything but by default on our minds it is a very very big number and you know why? Because when designing algorithms we mostly care about large and complex cases of a particular problem, not the small and simple ones. As an example, when talking about sorting an array we mostly think of sorting an array with a thousand or even a billion numbers and an array with only 5 numbers is not the matter of concern for us.
Computers can sort an array of length 5 super fast even if you choose the worst algorithm for doing so, but if you choose even a mediocre algorithm for sorting a billion numbers, you have to be super patient!
At this point, you may ask so how can we compare algorithms and choose the ones that will work better in extreme cases? Well, computer scientists also have a solution for that. There is an standard notation called "The big O notation" used to express how long an algorithm is going to take to execute if we feed it an input of size 'n'. As an example, the bubble sort algorithm that we just saw takes approximately O(n^2) operations when its input is of size 'n'.
Again, you may ask how did found out bubble sort takes about O(n^2) operations to do its job? To answer that question let's take a look at bubble sort implemented in Python:
Take a look at the instructions we have used on the "bubbleSort()" function. Which ones do you think are computationally expensive to do?
In fact, running a single "if" instruction or assignment of value to a variable is nothing for the computer! But when the computer has to do those simple instructions over and over, their cost becomes considerable. We assume simple instruction like a single "if" instruction or a single variable assignment cost O(1) and when they are included inside a loop that iterates for 'n' times their cost will become O(1*n)=O(n).
The thing about bubble sort algorithm is that we have "nested loops" so our inner loop is included inside another larger loop that iterates 'n' times too. That means whatever is included inside the inner loop will be repeated O(n*n) times so their cost is O(1*n*n)=O(n^2). That is how we can find out the cost of an algorithm by looking at its implementation!
Bubble sort is not the only algorithm we can use for sorting an array but there are other algorithms like "merge sort" or "quick sort" that are less computationally expensive and can be done in O(n*log(n)).
All we have discussed was in the context of classical computers. In fact, computer scientists have proven that it is impossible to come up with an algorithm that can sort an array in less than O(n*log(n)). What if we can sort numbers much faster with quantum computers? After all, sorting is not a super complex problem. There are problems that are so complex that any algorithm we come up with will be unable to solve the problem on a classical computer in finite time.
For example, you may come up with an algorithm that takes 4.5 billion years to be able to simulate how exactly the "Big Bang" has happened but is there any use to that algorithm at all? Who is going to wait 4.5 billions years for that to be done?
This is where quantum computers enter the battlefield!
Quantum Algorithms
Quantum computers have potential to solve CERTAIN problems faster than classical computers due to their use of quantum properties.
Quantum computers use a fundamentally different instruction set than classical computers; due to this, they can run different algorithms. Through clever use of entanglement, superpostion, probabilistic measurement, and more, we are able to communicate with the quantum computer. Below is a basic worflow of how we would approach creating a quantum algorithm.
Some of the quantum algorithms that we can solve right now include:
- The Deutsch Algorithm, which tells us is a Boolean (a true or false statment) is "constant" or "balanced". a constant statement would give us all either 1 or 0, and a balanced function would give us exactly 50% 1s and 50% 0s.
- Simon’s Problem, which was the first algorithm to show us exponential speed up in computational time compared to the best clssical algorithm. In Simon's problem, we are given an unknown function (called a Blackbox function) that can work in one of two ways. It can either be a 1:1 function (have exactly one output for any input) or a 2:1 function, which has exactly one output for every two inputs.
- The Bernstein-Vazirani Algorithm, which is similar to the Deutsch Algorithm, except it utilizes a blackbox function with an unknown string instead of an unknown boolean.
Each link will take you to the Qiskit textbook for each algorithm, which contains more in depth explanation and built in notebooks to explore. We are also going to work through them on our own in upcoming sections!
Working with Oracles
Quantum Oracle is a black box used extensively in quantum algorithms for the estimation of functions using qubits.
We often consider a quantum computer to behave like a black box, or an oracle - we don’t care about the specifics of the circuit it implements, we just assume that it will perform some operation that we specify and return us an output in the form of qubits.
0 Comments