5 Transformative Quantum Algorithms

Will quantum computing help us create a better world, or destroy it? Now if you learn one thing from me today, it's this: Quantum computers don't work by trying every possibility at once. Quantum computers don't speed up every problem. They are faster for a certain set of problems. But there are only a few dozen or so quantum algorithms. Now, in traditional terminology, algorithm means just a set of instructions. But when we talk about quantum algorithms, we mean instructions that actually harness quantum properties and potentially can solve these mathematical problems faster than a classical machine. Join this channel to get access to perks like behind the scenes and support my channel! https://www.youtube.com/channel/UCzaYH6WeohiHKj3Ih_GdZdQ/join or the same perks over on Patreon: https://www.patreon.com/amarchenkova 0:00 What quantum computers can do 1:20 Variational Quantum Eigensolver 5:11 Quantum Unconstrained Binary Optimization 6:59 Quantum Machine Learning 10:02 Grover's Algorithm 12:27 Shor's Algorithm Variational Quantum Factoring: https://arxiv.org/abs/1808.08927 Eigenvectors: https://textbooks.math.gatech.edu/ila/eigenvectors.html https://scottaaronson.com/papers/qml.pdf Quantum Machine Learning review: https://arxiv.org/pdf/1409.3097.pdf "Quantum resource estimates for computing elliptic curve discrete logarithms": https://arxiv.org/abs/1706.06752 "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" https://arxiv.org/abs/1905.09749 John Preskill's intro to quantum information lecture: https://www.youtube.com/watch?v=Q4xBlSi_fOs #1 Variational Quantum Eigensolver (VQE) and chemical simulations Variational quantum eigensolver is one algorithm that can have near term applications. One thing you could do is simulate molecules and chemical reactions. In chemistry, the properties of atoms and molecules can be found by solving the Schrödinger equation. However, the problem gets harder the more components, the more atoms you add, so exact calculations are hard above just a few atoms. There are approximate solutions, but once you get up to just a few dozen atoms, classical computers just can't do these problems efficiently anymore. Very quickly we reach a point where we can't solve these problems anymore. What the variational quantum eigensolver really does is calculate the eigenvalues of a matrix. And it does so efficiently for large matrices, which means we can actually calculate these properties of large molecules. #2 Quantum unconstrained binary optimization (QUBO) used for optimization problems like traveling salesman Quantum annealers are built for translating Quantum unconstrained binary optimization (QUBO) and Ising problems effectively onto quantum hardware. The problems this can solve efficiently are traveling salesman, scheduling problems, optimal placement problems, graph coloring problems, and even game optimization! #3 Quantum Machine Learning Algorithms Quantum machine learning, and the research, can take different forms. First, there are the actual quantum machine learning algorithms on quantum computers. Then, there are also classical algorithms, inspired by quantum mechanics. We can also try to do classical machine learning on quantum data. All of these fall under the "quantum machine learning" umbrella. #4 Grover's algorithm for efficient search Grover's algorithm is another cool one that could help with efficient search. Search complexity for unsorted databases is O(n), using Big O notation. Grover's algorithm, which takes sqrt(N) time, is the fastest possible quantum algorithm for searching an unsorted database. #5 Shor's Algorithm for fast number factoring (like breaking RSA encryption) Now I've talked a little bit about Shor's algorithm in a couple of my other videos, because Shor's algorithm is the first algorithm a lot of people hear about when related to quantum, and they panic! Breaking encryption! Shor's algorithm can find the prime factors of a number and can "undo" this factoring problem much more easily than a classical computer. And this algorithm was created in 1994! How Shor's algorithm works is by finding the "period" of a function. #quantumalgorithms #quantumcomputing #quantumphysics