November 27, 2017 at 17:26Quantum computing versus classical: why do we need so many numbers
Due to the general boom of the blockchain and all bigdates, another promising topic has left the first lines of technological news - quantum computing. And they, by the way, are able to turn over several IT areas at once, starting with the notorious blockchain and ending with information security. In the next two articles, Sberbank and Sberbank Technologies will tell you why quantum computing is cool and what they are doing now.
To deal with quantum computing, it’s worth first to refresh the knowledge of the classical ones. Here, the unit of information being processed is a bit. Each bit can be in only one of two possible states - 0 or 1. A register of N bits can contain one of 2 N possible combinations of states and is represented as a sequence of them.
For processing and converting information, bitwise operations that come from Boolean algebra are used. The main operations are single-bit NOT and two-bit AND and OR. Bitwise operations are described through truth tables. They show the correspondence of input arguments to the obtained value.
Classical computing algorithm is a set of sequential bit operations. It is most convenient to reproduce it graphically, in the form of a diagram of functional elements (SFE), where each operation has its own designation. Here is an example of SFE for checking two bits for equivalence.
Now move on to a new topic. Quantum computing is an alternative to classical algorithms based on the processes of quantum physics. It says that without interacting with other particles (that is, until the moment of measurement), the electron does not have unambiguous coordinates in the orbit of the atom, and at the same time it is at all points of the orbit. The region in which the electron is located is called the electron cloud. In the course of a well-known experiment with two slits, one electron passes simultaneously through both slits, while interfering with itself. Only during measurement does this uncertainty collapse and the coordinates of the electron become unambiguous.
The probabilistic nature of measurements inherent in quantum computing underlies many algorithms - for example, searching in an unstructured database. Algorithms of this type incrementally increase the amplitude of the correct result, allowing you to get it at the output with maximum probability.
In quantum computing, the physical properties of quantum objects are implemented in so-called qubits (q-bit). The classic bit can be in only one state - 0 or 1. Before the measurement, the qubit can be in both states simultaneously, therefore it is customary to denote it by the expression a | 0⟩ + b | 1⟩, where A and B are complex numbers satisfying the condition | A | 2 + | B | 2 = 1. The measurement of a qubit instantly “collapses” its state into one of the basic ones - 0 or 1. In this case, the “cloud” collapses to a point, the initial state is destroyed, and all information about it is irretrievably lost.
One application of this property is theSchrödinger cattrue random number generator. The qubit is introduced into a state in which the measurement result can be 1 or 0 with the same probability. This condition is described as follows:
Let's start with the basics. There is a set of initial data for calculations represented in binary format by vectors of length N.
In classical calculations, only one of 2 n data variants is loaded into the computer memory and for this variant the function value is calculated. As a result, only one of 2 n possible data sets is simultaneously processed .
In the memory of a quantum computer, all 2 n combinations of source data are simultaneously presented . Transforms apply to all of these combinations at once. As a result, in one operation, we calculate the function for all 2 npossible options for the data set (the measurement in the end will still give only one solution, but more on that later).
Both classical and quantum computing use logical transformations - gates . In classical calculations, the input and output values are stored in different bits, which means that in gates the number of inputs may differ from the number of outputs:
Consider the real problem. It is necessary to determine if two bits are equivalent.
If we get one at the classical calculations at the output, then they are equivalent, otherwise not:
Now we will represent this problem with the help of quantum calculations. In them, all transform gates have as many outputs as inputs. This is due to the fact that the result of the conversion is not a new value, but a change in the current state.
In the example, we compare the values of the first and second qubits. The result will be in the zero qubit - the qubit flag. This algorithm is applicable only to the base states - 0 or 1. Here is the order of quantum transformations.
Let's try to compare classical and quantum computing in more serious problems. To do this, we need some more theoretical knowledge.
In quantum computing, the processed information is encoded in quantum bits - the so-called qubits. In the simplest case, a qubit, like a classical bit, can be in one of two basic states: | 0⟩ (short notation for vector 1 | 0⟩ + 0 | 1⟩) and | 1⟩ (for vector 0 | 0⟩ + 1 | 1⟩). A quantum register is a tensor product of qubit vectors. In the simplest case, when each qubit is in one of the basis states, the quantum register is equivalent to the classical one. The register of two qubits in the state | 0> can be written in the following form:
(1 | 0⟩ + 0 | 1⟩) * (1 | 0⟩ + 0 | 1⟩) = 1 | 00⟩ + 0 | 01 ⟩ + 0 | 10⟩ + 0 | 11⟩ = | 00⟩.
To process and transform information in quantum algorithms, the so-called quantum gates (gates) are used. They are presented in the form of a matrix. To get the result of applying the gate, we need to multiply the vector characterizing the qubit by the matrix of the gate. The first coordinate of the vector is the factor in front of | 0⟩, the second coordinate is the factor in front of | 1⟩. The matrix of the main one-qubit gates looks like this:
But the example of the application of the gate Not:
X * | 0⟩ = X * (1 | 0⟩ + 0 | 1⟩) = 0 | 0⟩ + 1 | 1⟩ = | 1⟩
The factors in front of the basic states are called amplitudes and are complex numbers. The modulus of a complex number is equal to the root of the sum of the squares of the real and imaginary parts. The square of the amplitude modulus in front of the base state is equal to the probability of getting this basic state when measuring qubit, so the sum of the squares of the amplitude moduli is always 1. We could use arbitrary matrices for transformations over qubits, but because the norm (length) vector must always be equal to 1 (the sum of the probabilities of all outcomes is always equal to 1), our transformation must preserve the norm of the vector. This means that the transformation must be unitary and the corresponding matrix is unitary. Recall that the unitary transformation is reversible and UU † = I.
For more visual work with qubits, they are represented by vectors on the Bloch sphere. In this interpretation, single-qubit gates represent the rotation of the qubit vector around one of the axes. For example, the gate Not (X) rotates the qubit vector by Pi relative to the X axis. Thus, the state | 0>, represented by a vector directed strictly up, goes into the state | 1>, directed strictly down. The state of a qubit on the Bloch sphere is determined by the formula cos (θ / 2) | 0⟩ + e iϕ sin (θ / 2) | 1⟩
To build algorithms, only single-qubit gates are not enough for us. Gates are needed that perform transformations depending on certain conditions. The main tool is the CNOT two-qubit gate. This gate applies to two qubits and inverts the second qubit only if the first qubit is in the state | 1 состоянии. The CNOT gate matrix looks like this:
But an application example:
CNOT * | 10⟩ = CNOT * (0 | 00⟩ + 0 | 01⟩ + 1 | 10⟩ + 0 | 11⟩) = 0 | 00⟩ + 0 | 01⟩ + 1 | 11⟩ + 0 | 10⟩ = | 11⟩
Using the CNOT gate is equivalent to performing the classic XOR operation with writing the result to the second qubit. Indeed, if you look at the truth table of the XOR and CNOT operator, we will see the correspondence:
The CNOT gate has an interesting property - after its application, the qubits become entangled or untangled, depending on the initial state. This will be shown in the next article, in the section on quantum parallelism.
Having a full arsenal of quantum gates, we can begin to develop quantum algorithms. In a graphical representation, qubits are represented by straight lines - “strings” on which gates are superimposed. Pauli single-quart gates are indicated by ordinary squares, inside of which the axis of rotation is represented. The CNOT gate looks a bit more complicated: CNOT Gate
Application Example:
One of the most important actions in the algorithm is to measure the result. The measurement is usually indicated by an arc scale with an arrow and a designation about which axis the measurement is going.
So, let's try to build a classical and quantum algorithm that adds 3 to the argument.
The summation of ordinary numbers by a column implies the performance of two actions on each digit - the sum of the digits themselves and the sum of the result with the transfer from the previous operation, if there was such a transfer.
In the binary representation of numbers, the summation operation will consist of the same actions. Here is the python code:
Now let's try to develop a similar program for a quantum computer:
In this scheme, the first two qubits are an argument, the next two are hyphenations, the remaining 3 are the result. This is how the algorithm works.
By running both examples, we get the same result. On a quantum computer, this will take longer because it is necessary to conduct additional compilation into quantum-assembler code and send it for execution to the cloud. The use of quantum computing would make sense if the speed of performing their elementary operations - gates - would be many times lower than in the classical model.
The measurements of specialists show that the execution of one gate takes about 1 nanosecond. So, the algorithms for a quantum computer should not copy the classical ones, but use the unique properties of quantum mechanics to the maximum. In the next article, we will analyze one of the main such properties - quantum parallelism - and talk about quantum optimization in general. Then, we determine the most suitable spheres for quantum computing and talk about their application.
Based on the materials of Dmitry Sapaev , senior manager of IT systems development at the SEC development department of Sberbank Technologies, and Dmitry Bulychkov, project director at the Sberbank Technology Innovation Center.
UPD : We published the second part of the article, where we dive deeper into quantum computing and talk about their practical application.
Classical calculations: AND, OR, NOT
To deal with quantum computing, it’s worth first to refresh the knowledge of the classical ones. Here, the unit of information being processed is a bit. Each bit can be in only one of two possible states - 0 or 1. A register of N bits can contain one of 2 N possible combinations of states and is represented as a sequence of them.
For processing and converting information, bitwise operations that come from Boolean algebra are used. The main operations are single-bit NOT and two-bit AND and OR. Bitwise operations are described through truth tables. They show the correspondence of input arguments to the obtained value.
Classical computing algorithm is a set of sequential bit operations. It is most convenient to reproduce it graphically, in the form of a diagram of functional elements (SFE), where each operation has its own designation. Here is an example of SFE for checking two bits for equivalence.
Quantum computing. Physical basis
Now move on to a new topic. Quantum computing is an alternative to classical algorithms based on the processes of quantum physics. It says that without interacting with other particles (that is, until the moment of measurement), the electron does not have unambiguous coordinates in the orbit of the atom, and at the same time it is at all points of the orbit. The region in which the electron is located is called the electron cloud. In the course of a well-known experiment with two slits, one electron passes simultaneously through both slits, while interfering with itself. Only during measurement does this uncertainty collapse and the coordinates of the electron become unambiguous.
The probabilistic nature of measurements inherent in quantum computing underlies many algorithms - for example, searching in an unstructured database. Algorithms of this type incrementally increase the amplitude of the correct result, allowing you to get it at the output with maximum probability.
Qubits
In quantum computing, the physical properties of quantum objects are implemented in so-called qubits (q-bit). The classic bit can be in only one state - 0 or 1. Before the measurement, the qubit can be in both states simultaneously, therefore it is customary to denote it by the expression a | 0⟩ + b | 1⟩, where A and B are complex numbers satisfying the condition | A | 2 + | B | 2 = 1. The measurement of a qubit instantly “collapses” its state into one of the basic ones - 0 or 1. In this case, the “cloud” collapses to a point, the initial state is destroyed, and all information about it is irretrievably lost.
One application of this property is the
Quantum and classical calculations. First round
Let's start with the basics. There is a set of initial data for calculations represented in binary format by vectors of length N.
In classical calculations, only one of 2 n data variants is loaded into the computer memory and for this variant the function value is calculated. As a result, only one of 2 n possible data sets is simultaneously processed .
In the memory of a quantum computer, all 2 n combinations of source data are simultaneously presented . Transforms apply to all of these combinations at once. As a result, in one operation, we calculate the function for all 2 npossible options for the data set (the measurement in the end will still give only one solution, but more on that later).
Both classical and quantum computing use logical transformations - gates . In classical calculations, the input and output values are stored in different bits, which means that in gates the number of inputs may differ from the number of outputs:
Consider the real problem. It is necessary to determine if two bits are equivalent.
If we get one at the classical calculations at the output, then they are equivalent, otherwise not:
Now we will represent this problem with the help of quantum calculations. In them, all transform gates have as many outputs as inputs. This is due to the fact that the result of the conversion is not a new value, but a change in the current state.
In the example, we compare the values of the first and second qubits. The result will be in the zero qubit - the qubit flag. This algorithm is applicable only to the base states - 0 or 1. Here is the order of quantum transformations.
- We act on the qubit flag with the “Not” gate, exposing it to 1.
- We use the two-qubit gate “Controlled Not” twice. This gate changes the value of the flag qubit to the opposite only if the second qubit participating in the transformation is in state 1.
- We measure the zero qubit. If you get 1 as a result, then the first and second qubits are either both in state 1 (the qubit flag twice changed its value) or in state 0 (the qubit flag has remained in state 1). Otherwise, qubits are in different states.
Next level. Pauli's Quantum One-Q Gate
Let's try to compare classical and quantum computing in more serious problems. To do this, we need some more theoretical knowledge.
In quantum computing, the processed information is encoded in quantum bits - the so-called qubits. In the simplest case, a qubit, like a classical bit, can be in one of two basic states: | 0⟩ (short notation for vector 1 | 0⟩ + 0 | 1⟩) and | 1⟩ (for vector 0 | 0⟩ + 1 | 1⟩). A quantum register is a tensor product of qubit vectors. In the simplest case, when each qubit is in one of the basis states, the quantum register is equivalent to the classical one. The register of two qubits in the state | 0> can be written in the following form:
(1 | 0⟩ + 0 | 1⟩) * (1 | 0⟩ + 0 | 1⟩) = 1 | 00⟩ + 0 | 01 ⟩ + 0 | 10⟩ + 0 | 11⟩ = | 00⟩.
To process and transform information in quantum algorithms, the so-called quantum gates (gates) are used. They are presented in the form of a matrix. To get the result of applying the gate, we need to multiply the vector characterizing the qubit by the matrix of the gate. The first coordinate of the vector is the factor in front of | 0⟩, the second coordinate is the factor in front of | 1⟩. The matrix of the main one-qubit gates looks like this:
But the example of the application of the gate Not:
X * | 0⟩ = X * (1 | 0⟩ + 0 | 1⟩) = 0 | 0⟩ + 1 | 1⟩ = | 1⟩
The factors in front of the basic states are called amplitudes and are complex numbers. The modulus of a complex number is equal to the root of the sum of the squares of the real and imaginary parts. The square of the amplitude modulus in front of the base state is equal to the probability of getting this basic state when measuring qubit, so the sum of the squares of the amplitude moduli is always 1. We could use arbitrary matrices for transformations over qubits, but because the norm (length) vector must always be equal to 1 (the sum of the probabilities of all outcomes is always equal to 1), our transformation must preserve the norm of the vector. This means that the transformation must be unitary and the corresponding matrix is unitary. Recall that the unitary transformation is reversible and UU † = I.
For more visual work with qubits, they are represented by vectors on the Bloch sphere. In this interpretation, single-qubit gates represent the rotation of the qubit vector around one of the axes. For example, the gate Not (X) rotates the qubit vector by Pi relative to the X axis. Thus, the state | 0>, represented by a vector directed strictly up, goes into the state | 1>, directed strictly down. The state of a qubit on the Bloch sphere is determined by the formula cos (θ / 2) | 0⟩ + e iϕ sin (θ / 2) | 1⟩
Quantum two qubit gates
To build algorithms, only single-qubit gates are not enough for us. Gates are needed that perform transformations depending on certain conditions. The main tool is the CNOT two-qubit gate. This gate applies to two qubits and inverts the second qubit only if the first qubit is in the state | 1 состоянии. The CNOT gate matrix looks like this:
But an application example:
CNOT * | 10⟩ = CNOT * (0 | 00⟩ + 0 | 01⟩ + 1 | 10⟩ + 0 | 11⟩) = 0 | 00⟩ + 0 | 01⟩ + 1 | 11⟩ + 0 | 10⟩ = | 11⟩
Using the CNOT gate is equivalent to performing the classic XOR operation with writing the result to the second qubit. Indeed, if you look at the truth table of the XOR and CNOT operator, we will see the correspondence:
| Xor | CNOT | |||
| 0 | 0 | 0 | 00 | 00 |
| 0 | 1 | 1 | 01 | 01 |
| 1 | 0 | 1 | 10 | eleven |
| 1 | 1 | 0 | eleven | 10 |
The CNOT gate has an interesting property - after its application, the qubits become entangled or untangled, depending on the initial state. This will be shown in the next article, in the section on quantum parallelism.
Algorithm construction - classical and quantum implementation
Having a full arsenal of quantum gates, we can begin to develop quantum algorithms. In a graphical representation, qubits are represented by straight lines - “strings” on which gates are superimposed. Pauli single-quart gates are indicated by ordinary squares, inside of which the axis of rotation is represented. The CNOT gate looks a bit more complicated: CNOT Gate
Application Example:
One of the most important actions in the algorithm is to measure the result. The measurement is usually indicated by an arc scale with an arrow and a designation about which axis the measurement is going.
So, let's try to build a classical and quantum algorithm that adds 3 to the argument.
The summation of ordinary numbers by a column implies the performance of two actions on each digit - the sum of the digits themselves and the sum of the result with the transfer from the previous operation, if there was such a transfer.
In the binary representation of numbers, the summation operation will consist of the same actions. Here is the python code:
arg = [1,1] #задаем аргумент
result = [0,0,0] #инициализируем результат
carry1 = arg[1] & 0x1 #складываем с 0b11, так что перенос от младшего бита появится в том случае, если у агрумента младший бит = 1
result[2] = arg[1] ^ 0x1 #складываем младшие биты
carry2 = carry1 | arg[0] #складываем с 0b11, так что перенос от старшего бита появится в том случае, если у агрумента старший бит = 1 или был перенос с младшего бита
result[1] = arg[0] ^ 0x1 #складываем старшие биты
result[1] ^= carry1 #применяем перенос с младшего бита
result[0] ^= carry2 #применяем перенос со старшего бита
print(result)Now let's try to develop a similar program for a quantum computer:
In this scheme, the first two qubits are an argument, the next two are hyphenations, the remaining 3 are the result. This is how the algorithm works.
- The first step to the barrier, we put the argument in the same state as in the classical case - 0b11.
- Using the CNOT operator, we calculate the value of the first transfer - the result of the arg & 1 operation is unity only when arg is 1, in this case we invert the second qubit.
- The next 2 gates implement the addition of the least significant bits - we translate qubit 4 into the state | 1⟩ and write the result of XOR into it.
- The large rectangle denotes the CCNOT gate, an extension of the CNOT gate. In this gate, two control qubits and the third are inverted only if the first two are in state | 1. The combination of 2 CNOT gates and one CCNOT gives us the result of the classic operation carry2 = carry1 | arg [0]. The first 2 gates set the carry to one if one of them is 1, and the CCNOT gate handles the case when they are both equal to one.
- Add senior qubits and transfer qubits.
Intermediate conclusions
By running both examples, we get the same result. On a quantum computer, this will take longer because it is necessary to conduct additional compilation into quantum-assembler code and send it for execution to the cloud. The use of quantum computing would make sense if the speed of performing their elementary operations - gates - would be many times lower than in the classical model.
The measurements of specialists show that the execution of one gate takes about 1 nanosecond. So, the algorithms for a quantum computer should not copy the classical ones, but use the unique properties of quantum mechanics to the maximum. In the next article, we will analyze one of the main such properties - quantum parallelism - and talk about quantum optimization in general. Then, we determine the most suitable spheres for quantum computing and talk about their application.
Based on the materials of Dmitry Sapaev , senior manager of IT systems development at the SEC development department of Sberbank Technologies, and Dmitry Bulychkov, project director at the Sberbank Technology Innovation Center.
UPD : We published the second part of the article, where we dive deeper into quantum computing and talk about their practical application.