1. What is QIP: Disciplines and goal
Quantum Information Processing(QIP) is a general terminology that extends the concept of quantum computing, which is supported by Quantum mechanics and Information theory. QIP mainly consists of three disciplines, which are quantum sensing, quantum communication and quantum computing. Three branches are all about data. Quantum sensing is about collection of data. Quantum communication is about transmission of data, and Quantum computing is about processing of data. Since quantum systems are highly sensitive to its surroundings, precise processing is also hindered and implementation of quantum computing algorithms is hard.
Then, what is QIP? Quantum Information Processing is the result of using the laws of quantum physics to perform information processing tasks that were previously believed impossible or infeasible. To be frankly, this definition is the goal of QIP, which is not always available. However, there are some fields of applications that QIP shows supremacy.
2. Fundamental questions in quantum computing: CS perspective
Fundemantal questions in computer science view include such questions like "is a problem computable?", and "how much resource is required?". In the second statement resource is an intrinsic and abstract concept, which roughly indicates the required amount of spacetime for solving the problem and notated by Big O (i.e. O(f(n)). Extended Church-Turing thesis(Extended C-T thesis) gives a fundamental explanation of relationship between hypothetical turing machine and realistic model. According to Extended C-T thesis, a probablistic turing machine(PTM) can efficiently simulate any realistic model of computing. We can argue that our laptop can efficiently simulate PTM, and PTM can efficiently simulate any realistic device. The concept of "efficient" is defined that complexity of simulating algorithm is bounded to polynomial with N (i.e.). However, the emergence of quantum computer violates the intrinsic & mathematical thesis. If we build a computer that follows a rule of quantum mechanics, the relationship of Extended C-T thesis will be broken since we don't know how to simulate quantum computer with classical computing methods. Thus, QIP intrinsically challenges some conventional laws or thesis while these violations motivate the emergence of QIP, ironically.
3. Motivation of QIP: fundamental challenges
Since 1990s, computational power has been increased due to the development of engineering technologies that conduct more transistors in a given space. Moore's law argued the exponential increasement of computational power across time, but quantum mechanics suggests a fundamental limit of computational power. As transistor size and distance decreases, when it becomes comparable to the size of atom, quantum mechanic behaviors will emerge(e.g. tunneling). The motivation of QIP comes from this point. If it is inavoidable on quantum mechanics' effect, why don't we exploit it? Intuitively, this argument seems plausible. Since classical mechanics is the special case of quantum mechanics under v/c << 1 constraint, quantum mechanics is naturally superior to the classical mechanics. This analogy gives an idea that quantum computer that follows the rule of quantum mechanics is also naturally superior to classical computer. Despite of this intutition, quantum computer is not just a "better" classical computer. They are based on a different set of rules, thus pros and cons exists. Currently quantum computer shows some supremacy in specific problems, in a limited performance.
4. How much quantum computation is faster?
Efficiency and computational cost of problem solving algorithms are illustrated by big O notation, which indicates the relationship between increment of problem size and computational cost. For example, in language of computer science, 'efficiently' means polynomial time complexity. Quantum computation shows supremacy in RSA code breaking problem, which is a factoring problem. It is known that finding two prime numbers p,q that satisfies pq = N is equivalent to guessing the password. Shor's algorithm is a quantum algorithm at solves prime factoring problem, and theoretically quantum computing shows supremacy at solving 512-bit length RSA problem.
5. Classical vs Quantum computation
Quantum Computing can be interpreted in terms of duality. One of the hallmakrs of quantum mechanics is wave-particle duality, while quantum computing leverages this duality by achieving analog-digital duality. General computing process consists of input, evaluation, and output step. Quantum computing gives a wave-like input, evaluate through quantum circuits, and observe the particle-like output. Digitalized signal is easy to cope with error by discretization, while analog signals are hard to scale-up to large devices since we can't acquire 100% precision on continuous real numbers. Quantum computing will link analog input signal and particle-like output observations by leveraging the power of wave-particle duality.
At the next article, let's dicuss more about philosophical differences between classical and quantum computation.
