We can now start quantum computing. Before starting quantum computing, let me first explain what computing is, or how we can characterize computing, and algorithms. In a simple term, computation is a transformation of input to something, and something will be the solution of some problem that you want to solve from the beginning. Computing or algorithm is a process that transforms the trivial state, so it's important that we have trivial input here. Then the output must be meaningful. Meaningful in the sense that, it gives you the solution of some problem we want to solve from the beginning or it have solving the problem, so either way. Important condition in the idea of the concept of computing is that, it should exploit a finite resources. Resources here could be time, or steps, or space, so resource should be a finite. For instance, say algorithm that run infinite number of loop is not an algorithm because it doesn't stop. It should have stop at some point and is finite time and it doesn't exploit infinite number of resources. That's computing we often and can think about or we can translate the tutting machine to this picture then in practical sense, and this is computing. Then this computing process can be written or composed by few number of logic gates. For instance, you can apply NAND, OR gate and etc. These form are universal gate. Using this gate, you can construct any steps of logics for this bit. Now we want to translate or transfer this idea to quantum computing. It's not like to translate this trivial input to trivial quantum state, so we can put just this guy. We put here n bits and here you put the n qubit and the output, in general we can put n bit and therefore the output will be n qubit quantum state here. Then process of n qubit or a transformation of n qubit quantum state. We can draw a very big unit of transformation. This is the transformation of n qubit state. Similarity to the universal logic gate here, we have a universe quantum gates. A good example would be CNOT and single qubit rotation. We can put here n Theta, so there's single qubit operation and CNOT gate. Or we can put Clifford gate and some non Clifford gate, for instance, and T gate. Or we can choose a Toffoli gate and Hadamard gate. Toffoli gate is a three qubit and combining them, you can approximate any quantum circuit. If you see this one, this is not really quantum computing because we have to learn about this solution by measurement. This would be by measurement, and this will be by preparation or initialization. We have to prepare quantum states from classical bits. Then we process in a quantum way rather than this classical way. Then we get solution or states right after the evolution. We will learn about some meaningful messaging or from this rejecting state by measurement. These full process, we can call quantum computing, and this one is a classical computing. The important part is this transformation. This is a general picture of quantum computing or quantum algorithm. The task is to compose this part, how we can transform the initial state to output state. So far, there are number of quantum algorithms, and most of them, there are two roots. The first one is Grover algorithm. This is the type that follows this one precisely. It start with initial state, which is zero and [inaudible]. Why do we prepare this kind of states? Because these generate uniform superposition of all possible states, all N qubit states. The rejecting state here is, I mean, just for convenience, for now, I will write here as 0 plus N. Yeah. I put to N is i^N. You start with the initial states. You know from the superposition of N state. The goal of a Grover algorithm is to transform this guy to one of the states, t. t, is one of this states. What is the difference between this state and this state? If you perform measurement on this state, say in the computational basis, the probability that you can find a t state here is just 1 over N. After this transformation, the probability that we find or we measure this state of t here is 1. It's a transformation of the probability 1 over N to N. You can see this one is amplification of the amplitude of the t state. The more general concept, we call quantum. This process is really amplify or increase the amplitude of t we call target state from the beginning and to the end. What would be the classical analogy of this picture? Initially, we have the probability 1 over N. After all, we have N. You can think about some database here, but it is unsorted, so unsorted, or unstructured database. Suppose there are N items and we want to find something, we want something desired, and that we can put t. In the beginning, the probability that we can find the target here is the same 1 over N. Then after all, we want to find the target. This means the probability that we won't have the target is one. This is precisely database searching algorithms. Classically, how long does it take from this probability to this one? It takes about some iteration, which is proportional to N. This is actually optimized, so we put here 0,N. Want has to check out this DB about this time, statistically the complexity. Quantumly, how long does it take from here to here, in fact, is about scale, is some number of iterations which is proportional to square root N. We have a quadratic speed up in Grover case. This complexity is proven to be optimal, and this is optimal. Grover algorithm or quantum searching algorithm, is one instance where we can see clear a quantum advantages over classical cases. This is really mapping from initial state to the resulting state, which is t and target so this should be T_1 and T_n. All computation is done by these quantum amplitude amplification process is quantum computing. The next or the other class is a Shor or quantum prime number factorization accuracy. This class is not purely classical and may contain two steps. I start with the initial state here, and then there is a quantum pilot and we perform measurements. After measurement, there is a classical algorithm. Yeah, this applies some continued fractions and some classical post-processing, so this combination of quantum and classical. A key component in this quantum part is a period of finding or order finding. The goal of this quantum process to find the order, which is related to prime number factorization. Technically, if you look more carefully, the real quantum step here is a quantum Fourier transformation, which is analogy of fast Fourier transformation in signal processing. This is the backbone or the key part of the speedup of the prime number factorization, how does it work? If you recall this fast Fourier transformation, it is mapping from vector. Initially we have 0 to n minus 1, n is mapping to y_0, y_n. It's mapping from vector to vector. The relation between these two guys is, so initially, we have this vector n is maps to this one, by the Fourier transformation. Quantum Fourier transformation is a mapping from state to quantum state. Initially, if we have states right here, Xj and j, and it maps to quantum Fourier transformation and maps k to yk and k. This is coefficient, and what QFT does, it transform this bases to k, so it maps j to k. This is j. This QFT transform the bases and then rewrite this part, and you can get yj, which is coefficient, and that corresponds to this guy. Then the resources we need to this one is actually, if we have a relation, I wrote here, this guy, then the number of gates we need to realize fast Fourier transformation is proportional to n times 2^n gates. That's some resources we need, and the quantum Fourier transformation for that, we need n square quantum gate. We have some speedup from here, or advantage from here to here. If you compare these two numbers, so n times m, and this is the case of a fast Fourier transformation, then here we have n times log n. This exponential part is transformed to polynomial part here. Most quantum algorithms known so far, they can be classified either Grover type or Shor type or applications of quantum Fourier transformation. Grover type domain, quantum part is the quantum amplitude amplification. Panama factorization, the key part is quantum Fourier transformation, this is the path that gives you speedup over classical counterpart.
