An algorithm is a set of instructions or procedures for solving or performing a problem. A quantum algorithm is designed to operate on a quantum computer. The algorithms leverage the properties of quantum mechanics, such as superposition and entanglement, to solve problems more efficiently than classical algorithms. We will learn about some critical concepts associated with algorithms and some famous quantum algorithms!
Big O Notation
Big O notation describes the worst-case time it takes an algorithm to run as a function of the input size. For instance, if an algorithm takes constant time, it would be described as O(1). However, if an algorithm takes time proportional to the input size, it would be described as O(n). Other standard notations for big O include O(n^2) for quadratic time and O(log n) for logarithmic time.
The Goal
The fundamental goal for quantum algorithms is to offer a speed up over their respective classical versions. For instance, classically, the time complexity to search an unstructured list would be 0(n) (looking over each element at a time), where using Grover's algorithm, you can shorten the time complexity to O(n^1/2), a quadratic speedup.
Source: http://bigocheatsheet.com/
An oracle can be considered a magical black box that can answer specific questions with a single output. Don't worry about how for now. We want to get a high-level understanding of the concept. For example, if you wanted to know the answer to a math problem, the oracle could give you the solution without going through all the steps to solve it yourself. We use oracles when designing quantum computers.
If you are still confused, watch the video!
Quantum algorithms have three main limitations, including:
Limited scope
Quantum algorithms are designed to solve specific problems more efficiently than classical algorithms. They cannot be used to solve all problems and may not be more efficient for some issues.
Error correction
Qubits are very fragile and sensitive and, therefore, susceptible to errors due to their surroundings. As a result, we must first design fault-tolerant qubits before we can unleash the full potential of quantum algorithms.
Physical limitations
Quantum algorithms require thousands of qubits, and current quantum computers can't support that many.
NISQ stands for "Noisy Intermediate-Scale Quantum," it refers to a class of quantum computers currently being developed. While these computers are not as powerful as the hypothetical fully fault-tolerant quantum computers, they still have the potential to solve specific problems more efficiently than classical computers.
To look at the interaction between classical and quantum computers look at the diagram I’ve drawn!!
Variational Quantum Eigensolver. VQE is used to study molecules, tiny particles that makeup everything around us. It helps scientists understand the properties of molecules and how they react with each other. One real-world application of VQE could be in designing new medicines. By using VQE, scientists can simulate the behaviour of different molecules and find the ones that work best as new drugs to fight diseases.
Quantum Approximate Optimization Algorithm. This algorithm helps solve optimization problems, which involve finding the best solution among many possibilities. An example of an optimization problem is finding the shortest route to visit multiple places. One real-world application of QAOA could be logistics, where companies must plan the most efficient delivery routes for their trucks. QAOA can help find reasonable solutions quickly, saving time and resources.
In this section, we’ll learn about the most famous Quantum Algorithms through real world scenarios!