00:00Will quantum computing help us create a better world, or will it destroy it? Now, if you learned one thing from me today, it's this: quantum computers don't work by trying every possibility at once

00:11Quantum computers don't speed up every single problem, they're faster for a certain set of problems, but there's only a few dozen or so quantum algorithms

00:18Now, in traditional terminology, algorithm means just a set of instructions, but when we talk about quantum algorithms, what we really mean is instructions that actually harness quantum properties and can potentially solve these mathematical problems much

00:26faster than a classical machine

00:33So you're saying, wait, only a few dozen quantum algorithms that are useful, what good is that, and can it run Crysis? Really need to be asking the important things here

00:41The answer here is that quantum computers could, in theory, simulate any classical system, so technically it can, but it won't do you any good, and I really don't have enough qubits for it

00:49However, even though there's a limited number of quantum algorithms, the ones that do exist can have a huge impact on very important problems

00:56Let's talk about these five quantum algorithms that can change the world, some that can

00:59have really near-term impacts

01:01Quantum computing is coming into the real world, so be ready

01:04And obviously, these are light overviews of each algorithm, and there are more things to go over, like the actual math, the circuits, and the steps, so subscribe to this channel to be notified when I put out new videos

01:15But by the end, I think you'll start building a little more intuition of what problems can actually be quantumable

01:20Number one, the variational quantum eigensolver, or VQE, and chemical simulations

01:25The variational quantum eigensolver is one algorithm that can have really near-term applications, one

01:30thing you could do is simulate molecules and chemical reactions, and how can it do that? In chemistry, the properties of atoms and molecules can be found by solving the Schrödinger equation

01:39However, the problem gets harder, the more components, the more atoms you add, so exact calculations are hard above just a few atoms

01:46There's always approximate solutions, but once you get up to a few dozen atoms, classical computers just can't do those problems efficiently anymore, and very quickly, we get to a point where we can't solve any of these problems anymore

01:57So how does VQE work on a high level? What the quantum Variational eigensolver really does is calculate the eigenvalues of a matrix, and it does so really efficiently for large matrices, which means we can actually calculate these properties of large molecules

02:09The matrix that we use in this calculation is a matrix that represents the Hamiltonian

02:14The Hamiltonian describes the total energy of the system of atoms and molecules that we want to consider

02:20The quantum subroutine has two steps: number one, prepare the quantum state, and sats number two, measure the expectation value, which, if you're familiar with machine learning, can be thought of as the cost

02:30function, so we start with an ansatz, which really means an educated guess or assumption

02:36For us, in the problem of simulating molecules and finding the ground state energy, we want to have a guess of the quantum state

02:41The trick is actually preparing these ansatz; the guess actually needs to be pretty good, and what this hybrid algorithm does is actually uses this quantum step inside a classical optimization loop to help prepare it

02:53The classical step then loops until we find the minimum eigenvalue of the Hamiltonian, or the state of the system, which is the lowest ground state energy, and now you see why it's

03:01called variational

03:02It's a mathematical analysis that uses variations, which is small changes in functions, to find the maximum and minima, just so what we're doing here with our minimization of the expectation values

03:13It also means, because of the variational principle, the expectation value is larger than the smallest eigenvalue of h

03:20The quantum subroutine measures that expectation value and gets it closer to the smallest eigenvalue of the Hamiltonian, which is the ground state energy we're looking for

03:27We can then use this minimum energy in other calculations, like modeling the evolution of the Wave function and the wave function representing the molecule over time

03:36Now, I know this is a lot, but this is just an intro to the algorithms and what they do, so don't worry if you don't understand this completely

03:41I plan to make videos in the future breaking down each algorithm separately and diving really deep into the math and circuits, so make sure to like this video and subscribe if you'd like that

03:52Beyond just chemistry, the solution of large eigenvalue problems would have even more applications that would really affect our day-to-day life, like for example, designing new materials, whether they could be discovering new materials that, I don't know, stand up to higher heat or strain for airplanes, so maybe we could fly faster or make more effective batteries

04:09We're coming into the NISQ era, this noisy intermediate scale quantum device era, and our chips have only a few hundred physical qubits and have a high error rate, low coherence time, and they may need a lot of error correction

04:20However, algorithms like VQE only need a handful of cubits to work and are a shallow circuit

04:26A shallow circuit means that it does not really have a lot of sequential gates

04:29That matters because quantum information can only be stored for a short amount of time called the coherence time, we need to apply all the gates and read out the data before the quantum bits decohere, and the deeper the algorithm, the longer the coherence time

04:40But how VQE works is by calculating some part of the data using a quantum computer and feeding that information back into a regular computer and looping back

04:50It's what we call a hybrid classical quantum algorithm, so if we don't have a lot of gates that need to go in order, then we can have a shorter coherence time

04:57Other examples of variational algorithms include variational quantum factoring, it's Actually, factoring numbers for breaking RSA encryption in a new way, there's also quantum approximate optimization algorithm, which can be applied to scheduling problems, for example

05:11Number two, quantum unconstrained binary optimization, CUBO, used for optimization problems like traveling salesmen

05:16Quantum annealers are built for translating these CUBO problems and icing problems effectively onto quantum hardware

05:23This is super useful because efficiency is kind of an everyday problem

05:28We want everything to be more efficient in our lives, right? Binary objective functions, the ones that CUBO can do efficiently, can be looked at as graphs

05:34This graph can be translated onto the topology of the quantum chip, so you can take this optimization problem and you construct the Hamiltonian equation needed to minimize, and you can represent it with this graph where the nodes are A and B, the time they spend in each city for example to make the sale, and the weights corresponding to that equation, and the edge between them, the A and B with the weight seven, may be the time that they spend traveling between the cities

05:58The minimization of this function is the lowest energy state of the system, so practically how Does this work? We apply a magnetic field to control the superposition of the qubit, changing the probability of it being one or zero, and the weights here are controlled by the qubit superposition

06:13You can do the same thing to the coupler, and that correlates the two qubits, and that corresponds to, say, the distance between the cities and the traveling salesman

06:22So you see how these QUBO problems can map from that equation onto the qubits and the connections between them, and for the optimizing solution, you can think of this as looking over a landscape and finding where the low point is, the lowest energy

06:33configuration is the optimal solution to these QUBO problems

06:37What other problems can it solve? Well, another one, for example, is a satellite placement problem

06:42We want to determine where we should place satellites to cover observation of the points that you want

06:46Another one is a nurse scheduling problem

06:48So check out this video here where I talk a little bit more about quantum annealers and the differences between them and universal-gate quantum computers, and some more on the hardware and applications of these annealers

06:58Number three, quantum machine learning algorithms

07:00Now, this is not a particular algorithm, but I did want to discuss a little bit about quantum machine learning and what it is, and some of the research directions behind them

07:09Quantum machine learning and the research can take different forms, so first, there's actual quantum machine learning algorithms on quantum computers, then there are also classical algorithms inspired by quantum mechanics

07:20We can also try to do classical machine learning on quantum data

07:23All of these fall under the quantum machine learning umbrella

07:25One major research push in quantum machine learning has been developing quantum versions of known Classical machine learning algorithms, however, another direction has been to make quantum algorithms all entirely quantum, for example, one is pattern recognition, but you can, like we talked about with VQE, and we'll later talk about with Shor's algorithm, also have quantum subroutines

07:45One idea is to have the quantum subroutine maybe prepare data in a way that a classical computer can more efficiently process or speed up a bottleneck in the training

07:52A lot of research is being put into finding quantum versions of K nearest neighbor methods or support vector machines and other classical machine

08:02Learning algorithms, however, an interesting path going on is talking about quantum learning

08:08How would quantum tech process input outputs and either optimize parameters and learn, hopefully, a new effective strategy for learning? How do we even represent data in a quantum way? There are proposals for quantum versions of neural networks as well

08:20Most of them work with hot field networks, which are powerful for the related task of associated memory that's actually derived from neuroscience rather than machine learning, but how good are neural networks anyway? I talked to one of my friends in Neuroscience, a bit about this actually, quantum neural network models actually work for a lot of things, but they're not great for some instances, and maybe a lot of instances, just because this is an oversimplified representation of the brain, that doesn't mean that the whole neural network model is totally useless

08:48Other approaches, like modified convolutional neural networks, could be able to deal with these special cases, and we can try to better represent what the brain does then, so quantum is not a perfect model here either

08:59Now, there are a ton of approaches like using quantum fuzzy feed-forward

09:03networks or pattern recognition with adiabatic computing, there's still a lot going on, and it's still a really young field and has a lot of open questions and directions to research

09:13I'll actually link a paper below that actually reviews the developments of quantum machine learning and introduces you to a lot of these concepts and how they relate to classical machine learning, so if you want to become involved in quantum machine learning, classical machine learning backgrounds are actually highly recommended

09:28If you want to get started in that, I really recommend Andrew Ng's courses, his machine Learning course is a classic, and his deep learning specialization is one of the best online courses I've ever taken

09:36The impact here, I feel, is similar to any machine learning algorithms, and the impact we've seen over the last years

09:43We've seen a huge machine learning impact

09:44You know, Google Pagerank was one of the first examples of machine learning, and Google pretty much rules our life today, and now everyone can train a neural net pretty easily with just a few lines of code, but there's a lot of data in the world, and it's only increasing, so we can hope that quantum can help with processing or making more

09:59Efficient algorithms, number four, Grover's algorithm for efficient search

10:04Search complexity for unsorted databases is of N, using big O notation

10:08Grover's algorithm, which actually takes the square root of N time, is the fastest possible quantum algorithm for searching an unsorted database

10:16So a lot of other quantum algorithms are exponential speed ups, and this is only quadratic, but again, think of how often we search every day

10:24Wouldn't it be really impactful to have a quadratic speed up? But here's a key point, when you talk about Grover's algorithm searching faster, sometimes people may think, oh

10:32It's just parallelizing, but no, quantum annealers are built for translating these CUBO problems and Ising problems effectively onto quantum hardware

10:40A better way to think about this is that the Grover's algorithm doesn't actually search faster, but it actually inverts a function

10:47Germa's algorithm applies when you have a function that returns true for one of its possible inputs and false for all the others

10:53The job of this algorithm is to find the one that returns true, so what it really does is it searches the input of the function until it finds the single input that causes the function to return true

11:05So even though Grover's can search faster, ask yourself, does your application have a way to map it onto the quantum system? So molecules are a little more clear to map onto quantum states, but how do you map a word onto a qubit state, and can you actually find a function that returns true for that specific input? It's not like what we can do with quantum states is like what we can do classically with, for example, converting a string array into a map, and obviously there's some different complexities if we talk about binary search or something like that, but maps are much faster, so even though Grover's could work

11:35For searching, it does not guarantee that we can speed up every search

11:40Really, the power of Grover's algorithm will come when search can't actually scale well classically, because remember, classical algorithms and parallelization are actually pretty powerful right now

11:49For example, people ask me a lot about solving hashing with Grover's algorithm, but there's actually classical algorithms on collisions that are much more effective than Grover's

11:58So what we really want to do is actually compare Grover's power against the best possible classical algorithms available, and not just in a normal case

12:05So examples of these problems, or Grover's, can actually be useful, and where the problem quickly scales more difficult classically, are traveling salesmen or graph coloring problems, where you have to color a map, for example, with three colors and make sure the same color isn't touching

12:18So while Grover's maybe won't be useful for every search, there is research going into implementing Grover's algorithm to solve NP complete problems, and that would be huge

12:27Number five, Shore's algorithm for fast number factoring, like breaking RSA encryption

12:32Now, I've talked a little bit about Shore's algorithm, and a couple of my other videos, because Shor's algorithm is kind of the first algorithm a lot of people hear about when you're learning about quantum computing, and they panic

12:42Break encryption, two common cryptosystems are RSA and elliptic curve

12:46When you're online, any information that you exchange will be encrypted with an algorithm, and often one of these, and both of these are vulnerable to attacks by quantum computers

12:56Multiplying two prime numbers together is easy, but taking a large number and factoring it to get those two primes is difficult, so it would take longer than the age of the universe, right? Now, to factor a 1,400-bit key with a classical computer, Shor's algorithm can actually 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

13:20How Shor's algorithm actually works is by finding the period of a function

13:24What's the period of a function? It's when you apply some operations and the results go up and back down, kind of like a frequency wave

13:28So, for example, you can take a number to the N and apply a modulus function to it, say 91

13:34Prime factors of 91 are 7 and 13, since it's a modulus, the remainder one is divided by 91, you know that the answer can vary between 0 and 90, but not above that

13:43So even as the number gets bigger, we can fit more 91's into it, and the remainder varies

13:49This function has a period associated with it, 12, because once we get to 2 to the 12, the remainder is 1 again

13:57So we can find the factors quickly if we have a fast way of finding the period of a known periodic function

14:03There are five steps to this, but only one of them is actually quantum

14:06Now, what known classical function do we have that relates to frequency and time? The Fourier transform

14:10We actually have a quantum version called The quantum Fourier transform, a Fourier transform, maps from the time domain to the frequency, or the Fourier domain

14:19Frequency is exactly what we want to know here, and quickly

14:22Now, you may say this is trivial using 91 or 25

14:26Sure, it is trivial, but it shows the proof of concept to understand why a quantum algorithm is faster than a classical algorithm and actually works differently

14:33Now, why can this change the world? Well, breaking encryption is a pretty big problem

14:37We're going to have to find new encryption techniques that stand up to quantum computing attacks

14:43Now, it would take about 4,000 qubits to break an

14:45RSA key, except don't panic, these are actually perfect logical qubits because of error correction

14:50We actually need many more physical qubits

14:54John Preskill noted his electron quantum information that we would need something like 10 million physical qubits to actually run the Shor's algorithm to break an RSA key of that size, and we're still pretty far away from that milestone, but it's something we have to consider

15:06Hey, I said not all quantum algorithms are good, right? That makes quantum computing a technology with a lot of potential future impact, not even looking at the use cases in cyber security and telecommunications, so even though we only have a dozen quantum algorithms, the impact that they can have is huge, since optimization and search problems, well, they're really everywhere

15:26You can actually go to this website, quantumalgorithmzoo.org, to see a list of quantum algorithms

15:33As we look into more algorithms, they can actually help with a lot of optimization problems and even search, and really, this is the key to quantum algorithms and their impact

15:41We have to figure out how to map the actual problem onto a qubit and the quantum states

15:46I hope you enjoyed this video and learned a little bit more about What problems can actually be quantum-able? And if you did, please like this video and subscribe, and I'll see you in the next one.