The Hype of Quantum Algorithms

Quantum algorithms, different from quantum protocols, are a specific procedure for solving computational problems. These are different from protocols because they are a set of standard rules that allow multiple devices to communicate. Algorithms are a set of instructions given to a computer.

The two main goals of effective algorithms, quantum and classical, are simple:

1. Accuracy — to solve a problem correctly
2. Efficiency — to solve a problem as fast as possible

While it is important to solve problems correctly, this is usually not the issue algorithms run into. However, many times it comes down to how fast an algorithm can be computed. This is why there is a set notation to differentiate the efficiency of each algorithm, known as Big-O Notation.

Big-O Notation reports the number of operations needed to run based on the worst-case performance of the algorithm, expressed as a function of input size (n). This is different from runtime because runtime can change solely based on the hardware used to run the algorithm.

By using this benchmark to compare efficiency, algorithms can be represented in Big-O Notation in the form of O(f(n)). Where O stands for order and inside is the function of n that determines how many operations are done as the input size increases or decreases. Below are common functions of input size in Big-O Notation.

For quantum algorithms, the goal is to build ones that can perform more efficiently than their classical counterparts. Quantum algorithms can do this by leveraging quantum mechanical properties, such as superposition, interference, and entanglement. In fact, some quantum algorithms that can do this already exist. One such algorithm is Grover’s Algorithm, which has a quadratic speedup for search using amplitude amplification. This algorithm can perform in square root time instead of in linear time. Another algorithm is Shor’s Algorithm, which has a super-polynomial speedup for factoring using Quantum Fourier Transform. This algorithm can perform in cubed logarithmic time instead of approximately quadratic time.

Many algorithms being developed today, however, cannot be made using just quantum computing because not all quantum algorithms are more efficient than their classical counterparts, especially with current noisy quantum computers. This is what has formed near-term and hybrid algorithms that can perform applications on noisy, small available quantum devices. With hybrid algorithms, they use a combination of classical and quantum algorithms to create even greater results than choosing one or the other. In the future, the use of hybrid algorithms will become more prevalent because they take advantage of classical and quantum computing.