Quantum Algorithms

Quantum computing has been on the rise in popularity the last couple of years, with Google, Microsoft and IBM leading the way. We know that in order for a computer to do anything useful, it often makes use of reusable ways of solving problems known as algorithms. However, quantum computing algorithms are very different from their classical counterparts.

Although quantum computers probably wont replace classical computers in the near future, there are some things that classical computers just cannot do very well (due to time requirements) or at all. This is where quantum computation excels, as it is able to take advantage of quantum physics to significantly reduce the amount of time required to solve large problems. To do this, one can make use of quantum algorithms to assist with such calculations.

What is a quantum algorithm? Well there are many examples of such quantum algorithms. What they do is take advantage of quantum superpositions and entanglements to arrive at answers much faster than a classical computer could (depending on the problem). By possessing all states at once, it essentially takes all possible routes at once, instead of step by step. Lets take a look at the first one called the Deutsch algorithm.

The Deutsch algorithm was created as more of a theoretical excessive to prove that it could be done. It was put together by David Deutsch in 1985 where he wanted to prove that such an algorithm could solve a problem with fewer steps than what a classical computer would require. The problem was this:

There are 4 functions
f0 => f0(0) = 0 and f0(1) = 0
f1 => f1(0) = 0 and f1(1) = 1
f2 => f2(0) = 1 and f2(1) = 0
f3 => f3(0) = 1 and f3(1) = 1
f0 and f3 are called constants, f1 and f2 are called balanced functions

The problem requires that each function gets tested to see if it is a balanced function or if it is a constant function. To do this with a classical computer would require that each function be tested with two bits; however, Deutsch wanted to prove that using quantum computation it would only require testing once each time.
(here is a diagram of what it would like)

In future articles we will go over how to draw a quantum circuit. Here is a basic explanation of the process:

goes through the Hadamard gates, then puts into state
Then proceeds to the f gate which then further modifies the state
Examining the state, we can say
f0 =>
f1 =>
f2 =>
f3 =>
Next through the last Hadamard gate
if i = 0 then qubit is |0>
if i = 1 then qubit is |1>
if i = 2 then qubit is -|1>
if i = 3 then qubit is -|0>

Making the final measurement, we would get a 0 if it was i=0 or i=3 and a 1 if i=1 or i=2
Basically, this proves that it is possible to solve the problem with fewer steps required. This of course was a simplified explanation of the algorithm, but it effectively demonstrates that taking advantage of the quantum world has great potential to help solve very difficult problems, by classical computation standards.

Further reading/watching
Quantum computing for everyone
Quantum computing: an applied approach
https://www.youtube.com/watch?v=sjINVV2xOow a playlist by Andrea Morlleo