April 2, 2018 at 10:23Introduction to Quantum Computing
- Transfer
Hello, Habr! Most recently, we told you about quantum computing and the Q # language . Today, we will go into theory even deeper and look at the history of quantum computing. In addition, in this article you will find 5 requirements for a quantum computer. What properties should a machine of the future have? Read under the cut!
As you know, the idea of quantum computing was introduced by Richard Feynman in 1981 during a report at the first conference “Physics of Computing” ( Feynman, 1982 - recommended for familiarization). During the report, Feynman considered a number of difficulties associated with modeling complex quantum systems using classical computers and put forward the following assumption: in order to reliably model quantum systems, it is necessary to strive to create quantum computers.
Since then, the field of quantum computing has developed very dynamically. Now we have come close to the true physical implementation of a scalable quantum computer (more on this in the following publications).
The most fundamental difference between a classical computer and a quantum one is the implementation of a bit. Bit (born bit, short for "binary digit" - binary number) - the smallest unit of digital data. A classical bit at any given moment in time can take only one of two values: 0 or 1. A quantum bit (qubit) obeys the laws of quantum mechanics and therefore can be in a superposition of states 0 and 1.
These classical states 0 and 1 correspond to the notation Dirac | 0 > and | 1>, and the formula of the qubit state is as follows:
.
Here
are the complex-valued coefficients corresponding to the normalization requirement
(this means that the probability of detecting a qubit in one of these two states is 100%, and the probability of detecting it in some other state is 0%).
Since
, the wave function | ψ〉 can be rewritten as follows:
As it turns out, the global phase
does not affect the results of experiments, and therefore it can be ignored. However, the local phase 
remains, and the wave function takes the following form:
Having written it in this form, we can represent the superposition of the states | 0〉 and | 1〉 in visual form using the Bloch sphere:
Now, any unitary transformation of the wave function | ψ〉 can be represented as a simple displacement of a point (it is denoted as | ψ〉) along the surface of a sphere. For example, the state | ψ〉 = | 0〉 corresponds to a point on the z axis, indicated in the figure as | 0〉. Unfortunately, this visual representation is only suitable for single-qubit states: no generalization has yet been invented for multi-qubit systems. In this series of articles, we will return to the sphere of Bloch.
The phenomena of superposition and entanglement * make it possible to perform certain operations using quantum computers faster than possible (according to modern concepts) using classical computing systems. Examples of such operations are decomposing numbers into prime factors ( Shor, 1997 ) and searching through unstructured data (Grover, 1997 ). Moreover, thanks to these unique quantum-mechanical features, whole new fields of science and technology appear, for example, quantum cryptography ( Bennett & Brassard, 1984 ). In the next section, we will consider the requirements that apply to such systems.
* A superposition is a phenomenon in which the state of a quantum system is described by a probabilistic distribution of possible states of one qubit, for example,
. For a state of entanglement, two or more qubits (or, in a more general case, degrees of freedom) are needed. Einstein described this phenomenon as a “terrible action at a distance” - the interconnection of two particles, in which an operation on one of them can affect the state of the other, regardless of the distance and physical barriers between them (however, the prohibition on transmitting information at a superluminal speed remains valid ) An example of a state of entanglement is Bell's condition:
In 2008, David Divincenzo formulated five conditions (they are a revised version from an article from 1996 ) that a system must meet in order to be considered a scalable quantum computer . We will use these conditions as the basis for further discussions in this series of publications. Below I give their general wording (a detailed discussion is given in the original article).
A quantum computer should allow an increase in the set of qubits to an amount sufficient for complex calculations. “Well described” is a qubit whose properties and interactions with other parts of the system are well known.
By the beginning of the calculations, the system should be in a simple, well-known state. If we do not have the opportunity to re-bring the system to this simple initial state (initialize it), then it cannot be considered a computer at all.
For a number of reasons (for example, due to interaction with external systems), the qubit system is difficult to maintain in a prepared state long enough before it “decodes” due to the manifestation of unwanted interactions between the system and its unknown and uncontrolled environment. After decoherence of a quantum system, the results of measurements of quantum bits (0 and 1) will be described not by a quantum distribution, but by a statistical one. It is impossible to restore the decoded state by any quantum operations. Therefore, the period for which the system goes into a decoherent state should be much longer than the time required to perform operations on the valves.
A universal set of gates is called sufficient to perform any quantum calculation. Here is the minimum required set of operations: moving single qubits to any point on the Bloch sphere (using single-qubit gates) and entangling system components (this requires multi-qubit gates). For example, a universal set includes a Hadamard valve, a phase shift valve, a CNOT valve, and a π⁄8 valve. With their help, you can perform any quantum calculation on an arbitrary set of qubits.
It is necessary to be able to obtain the result of calculations by reading the final state of individual qubits.
There are two additional requirements regarding quantum communication - they relate to the processing of quantum information:
Currently, active work is underway on several physical models of quantum computing: ion traps, photonic qubits, topological qubits, etc. Whatever the basic physical principles, a quantum computer must comply with the five fundamental (and two additional) principles outlined above .
In a future publication, we will look at some of these potential quantum computers, but first you need to get acquainted with quantum gates and circuit diagrams. They will be the subject of my next article. See you next time!
Articles from the cycle:
Introduction
As you know, the idea of quantum computing was introduced by Richard Feynman in 1981 during a report at the first conference “Physics of Computing” ( Feynman, 1982 - recommended for familiarization). During the report, Feynman considered a number of difficulties associated with modeling complex quantum systems using classical computers and put forward the following assumption: in order to reliably model quantum systems, it is necessary to strive to create quantum computers.
Since then, the field of quantum computing has developed very dynamically. Now we have come close to the true physical implementation of a scalable quantum computer (more on this in the following publications).
The most fundamental difference between a classical computer and a quantum one is the implementation of a bit. Bit (born bit, short for "binary digit" - binary number) - the smallest unit of digital data. A classical bit at any given moment in time can take only one of two values: 0 or 1. A quantum bit (qubit) obeys the laws of quantum mechanics and therefore can be in a superposition of states 0 and 1.
These classical states 0 and 1 correspond to the notation Dirac | 0 > and | 1>, and the formula of the qubit state is as follows:
. Here
are the complex-valued coefficients corresponding to the normalization requirement(this means that the probability of detecting a qubit in one of these two states is 100%, and the probability of detecting it in some other state is 0%). Since
, the wave function | ψ〉 can be rewritten as follows: As it turns out, the global phase
does not affect the results of experiments, and therefore it can be ignored. However, the local phase remains, and the wave function takes the following form: Having written it in this form, we can represent the superposition of the states | 0〉 and | 1〉 in visual form using the Bloch sphere:
Now, any unitary transformation of the wave function | ψ〉 can be represented as a simple displacement of a point (it is denoted as | ψ〉) along the surface of a sphere. For example, the state | ψ〉 = | 0〉 corresponds to a point on the z axis, indicated in the figure as | 0〉. Unfortunately, this visual representation is only suitable for single-qubit states: no generalization has yet been invented for multi-qubit systems. In this series of articles, we will return to the sphere of Bloch.
The phenomena of superposition and entanglement * make it possible to perform certain operations using quantum computers faster than possible (according to modern concepts) using classical computing systems. Examples of such operations are decomposing numbers into prime factors ( Shor, 1997 ) and searching through unstructured data (Grover, 1997 ). Moreover, thanks to these unique quantum-mechanical features, whole new fields of science and technology appear, for example, quantum cryptography ( Bennett & Brassard, 1984 ). In the next section, we will consider the requirements that apply to such systems.
* A superposition is a phenomenon in which the state of a quantum system is described by a probabilistic distribution of possible states of one qubit, for example,
. For a state of entanglement, two or more qubits (or, in a more general case, degrees of freedom) are needed. Einstein described this phenomenon as a “terrible action at a distance” - the interconnection of two particles, in which an operation on one of them can affect the state of the other, regardless of the distance and physical barriers between them (however, the prohibition on transmitting information at a superluminal speed remains valid ) An example of a state of entanglement is Bell's condition:Five requirements for a quantum computer (and two additional)
In 2008, David Divincenzo formulated five conditions (they are a revised version from an article from 1996 ) that a system must meet in order to be considered a scalable quantum computer . We will use these conditions as the basis for further discussions in this series of publications. Below I give their general wording (a detailed discussion is given in the original article).
1. The physical system must be scalable, and the state of the qubits must be known
A quantum computer should allow an increase in the set of qubits to an amount sufficient for complex calculations. “Well described” is a qubit whose properties and interactions with other parts of the system are well known.
2. A quantum computer should allow reliable preparation of qubit sets in a simple initial state (for example, | 000 ...〉)
By the beginning of the calculations, the system should be in a simple, well-known state. If we do not have the opportunity to re-bring the system to this simple initial state (initialize it), then it cannot be considered a computer at all.
3. The system must have sufficient durability to perform operations on qubits
For a number of reasons (for example, due to interaction with external systems), the qubit system is difficult to maintain in a prepared state long enough before it “decodes” due to the manifestation of unwanted interactions between the system and its unknown and uncontrolled environment. After decoherence of a quantum system, the results of measurements of quantum bits (0 and 1) will be described not by a quantum distribution, but by a statistical one. It is impossible to restore the decoded state by any quantum operations. Therefore, the period for which the system goes into a decoherent state should be much longer than the time required to perform operations on the valves.
4. The system should allow the implementation of a “universal set” of valves
A universal set of gates is called sufficient to perform any quantum calculation. Here is the minimum required set of operations: moving single qubits to any point on the Bloch sphere (using single-qubit gates) and entangling system components (this requires multi-qubit gates). For example, a universal set includes a Hadamard valve, a phase shift valve, a CNOT valve, and a π⁄8 valve. With their help, you can perform any quantum calculation on an arbitrary set of qubits.
5. The system must support the measurement of individual qubits.
It is necessary to be able to obtain the result of calculations by reading the final state of individual qubits.
There are two additional requirements regarding quantum communication - they relate to the processing of quantum information:
- The system must have the ability to reliably convert data stored in the form of stationary (computing) qubits into network (transmitted) qubits (for example, photons) and vice versa.
- The system must be able to correctly transmit network qubits between endpoints.
Currently, active work is underway on several physical models of quantum computing: ion traps, photonic qubits, topological qubits, etc. Whatever the basic physical principles, a quantum computer must comply with the five fundamental (and two additional) principles outlined above .
In a future publication, we will look at some of these potential quantum computers, but first you need to get acquainted with quantum gates and circuit diagrams. They will be the subject of my next article. See you next time!
Additional Resources
- Author page on GitHub.
- Personal blog of the author.
- Posted on LinkedIn .
- Microsoft Quantum .
- Microsoft Quantum Development Kit .
- Microsoft Quantum blog .
- Telegram channel of Stas Pavlov with news from the world of quantum computers Qubit (Quantum Daily) .
- The next DotNext event (St. Petersburg, April 22-23), speaker Rolf Huisman (Microsoft MVP), report Programming quantum computers in .NET using Microsoft Q # .