Very much enjoyed @Guillermo_Alonso tutorial on Grover. I am interested in two questions. First, where exactly is the quantum resource. Second, does the oracle need to check all entries anyway (to decide for which one amplitude needs to be negated). Thanks!
1 Like
Hi @epothos 
I’m not sure I understand the first question, could you elaborate on it a bit more? Regarding the second question, it is very interesting! One of my favorite papers is the Brassard algorithm (Amplitude Amplification) which is a generalization of Grover. It allows you to search on sets of interest and not have to spend resources on searching the whole space
thanks for the prompt rely! Regarding the first question, where does the quantum ‘magic’ come from? Why can’t we implement everything as an algebraic recipe on a classical computer? Why do we need a quantum computer for grover to work? Regarding the second question, I am still puzzled by the fact that the oracle in grover needs to check all possible solutions in our state – is this not an operation analogous to the classical brute force algorithm?
The “magic” is precisely there, the brute force in quantum manages to decrease the complexity by a quadratic factor 
This is because the grover operator as it is constructed allows to interfere in states in a way that a classical computer could not. There is a visual representation that allows you to understand this in a clearer way, I invite you to take a look at the codebook.
1 Like
Thanks and very beautiful graphical illustration! I can understand the algebraic steps reasonably well, still I am unclear on my initial questions: in what part of the setup do we assume quantum physical resources. Put differently, why can’t we just write out Psi as a linear, classical mixture. That is, in what part of the setup is the quantum physical resource needed. And second to make this work we need to check all states against the oracle. For example, in the first step, we flip the sign of the solution state. If we know which state we have to focus on for flipping the sign, don’t we basically know the solution already? Thanks!
Hi @epothos, good questions! I think it’s best if Guillermo answers this question himself next week so make sure to come back then to get his answer to your questions.
Have a good weekend!
Hello @epothos ! The Grover operator is an operator that takes a superposition of all inputs, i.e. “all at the same time”. It then acts on them by amplifying the probability of the good ones. It would not be the same as sending a list with all possible values as that would be neither time nor memory efficient. Regarding the second question, it is something I tried to emphasize in the video, imagine I give you a sudoku. You will probably be able to detect if it is well done (and therefore a solution) or not. That does not imply that you know how to solve the sudoku That is what the oracle does, it detects if something is a solution, not tell you how to get it.
1 Like
Thanks and these are really great answers! Insight here though is still a little elusive: why does the state have to be a superposition as opposed to a linear mixture? Why can’t we have a linear mixture and reverse weight/ amplitude in that? That is, the necessity for a superposition in Grover is not evident. Also, I understand the sudoku example – this is a great example. However, my question is that, as in the classical case, for Grover to work the oracle needs to check all possible solutions. Why is it more efficient than the classical method? Thank you!
The answer to the first question is a somewhat complex phenomenon, interference. The fact that they are in superposition allows some solution candidates to interact with others . This means that they can cancel each other out or increase their presence in the set. Regarding the second question, although Grover searches the whole set, it has not had to generate each input one by one, by putting Hadamards gates he has generated the whole set so it has not really had to go through all the options in time O(N)
Thanks again Alonso and this is a great answer. Let me say first that I am familiar with superpositions, interference etc – many of the basic tools in quantum theory and quantum information (as I imagine some readers of this forum would be). Regarding Grover, how does interference help though? The intuitive explanation seems to be that the oracle checks the candidate solutions (in the superposition state) and as a result can flip the amplitude of the target solution. I am still unclear how the oracle can identify the target solution, without checking all of them 
Don’t worry, it’s not easy to understand at first time Let me give you another example. In this demo, I end up putting an example of Grover to factor numbers. The oracle does not know how to factor a number D, but if it receives two numbers m and n it easily knows how to check if it is the solution. It multiplies them and checks if the product is D.
The key is that we are not going to pass m and n one at a time (as we would do classically). We are going to send all possible combinations at the same time. That’s the reason of putting the Hadamards at the beginning.
2 Likes
Thanks for not giving up on me! I had a look at the other application, it’s great. I think it is clear how, with Grover, one can take any search problem and adapt it accordingly. I still can’t get over my main hurdle though! For Grover to work, you already need a representation of all possible solutions and an oracle capable of checking all these solutions! So, how can Grover do this in a way that utilises fewer resources? (It should not matter whether the candidate solutions are passed to the oracle one by one or simultaneously, since a naïve parallel architecture would always be equivalent to a sequential one…)
Even if you have k classical computers to run in parallel, the complexity of the algorithm will still be O(N) since O(N/k) = O(N) In quantum we will still have O(sqrt(N)) complexity
Yes, of course, I appreciate this! But this is what I was asking: even in the quantum case, it looks like the oracle needs to check all possible solutions…so where does the saving come from? Thanks!
It seems to run through them all but it doesn’t 
In the input we introduce all but the way to amplify the solutions is not by going through the vector and checking the solutions