Part 1.
Basic concepts

Chapter 1.
Introduction and Overview
__1.1 Overall Perspective
__1.1.1 History of Quantum Computation and Quantum Information
__1.1.2 Future Directions
__1.2 Quantum Bit
__1.2.1 Multiple Qubits
__1.3 Quantum Computation
__1.3.1 Single-qubit gates
__1.3.2 Multi-qubit gates
__1.3.3 Measurements on a basis other than a computational basis
__1.3.4 Quantum Circuits
__1.3.5 Qubit copy circuit?
__1.3.6 Example: Bell status
__1.3.7 Example: Quantum Teleportation
__1.4 Quantum Algorithms
__1.4.1 Classical Computation on Quantum Computers
__1.4.2 Quantum Parallelism
__1.4.3 Deutsch algorithm
__1.4.4 Deutsch-Josa algorithm
__1.4.5 Summary of Quantum Algorithms
__1.5 Experimental Quantum Information Processing
__1.5.1 Stern-Gerlach experiment
__1.5.2 Prospects for Practical Quantum Information Processing
__1.6 Quantum Information
__1.6.1 Quantum Information Theory: Example Problems
__1.6.2 Quantum Information in a Broader Context
__History and Additional Materials

Chapter 2.
Introduction to Quantum Mechanics
__2.1 Linear Algebra
__2.1.1 Basis and Linear Independence
__2.1.2 Linear operators and matrices
__2.1.3 Pauli matrix
__2.1.4 Inner product
__2.1.5 Eigenvectors and Eigenvalues
__2.1.6 Adjoint Operators and Hermitian Operators
__2.1.7 Tensor product
__2.1.8 Operator functions
__2.1.9 Exchangers and Counter-Exchangers
__2.1.10 Polar decomposition and singular value decomposition
__2.2 Postulates of Quantum Mechanics
__2.2.1 State space
__2.2.2 Evolution
__2.2.3 Quantum Measurement
__2.2.4 Quantum state distinction
__2.2.5 Projective Measurement
__2.2.6 POVM Measurement
__2.2.7 phase
__2.2.8 Complex Systems
__2.2.9 Quantum Mechanics: Worldview
__2.3 Application: Ultra-high-density coding
__2.4 Density Operator
__2.4.1 Ensembles of quantum states
__2.4.2 General characteristics of density operators
__2.4.3 Conversion density operator
__2.5 Schmidt Decomposition and Purification
__2.6 EPR and Bell's Inequality
__History and Additional Materials

Chapter 3.
Introduction to Computer Science
__3.1 Computational Model
__3.1.1 Turing Machine
__3.1.2 Circuit
__3.2 Analysis of computational problems
__3.2.1 How to Quantify Computational Resources
__3.2.2 Computational Complexity
__3.2.3 Decision Problem and Complexity Classes P and NP
__3.2.4 Numerous complexity classes
__3.2.5 Energy and Computation
__3.3 Perspectives on Computer Science
__History and Additional Materials

Part 2.
quantum computing

Chapter 4.
quantum circuit
__4.1 Quantum Algorithms
__4.2 Single-qubit operations
__4.3 Control operation
__4.4 Measurement
__4.5 Universal quantum gates
__4.5.1 Level 2 Unitary Gates are universal
__4.5.2 Single-qubit and CNOT gates are universal
__4.5.3 Discrete set of universal operations
__4.5.4 Approximating arbitrary unitary gates is generally difficult.
__4.5.5 Quantum Computational Complexity
__4.6 Summary of Quantum Circuit Computational Models
__4.7 Simulation of Quantum Systems
__4.7.1 Simulation Operation
__4.7.2 Quantum Simulation Algorithm
__4.7.3 Explanation Example
__4.7.4 Perspectives on Quantum Simulation
__History and Additional Materials

Chapter 5.
Quantum Fourier Transform and Its Applications
__5.1 Quantum Fourier Transform
__5.2 Phase estimation
__5.2.1 Performance and Requirements
__5.3 Application: Finding Order and Factoring
__5.3.1 Application: Finding the Order
__5.3.2 Application: Factoring
__5.4 General Applications of the Quantum Fourier Transform
__5.4.1 Finding the period
__5.4.2 Discrete logarithm
__5.4.3 Hidden Subgroup Problem
__5.4.4 Other quantum algorithms?
__History and Additional Materials

Chapter 6.
Quantum search algorithm
__6.1 Quantum Search Algorithm
__6.1.1 Oracle
__6.1.2 Procedure
__6.1.3 Geometric Visualization
__6.1.4 Performance
__6.2 Quantum exploration as quantum simulation
__6.3 Quantum Counting
__6.4 Speeding up the solution of NP-complete problems
__6.5 Quantum exploration of unstructured databases
__6.6 Optimality of Search Algorithms
__6.7 Limitations of the Black Box Algorithm
__History and Additional Materials

Chapter 7.
Quantum Computers: Physical Realization
__7.1 Basic Principles
__7.2 Conditions for Quantum Computation
__7.2.1 Representation of Quantum Information
__7.2.2 Performance of Unitary Conversion
__7.2.3 Preparation of the initial state as a reference
__7.2.4 Output result measurement
__7.3 Harmonic Oscillator Quantum Computer
__7.3.1 Physical Device
__7.3.2 Hamiltonian
__7.3.3 Quantum Computation
__7.3.4 Disadvantages
__7.4 Optical Photonic Quantum Computers
__7.4.1 Physical Device
__7.4.2 Quantum Computation
__7.4.3 Disadvantages
__7.5 Optical Resonator Quantum Electrodynamics
__7.5.1 Physical Devices
__7.5.2 Hamiltonian
__7.5.3 Single-photon single-atom absorption and refraction
__7.5.4 Quantum Computation
__7.6 Ion trap
__7.6.1 Physical Device
__7.6.2 Hamiltonian
__7.6.3 Quantum Computation
__7.6.4 Experiment
__7.7 Nuclear Magnetic Resonance
__7.7.1 Physical Device
__7.7.2 Hamiltonian
__7.7.3 Quantum Computation
__7.7.4 Experiment
__7.8 Other implementation systems
__History and Additional Materials

Part 3.
Quantum information

Chapter 8.
Quantum noise and quantum operations
__8.1 Classical Noise and Markov Processes
__8.2 Quantum Operations
__8.2.1 Overview
__8.2.2 Environment and Quantum Operations
__8.2.3 Operator-sum representation
__8.2.4 Axiomatic Approach to Quantum Operations
__8.3 Examples of Quantum Noise and Quantum Operations
__8.3.1 Diagonal sums and partial diagonals
__8.3.2 Geometrical illustration of single-qubit quantum operations
__8.3.3 Bit-inversion channel and phase-inversion channel
__8.3.4 Depolarizing Channel
__8.3.5 Amplitude attenuation
__8.3.6 Phase decay
__8.4 Applications of Quantum Operations
__8.4.1 Governing Equations
__8.4.2 Quantum Process Tomography
__8.5 Limitations of the quantum computation formalism
__History and Additional Materials

Chapter 9.
Distance measurement for quantum information
__9.1 Distance measures for classical information
__9.2 How close are two quantum states?
__9.2.1 Diagonal distance
__9.2.2 Fidelity
__9.2.3 Relationship between distance measures
__9.3 How well do quantum channels preserve information?
__History and Additional Materials

Chapter 10.
Quantum error correction
__10.1 Introduction
__10.1.1 3-qubit bit-reversal code
__10.1.2 3-qubit phase-flip code
__10.2 Shore Code
__10.3 Quantum Error Correction Theory
__10.3.1 Error Discretization
__10.3.2 Independent Error Model
__10.3.3 Degenerate Code
__10.3.4 Quantum Hamming Bound
__10.4 Creating Quantum Codes
__10.4.1 Classical linear code
__10.4.2 Calderbank-Shore-Stain Code
__10.5 Stabilizer Code
__10.5.1 Stabilizer Formal System
__10.5.2 Unitary Gate and Stabilizer Formulation
__10.5.3 Measurement in the Stabilizer Formal System
__10.5.4 Gottesmann-Neel theorem
__10.5.5 Creating a stable code
__10.5.6 Example
__10.5.7 Standard form of stabilizer code
__10.5.8 Quantum Circuits for Encoding, Decoding, and Correction
__10.6 Fault-Tolerant Quantum Computing
__10.6.1 Fault Tolerance: Full Outline
__10.6.2 Fault-Tolerant Quantum Logic
__10.6.3 Fault Tolerance Measurement
__10.6.4 Elements of Elastic Quantum Computation
__History and Additional Materials

Chapter 11.
Entropy and Information
__11.1 Shannon entropy
__11.2 Basic Properties of Entropy
__11.2.1 Binary Entropy
__11.2.2 Relative Entropy
__11.2.3 Conditional Entropy and Mutual Information
__11.2.4 Data Processing Inequalities
__11.3 Von Neumann Entropy
__11.3.1 Quantum Relative Entropy
__11.3.2 Basic Properties of Entropy
__11.3.3 Measurement and Entropy
__11.3.4 Quasi-additiveness
__11.3.5 Concavity of Entropy
__11.3.6 Entropy of Quantum State Mixing
__11.4 Strong quasi-additiveness
__11.4.1 Proof of Strong Quasi-Additivity
__11.4.2 Strong Quasi-Additivity: Basic Applications
__History and Additional Materials

Chapter 12.
Quantum information theory
__12.1 Quantum State Distinction and Accessible Information
__12.1.1 Holebo boundary
__12.1.2 Example of application of the Holebo boundary
__12.2 Data Compression
__12.2.1 Shannon's Noise-Free Channel Coding Summary
__12.2.2 Schumacher's quantum noiseless channel coding theorem
__12.3 Classical Information in Noisy Quantum Channels
__12.3.1 Communication in Noisy Classical Channels
__12.3.2 Communication via Noisy Quantum Channels
__12.4 Quantum Information in Noisy Quantum Channels
__12.4.1 Entropy Exchange and Quantum Fano Inequality
__12.4.2 Quantum Data Processing Inequalities
__12.4.3 Quantum Singleton Boundary
__12.4.4 Quantum Error Correction, Refrigeration, and Maxwell's Goblin
__12.5 Entanglement as a Physical Resource
__12.5.1 Transformation of Bipartite Pure State Entanglement
__12.5.2 Entanglement Distillation and Entanglement Dilution
__12.5.3 Entanglement Distillation and Quantum Error Correction
__12.6 Quantum Cryptography
__12.6.1 Private Key Cryptography
__12.6.2 Confidentiality Amplification and Information Coordination
__12.6.3 Quantum Key Distribution
__12.6.4 Confidentiality and Coherence Information
__12.6.5 Quantum Key Distribution Security
__History and Additional Materials

Appendix A1.
Notes on basic probability theory
Appendix A2.
Group theory
Appendix A3.
Solovey-Kitayev theorem
Appendix A4.
number theory
Appendix A5.
Public key cryptography and RSA encryption system
Appendix A6.
Proof of Reeve's theorem

◈ Structure of this book ◈

We will first look at quantum computation before quantum information, introducing specific details and then explaining more general information.
We first discuss specific quantum error correction codes and then explain more general results of quantum information theory.
And throughout the book, I will first introduce examples and then attempt to develop the general theory.

Part 1 provides a general overview of the key ideas and results in quantum computing and quantum information, and then moves on to the background knowledge in computer science, mathematics, and physics necessary for a deep understanding of quantum computing and quantum information.
Chapter 1 is an introductory chapter that examines the historical development and fundamental concepts of this field and addresses major unresolved issues.
The knowledge here is structured so that it can be understood even without a background in computer science or physics.
More detailed background information is covered in Chapters 2 and 3, which provide an in-depth explanation of the fundamental concepts of quantum mechanics and computer science.
Depending on your level of knowledge, you can focus on each chapter of Part 1, or you can revisit Chapters 1 through 3 later if you feel you have any gaps in your basic knowledge of quantum mechanics and computer science.

Part 2 explains quantum computing in detail.
Chapter 4 describes the fundamental elements required to perform quantum computation and presents many basic operations that can be used to develop more sophisticated quantum computational applications.

Chapters 5 and 6 describe the two currently known fundamental algorithms: the quantum Fourier transform and the quantum search algorithm.
Chapter 5 also explains how the quantum Fourier transform can be used to solve factorization and discrete logarithm problems, and the importance of these results to cryptography.

Chapter 7 describes general design principles and criteria for physical implementations of quantum computers, using several successfully demonstrated realizations in the laboratory.


Part 3 is about quantum information.
It covers what quantum information is, how information is represented and transmitted using quantum states, and how to describe and handle corruption of quantum and classical information.

Chapter 8 describes the properties of quantum noise, which are essential for understanding realistic quantum information processing, and the quantum computational formalism, which is a powerful mathematical tool for understanding quantum noise.

Chapter 9 describes distance measures for quantum information, which provide quantitative precision on what it means to say that two items of quantum information are similar.

Chapter 10 describes quantum error correction codes, which can be used to protect quantum computations from noise effects.
A key achievement of Chapter 10 is the threshold theorem, which shows that for realistic noise models, noise does not, in principle, significantly interfere with quantum computation.

Chapter 11 introduces the basic information theory concept of entropy and explains many properties of entropy in both classical and quantum information theory.

Finally, Chapter 12 discusses the information transfer properties of quantum states and quantum communication channels, detailing the strange and interesting properties that systems can possess when transmitting classical and quantum information, as well as when transmitting secret information.

It contains many verification and practice problems.
The verification questions help you understand basic knowledge and appear in the text.
It can be solved in a short period of time.
Practice problems appear at the end of each chapter and introduce new and interesting knowledge not fully covered in the text.
Practice problems are often divided into several parts and require some depth of thinking.
Some issues were unresolved at the time this book was published.
I have mentioned this issue.


Appendix 1 covers basic definitions, notation, and basic probability theory results.
The material here will be familiar to the reader and is intended for easy reference.

Likewise, Appendix 2 is included mainly for convenience in learning the basic concepts of group theory.


Appendix 3 contains a proof of the Solovay-Kitaev theorem, an important result in quantum computing. This proof shows that any quantum gate can be quickly approximated using a finite set of quantum gates.


Appendix 4 covers the fundamentals of number theory necessary to understand quantum algorithms for factoring and discrete logarithms, as well as the RSA cryptosystem, and Appendix 5 examines the cryptosystem itself.


In Appendix 6, we explore Lieb's theorem, which is one of the most important results in quantum computation and quantum information and was the forerunner of important entropy inequalities such as the famous strong subadditivity inequality.
The proofs of the Solovey-Kitaev and Reeve theorems are so long that I felt it would be better to treat them separately from the main text.

◈ Author's Note ◈

This book introduces key ideas and techniques in the fields of quantum computing and quantum information.
Because this field is rapidly evolving and involves multiple disciplines, it can be difficult for beginners to grasp the overall outline of the key technologies and outcomes in this field.
Therefore, the purpose of this book is twofold.
First, we introduce the background knowledge of computer science, mathematics, and physics necessary to understand quantum computing and quantum information.
It is written at a level that is accessible to readers with a background in one or more of the three fields, including first-year graduate students and beyond.
The most important thing is to be proficient in mathematics and willing to learn about quantum computing and quantum information.

A second purpose of this book is to develop in detail key results in quantum computation and quantum information.
Readers should develop a working knowledge of the fundamental tools and results of this exciting field through thorough study, either as part of a general education or in preparation for independent research in quantum computation and quantum information.

◈ Translator's Note ◈

This book was first published in 2000 and reissued as a 10th anniversary edition in 2010.
Now, 22 years after its publication, this translated version is presented to domestic readers.
If 22 years have passed, it is enough to feel outdated in today's world where new information and new technologies are pouring in every day.
However, this book is still considered the bible of quantum computing and quantum information.
To understand why the value of this book has not diminished despite the passage of time, we need to examine the circumstances of its publication.


If quantum mechanics had a turbulent period in the 1920s and 1930s, quantum computing experienced its turbulent period in the 1990s.
In 1993, Dr. Charles Bennett's group working at IBM theoretically established the concept of quantum teleportation using entanglement.
In 1994, Dr. Peter Shor announced the 'Shor algorithm', which had a great impact on society.
It was a major incident that showed that the RSA encryption system we currently use is by no means secure.
In the same year, Dr. Shor also discovered that error correction in quantum computing is possible by using entangled states through an error syndrome measurement method.


In 1996, Rob Grover, a researcher at Bell Labs, announced the 'Grover Algorithm', which significantly reduced the time for search problems and gave confidence that quantum computers could surpass classical computers.
In 1997, Professor Zeilinger's group at the University of Innsbruck experimentally implemented the concept of quantum teleportation, which had been theoretically proposed four years earlier.
Since this book was written during such a turbulent time, it can be seen as containing vivid knowledge up to that time.
Current quantum computing technology builds on that knowledge.
Therefore, even though time has passed, this book is not outdated, but rather serves as a basic guide to understanding current technology.

In November 2021, an article appeared online claiming that IBM had set a new milestone in quantum computing by developing a 127-qubit 'Eagle' CPU.
Of course, this number of qubits is only the number of physical qubits, not the number of logical qubits, so the actual amount of information processing is greatly reduced.
For example, if 9 qubits are used for error correction when processing information of 1 qubit, even if it is a 127-qubit quantum computer, the actual information processing capacity will be roughly equivalent to that of a 12-qubit quantum computer.
This means that performance may be much lower than expected, as more qubits need to be allocated to error correction when noise is high or to achieve greater accuracy.
This shows that there is great room for improvement in the future, and its potential for development is limitless.
I am very pleased to be able to translate this masterpiece on quantum computing at this time.


This translation, which commemorates the 22nd anniversary of the publication in Korean, incorporates all the corrections to errors reported in the original text.
Since readers of this book will most likely refer to the original English text or paper, the translated terms are those that can be easily inferred from the English text or are identical to the original English text, and the corresponding textbook terms are added in the footnotes.
For example, information theory textbooks translate code and encoding as 'sign' and 'encoding', but this book uses the original terms 'coding' and 'encoding'.
The "History and Additional Resources" section of each chapter systematically organizes reference materials along with the history, which I believe will make readers feel like they have found a treasure.
The translator feels happy just with the 'History and Additional Materials' section.


I sincerely hope that readers will use this book as a foundation to contribute significantly to the development of quantum computing in our country.