“I think I can safely say that no one understands quantum mechanics.” – Richard Feynman
The topic of quantum computing has always attracted technical writers and journalists. Its potential in the field of computing and complexity gave it a certain mystical halo. All too often, feature articles and infographics describe in detail the various perspectives of this industry, while barely touching on its practical applications: this can mislead the not too attentive reader.
Popular science articles omit descriptions of quantum systems and make statements like:
A normal bit can be either 1 or 0, but a qubit can be both 1 and 0 at the same time.
If you're very lucky (which I'm not sure about), you'll be told that:
The qubit is in superposition between "1" and "0".
None of these explanations seem plausible, since we are trying to formulate a quantum mechanical phenomenon using language tools created in a very traditional world. To understand the principles of quantum computing, it is necessary to use a different language - mathematical.
In this tutorial, I'll cover the mathematical tools needed to model and understand quantum computing systems, and how to illustrate and apply quantum computing logic. Moreover, I will give an example of a quantum algorithm and tell you what is its advantage over a traditional computer.
I will do my best to tell about all this in an understandable language, but still I hope that the readers of this article have a basic understanding of linear algebra and digital logic (linear algebra is described , about digital logic - ).
First, let's go over the principles of digital logic. It is based on the use of electrical circuits to carry out calculations. To make our description more abstract, let's simplify the state of the electrical wire to "1" or "0", which will correspond to the states "on" or "off". By arranging the transistors in a certain sequence, we will create so-called logic elements that take one or more input signal values and convert them into an output signal based on certain rules of Boolean logic.
Common logic elements and their state tables
On the basis of chains of such basic elements, more complex elements can be created, and on the basis of chains of more complex elements, we can ultimately, with a large degree of abstraction, expect to obtain an analogue of the central processor.
As I mentioned earlier, we need a way to represent digital logic mathematically. First, let's imagine mathematical conventional logic. Using linear algebra, classical bits with values "1" and "0" can be represented as two column vectors:
where the numbers on the left are vector. By representing our bits in this way, we can model logical operations on bits using vector transformations. Please note: despite the fact that when using two bits in logical elements, you can perform many operations ("AND" (AND), "Not" (NOT), "Excl. Or" (XOR), etc.), when using one bit, only four operations are possible: identical transformation, negation, calculation of the constant "0" and calculation of the constant "1". With identical conversion, the bit remains unchanged, with negation, the value of the bit is reversed (from "0" to "1" or from "1" to "0"), and the calculation of the constant "1" or "0" sets the bit to "1" or "0" regardless of its previous value.
| Identity | Identity transformation |
| the Negation | Denial |
| Constant-0 | Calculation of the constant "0" |
| Constant-1 | Calculation of the constant "1" |
Based on our new representation of a bit, it is quite easy to perform operations on the corresponding bit using a vector transformation:
Before moving on, let's look at the concept , which simply implies that in order to ensure the reversibility of an operation or a logic element, it is necessary to determine a list of input signal values based on the output signals and the names of the operations used. Thus, we can conclude that the identity transformation and negation are reversible, but the operations for calculating the constants "1" and "0" are not. Thanks to quantum mechanics, quantum computers use exclusively reversible operations, so we will focus on them. Next, we transform the irreversible elements into reversible ones to make them usable by a quantum computer.
With individual bits can be represented by a set of bits:
Now that we have almost all the necessary mathematical representations, let's move on to our first quantum gate. This is the operator , or Controlled Not (NOT), which is of great importance in reversible and quantum computing. The CNOT element is applied to two bits and returns two bits. The first bit is assigned to "control", and the second - "control". If the control bit is set to "1", the control bit changes its value; if the control bit is set to "0", the control bit is not changed.
This operator can be represented as the following transformation vector:
To demonstrate everything that we have already dealt with, I will show the use of the CNOT element in relation to a set of bits:
To summarize what has already been said: in the first example, we decompose |10⟩ into parts of its tensor product and use the CNOT matrix to obtain a new corresponding state of the product; then we factorize it up to |11⟩ according to the table of CNOT values given earlier.
So, we remembered all the mathematical rules that will help us deal with traditional computing and ordinary bits, and finally we can move on to modern quantum computing and qubits.
If you've read this far, I have good news for you: qubits can be easily expressed mathematically. In general, if the classical bit (cbit) can be set to |1⟩ or |0⟩, the qubit is simply in superposition and can be both |0⟩ and |1⟩ at the same time before measurement. After measurement, it collapses into |0⟩ or |1⟩. In other words, a qubit can be represented as a linear combination of |0⟩ and |1⟩ according to the formula below:
where a₀ и a₁ represent, respectively, the amplitudes |0⟩ and |1⟩. They can be thought of as "quantum probabilities" that represent the probability of a qubit collapsing into one of the states after it has been measured, since in quantum mechanics an object in a superposition collapses into one of the states after being fixed. Let's expand this expression and get the following:
To simplify my explanation, this is the representation I will use in this article.
For this qubit, the chance of collapsing into a value a₀ after measurement is equal to |a₀|², and the chance of collapsing into a value a₁ equals |a₁|². For example, for the following qubit:
the chance of collapsing into "1" is |1/ √2|², or ½, that is 50/50.
Since in the classical system all probabilities must add up to one (for a complete probability distribution), we can conclude that the squares of the absolute values of the amplitudes |0⟩ and |1⟩ must add up to one. Based on this information, we can write the following equation:
If you are familiar with trigonometry, you will notice that this equation corresponds to the Pythagorean theorem (a² + b² = c²), that is, we can graphically represent the possible states of a qubit as points on a unit circle, namely:
Logical operators and elements are applied to qubits in the same way as in the case of classical bits - based on matrix transformation. All the reversible matrix operators that we have remembered so far, in particular CNOT, can be used to work with qubits. Such matrix operators make it possible to use each of the qubit amplitudes without measuring and collapsing it. Let me give you an example of using the negation operator on a qubit:
Before we continue, I will remind you that the values of the amplitudes a₀ and a₁ are actually , so the state of the qubit can most accurately be displayed on the XNUMXD unit sphere, also known as :
However, to simplify the explanation, we will limit ourselves here to real numbers.
It seems the time has come to discuss some logic gates that only make sense in the context of quantum computing.
One of the most important operators is the "Hadamard element": it takes a bit in the state "0" or "1" and puts it in the appropriate superposition with a 50% chance of it collapsing into "1" or "0" after measurement.
Note that there is a negative number at the bottom right of the Hadamard operator. This is due to the fact that the result of applying the operator depends on the value of the input signal: — |1⟩ or |0⟩, and therefore the calculation is reversible.
Another important point related to the Hadamard element is its reversibility, i.e. it can take a qubit in the appropriate superposition and transform it into |0⟩ or |1⟩.
This is very important, because it gives us the ability to transform from a quantum state without determining the state of the qubit - and, accordingly, without its collapse. Thus, we can structure quantum computing on the basis of a deterministic rather than a probabilistic principle.
Quantum operators containing only real numbers are their own opposite, so we can represent the result of applying the operator to a qubit as a transformation within the unit circle in the form of a state machine:
Thus, the qubit, the state of which is presented in the diagram above, after applying the Hadamard operation, is transformed into the state indicated by the corresponding arrow. Similarly, we can construct another state machine that will illustrate the transformation of a qubit using the negation operator as shown above (also known as the Pauli negation operator, or bit inversion), as shown below:
To perform more complex operations on our qubit, we can chain multiple operators or apply elements multiple times. An example of a serial transformation based on as follows:
That is, if we start at bit |0⟩, apply a bit inversion, and then a Hadamard operation, then another bit inversion, and another Hadamard operation, after which a final bit inversion, we end up with a vector reduced to on the right side of the chain. By layering different state machines on top of each other, we can start at |0⟩ and keep track of the colored arrows corresponding to each of the transformations to understand how it all works.
Since we have come this far, it is time to consider one of the types of quantum algorithms, namely − , and show its advantage over a classical computer. It is worth noting that the Deutsch-Joji algorithm is completely deterministic, that is, it returns the correct answer 100% of the time (unlike many other quantum algorithms based on the probabilistic determination of qubits).
Let's imagine that you have a black box that contains a function / operator on one bit (remember - using one bit can only perform four operations: identity transformation, negation, calculation of the constant "0" and calculation of the constant "1"). What exactly is the function of the box? You don't know which one, but you can iterate over as many input values as you like and evaluate the output results.
How many inputs and outputs will have to be run through the black box to find out which function is being used? Think about it for a second.
In the case of a classical computer, 2 queries would be required to determine which function to use. For example, if when we enter "1" we get "0" as the output, it becomes clear that either the function for calculating the constant "0" or the negation function is used, after which you will have to change the value of the input signal to "0" and see what happens at the exit.
In the case of a quantum computer, two queries would also be required, since you still need two different output values to accurately determine the function to apply to the input value. However, if you slightly reformulate the question, it turns out that quantum computers still have a serious advantage: if you wanted to know whether the applied function is constant or variable, the advantage would be on the side of quantum computers.
A boxed function is variable if different values of the input signal produce different results at the output (for example, identical conversion and bit inversion), and if the output value does not change regardless of the input value, then the function is constant (for example, calculating a constant "1" or calculation of the constant "0").
Using a quantum algorithm, you can determine whether a function in a black box is a constant or a variable based on just one query. But before we look at how to do this in detail, we need to find a way to structure each of these functions on a quantum computer. Since any quantum operators must be reversible, we immediately run into a problem: the functions for calculating the constants "1" and "0" are not.
In quantum computing, the following solution is often used: an additional output qubit is added, which returns any value of the input signal received by the function.
| To: | After: |
|
|
|
Thus, we can determine the input values solely on the basis of the output value, and the function becomes invertible. The structure of quantum circuits creates the need for an extra input bit. For the sake of developing the corresponding operators, let's assume that the additional input qubit is set to |0⟩.
Applying the same representation of a quantum circuit that we used earlier, let's see how each of the four elements (identity transformation, negation, calculation of the constant "0", and calculation of the constant "1") can be implemented using quantum operators.
For example, this is how you can implement the function of calculating the constant "0":
Calculation of the constant "0":
Here we don't need operators at all. The first input qubit (which we took to be |0⟩) is returned with the same value, and the second input value returns itself, as usual.
With the function of calculating the constant "1", the situation is a little different:
Calculation of the constant "1":
Since we have assumed that the first input qubit is always set to |0⟩, it always produces a one as the result of applying the bit-reversal operator. And as usual, the second qubit gives its own value at the output.
When mapping the identity transformation operator, the problem becomes more complicated. Here's how to do it:
Identity transformation:
The symbol used here denotes the CNOT element: the top line indicates the control bit, and the bottom line indicates the control bit. Recall that when using the CNOT operator, the value of the control bit changes if the control bit is |1⟩, but remains unchanged if the control bit is |0⟩. Since we assumed that the value of the top line is always |0⟩, its value is always assigned to the bottom line.
Similarly, we act with the negation operator:
Negation:
We simply invert the bit at the end of the output line.
Now that we've got the preview out of the way, let's look at the specific advantages of a quantum computing machine over a traditional computer when it comes to determining whether a function hidden in a black box is constant or variable using only one query.
To solve this problem using quantum computing in a single request, it is necessary to transform the input qubits into a superposition before passing them to the function, as shown below:
The Hadamard element is reapplied to the result of using the function to bring the qubits out of superposition and make the algorithm deterministic. We start the system in state |00⟩ and, for reasons I'll explain in a moment, we get the result |11⟩ if the applied function is constant. If the function inside the black box is a variable, then after the measurement the system returns the result |01⟩.
To deal with the rest of the article, let's turn to the illustration I showed earlier:
By using the bit inversion operator and then applying the Hadamard element to both input values equal to |0⟩, we ensure that they are translated into the same superposition of |0⟩ and |1⟩, namely:
Using the example of passing this value to a function in a black box, it is easy to demonstrate that both functions of a constant value give |11⟩ at the output.
Calculation of the constant "0":
Similarly, we can see that the function for calculating the constant "1" also produces |11⟩ as output, i.e.:
Calculation of the constant "1":
Note that both values will be |1⟩ in the output because -1² = 1.
By the same principle, it can be proved that when using both variable functions, we will always get |01⟩ as an output (assuming the same method is used), although everything is a little more complicated here.
Identity transformation:
Since CNOT is a two-qubit operator, it cannot be represented as a simple state machine, and therefore two output signals must be determined based on the tensor product of both input qubits and multiplication by the CNOT matrix as described earlier:
With this method, we can also confirm that the output is |01⟩ if the negation function is hidden in the black box:
Negation:
Thus, we have just demonstrated a situation in which a quantum computer is unambiguously more efficient than a conventional computer.
What next?
I propose to end here. We did a great job as it is. If you understood everything that I have said, I think now you have a good understanding of the basics of quantum computing and quantum logic, and also understand why quantum algorithms can be more effective than traditional means of calculation in certain situations.
My description can hardly be called a full-fledged guide to quantum computing and algorithms - it is rather a brief introduction to mathematics and notation, designed to dispel readers' ideas about the subject imposed by popular science sources (seriously, many people really cannot understand the situation!). I did not have time to touch on many important topics - for example, such as , the complexity of the amplitude values |0⟩ and |1⟩, and the functioning of various quantum logic elements under transformation by the Bloch sphere.
If you want to systematize and structure your knowledge about quantum computers, strongly I recommend you read Emma Strubel: Despite the abundance of mathematical formulas, this book covers quantum algorithms in much more detail.
Source: habr.com