5 Quantum Algorithms That Could Change The World
Ғылым және технология
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!
/ @anastasia-marchenkova
or the same perks over on Patreon:
/ 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: arxiv.org/abs/1808.08927
Eigenvectors: textbooks.math.gatech.edu/ila...
scottaaronson.com/papers/qml.pdf
Quantum Machine Learning review: arxiv.org/pdf/1409.3097.pdf
"Quantum resource estimates for computing elliptic curve discrete logarithms": arxiv.org/abs/1706.06752
"How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" arxiv.org/abs/1905.09749
John Preskill's intro to quantum information lecture: • John Preskill - Introd...
#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
Пікірлер: 104
I am so glad that I found your channel. I am learning a lot how to explain stuff to non-expert with enough depth. Deep caring for the audience
Your channel will hit a million and more subscribers. Happy that found you early on. Keep up the good work :)
Thanx Anastasia! As always straight to the point, helpful and well-organized. 🎯 I have a better clue know where to focus my quantum algorithms study.
I am a newbee in the QC field and was procrastinating to work on some homeworks for a while. You just triggered the switch on button. Thanks a lot.
Pioneering so much from one youtube channel! Keep going! The future needs this!
@91722854
3 жыл бұрын
yea, general science and STEM p[romoting channels are oversaturated and we need these now
Great job Anastasia! I can tell you’re putting a lot of work into the channel!
im doing a project using quantum computing this summer. i watch these videos for inspiration to not give up, so thanks!
Welcome back after a long break 🤗🤗
@devanshsavansha9061
3 жыл бұрын
@@Anastasia-Marchenkova I hope you stay safe and healthy 😁😁
@CryptoReds
3 жыл бұрын
@@Anastasia-Marchenkova We want more 🤩
Some of the concepts you've mentioned like the traveling salesman reminds me of an audio book called "Algorithms to live by the computer science of human decisions " by Brian Christian, and Tom Griffith. It's tough read but I'm gonna give it another go since I found a KZread community that actually understands this stuff.
Your video came after so many days 😭😭 Knowledgeable video After watching your video I get motivated towards my work
Your videos are shockingly informative! There was so much good info in here! Very much appreciated!
@voidisyinyangvoidisyinyang885
Жыл бұрын
@@Anastasia-Marchenkova that's what I was wondering! Hilarious. shockingly.
Yes! I was looking for you to address commercial applications of qc. Thank you. I hope this becomes a running topic - applications of quantum computing from the quirky(quarky?) to serious world changing stuff.
@Brycki404
Ай бұрын
There isn’t any commercial applications. Quantum computers are limited and challenged similarly to the limitations and challenges of using superconductors in engineering. System Variables like temperature, pressure, etc can impact whether a superconductor works just like how Thermal fluctuations, control imperfections, and coupling to uncontrolled environmental degrees of freedom can cause noise and errors in quantum systems. This girl resembles how communism sounds good on paper, but doesn’t work in practice.
As always, thank you for uploading such a great video! ciaoo from Amsterdam
VQE reminds me of the variational methods used in certain types of auto encoders and probabalistic bayesian models. I am curious how those are different from the types of quantum algorithms proposed quantum machine learning. When you mention NISQ, I am curious if you are referencing Preskill's paper. That paper actually got me a bit demotivated but I wonder if it is worth a relook or if he has progressed in his research since then. Could would grover's algorithm be useful in situations where you want increased efficiency? Like say you have a database on a space station or have a throughput that is so high you are at the limits of power and heat capability? This is really inspiring! I was actually pretty disilusioned with quantum computing until recently, but I am getting more interested in the field again. Would you ever cover topological quantum computing and Non-Abelian Anyons? I became really interested in that area because I wanted to work with a certain researcher at my old college, but alas it never came to pass. Kept studying it on my own time. Mathematically it is interesting, but I am not so current with the research. I am curious if the promise of fault-tolerant quantum computing could be kept alive!
Variational algorithms in general are surprisingly powerful. In fact, as long as you have an ansatz that is highly entangled and well approximates a Hilbert space then you could solve many problems from simulations to possibly differential equations. Their downside is that they can have plateaus when we try optimizing, but shorter circuits are much less prone to this (ie the quantum convolutional NN).
would love that you talk about the hardware parts of quantum computer
Succinct clarity at its finest, Anastasia. Nice work!
@Anastasia-Marchenkova
Жыл бұрын
Thank you!
Weird comment here, but I do enjoy the new camera distance, it seems like it gives more space for the illustrations you bring up on screen which I find quite nice, keep it up with the great work!
so much new information for me! by the way, thanks a lot for this video!
I loved Crysis reference, and if you actually played the game, you totally rock!!!!!!!!. I did not fully understood the contents video, because last thing I did with a word quantum was spectrum analysis. For these reasons, I will keep up with your updates.
What do you think about quantum computers for ordinary consumers? Would love to hear you on this.
This channel is growing rapidly
Please make a video about IBM Quantum Developer Certification. By the way huge fan of yours from India 🇮🇳 😃👍
Mapping the cost function to qubit is my life!
Anastasia, what is the solution to the schrodinger equation?
Can the "Variational Quantum Eigensolver" sove all types of matrixes? Could this be used to solve eigenfrequencies and eigenmodes for mechanical systems (Modal analysis) and linear buckling? I guess it will still take some time to create the model/matrix to solve, but solving these types of problems can easily take many hours on powerful pcs. The matrix is often quite big... think milions x millions in size. How does it scale, would we need many thousands qbits? I would like to se a video on this algoritme, preferably with som examples.
Do you know if there are algorithms that could help particle physics find new particles?
Do I have to learn quantum physics in order to learn or better understand cirq and qiskit? And are there any rumors that big tech companies are releasing quantum computers as products in the near future(as laptops for example)
Can you please do a video on Alphatensor and the next steps, this will be valuable
Amazing video ❤️👍🙏
Please make more vedios about cyber security algorithms applied by Quantum programming
First quality content. Thanks.
Can we rewrite operating systems for quantum computers???
@pnesty6044
3 жыл бұрын
@@Anastasia-Marchenkova how can i learn to help ? and it's the stack is open source?
@pnesty6044
3 жыл бұрын
@@Anastasia-Marchenkova sorry for my bad english
@obinator9065
3 жыл бұрын
Well, so how is true parallelism going to play into the whole equation? Windows and your typical Linux Distro aren’t suited for such a thing, so real time OS?
I think a 6th very important algorithm could be the quantum linear system solver algorithm. My research area needs a lot of linear system solving, and the quantum algorithm that does it could give a huge speedup on the huge matrices I work with.
@lordecircojeca2039
3 жыл бұрын
@@Anastasia-Marchenkova Electrical power systems. Basically, trying to "solve" an electrical transmission or distribution network (finding all the voltages, currents and power flows on each node and branch of the electrical network) requires solving a huge non-linear system. We then use numeric iterative methods (such as Newton's method) in order to solve it, but they require solving a linear system on each iteration.
Talking of crysis, We shouldn't be too hard on quantum computers so early on.
So, basically quantum computers are good solving matrix related problems. K-Means checks for the lowest Euclidean distance, I'd bet that it's done with matrix. Correct me if I'm wrong. Here's a wild thought. To my understanding, GPUs are good for solving matrixes, which is why they are used for graphics and mining. Could potentially Quantum computer help on those two applications?
Hey can u make an video of quantum applications in healthcare
GREAT VID! Will we have room temperature photonic quantum devices peripherally computing over PCIe on x86/64bit systems like GPUs? could such a device emulate a GPU processor with the efficiency needed for GPU substitution?
@kevinbuenoartbywave
3 жыл бұрын
IF so it would be interesting to benchmark OpenCL on it for sure
May I suggest that you add some pictures, tables and formulas? It would help to understand
@henriqueperdoncini
3 жыл бұрын
For sure I wouldn't understand half if I didn't already saw parts on other channels (3blue1brown I guess)
So basically our classical computers aren't getting any faster, because we've almost reached the size limit of transistors. However some NP problems can be solved on quantum computers using the few quantum algorithms we have. Is that correct or am I getting it wrong somewhere?
Hi. I am really new in this subject so forgive me if this question sounds stupid. The decoherence phenomenon in this video really caught my attention. I made a quick google search on how this relates to computer memory, and found that a number of research papers from the 90's were proposed to reduce the decoherence in quantum computer memory. My question is this: does decoherence make it inherently difficult for quantim computers "to store" memory state? What if you wish to investigate how a quantum computation produced certain results, would you be able to check its memory, or would you find nothing there since the memory woud have decohered already?
@blockhook
3 жыл бұрын
@@Anastasia-Marchenkova got it, thanks! Seems like there's a lot of whole new concepts and design that I have to understand along the way. Very interesting, nonetheless.
Can you tell me which REAL-LIFE applications of quantum computers have been used so far? I read the IBM website last week and realized most of the applications of quantum are ambiguous
Thank you ma'am
Do architecture in quantum computing behave like parallel programming using GPU (SIMD= Single Instruction Multiple Data) ?
@opentechforum1140
11 ай бұрын
Like to call it SISRMD I.e. Single Instruction Single Result Multi Data!!!
Never disappointed overall, but I was disappointed to see Grover's algorithm included in the list of practical algorithms. I love the algorithm because it is short, and even I can understand it, not to mention the insight it provides, but it is not practical. The first half of what you say below was already sort of apparent to me, but the second half is new to me (thank you): "But here's a key point, when you talk about Grover's algorithm ... The Grover's algorithm doesn't actually search faster, but it actually inverts a function. Grover's algorithm applies when you have a function that returns true for one of its possible inputs and false for all the others. The job of this algorithm is 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 that causes the function to return true ... Does your application have a way to map it onto the quantum system [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? ... Examples of these problems where Grovers can actually be useful ... are travelling salesman or graph colouring problems ... research going into ... solving NP complete problems ...". Sorry for the length of this next bit (something I wrote). I would link to just these words instead of pasting them if I knew how; kzread.info/dash/bejne/apWiuLCcYNXFaNI.html … the database analogy can be misconstrued. It is a search algorithm, but not a database search algorithm; think string pattern matching rather than database search. The algorithm is a method to amplify an answer. In the database analogy, the answer is provided by a spiteful oracle. If you research Grover's Algorithm, you will find the context for the oracle reference; the adjective "spiteful" is mine. 101 is the ID of Charlie, it is not Charlie's telephone number; we are not told the telephone number, despite Andrea inadvertently saying, "we want to find which name that goes with the code 101". No, we want to find the code that goes with the unstated telephone number. We ask an oracle, "Who has the telephone number 87546328?". In the illustration, there are only eight people in the telephone book, and their names are encoded with three classical bits. Being an oracle, it/he/she knows the answer straight away and does not need to do a database search. If the oracle were not spiteful, the oracle would send you three classical bits (say "101") to be read by your classical computer. But being spiteful, it sends you three quantum bits in a superposed state, where each of the eight possible states is given a small probability, except one state (the answer within the answer) is given a slightly different probability, and you have to extract the classical encoding from the quantum encoding. We cannot read that quantum superposition! If we tried, we would get any one of the possible eight states with an almost equal probability. Grover's algorithm amplifies the probability of, in this case, the 101 state (with each iteration) and reduces the probabilities of the other seven states, until we can read out the answer with confidence. So the number of Grover/Quantum Search iterations for this very small search is 2 or 3 compared to an average number of 4 iterations in a linear search. But this is comparing apples with oranges in the context of a database search. The comparison is however valid when comparing the number of iterations to resolve a quantum superposition of qubits to find a needle in a haystack by Grover's algorithm versus a linear search (if it were possible, which it is not) to inspect the respective probabilities of eight possible outcomes to find the sole outcome with a probability that is different from all the rest. ... Incidentally, in answering another question I remembered the state that is different from the other states does not have a slightly different probability from the other possible outcomes, but its probability amplitude has a different phase from the probability amplitudes of the other possible outcomes.
@xbrlinfinity9399
3 жыл бұрын
Ah, thank you. I now see the greater significance of what you say, and Grover's algorithm could indeed be practical for certain problems, albeit not for database search. You said "So what it really does is it searches the input of the function until it finds the single input that that causes the function to return true". This is equivalent to my "it [receives] … quantum bits in a superposed state, where each of the … possible states is given a small probability, except one state (the answer within the answer) is given a … different [phase], and you have to extract the classical encoding from the quantum encoding." The encoding is what you say, "map a word onto a qubit state". What you say next is beyond my pay grade "Does your application have a way to map it onto the quantum system", but your next question is easy "can you actually find a function that returns true for that specific input?" That function is a readout of the register of qubits after applying Grover's algorithm.
Time to get post quantum encryption going; RSA Encryption less safe lol
Looking forward to seeing ECC getting trampled on.
But can it run Crysis?? 🤣 This is one of your best videos. Never paid much attention to Shor's algorithm before, but after your simple example I just ran the algorithm on another example on my mind and it worked fine (I found the prime factors), it seems easy to implement (although I don't have idea which step the quantum computers will have an advantage)
Are decoherence times and amount of error checking things that can be improved with better designs or is it something fundamental to quantum processors? Also that necklace looks really good on you, I’m blond too it’s got me thinking.
@Reliquancy
3 жыл бұрын
@@Anastasia-Marchenkova So, like for example could a quantum gate ever be as reliable at holding state as say a storage transistor or is entropy putting some kind of hard limits in it?
is QC a threat to btc and other blockchain technologies?
@paddym6075
3 жыл бұрын
@@Anastasia-Marchenkova cool, i will check it. thanks 🙏🏼
This is the video that started to change the world.
heinsernberg uncertainty principle deta*deltap
Can you please make more hard video's because this is extremely easy.
You are the best
Gorgeous!
The scariest part of Shor's algorithm is that theoretically malicious people could be storing data today and break it when Quantum computers exist, and there is not much to be done about it!
@obinator9065
3 жыл бұрын
@@Anastasia-Marchenkova r/datahoarder They hoard everything Probably a lot of stuff on internet archive too
Never expected I would learn tech from a blonde! Keep it up
Butterfly Effects and Quantum Choas algorithm ? Or even an algorithm to create artificial general intelligence ?
If a quantum computer were to run Crysis, how many qubits would it need?
Now if you learn one thing from me today, it's this: Don't listen to the Anglos. Ising is 'easing', not 'icing'.
I think was she is trying to say here is the following: IonQ🚀 🚀 🚀
I want a quantum programming video
@rishijha2794
3 жыл бұрын
@@Anastasia-Marchenkova start from beginners to advance
Welcome back ! By the way you look gorgeous always
love you ma'am
Great video. Many thanks. Could you please speak a little bit slower. I need time to process what you are saying 😂
I would like to build a quantum super smartphone out of boredom :D
❤
Oh man so it cant run crisis Damn
anyone else feel like a chicken watching tv but find her cute?
@mandakhbayar.m8298
3 жыл бұрын
Exactly
Какая бодрая !
But you need to uncompute afterwards...
Out of topic: has anyone ever told you that you resemble a lot Madelaine Petsch (from Riverdale)? If not, I'm saying. 🥰
@SuperTom15100
3 жыл бұрын
I sure didn't expect to see a comment referencing Riverdale while learning about quantum algorithms :D
Like 334°
Its really hard to actually focus when the teacher is attractive😨
Your audio and video are out of sync
how's your vaccine?
@Mrlimsuliong
3 жыл бұрын
@@Anastasia-Marchenkova glad to hear that)
is there are an algorithm find out , why women's shirts are translucent?
Are you a man?
Hotter than any girl with onlyfans