The Quantum Earthquake
What are Quantum Algorithms and How do they Work?
When you start your quantum journey, you might feel like you are sitting on an earthquake! As I write this I really am, we had an earthquake here in the Northeastern United States! Even a small one can be scary — and so can quantum algorithms! — so today I want to alleviate the fear and shock of a quantum earthquake. In this article, I will explain how quantum algorithms work, how they differ from their classical counterparts, and how you can go from understanding classical algorithms to quantum algorithms.
Like many others, I first learned about classical algorithms, including the bubble sort, selection sort, and binary search algorithms to name a few. For me, it helped me better understand the basics of quantum algorithms since both types of programs are categorized in similar ways, such as by their function (ex. sorting or searching). Although other properties of classical algorithms, including time complexity, are not focused as much for quantum algorithms, one way we can categorize quantum algorithms is by the way they are executed. The two categories I’ll be explaining today are pure and hybrid quantum algorithms.
To provide some background information, quantum computers are made up of quantum bits or qubits, which utilize the “strange” principles of quantum mechanics. One such property is superposition, and in simple terms, it means that particles can exist in a state where they can be in multiple states at the same time! While classical bits exist as either 0 or 1, a qubit can represent information by existing as a combination of states 0 and 1. This allows quantum computers to perform certain calculations very quickly, as well as output a superposition of values.
Another property that is used all the time is entanglement. Entanglement is when a pair or group of particles is connected such that the quantum state of each particle can’t be described independently of the other particles’ states. Instead of manipulating each bit individually like in classical computing, quantum computers can manipulate many qubits at once, suggesting that some problems can be completed more speedily with entangled qubits. Combining superposition and entanglement, we see that quantum computers can process and calculate data much faster than classical computers, especially when the data set is very large.
Now, pure quantum algorithms are programs that are executed completely on quantum computers. As mentioned earlier, qubits can represent multiple states simultaneously because of their property of superposition. In Qiskit, you can simulate doing this by adding a Hadamard (H) gate to a quantum circuit. As you read more Qiskit tutorials, you will see that the H gate is unique to quantum computing, and it is a helpful way to use the properties of quantum mechanics computationally.
Meanwhile, for real physical quantum computers, scientists “add a Hadamard gate” by using microwave beams and bouncing them off the qubits. This requires a lot of precision, so even if there was the slightest electromagnetic disturbance, a quantum computer’s calculations would be affected.
As you can see, it seems quite difficult to only use quantum computers to execute the quantum algorithms. Hybrid quantum algorithms, on the other hand, use both classical and quantum computing resources. These programs are also known as variational quantum algorithms or VQAs, and they use a classical optimizer to train the parameters of a state prepared by a quantum circuit. Another important component of VQAs is cost functions, or loss/objective functions. This term pops up everywhere in hybrid quantum algorithms because cost functions reveal if an algorithm is making many errors or not. In other words, VQAs aim to reduce their errors by minimizing their cost function.
Furthermore, while cost functions are used in classical machine learning, the cost functions in VQAs are evaluated on a quantum computer, which can be more efficient than their classical counterparts thanks to superposition again! By combining specific parts of classical and quantum computing, we can create powerful algorithms that perform complex optimization tasks more quickly and cost-effectively.
Recap
In this article, we went over the following quantum computing concepts:
- Classical vs Quantum Algorithms
- Superposition
- Entanglement
- Quantum vs Classical Bits
- Pure Quantum Algorithms
- Hybrid/Variational Quantum Algorithms
- Cost Functions
I would like to end with an important point to keep in mind — quantum algorithms and computers are not meant to replace classical computers, but they may be more efficient in certain topics, such as factorization, classification, and many more! As seen with VQAs, combining both quantum computing and classical machine learning can be more powerful than their separate implementations. I hope this has helped clear up any questions you had about quantum algorithms!
Make sure to check out Vidur’s article on specific examples of quantum algorithms and how they work!
For some more readings, check out these links below:
