Fundamentals of Quantum Information

The following sections are included:

• Preface
• Preface
• Contents

The formulation of classical physics was started at the beginning of the 17th century by an Italian scientist Galileo Galilei. Through 17th century to 19th century, many experimental and theoretical findings were achieved by several brilliant scientists. The mechanics were established by Galileo Galilei and Isaac Newton, the electromagnetism by Michael Faraday and James Maxwell and the thermodynamics by Ludwig Boltzmann. At the end of the 19th century, many physicists thought that all problems of physical world were solved and the description of the universe was complete. However there were still few unsolved problems. Two of the major unsolved problems were Michelson-Morley measurement of speed of light and the black-body radiations. The study of two problems led to great discoveries in the history of science; special relativity and quantum mechanics. Albert Einstein contributed to both discoveries in 1905…

Any physical phenomenon is described by a state vector and an operator in the quantum world. We present mathematical methods which connect the microscopic physical world to the quantum mechanics. Two different representations will be discussed in this chapter. One is the matrix mechanics formulated by W. Heisenberg. Another one is Schrödinger wave mechanics. At first two models appear very different each other, but it was proved that two theories are completely equivalent and lead to the same physical predictions. Both models have been quite useful not only in the formulation of quantum mechanics, but also in the development of quantum information theory.

It is known that a particle shows two different characters, particle-wave duality in the quantum mechanical world. Photons show the character of wave, such as diffraction and interference, but the photo-electric effect and the black-body radiation can be explained only by the particle character of light. In the microscopic world, duality is a property not only inherent in photons but also common in all particles including electrons, protons and neutrons. From this peculiar character of particles, the motion in the microscopic world can be understood only in the probability interpretation, i.e., the particles are described by the wave function ψ with a wave character and the measurements give the probabilities of finding particles in space-time. This is the concept called the Copenhagen interpretation of quantum mechanics, developed by Niels Bohr and his group. In this chapter, we summarize the basic ideas, principles and concepts of quantum mechanics.

In the 1920s when quantum mechanics was being established, there was a famous controversy between Bohr and Einstein about the statistical interpretation of quantum mechanics. The controversy was finally concluded by an emphatic victory of Bohr, since his statistical interpretation and the duality of wave and particle explained many experimental facts without any difficulty. The “Gedanken” experiment on two entangled particles (the EPR pair) presented by Einstein, Podolski and Rosen in the course of the controversy, however, has had a continuous influence for many years on quantum communication and quantum cryptography which are being developed at the present day.

A mathematical model of classical computer was invented by Alan Turing and named “Turing machine” model, which is an idealized computer with a simple set of instructions and infinite memories. Soon after Turing’s model was proposed, John von Neumann developed a theoretical model for how to implement all the components in a computer to be fully capable as a Turing machine. In more practical way, we will make use of the circuit model, which is useful also in the study of quantum computation. A circuit may involve many inputs, outputs, many wires and many logic gates. These circuits will be implemented by semi-conductors, which have two functions as conductor and insulator and acts under given conditions as a high-speed switch that leads and stops electricity. Modern computers such as personal computers (PC) use integrated circuits (IC) of semiconductor. While the peculiar feature of semiconductor is based entirely on physics of quantum mechanics, we do not call these computers “quantum computers” but rather called “classical computers”, because logic gates are based on binary representations and any quantum state of atom or molecule is not used as a logic gate: in classical computers, the data are represented by two logical values 0 and 1 in the circuits using devices with high voltage/low voltage, current on/off, and/or direction of magnetization up/down.

As was described in Chapter 3 on “Basic Concepts of Quantum Mechanics”, a quantum bit (qubit) might be implemented by two quantum states with two different eigenenergies. The logical values 0 and 1 can be obtained, for example, by the direction of spin of an electron or an atom, the ground state and an excited state of an atom, and also the slit that a photon pass through…

The concept of entropy was firstly introduced in thermodynamics to measure the disorder and the uncertainty of a system. In physics, the entropy has been used to measure the diffusion of heat or materials. Nowadays, the idea of entropy is used also in the communication theory as a measure of the transmission speed of information, i.e., how much information can be delivered in a fixed time period. In data communication, the information is transmitted as bits, irrespective of whether it contain characters or pictures. There are many algorithms to change the data to the bit information. If the amount of contents is the same, it is obvious that the less bit length makes the faster communication. Thus, the concept of entropy is closely related to the problem of data compression…

A mathematical model of present computers (classical computers) was invented by Alan Turing in 1930s, and it is called the Turing Machine. The procedure to solve problems on a classical computer is given as “instructions” on the Turing machine. The combination of these instructions is called “algorithm”. Examples of the simplest algorithms are the arithmetic operations such as addition and subtraction. Among these algorithms, the multiplication is relatively fast, while those for division and chess game are rather slow. A typical one among slow algorithms is the factorization. It is an important subject for the model of computers to invent an effective algorithm for a certain problem. The effective algorithms mean that the instructions are finished in polynomial time. When one tries to solve the problem of factorization on a classical computer, the computational time increases exponentially, and it becomes practically impossible to solve the problem with a large number of digits. There is a problem called RSA139 in which the number to be solved has 139digits. It took ten years to solve this RSA139 problem. The public key cryptography, one of the most advanced system of cryptography today, is based upon the difficulty of factorization…

From the period of old Roman empire, the cryptography has been used for various purposes including those in military, in diplomacy, and in trade of commerce. Encoding and decoding cryptographic codes have close relation with many types of nation-wide crises and criminal cases in history. Up to the present days, the intelligence agencies of many countries continue to be engaged in developing and breaking new cryptography codes day and night. The RSA cryptography, one of the most sophisticated cryptographies today, is considered to be broken sooner or later when the speed of computers develops remarkably. The cryptography systems in use at present are generally called classical cryptography. Recently, new type of cryptography that is completely different from the classical cryptography is proposed. That is the quantum cryptography. The coding in quantum cryptography is based on the theory of observation in quantum mechanics, and it is considered impossible to tap the codes theoretically due to the irreversible phenomenon called the contraction of wave packets. The implementation of quantum cryptography coding will mean the perfect cryptography that is in principle unbreakable.

The quantum search algorithm was discovered by L. K. Grover in 1997, and is called Grover’s algorithm after his name. Let us consider how to find elements marked by a certain symbol out of a database consisting of N elements (say, multi-million elements). This problem is similar to how to find the name of the person from a telephone book knowing only his/her telephone number. This search takes by far more time than finding the phone number from the name of the person. The difference comes from the structure of the telephone book. In the telephone book, the names are arranged in the alphabetical order and constitute the structured database, while phone numbers do not form any structure in the telephone book. In classical computers, when we search one target element from the database with N elements, we need N/2 trials on average. Grover showed using the quantum search algorithm that $\sqrt{N}$ trials will be enough on average to find the target element from the database with N elements. Shor’s quantum computation algorithm was an epoch-making algorithm which made possible to solve the factorization problem in polynomial time, while the classical computers need exponentially increasing time to solve it. In comparison, Grover’s algorithm makes the data search possible by $O\left(\sqrt{N}\right)$ computation time, while it takes O(N) computation time by the classical computers. Concerning the reduction of computing time, Grover’s algorithm may look less powerful than Shor’s algorithm. However, it has good potentiality of application in the wide area such as NP-complete problems and structured databases.

To implement quantum computers, one needs physical systems to perform the unitary transformations such as the Hadamard transformation on qubits. Quantum devices by atoms, molecules and atomic nuclei, are invented as quantum computers, those using photons or superconducting devices are invented as quantum computers, where the systems are controlled according to the laws of quantum mechanics…

Quantum gates or universal quantum gates have been used a common concept of quantum computer. There is another type of quantum computing algorithm, which is recently implemented as an effective concept of quantum computer. This is the quantum annealing computer. The quantum annealing machine is shown recently a very powerful tool to solve combinatory optimization problems such as traveling salesman problem (TSP). A Canadian venture company D-Wave Systems has commercialized this type of quantum computer with 2000 Q-bits on the market.

The following sections are included:

• Appendix A Basic Theory of Numbers
  • Congruence
  • Euler’s theorem (Fermat’s little theorem)
  • Euclid’s algorithm
  • Diophantus equation (Indeterminate equation)
  • Chinese remainder theorem
  • Continued fractions
• Appendix B Solutions of Problems

The following sections are included:

• Bibliography
• Index