The first quantum algorithm has been introduced by David Deutsch. Following by his name David Deutsch, we call the Deutsch algorithm. This algorithm has been introduced in 80s. David Deutsch was thinking about how powerful quantum computing is and so he invented an artificial mathematical problem just to show the capability of quantum computing. Mainly he wanted to show quantum computing is more powerful than a classical counterpart. It's a very simple problem and is actually about the function f, is a mapping from one bit to one bit. It's a very simple function. The question and the main problem is a decision problem. Given this function, the question is to decide if the function is balanced or constant. It is important that we don't have to know the function and we just want to decide if the function is constant or balanced. Here the function is called constant if it's a mapping of this domain 0 and 1 into a single value 0 or 1, to single value 1, then the function is called a constant. Balanced means that a function is a one-to-one correspondence. If mapping 0, 1 to 0, 1 or 0, 1 to 1, 0, then the function is called balanced. Given this function, we have to solve or decide if the function is constant or balanced. How can you do that? To make this conclusion, we first have to compute this guy and this guy. Learning this one by computing the function f once and the second time we compute this guy and we compare them. If they are equal or different. If they are equal, then the function must be constant. If they are unequal, then the function must be balanced. We have to compute the function f twice. Once and the second time here. Or perhaps it maybe easier to put it this way. If we learn this guy, then we can find the function is constant or balanced. If it's zero, then the function must be a constant. In this case, both of them are 0 or 1. Or if this is 1, which means two values are different, then the function must be balanced. I want to note that knowing either of them, if I know f of 0, f of 1, just one of them, then it doesn't help me. I have to know both of them. Which means, to solve this decision problem, we have to compute the function f twice. That's actually the complexity or the difficulty of solving the problem. David Deutsch here has shown that in quantum way, this can be reduced to single. Computing some quantum function f once, then we can have the solution here. How does it work? This is called Deutsch algorithm. To approach this problem in a quantum way, we have to find the quantum reallocation of this function. We have to consider this transformation is a transformation from state to state, unitary transformation. Then we have to find if this guy f is constant or balanced. This is our task. This one bit mapping may not be reversible, but this guy should be reversible because of the unitarity condition. We can realize this guy as a mapping from X and Y can be too big because to preserve the unitarity, it's mapping from X to Y plus NFX. You can think of a C-NOT gate, then C-NOT gate means addition. Addition is transformed to unitary transformation then we have a C-NOT gate. Here we are thinking of the quantum counterpart of this guy and we have the computation here. This defines to compute f in a quantum way. An important technique we will use to approach this Deutsch algorithm, it affects kickback technique. We write phase kickback and how it works. You can start with this guy and minus just for convenience. You put minus here and 0. Later, I will clarify that why we have to put minus here because this is for the phase technique, but let's put here minus. This means we apply this f 2 and then if you apply this guy here, then we have zero plus f 0. Here minus 0 and 1 plus f 0. There are two possibilities now. The first case, f 0 could be 0. Then the outcome we have here is a 0 and 1 and therefore is simply 0 and minus. The second function could be 1. Then we have 1 and here 0, therefore we have a minus vector, minus 0 and minus. This is a global phase at this one-dimensional, but if you apply this one for two qubit with conditioning, then this plays a role. We want to keep this minus sign here. Overall, we can simplify this question as minus 1, f 0, because f 0 is 1 then minus, and 0, then we have nothing. Then equals 0 and minus. You can generalize this one to any qubit. In general, you can put here X and minus and the outcome can be simplified as minus 1 and F X, and minus. If you look at the first qubit here, the qubit in the first resistor, X is mapped to X so it remain the same. But we have a phase vector here. This appears due to the interaction between the first and second qubit. The interaction happens by this guy. If you start this transformation without minus, then you won't have this phase vector. You could have this phase vector because the two qubits interacted via this unitary transformation. This one is exploited to have a phase vector here. This is called a phase kickback technique.
