Hi Travis Enjoying your videos' Question: how does one READ THE INPUT DATA and APPLY it to the FUNCTION? If one uses a classical computer to supply the data sequentially off a hard drive or memory, surely the quantum processor will be in continuous 'wait states' which would make processing slow!
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
Great vid! Thanks! I have a little issue with how you’ve written your limits on the summation signs at minute 6.34. We aren’t really summing over y, we’re summing over all combinations of 2^n bit strings right? So y=0 would correspond to |00...0>. Would it be better to write at the bottom of the sum: y = {0,1}^n? Or maybe to sum over index i and put a subscript on the y: |y_i> therefore when i=0 |y_0> = |00...0>? I’m only learning this for the first time so maybe you are just following a convention I haven’t come across yet in which case I apologise!
Excellent question! So I assume you mean why 'n + 1' instead of 'n,' or in other words why is there an extra qubit? Well that extra qubit actually has a specific name. It is called the 'Ancilla bit' and is used to assist in the computation. The Ancilla bit can safety ignored in later steps of the equation when it has served its purpose and is not longer needed. Here's the Wikipedia article on it if you are interested. en.wikipedia.org/wiki/Ancilla_bit If you want to know exactly how it assists in this computation, let me know and I'll figure out the best way to explain it.
Hi Abhinavan! An oracle function is just an easy way of saying "assume we have a function that can solve a particular problem." For this algorithm it is useful because it would be tedious and unnecessary to have to show excatly what the equations behind the balancing function is, so makes the overall problem easier to understand. However, if you wanted to actually implement this function on a real computer, you would need the details of the algorithm instead of simply declaring it an Oracle function. Here is a link to the Wikipedia article if you would like some more information. en.wikipedia.org/wiki/Oracle_machine
You used different definition of balanced for the first half of your video and the second half. And FYI your second definition can be solved in (on average) constant time on a classical computer, which is with high probability faster than quantum computer.
I'm not sure what you mean by two definitions. If you are referring to the fact that in the first first part I say a constant function outputs all 0's and in the second part I show the balanced function outputting all 0's, keep in mind that the output of the function and the output of the simulator are not the same. The difference is that the function outputs the value of a SINGLE input and the quantum simulator outputs the value of ALL the inputs. As such, I don't see how a classical computer can solve this problem in constant time.
Travis Gritter Oh actually you only said it once that balanced is that there is an even number of 0 and 1 outputs (the word even is very misleading). For the latter question, a randomized algorithm can find one such input with half probability and therefore if one attempts C (constant) times, and the probability that he fails is 2^-C which can be arbitrarily small regardless of n. Of course you can argue about worst case but in reality it almost never happens.
Ah I see, yes this question is all about solving for the worst case scenario. In the best case a classical computer can solve it in two steps (i.e the function outputs a 0 and then 1, ensuring it is balanced), a quantum computer however can solve it in the worse case in just one step. And yes you are also right that this question has very little practical application. Keep in mind that this is the first quantum algorithm ever created, and was designed specifically to show how quantum computers can solve questions faster than classical ones. However, people have used this question to design other quantum algorithms that do have practical applications. For example, Grover's Search Algorithm, a very practical quantum algorithm, was directly inspired by this problem. The hope is that there's many other practical quantum algorithm's out there to be discovered as well.
I think it's worth adding that the runtime that was being compared is in the big O notation, that is we're simply considering the upperbound for both algorithms. Do note that although the average runtime is indeed considered as well in most algorithm analysis.
Quantum information is exciting but we haven't figured out how to communicate with parallel universes yet.
2^(n-1) + 1 should be 3 because n is 2.
Hi Travis
Enjoying your videos'
Question: how does one READ THE INPUT DATA and APPLY it to the FUNCTION?
If one uses a classical computer to supply the data sequentially off a hard drive or memory, surely the quantum processor will be in continuous 'wait states' which would make processing slow!
Sir,could you give the overview of whats the use of QFT and what changes it brings to the circuit(in reference to the Shor's Algorithm)
what was the simulator used? i need it pLEASE
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
What other pragmatic algotithm?Please state or show.Thanck you.
Great vid! Thanks! I have a little issue with how you’ve written your limits on the summation signs at minute 6.34.
We aren’t really summing over y, we’re summing over all combinations of 2^n bit strings right? So y=0 would correspond to |00...0>. Would it be better to write at the bottom of the sum: y = {0,1}^n? Or maybe to sum over index i and put a subscript on the y: |y_i> therefore when i=0 |y_0> = |00...0>?
I’m only learning this for the first time so maybe you are just following a convention I haven’t come across yet in which case I apologise!
You made a mistake at the end. You said that constructive interference as constant whereas destructive interference is the real constant function.
Nice work.
Why 1/(sqrt(2^("n+1")) rather than "n" at 5:35?
Excellent question! So I assume you mean why 'n + 1' instead of 'n,' or in other words why is there an extra qubit? Well that extra qubit actually has a specific name. It is called the 'Ancilla bit' and is used to assist in the computation. The Ancilla bit can safety ignored in later steps of the equation when it has served its purpose and is not longer needed. Here's the Wikipedia article on it if you are interested.
en.wikipedia.org/wiki/Ancilla_bit
If you want to know exactly how it assists in this computation, let me know and I'll figure out the best way to explain it.
Travis Gritter Oh, I see! Thanks for your reply and great video :)
I am not able to find about oracle function, plz help me to find it out
Hi Abhinavan! An oracle function is just an easy way of saying "assume we have a function that can solve a particular problem." For this algorithm it is useful because it would be tedious and unnecessary to have to show excatly what the equations behind the balancing function is, so makes the overall problem easier to understand. However, if you wanted to actually implement this function on a real computer, you would need the details of the algorithm instead of simply declaring it an Oracle function. Here is a link to the Wikipedia article if you would like some more information.
en.wikipedia.org/wiki/Oracle_machine
You used different definition of balanced for the first half of your video and the second half. And FYI your second definition can be solved in (on average) constant time on a classical computer, which is with high probability faster than quantum computer.
I'm not sure what you mean by two definitions. If you are referring to the fact that in the first first part I say a constant function outputs all 0's and in the second part I show the balanced function outputting all 0's, keep in mind that the output of the function and the output of the simulator are not the same. The difference is that the function outputs the value of a SINGLE input and the quantum simulator outputs the value of ALL the inputs. As such, I don't see how a classical computer can solve this problem in constant time.
Travis Gritter Oh actually you only said it once that balanced is that there is an even number of 0 and 1 outputs (the word even is very misleading). For the latter question, a randomized algorithm can find one such input with half probability and therefore if one attempts C (constant) times, and the probability that he fails is 2^-C which can be arbitrarily small regardless of n. Of course you can argue about worst case but in reality it almost never happens.
Travis Gritter I just want to argue that this algorithm isn't as practical as you claimed. It's only a breakthrough of worst case complexity.
Ah I see, yes this question is all about solving for the worst case scenario. In the best case a classical computer can solve it in two steps (i.e the function outputs a 0 and then 1, ensuring it is balanced), a quantum computer however can solve it in the worse case in just one step.
And yes you are also right that this question has very little practical application. Keep in mind that this is the first quantum algorithm ever created, and was designed specifically to show how quantum computers can solve questions faster than classical ones. However, people have used this question to design other quantum algorithms that do have practical applications. For example, Grover's Search Algorithm, a very practical quantum algorithm, was directly inspired by this problem. The hope is that there's many other practical quantum algorithm's out there to be discovered as well.
I think it's worth adding that the runtime that was being compared is in the big O notation, that is we're simply considering the upperbound for both algorithms. Do note that although the average runtime is indeed considered as well in most algorithm analysis.
1-07-2020.One small tip, if you are going to show a arrow please make it RED and when you subtact makeit Orenge,Thanck you.