Super clear explanation! This is really going to help me in my Extended Essay (I am doing the IB diploma). I really don't understand how you aren't more recognized.
I've watched a few videos on this algorithm, but nobody has yet explained how you initially flip the amplitude of the item you're looking for. I mean, you have to know what item it is to flip it. But if you already know what item it is, the search is over before it's already begun.
Great question Paul! I was thinking about that too for a while. You are correct in saying that we must already know what the value we are looking for is in order to encode it into the quantum circuit. However, the important thing to keep in mind is that we are searching an Oracle function instead of an actual database. We could also search a quantum database, but the encoding of a quantum database is much more complicated so it is much simpler to demonstrate Grover's algorithm using an Oracle function. Of course another problem is that almost all databases used today aren't stored on quantum computers, so in terms of practicality there is a cost of translating a classical database into a quantum one. In some cases the cost of doing this may be so high that Grover's algorithm becomes inefficient. One example would be when data is stored in several different places (such as webpages) and must be collected before being translated into a quantum database. However as quantum technology progresses, the more useful Grover's algorithm will become. Thanks again for the question and let me know if you have any more. I'm also still learning about how exactly these things work.
If you Google "quantum optical implementation of Grover's algorithm" then you'll see some articles and videos that somewhat answer my question. Like you, I'm still learning about how these things work.
You already know what the item is, but you don't know where it is if you think of an unsorted database. So what you are doing is basically searching once and making the likely hood that you get the item you want on that try 100%.
Farzher, the point of Grovers alg is to make the likely hood of collapsing the state into a basis you desire. You know what you are looking for, but not where it is, so you increase the amplitude of the basis you want so it will collapse into that
It took me a while, but I think I finally know how to convince you there are parallel universes. Keep an eye on my new tutorial series if you are curious. I am creating it pretty much just to address this problem.
Does it actually _have_ to be explained in terms of parallel universes? Even if that's truly what's going on, I feel like this could be explained in much simpler terms. You can simulate this problem on a computer simply with some linear algebra, so I feel like what's going on isn't inherently related to whether or not it's in parallel universes or not, that's just an extra tidbit that only serves to confuse people.
it's not parallel universes. Each set of qbit exists in a state with a random chance to collapse into one of many unique states. This random probability can be altered by performing certain operations that essentially "weigh the dice" towards a certain result
@@maxwellsimon4538Personally I think an epistemic approach makes more sense. The qubit never exists in an indeterminate state, it always has a definite single value. What is random is not the qubit's state but permutations to the state as it undergoes certain interactions. This can be shown with the Stern-Gerlach apparatus. Electrons that have a known spin will randomize their spin it you measure them in a different measurement basis, with a greater degree of difference between the electron's phase and measurement basis increases the likelihood of a random permutation up to 90 degrees where it is 100%. The reason this is simpler is because it means when you predict a qubit has a 50% chance of being 0 or 1, that does not mean it is 0 or 1 at the same time but it is a statement of knowledge, a prediction, about an outcome. You never have to posit any qubits take all possible paths or try every possible combination. It takes on a random value whenever it interacts with other qubits but never exists in a valueless indeterminate state and only ever has one value at a time, which is confirmed by experiment because no one has ever observed a qubit in a state other than 0 and 1.
I see how this works and you did a good job explainging. But just to be clear it seems we always have to first build the oracle first? i.e. there is an infinite number of oracles for infinite set of integers for example if you were searching for integers; and the actual step 0 is to come up with the oracle function pertinent to the what you're searching for. Did I understand correctly?
To the people who suggested that Travis stop saying "in a parallel universe". In between "shut up and calculate" and "many worlds", there is an alternative view: ruclips.net/video/igDnqZG0-vs/видео.html
Why don't we just stop with the mysticism entirely and just admit we don't know what state the qubit is in? No one has ever observed a qubit in more than one state nor is it necessary to believe to explain any quantum phenomena.
In the simplest terms - Grovers algorithm can solve big problems by doing multiple computations simultaneously instead of sequentially? To me it seems that Grovers Algorithm only saves you one step here on this small data set. On a classical computer, if I am trying to find an Ace among 4 flipped over playing cards, I can flip one at a time until I've flipped three and if I haven't found it yet, I know it's the fourth card. Using Grovers and two qbits, I can flip two cards at once. So if I do that twice I have found the card definitively. Not very impressive with such a small N, but I guess I can see how this becomes way more powerful when N is large. Flipping 2 (or as many qbits as I have) each step can solve a bigger problem a lot "faster." What I don't understand is why this is better than having two classical computers run on the same data simultaneously. Gimme two CPUs, one flips the even cards and the other flips the odd cards. Same number of steps as using two qbits.
Using multiple clusters (or computers) to solve a problem in a distributed way is good only to the point where we are okay with getting results, not in real-time. A distributed computation, as you suggested suffers from the time-synchronization problem and latency. Therefore search algorithm that needs to operate in real-time will not be the same with the distributed computer as with quantum computers. There might be some other reasons but this is what I can think of.
The square root of 2^256 is 2^128. That's an improvement of 2^128. The best GPUs can do 10TFlops, so they check 2^43 per second. So a quantum computer can be ~ 2^80 times faster. Matters if e.g. you want to hack a 256bit hash.
Hi Physics Guy! So I used a wide variety of sources, but the IBM Q Experience was definitely one of them and you are right in that I should mention my sources. I have included as many I could remember, and I'll make sure to do so from now on. The source that had the biggest influence on me was undoubtedly David Deustch. The guy literally invented Quantum Computing, so if you want a real expert make sure to check him out. I do have some Computer Science education, but really I'm just a guy on RUclips trying to make Quantum Computing make sense to the non-expert, like myself.
Through my search of literature I've only been able to find grover's algorithm with 4 qubits. Is there some sort of physical limitation to how much it can be scaled?
Hi Qulaey, thanks for your question! No, there is no limit for the number of qubits that Grover’s Algorithm can use. The runtime for Grover’s Algorithm is O(sqrt(n)) where n is any positive natural number to infinity. The reason you are often seeing a 2 qubit oracle (with 4 possible states) is likely because 2 qubits makes for the easiest example to demonstrate the algorithm. Here’s an example of a 5 qubit Grover’s Algorithm for your convenience: www.travisgritter.me/quantum/?example=Grover%27s%20Algorithm That being said, the more qubits that are used in a real quantum computer the more unstable the quantum system becomes. So while there are no theoretical limits on the number of qubits that can be used in Grover’s algorithm, there are certainly practical limits as research into quantum computers continues. Hope that answers your question!
Theoretically - no limitation (If you have access to the required qubits) Practically - yes (Because all the cloud services that provide Quantum Computers only let you do maximum 1024 shots per call, You can do multiple calls obviously but it would require a lot of time and money)
Hey I want to ask something. You said the time that took computation is N**0.5 but in normal cases N well. Here "N" is confusing me. Now let us suppose we have 64 state so 64 bit. And one of them in those 64 bit is 1 and others are 0. If we use a normal computer we will find the answer on average N/2 step. Now in quantum computer we can use just 6 bits to represent those 64 step. In this case average time to find the solution is 64**0.5 or 6**0.5 ? I am asking this cause as you said İf N = 4 we would have 2 attempts to solve it right I mean it couldnt give us the right solution in the first attempt but it does. Is it gives us the right solution in one step just because that we applied the oracle function twice ? If we had 64 state we should apply oracle function 8 times to get the result in one step ? Its kind of confusing for me. Can you little bit more explain this Time complexity thing. Thanks :)
Hi Arman. Sorry for the delay in replying. Yes you have it correct. The time complexity is indeed determined by the number of times you invoke the Oracle function, and not the number of times you run the whole circuit. So when N = 4, it will indeed take 2 attempts to solve it as you say because we are invoking the Oracle function twice. You will in fact only need to run the whole circuit once no matter what N is equal too, so I agree it may have be misleading for me to have mentioned running it once. But thanks for pointing that out, and I'm glad you were able to understand it regardless!
Hey Travis I just watched your video on quantum gates loved it !!!!!! I guess I just don’t understand com”ex number s right now I need a math tutor big time!
Thanks Jon! Complex numbers are easier than you think. They just have a real number component and an imaginary number component. So an example of one would be like this: 1 + i. If you understand imaginary numbers (which are just the square root of negative 1) than you can understand complex numbers.
0:14 and 9:19 how do you know that it uses parallel universes since we aren't sure they exist? Is superposition a way to prove the many-worlds theory just because we have no other way to explain it?
Hi Kassiel! That is a very excellent question! It took me a while to wrap my head around that myself. But I am now currently creating a new series to answer just that question. My next video will be out in a few days and I recommend you watch it for some more details. But you answer you're question briefly here, parallel universes are the best way to solve the problems with the Copenhagen interpretation of Quantum Physics, particularly concerning wave-function collapse. Secondly, while we cannot directly observe parallel universes there are experiments that have been done that do show evidence of parallel universes by observing the effect they have on our universe. It takes a while to wrap your mind around, but I will be covering all of this in a lot more detail in my upcoming videos. Make sure to stay tuned as it really begins to blow your mind when you understand it.
I want to take a moment to thank you for answering the comments which I should've done in my first comment. Are you going to do it in a fashion that PBS space time or Vsauce uses, which makes it a lot easier for laymen to understand? I don't ask as a way of wrapping my mind around it, but instead as a matter of being sure that parallel universes is what quantum computers use for calculation as opposed to some other explanation. Once again, thank you so much for taking the time.
No worries! This has pretty much become my favorite topic and answering questions helps me understand it better too! So I'm going to do it by looking at some important experiments, and the major interpretations of it. For example, in my next video I'm going to perform the Double Slit Experiment and then look at how the Copenhagen Interpretation would explain it, and then how the Many-Worlds Interpretation would explain it and why its much better. And then look at some other experiments too. So I suppose more like PBS style! And yes, you need to assume there are parallel universes for Quantum Computing to work. Just assume that it is true for now, and I'll work on making it clear why it very likely is.
Haha you're the man. Alright deal. Are Copenhagen and Many-Worlds the only two interpretations? And if they are it might be because we don't understand it enough to have more interpretations.
No there are actually quite a few interpretations of Quantum Physics. I'll include a link to a list of them below. But the Copenhagen and Many Worlds are definitely the most popular interpretations at the moment. Most of the others are responses to them. But I definitely encourage you to check them all out if you are interested. en.wikipedia.org/wiki/Interpretations_of_quantum_mechanics
Hi Jon great question! So it depends what you mean. So on this simulator you are able to change the initial value of the Qubits by clicking on them. However, the initial value of the Qubits doesn’t really matter since it’s the configuration of the Oracle that is responsible for encoding the value you are looking for. So in order to build your own Oracle you would need to find a gate configuration that outputted 1 for only the value you were looking for. For example, let’s say you had two qubits with four possible inputs (00, 01, 10, 11), and you wanted to search for the value 11. If this were a classical computer you could simply use an AND gate for the Oracle function because it would output 1 only for the value 11 and 0 for all other values (en.wikipedia.org/wiki/AND_gate). Now this quantum simulator doesn’t give you an AND gate, but you can use other gates like the Controlled Not gate to encode an Oracle function to search for a particular item in any other series of inputs. Hopefully that answers your question!
The Quantum Simulator I am using in the video is a Javascript based one I am using from a programmer named Dave Wybiral. You can find the link here: qcsimulator.github.io
Instead of explaining portions and portions of the computation, can you walk through it gate by gate without the concept of oracle, etc? Because I understood all the oracles, but the gate that you used to represent the oracle just simply doesn't make sense.
Hi Huadong, that is an excellent question! So the thing to keep in mind is that there is no single Oracle function that I can provide a gate by gate description for. Instead what Grover's algorithm asks is given ANY oracle function where the output f(x) = 1 when x is equal to the input you are looking for and outputs f(x) = 0 when x is not equal to the input you are looking for, how can we find the value of x where f(x) = 1. So really what the Oracle function does is encode the value of x you are looking for into a series of gates, and then performs a search by inputting qubits through those gates. If you watch the end of my video I give examples of four different gate by gate encoding of Oracle functions that will output f(x) = 1 when x is equal to 00, 01, 10 and 11 respectively. If you want further examples, here is a link to two slightly more complicated encoding of Oracle functions (highlighted in the red box): physics.stackexchange.com/questions/251343/quantum-grovers-algorithm-constructing-the-black-box-gate Now with this in mind you may ask if the input of x we are looking for is already encoded in the gates, than why do we bother running Grover's algorithm at all? Why can't we just examine the configuration of the gates to determine the value of x we are looking for? Now in simpler Oracle functions like the 2 qubit one I examine in my video, this is quite easy to do. However, once you get to more complicated Oracle functions like the ones in the link above, it becomes much more complicated to do so by simply examining the gates and thus running Grover's algorithm would be the best way to find the value of x we are searching for. So to summarize, there is not one single Oracle function used in every instance of the Grover's algorithm, but instead there any INFINITELY many possible Oracle functions of which I have provide 6 examples with gate by gate descriptions for you to look at. What Grover's algorithm does is when given ANY Oracle function that outputs f(x) = 1 when x is equal to the value we are looking, and f(x) = 0 when x is NOT equal to the value we are looking for, it can find the value of x where f(x) = 1 in sqrt(X) time. Let me know if you have any further questions as the concept of the Oracle functions is fundamental to this algorithm, and can be a bit difficult to figure out.
Now I finished reading and understanding the content, thank you so much for explaining, I am still confused, but I do feel I understood more from your explanation, quantum physics really takes time to understand....
No worries! Feel free to let me know what you are still confused about. Honestly I love answering questions, I learned quite a bit more about Oracle functions just by answering your question. We really are in this together in trying to wrap our minds about Quantum Physics.
Although I don't understand it too well, I like the effort. The repeated claim that quantum computers are faster is a bit annoying. For the time being they can only solve problems THEORETICALLY in a very restricted area. IN PRACTICE the situation is even worse. Nevertheless, thanks.
I paused the video to make this comment... Granted that I don't know yet how Grover's algorithm works and how it can perform the search much faster, but I can guarantee that it is very misleading to say that a classical computer would take a million tries to find an item in a list of one million items if it were in the last position. Typically, the list would be indexed, which means that the items are sorted and appear in either ascending or descending order, using any measure that is relevant. For numbers, it would be typically be the value of the number itself, for text it would be its alphabetical order, so that the strings of text appear in the same order that they would appear in a dictionary. A binary search can be performed on such list, which guarantees that the item will be found in less than 20 tries, not a million. What binary search does is it looks at the item in the very middle of the list and compares it to the searched item. If the item in question is not what we are looking for, then we compare its value to our searched value. If the value we are searching for is greater, then we through away the first half of the list, and continue searching only in the second half. That is because it is presumed that the list is sorted of course, and there would be no way that the item we are looking for is in the first half. If the item is not found after 20 tries, it doesn't exist in the list. I think its important to rectify that, because for someone like me, it is a reason to not watch the rest of the video...
Hi Rick! Yes, you are correct in pointing out that if a list is sorted than we can use much faster search algorithms like binary search, and wouldn't need a quantum algorithm at all. However, Grover's algorithm is all about searching through data that is unsorted (i.e is not indexed). In these cases, algorithms like binary search do not work and the fastest search algorithm we know on a classical computer is indeed O(n) in the worst case. When you say "typically, the list would be indexed," this usually means the data has gone through a sorting algorithm, which has a minimum run time of O(n log n). This itself is much slower than using Grover's Algorithm, which has a run-time of O(sqrt n). Thus, if you ever need to search through data that is not sorted (which definitely happens quite a bit), than Grover's Algorithm will indeed have a lower worst case run-time than any classical algorithm.
Here's a good example to illustrate what I'm talking about. Imagine you had a old paper phone book, like the Yellow Pages, and wanted to look up the phone number of one of your friends. If you knew that person's name it would be pretty easy to find that person's phone number since the names are all sorted in alphabetically order, and you wouldn't need Grover's algorithm at all. However, let's say all you had was a phone number, and you wanted to find the name of the person that number belonged to, the only way you could do so would be to look at every phone number one by one until you found the matching number, since phone books are not sorted in numerical order of phone numbers. Thus, if there were a million phone numbers in the phone book, in the worst case, you would have to look through all one million entries until you found the matching phone number. However, if you use Grover's algorithm you would only have to look through 1000 entries because you would be searching in several parallel universes at the same-time. (If you are confused by that last sentence, stayed tuned to my new video tutorial series where I will talk a lot more about parallel universes and the many-worlds interpretation).
You are talking about a sorted/indexed list, which is NOT a worst case scenario. To determine the time complexity of an action, the worst case scenario is assumed, which in the case of search is a unstructured list with the element we are searching for at the end. So the explanation he gave is correct.
Yes, in the time spent thinking about this topic since making this video, I’ve become more convinced that the Many Worlds Interpretation is the best interpretation of quantum mechanics. Consider the following points: 1. What arguments are there for there being only one universe? The best one that I can think of is that it appears as if there is only one when you think back to a particular event, say for example who won the Euro Cup this year. You and everyone else you know can only remember one event happening, in this case Italy winning the Euro Cup. But what if there were parallel universes? In that case someone living in that other universe would also think only one outcome occurred, say instead England winning the Euro Cup. So for each person in a parallel universe it would appear as if there was one universe, since they couldn’t directly observe the other ones. So thinking there is only one universe could simply be an illusion of perspective, similar to why people once thought the sun revolved around the earth. So the fact that it appears there is one universe doesn’t necessarily mean there is just one; it could very easily just be an illusion of perspective. 2. If you believe there is only one universe you must answer this question: why can we not know with certainty what is going to happen in the future, even when we have maximum knowledge about a quantum system? If there is just one universe then for any given event there must only be one outcome right? So then with all our advances in technology why have we not been able to figure out what the single outcome will be? Even with simple quantum systems? For example, if I ask you who is going to win the Olympics this year, the most accurate way you could describe it would be by expressing the possible outcomes as probabilities. For instance, you may say the US has a 33% chance, China a 29% chance, Japan 26%, and so on. But if there is one universe, then would it be possible to know which outcome will happen with certainty if we had all the information about the system? You may say, there are too many variables to calculate who will win the Olympics with certainty, and you are right! So let's instead consider a very simple 3 qubit circuit in a quantum simulator pictured in this link below: www.dropbox.com/s/7ig9k0ap3fii7v3/QuantumCircuit.png?dl=0 So now that we have a very simple quantum system and do not have to worry about any problems with measurement since it's on a simulator, are we now able to know which outcomes will happen with certainty? No, the outcome is still expressed as a probability, |100> has a 25% chance, |101> a 25% chance, |110> a 25% chance and so on. If there is one universe, should not one outcome always be 100%? To quote Einstein on this problem: “God does not play dice!” This is the problem that The Many Worlds Interpretation so elegantly solves. It says that the full description of a quantum system is the sum total of all the probabilities of the wave function. So there is no need to explain why one outcome occurs instead of another, because all possible outcomes actually occur. So when you make an observation you really are only observing one small part of the whole system. Also, do not forget that you yourself are also a quantum system since you yourself are also built from atoms and electrons. As such, the best way to describe your interaction with a real quantum circuit would be to add the sum of total number of ‘versions’ of you who observe |000>, plus the number of ‘versions’ of who observe |001> plus the number who observe |010>, and so on, until you reach 100% (i.e fully describe a quantum interaction; no more dice!). And since the athletes and venues of the Olympics are also built from atoms and electrons, the best description of the system would be to say in 33% of the universes the United States will be the winner, in 29% of the universes Japan will win, in 26% China will win, and so on. Since there will be more universes where the US is the winner, it is more likely that you will end up as a version of you who observes the US winning, and less likely you will end up as a version of you that observes the Philippines winning the Olympics. As you can see by describing a quantum system as the sum total of all possibilities you can avoid the problem of explaining why in some quantum systems we cannot know which outcome will occur with certainty, since all outcomes actually occur. So even if you disagree with everything I wrote above, you must still answer this question. If there is only one universe, then why cannot we not know what that single outcome of a future event will be, even in a very simple quantum system with perfect measurements? 3. Observe how easily your mind can imagine parallel universes. You can very easily imagine England or Italy winning the Euro Cup. You can easily imagine the US, China, Japan or any other country winning the olympics. You can imagine what your life would have been like if you had chosen a different career, or hadn’t broken up with a particular partner. When you decide to buy insurance for example you are imagining the universes where you might be glad you made the purchase, or the probability of universes where you didn’t need it at all. Think about the different universes humans have created in books and movies, or the different future projections people have for the future of humanity. Not all you can imagine will actually occur of course, but the fact our minds can so easily think about parallel universes I believe gives us a hint to the structure of reality our brains evolved in. Your brain it would seem is highly evolved to calculate the multiverse. Parallel universes seem a strange idea at first, but not as much when you consider the fact you are thinking about parallel universes all the time. These are just general philosophical arguments though and a high level overview about how I think about the Everett Interpretation. Ultimately looking at quantum experiments (i.e double slit, beam splitter) is probably the best place to start for thinking about this. But it was nice to be able to get these thoughts out, so thanks for being the outlet to my long winded response! Let me know if you have any more questions or comments.
@@travisgritter34971. Shifting the burden of proof. You have to prove parallel universes, we don't have to disprove it. 2. The fact we cannot predict the outcome of an experiment with certainty does not prove there are parallel universes. 3. Your argument is literally that because you can imagine something it must be real...just lol
Super clear explanation! This is really going to help me in my Extended Essay (I am doing the IB diploma). I really don't understand how you aren't more recognized.
I tried doing my IB paper on quantum computing but the teachers heavily discouraged me from it to the point I ended up dropping the class.
Yo holy crap I’m doing my IB essay on it too and I was legit on the verge of giving up till I found this guy
I've watched a few videos on this algorithm, but nobody has yet explained how you initially flip the amplitude of the item you're looking for. I mean, you have to know what item it is to flip it. But if you already know what item it is, the search is over before it's already begun.
Great question Paul! I was thinking about that too for a while. You are correct in saying that we must already know what the value we are looking for is in order to encode it into the quantum circuit. However, the important thing to keep in mind is that we are searching an Oracle function instead of an actual database. We could also search a quantum database, but the encoding of a quantum database is much more complicated so it is much simpler to demonstrate Grover's algorithm using an Oracle function.
Of course another problem is that almost all databases used today aren't stored on quantum computers, so in terms of practicality there is a cost of translating a classical database into a quantum one. In some cases the cost of doing this may be so high that Grover's algorithm becomes inefficient. One example would be when data is stored in several different places (such as webpages) and must be collected before being translated into a quantum database. However as quantum technology progresses, the more useful Grover's algorithm will become.
Thanks again for the question and let me know if you have any more. I'm also still learning about how exactly these things work.
If you Google "quantum optical implementation of Grover's algorithm" then you'll see some articles and videos that somewhat answer my question. Like you, I'm still learning about how these things work.
You already know what the item is, but you don't know where it is if you think of an unsorted database. So what you are doing is basically searching once and making the likely hood that you get the item you want on that try 100%.
yuppppp, same question. your input is 01, and the quantum output is 01... great job QM, you found it...
Farzher, the point of Grovers alg is to make the likely hood of collapsing the state into a basis you desire. You know what you are looking for, but not where it is, so you increase the amplitude of the basis you want so it will collapse into that
Thank you my recommendation video, you are good man.
Your explanation is top of notch when your background just your room.
Keep up the good work man
But you need to know what it’s going to output in order to program the oracle function, so what’s the point
I had the same question.
YOU LOST ME AT PARALLEL UNIVERSES!
It took me a while, but I think I finally know how to convince you there are parallel universes. Keep an eye on my new tutorial series if you are curious. I am creating it pretty much just to address this problem.
Does it actually _have_ to be explained in terms of parallel universes? Even if that's truly what's going on, I feel like this could be explained in much simpler terms. You can simulate this problem on a computer simply with some linear algebra, so I feel like what's going on isn't inherently related to whether or not it's in parallel universes or not, that's just an extra tidbit that only serves to confuse people.
it's not parallel universes. Each set of qbit exists in a state with a random chance to collapse into one of many unique states. This random probability can be altered by performing certain operations that essentially "weigh the dice" towards a certain result
@@maxwellsimon4538Personally I think an epistemic approach makes more sense. The qubit never exists in an indeterminate state, it always has a definite single value. What is random is not the qubit's state but permutations to the state as it undergoes certain interactions. This can be shown with the Stern-Gerlach apparatus. Electrons that have a known spin will randomize their spin it you measure them in a different measurement basis, with a greater degree of difference between the electron's phase and measurement basis increases the likelihood of a random permutation up to 90 degrees where it is 100%. The reason this is simpler is because it means when you predict a qubit has a 50% chance of being 0 or 1, that does not mean it is 0 or 1 at the same time but it is a statement of knowledge, a prediction, about an outcome. You never have to posit any qubits take all possible paths or try every possible combination. It takes on a random value whenever it interacts with other qubits but never exists in a valueless indeterminate state and only ever has one value at a time, which is confirmed by experiment because no one has ever observed a qubit in a state other than 0 and 1.
Thank you, if I had found this video earlier I would have saved 3 hrs watching qiskit...
I see how this works and you did a good job explainging. But just to be clear it seems we always have to first build the oracle first? i.e. there is an infinite number of oracles for infinite set of integers for example if you were searching for integers; and the actual step 0 is to come up with the oracle function pertinent to the what you're searching for. Did I understand correctly?
To the people who suggested that Travis stop saying "in a parallel universe". In between "shut up and calculate" and "many worlds", there is an alternative view: ruclips.net/video/igDnqZG0-vs/видео.html
Why don't we just stop with the mysticism entirely and just admit we don't know what state the qubit is in? No one has ever observed a qubit in more than one state nor is it necessary to believe to explain any quantum phenomena.
In the simplest terms - Grovers algorithm can solve big problems by doing multiple computations simultaneously instead of sequentially?
To me it seems that Grovers Algorithm only saves you one step here on this small data set. On a classical computer, if I am trying to find an Ace among 4 flipped over playing cards, I can flip one at a time until I've flipped three and if I haven't found it yet, I know it's the fourth card. Using Grovers and two qbits, I can flip two cards at once. So if I do that twice I have found the card definitively. Not very impressive with such a small N, but I guess I can see how this becomes way more powerful when N is large. Flipping 2 (or as many qbits as I have) each step can solve a bigger problem a lot "faster."
What I don't understand is why this is better than having two classical computers run on the same data simultaneously. Gimme two CPUs, one flips the even cards and the other flips the odd cards. Same number of steps as using two qbits.
Using multiple clusters (or computers) to solve a problem in a distributed way is good only to the point where we are okay with getting results, not in real-time. A distributed computation, as you suggested suffers from the time-synchronization problem and latency. Therefore search algorithm that needs to operate in real-time will not be the same with the distributed computer as with quantum computers. There might be some other reasons but this is what I can think of.
The square root of 2^256 is 2^128. That's an improvement of 2^128.
The best GPUs can do 10TFlops, so they check 2^43 per second.
So a quantum computer can be ~ 2^80 times faster.
Matters if e.g. you want to hack a 256bit hash.
@@npip99and how do you plan on doing that with current accuracy ranges ?
you should probably mention that all of these figures and explanations are from the IBM Q experience website....
Hi Physics Guy! So I used a wide variety of sources, but the IBM Q Experience was definitely one of them and you are right in that I should mention my sources. I have included as many I could remember, and I'll make sure to do so from now on.
The source that had the biggest influence on me was undoubtedly David Deustch. The guy literally invented Quantum Computing, so if you want a real expert make sure to check him out. I do have some Computer Science education, but really I'm just a guy on RUclips trying to make Quantum Computing make sense to the non-expert, like myself.
the best tutorial ever!
loved the visualization!!!!
Good job you know what you are talking about. Very well and very good.
4:45 Does Oracle Function have to perform n times to get the math done?
I am so confused!!!
Your explanation was really clear, thank you.
Through my search of literature I've only been able to find grover's algorithm with 4 qubits. Is there some sort of physical limitation to how much it can be scaled?
Hi Qulaey, thanks for your question! No, there is no limit for the number of qubits that Grover’s Algorithm can use. The runtime for Grover’s Algorithm is O(sqrt(n)) where n is any positive natural number to infinity. The reason you are often seeing a 2 qubit oracle (with 4 possible states) is likely because 2 qubits makes for the easiest example to demonstrate the algorithm. Here’s an example of a 5 qubit Grover’s Algorithm for your convenience: www.travisgritter.me/quantum/?example=Grover%27s%20Algorithm
That being said, the more qubits that are used in a real quantum computer the more unstable the quantum system becomes. So while there are no theoretical limits on the number of qubits that can be used in Grover’s algorithm, there are certainly practical limits as research into quantum computers continues. Hope that answers your question!
@@travisgritter3497 Thanks Travis I really appreciate the reply, In your example whats actually inside the "f7" and "grov" gates?
Theoretically - no limitation (If you have access to the required qubits)
Practically - yes (Because all the cloud services that provide Quantum Computers only let you do maximum 1024 shots per call, You can do multiple calls obviously but it would require a lot of time and money)
Hey I want to ask something. You said the time that took computation is N**0.5 but in normal cases N well. Here "N" is confusing me. Now let us suppose we have 64 state so 64 bit. And one of them in those 64 bit is 1 and others are 0.
If we use a normal computer we will find the answer on average N/2 step. Now in quantum computer we can use just 6 bits to represent those 64 step. In this case average time to find the solution is 64**0.5 or 6**0.5 ? I am asking this cause as you said İf N = 4 we would have 2 attempts to solve it right I mean it couldnt give us the right solution in the first attempt but it does. Is it gives us the right solution in one step just because that we applied the oracle function twice ? If we had 64 state we should apply oracle function 8 times to get the result in one step ?
Its kind of confusing for me. Can you little bit more explain this Time complexity thing. Thanks :)
Hi Arman. Sorry for the delay in replying.
Yes you have it correct. The time complexity is indeed determined by the number of times you invoke the Oracle function, and not the number of times you run the whole circuit. So when N = 4, it will indeed take 2 attempts to solve it as you say because we are invoking the Oracle function twice. You will in fact only need to run the whole circuit once no matter what N is equal too, so I agree it may have be misleading for me to have mentioned running it once. But thanks for pointing that out, and I'm glad you were able to understand it regardless!
Hey Travis I just watched your video on quantum gates loved it !!!!!! I guess I just don’t understand com”ex number s right now I need a math tutor big time!
Thanks Jon! Complex numbers are easier than you think. They just have a real number component and an imaginary number component. So an example of one would be like this: 1 + i. If you understand imaginary numbers (which are just the square root of negative 1) than you can understand complex numbers.
Nice video ! maybe it would be better if you notate the letters: It takes me quite a while to get me head around the notation of step 2 & 3
Great video, thank you very much
0:14 and 9:19 how do you know that it uses parallel universes since we aren't sure they exist? Is superposition a way to prove the many-worlds theory just because we have no other way to explain it?
Hi Kassiel! That is a very excellent question! It took me a while to wrap my head around that myself. But I am now currently creating a new series to answer just that question. My next video will be out in a few days and I recommend you watch it for some more details.
But you answer you're question briefly here, parallel universes are the best way to solve the problems with the Copenhagen interpretation of Quantum Physics, particularly concerning wave-function collapse. Secondly, while we cannot directly observe parallel universes there are experiments that have been done that do show evidence of parallel universes by observing the effect they have on our universe.
It takes a while to wrap your mind around, but I will be covering all of this in a lot more detail in my upcoming videos. Make sure to stay tuned as it really begins to blow your mind when you understand it.
I want to take a moment to thank you for answering the comments which I should've done in my first comment. Are you going to do it in a fashion that PBS space time or Vsauce uses, which makes it a lot easier for laymen to understand? I don't ask as a way of wrapping my mind around it, but instead as a matter of being sure that parallel universes is what quantum computers use for calculation as opposed to some other explanation. Once again, thank you so much for taking the time.
No worries! This has pretty much become my favorite topic and answering questions helps me understand it better too!
So I'm going to do it by looking at some important experiments, and the major interpretations of it. For example, in my next video I'm going to perform the Double Slit Experiment and then look at how the Copenhagen Interpretation would explain it, and then how the Many-Worlds Interpretation would explain it and why its much better. And then look at some other experiments too. So I suppose more like PBS style!
And yes, you need to assume there are parallel universes for Quantum Computing to work. Just assume that it is true for now, and I'll work on making it clear why it very likely is.
Haha you're the man. Alright deal. Are Copenhagen and Many-Worlds the only two interpretations? And if they are it might be because we don't understand it enough to have more interpretations.
No there are actually quite a few interpretations of Quantum Physics. I'll include a link to a list of them below. But the Copenhagen and Many Worlds are definitely the most popular interpretations at the moment. Most of the others are responses to them. But I definitely encourage you to check them all out if you are interested.
en.wikipedia.org/wiki/Interpretations_of_quantum_mechanics
i find it hilarious some people in the comments think the oracle function just checks if the input it a certain pre-knon value
Just a small thing its not "Lou"(Grover) , it's prounced as "Love".
I suggest you don't speak about paralel universes and better explain the algorithm better. But thanks, was definitely helpful.
How would you enter in your own values in the simulator that you use? Thank you!
Hi Jon great question! So it depends what you mean. So on this simulator you are able to change the initial value of the Qubits by clicking on them. However, the initial value of the Qubits doesn’t really matter since it’s the configuration of the Oracle that is responsible for encoding the value you are looking for. So in order to build your own Oracle you would need to find a gate configuration that outputted 1 for only the value you were looking for.
For example, let’s say you had two qubits with four possible inputs (00, 01, 10, 11), and you wanted to search for the value 11. If this were a classical computer you could simply use an AND gate for the Oracle function because it would output 1 only for the value 11 and 0 for all other values (en.wikipedia.org/wiki/AND_gate). Now this quantum simulator doesn’t give you an AND gate, but you can use other gates like the Controlled Not gate to encode an Oracle function to search for a particular item in any other series of inputs. Hopefully that answers your question!
This actually does help! Thanks a million!
clear and interesting, cool man
Thank you!
Which program are u using?
The Quantum Simulator I am using in the video is a Javascript based one I am using from a programmer named Dave Wybiral. You can find the link here: qcsimulator.github.io
This man is too smart to blink
Instead of explaining portions and portions of the computation, can you walk through it gate by gate without the concept of oracle, etc? Because I understood all the oracles, but the gate that you used to represent the oracle just simply doesn't make sense.
Hi Huadong, that is an excellent question! So the thing to keep in mind is that there is no single Oracle function that I can provide a gate by gate description for. Instead what Grover's algorithm asks is given ANY oracle function where the output f(x) = 1 when x is equal to the input you are looking for and outputs f(x) = 0 when x is not equal to the input you are looking for, how can we find the value of x where f(x) = 1. So really what the Oracle function does is encode the value of x you are looking for into a series of gates, and then performs a search by inputting qubits through those gates. If you watch the end of my video I give examples of four different gate by gate encoding of Oracle functions that will output f(x) = 1 when x is equal to 00, 01, 10 and 11 respectively. If you want further examples, here is a link to two slightly more complicated encoding of Oracle functions (highlighted in the red box):
physics.stackexchange.com/questions/251343/quantum-grovers-algorithm-constructing-the-black-box-gate
Now with this in mind you may ask if the input of x we are looking for is already encoded in the gates, than why do we bother running Grover's algorithm at all? Why can't we just examine the configuration of the gates to determine the value of x we are looking for? Now in simpler Oracle functions like the 2 qubit one I examine in my video, this is quite easy to do. However, once you get to more complicated Oracle functions like the ones in the link above, it becomes much more complicated to do so by simply examining the gates and thus running Grover's algorithm would be the best way to find the value of x we are searching for.
So to summarize, there is not one single Oracle function used in every instance of the Grover's algorithm, but instead there any INFINITELY many possible Oracle functions of which I have provide 6 examples with gate by gate descriptions for you to look at. What Grover's algorithm does is when given ANY Oracle function that outputs f(x) = 1 when x is equal to the value we are looking, and f(x) = 0 when x is NOT equal to the value we are looking for, it can find the value of x where f(x) = 1 in sqrt(X) time. Let me know if you have any further questions as the concept of the Oracle functions is fundamental to this algorithm, and can be a bit difficult to figure out.
Holy sh*t, I haven't finished reading your comment yet, but I really do appreciate you taking the time to write this much.
Now I finished reading and understanding the content, thank you so much for explaining, I am still confused, but I do feel I understood more from your explanation, quantum physics really takes time to understand....
No worries! Feel free to let me know what you are still confused about. Honestly I love answering questions, I learned quite a bit more about Oracle functions just by answering your question. We really are in this together in trying to wrap our minds about Quantum Physics.
Although I don't understand it too well, I like the effort. The repeated claim that quantum computers are faster is a bit annoying. For the time being they can only solve problems THEORETICALLY in a very restricted area. IN PRACTICE the situation is even worse. Nevertheless, thanks.
Great video, but please don't raise a matrix to the power of "t"
Awesome!
I have yet to find a video that explains anything to do with quantum computers without showing me a quantum physics equation nobody understands.
Hi Roberto! I'm actively working on some more videos currently, so what kind of videos are you looking for exactly? Just ones without equations?
THANK YO!!!
bad audio
Right. I do wish I had more professional video equipment. I believe I may have a solution for future videos coming soon!
God I picked this project to do for my quantum class and its terrible!!
I paused the video to make this comment...
Granted that I don't know yet how Grover's algorithm works and how it can perform the search much faster, but I can guarantee that it is very misleading to say that a classical computer would take a million tries to find an item in a list of one million items if it were in the last position.
Typically, the list would be indexed, which means that the items are sorted and appear in either ascending or descending order, using any measure that is relevant. For numbers, it would be typically be the value of the number itself, for text it would be its alphabetical order, so that the strings of text appear in the same order that they would appear in a dictionary. A binary search can be performed on such list, which guarantees that the item will be found in less than 20 tries, not a million. What binary search does is it looks at the item in the very middle of the list and compares it to the searched item. If the item in question is not what we are looking for, then we compare its value to our searched value. If the value we are searching for is greater, then we through away the first half of the list, and continue searching only in the second half. That is because it is presumed that the list is sorted of course, and there would be no way that the item we are looking for is in the first half. If the item is not found after 20 tries, it doesn't exist in the list.
I think its important to rectify that, because for someone like me, it is a reason to not watch the rest of the video...
Hi Rick! Yes, you are correct in pointing out that if a list is sorted than we can use much faster search algorithms like binary search, and wouldn't need a quantum algorithm at all. However, Grover's algorithm is all about searching through data that is unsorted (i.e is not indexed). In these cases, algorithms like binary search do not work and the fastest search algorithm we know on a classical computer is indeed O(n) in the worst case.
When you say "typically, the list would be indexed," this usually means the data has gone through a sorting algorithm, which has a minimum run time of O(n log n). This itself is much slower than using Grover's Algorithm, which has a run-time of O(sqrt n). Thus, if you ever need to search through data that is not sorted (which definitely happens quite a bit), than Grover's Algorithm will indeed have a lower worst case run-time than any classical algorithm.
Here's a good example to illustrate what I'm talking about. Imagine you had a old paper phone book, like the Yellow Pages, and wanted to look up the phone number of one of your friends. If you knew that person's name it would be pretty easy to find that person's phone number since the names are all sorted in alphabetically order, and you wouldn't need Grover's algorithm at all.
However, let's say all you had was a phone number, and you wanted to find the name of the person that number belonged to, the only way you could do so would be to look at every phone number one by one until you found the matching number, since phone books are not sorted in numerical order of phone numbers. Thus, if there were a million phone numbers in the phone book, in the worst case, you would have to look through all one million entries until you found the matching phone number. However, if you use Grover's algorithm you would only have to look through 1000 entries because you would be searching in several parallel universes at the same-time.
(If you are confused by that last sentence, stayed tuned to my new video tutorial series where I will talk a lot more about parallel universes and the many-worlds interpretation).
You are talking about a sorted/indexed list, which is NOT a worst case scenario.
To determine the time complexity of an action, the worst case scenario is assumed, which in the case of search is a unstructured list with the element we are searching for at the end. So the explanation he gave is correct.
Lol parallel universes? Anyone scientific turn back now
Yes, in the time spent thinking about this topic since making this video, I’ve become more convinced that the Many Worlds Interpretation is the best interpretation of quantum mechanics. Consider the following points:
1. What arguments are there for there being only one universe? The best one that I can think of is that it appears as if there is only one when you think back to a particular event, say for example who won the Euro Cup this year. You and everyone else you know can only remember one event happening, in this case Italy winning the Euro Cup. But what if there were parallel universes? In that case someone living in that other universe would also think only one outcome occurred, say instead England winning the Euro Cup. So for each person in a parallel universe it would appear as if there was one universe, since they couldn’t directly observe the other ones. So thinking there is only one universe could simply be an illusion of perspective, similar to why people once thought the sun revolved around the earth. So the fact that it appears there is one universe doesn’t necessarily mean there is just one; it could very easily just be an illusion of perspective.
2. If you believe there is only one universe you must answer this question: why can we not know with certainty what is going to happen in the future, even when we have maximum knowledge about a quantum system? If there is just one universe then for any given event there must only be one outcome right? So then with all our advances in technology why have we not been able to figure out what the single outcome will be? Even with simple quantum systems? For example, if I ask you who is going to win the Olympics this year, the most accurate way you could describe it would be by expressing the possible outcomes as probabilities. For instance, you may say the US has a 33% chance, China a 29% chance, Japan 26%, and so on. But if there is one universe, then would it be possible to know which outcome will happen with certainty if we had all the information about the system? You may say, there are too many variables to calculate who will win the Olympics with certainty, and you are right! So let's instead consider a very simple 3 qubit circuit in a quantum simulator pictured in this link below:
www.dropbox.com/s/7ig9k0ap3fii7v3/QuantumCircuit.png?dl=0
So now that we have a very simple quantum system and do not have to worry about any problems with measurement since it's on a simulator, are we now able to know which outcomes will happen with certainty? No, the outcome is still expressed as a probability, |100> has a 25% chance, |101> a 25% chance, |110> a 25% chance and so on. If there is one universe, should not one outcome always be 100%? To quote Einstein on this problem: “God does not play dice!”
This is the problem that The Many Worlds Interpretation so elegantly solves. It says that the full description of a quantum system is the sum total of all the probabilities of the wave function. So there is no need to explain why one outcome occurs instead of another, because all possible outcomes actually occur. So when you make an observation you really are only observing one small part of the whole system. Also, do not forget that you yourself are also a quantum system since you yourself are also built from atoms and electrons. As such, the best way to describe your interaction with a real quantum circuit would be to add the sum of total number of ‘versions’ of you who observe |000>, plus the number of ‘versions’ of who observe |001> plus the number who observe |010>, and so on, until you reach 100% (i.e fully describe a quantum interaction; no more dice!). And since the athletes and venues of the Olympics are also built from atoms and electrons, the best description of the system would be to say in 33% of the universes the United States will be the winner, in 29% of the universes Japan will win, in 26% China will win, and so on. Since there will be more universes where the US is the winner, it is more likely that you will end up as a version of you who observes the US winning, and less likely you will end up as a version of you that observes the Philippines winning the Olympics. As you can see by describing a quantum system as the sum total of all possibilities you can avoid the problem of explaining why in some quantum systems we cannot know which outcome will occur with certainty, since all outcomes actually occur. So even if you disagree with everything I wrote above, you must still answer this question. If there is only one universe, then why cannot we not know what that single outcome of a future event will be, even in a very simple quantum system with perfect measurements?
3. Observe how easily your mind can imagine parallel universes. You can very easily imagine England or Italy winning the Euro Cup. You can easily imagine the US, China, Japan or any other country winning the olympics. You can imagine what your life would have been like if you had chosen a different career, or hadn’t broken up with a particular partner. When you decide to buy insurance for example you are imagining the universes where you might be glad you made the purchase, or the probability of universes where you didn’t need it at all. Think about the different universes humans have created in books and movies, or the different future projections people have for the future of humanity. Not all you can imagine will actually occur of course, but the fact our minds can so easily think about parallel universes I believe gives us a hint to the structure of reality our brains evolved in. Your brain it would seem is highly evolved to calculate the multiverse. Parallel universes seem a strange idea at first, but not as much when you consider the fact you are thinking about parallel universes all the time.
These are just general philosophical arguments though and a high level overview about how I think about the Everett Interpretation. Ultimately looking at quantum experiments (i.e double slit, beam splitter) is probably the best place to start for thinking about this. But it was nice to be able to get these thoughts out, so thanks for being the outlet to my long winded response! Let me know if you have any more questions or comments.
@@travisgritter34971. Shifting the burden of proof. You have to prove parallel universes, we don't have to disprove it.
2. The fact we cannot predict the outcome of an experiment with certainty does not prove there are parallel universes.
3. Your argument is literally that because you can imagine something it must be real...just lol
The fuck? Why do you not go and act in a horror movie drama?
Can you plz bring your eyebrows down..
Use a mike.