Quantum computer
Regarding the recent discussion in the Radio-T podcast and quantum computer comments.
An interesting post with explanations of the principles of a quantum computer was written by LJ user ygam (by the way, a very interesting magazine in itself - I recommend) - it turned out, at least, much clearer than in Wikipedia.
Here is this post:
At the request of the workers, in a nutshell I will try to explain what a quantum computer is. I will try not to require knowledge of any mathematics except complex numbers and linear algebra.
Imagine a steel plate with two slits a meter apart, and a gun that can fire in the direction of the plate so that the bullet passes through one of the slits.
This system is described by two non-negative real numbers, the sum of which is equal to one ā the probability that the bullet will pass through the left slot and through the right slot. We write them in the form of a column vector. The probability that a bullet hits the target behind the screen is equal to the product of a certain string vector and a column vector of probabilities.
')
Now imagine a screen with two micron slits from each other, and a monochrome flash, the rays from which pass through both slits. As light is a wave, we will observe interference behind the screen. In some places, the intensity of the light will be greater than could be predicted from the intensity of light in the slots; constructive interference occurs there; some less; destructive interference occurs there. The simple formula for vector multiplication of intensities does not work with light, like bullets and probabilities. This shows that to describe the system it is not enough to give the light intensity in two slots (i.e. the fraction of the light energy of the flash passing through the screen, which passed through the left slot and through the right slot); amplitudes are needed - complex numbers, the squares of the moduli of which are intensities in two slots. The sum of the squares of their modules must be equal to one, as the sum of the probabilities for the bullet.
Louis de Broglie, Werner Heisenberg and other physicists of the first half of the last century discovered that objects in the material world have properties that are average between particles like bullets and waves like light. If the slotted screen is a nickel crystal lattice, instead of a pistol we have a cathode and electrons instead of bullets, then instead of a column vector of real probabilities, the sum of whose elements is one, we have a column vector of complex amplitudes, the sum of squares of the modules of the elements of which is one. The probability that an electron hits the sensor behind the screen is a complex-conjugate and transposed amplitude vector multiplied by a certain Hermitian matrix, and again multiplied by the amplitude vector itself. This matrix can be diagonal - but in this case, the whole point of using amplitudes instead of probabilities is lost; electrons are like bullets. More interesting is the situation when some off-diagonal elements of the matrix are not zero, and mean interference between possible states (for example, the passage of an electron through the left and through the right slit). Quantum mechanics tells us that, in general, it is non-diagonal, but as we move from the microworld to the macroworld, the noise of interaction with many objects erases elements outside the diagonal, so amplitudes are not needed for bullets, and you can get by with probabilities. This is called decoherence; This is exactly what happens when measuring microscopic quantities with macroscopic instruments.
The question of what this means, how an electron can pass through two slots and simultaneously interfere with itself, has been occupied by physicists and philosophers since quantum mechanics was formulated in the 1930s. Connect to the sensor amplifier, solenoid and a gun aimed at the cat. What is a live or dead cat with a certain probability is understandable; the cat is either alive or dead, we just know it not for sure, but with a certain degree of confidence. But a live or dead cat with a certain complex amplitude goes beyond the real meaning. Science not only has no answer to this question, but this question is beyond the scope of science. Science only knows that we are really dealing with amplitudes, not probabilities.
If the gun shoots through the slits in the plate, it informs the system behind the plate one bit of information - a bullet passed through the left slot or through the right one. If the cathode puts an electron in nickel, it informs the system for the crystal one quantum bit or qubit (qubit) of quantum information ā an electron passes through the left slot or through the right one. Suppose we have a hundred of such cathodes; 2100 ā 1030 initial states have the same amplitudes. Let's subject our system to external influence - magnetic fields, microwaves. Perhaps we will make the āinterestingā states constructively interfere, and the āuninterestingā states will be destructive. Then we measure the state of the system; with high probability it will be āinterestingā. If we can recognize an āinterestingā state, but do not know it, then we will recognize it. We built a quantum computer.
Why do you need a quantum computer? He cannot compute anything that the classical cannot compute, i.e. non-quantum computer. The gods of quantum mechanics multiply matrices; a classic computer does the same thing beautifully. And what can he do? It can use constructive and destructive interference in order to compute in parallel what a classical computer should calculate sequentially.
In 1992, David Deutsch and Richard Yozha invented an algorithm for the Alice and Bob problem from the previous record ā Bob sends all possible positions to Alice and another qubit, Alice performs some manipulations on them and responds, and Bob measures the additional qubit and gets the correct answer. In 1994, Peter Shor from Bell Labs discovered the quantum factor-expansion algorithm for an integer, the running time of which is proportional to the cube of the number of digits of a number; The classical algorithms for this problem are now unknown, the running time of which is proportional to any polynomial based on the number of digits of a number. Shor's algorithm can be generalized to other problems using the concepts of group theory. In 1996, Lov Kumar Grover from there also invented the quantum search algorithm. If among 2n lines of n bits, one satisfies some criterion (for example, it encodes the route of a traveling traveling salesman shorter than 1000 kilometers), then the brute force algorithm on a classical computer requires 2n steps; if we can expose a quantum computer to an effect that changes the sign of the amplitude of the state corresponding to this line and another effect, then after 2n / 2 steps, all states except our destructively interfere; measurement will give us our condition. In the 2000s, they invented a fast quantum algorithm to solve the equation x2 - n * y2 = 1 and several other mathematical problems.
No one has yet been able to build a non-toy quantum computer, and will not be able to in the near future. Using parallel spins of trillions of trillions of nuclei for qubits and nuclear magnetic resonance for measurements, in 2001 researchers from IBM and Stanford executed Shoreās algorithm and factorized the number 15. There are a number of exotic proposals like using two-dimensional quasiparticles that are neither fermions nor bosons, but Something third, with strange topological properties, but to their implementation is also very far. Perhaps even if it is impossible to build a non-toy quantum computer, studying quantum algorithms somehow helped in studying classical algorithms, and thus was not useless, but I am not competent enough to decide whether this is so or not.
An interesting post with explanations of the principles of a quantum computer was written by LJ user ygam (by the way, a very interesting magazine in itself - I recommend) - it turned out, at least, much clearer than in Wikipedia.
Here is this post:
At the request of the workers, in a nutshell I will try to explain what a quantum computer is. I will try not to require knowledge of any mathematics except complex numbers and linear algebra.
Imagine a steel plate with two slits a meter apart, and a gun that can fire in the direction of the plate so that the bullet passes through one of the slits.
This system is described by two non-negative real numbers, the sum of which is equal to one ā the probability that the bullet will pass through the left slot and through the right slot. We write them in the form of a column vector. The probability that a bullet hits the target behind the screen is equal to the product of a certain string vector and a column vector of probabilities.
')
Now imagine a screen with two micron slits from each other, and a monochrome flash, the rays from which pass through both slits. As light is a wave, we will observe interference behind the screen. In some places, the intensity of the light will be greater than could be predicted from the intensity of light in the slots; constructive interference occurs there; some less; destructive interference occurs there. The simple formula for vector multiplication of intensities does not work with light, like bullets and probabilities. This shows that to describe the system it is not enough to give the light intensity in two slots (i.e. the fraction of the light energy of the flash passing through the screen, which passed through the left slot and through the right slot); amplitudes are needed - complex numbers, the squares of the moduli of which are intensities in two slots. The sum of the squares of their modules must be equal to one, as the sum of the probabilities for the bullet.
Louis de Broglie, Werner Heisenberg and other physicists of the first half of the last century discovered that objects in the material world have properties that are average between particles like bullets and waves like light. If the slotted screen is a nickel crystal lattice, instead of a pistol we have a cathode and electrons instead of bullets, then instead of a column vector of real probabilities, the sum of whose elements is one, we have a column vector of complex amplitudes, the sum of squares of the modules of the elements of which is one. The probability that an electron hits the sensor behind the screen is a complex-conjugate and transposed amplitude vector multiplied by a certain Hermitian matrix, and again multiplied by the amplitude vector itself. This matrix can be diagonal - but in this case, the whole point of using amplitudes instead of probabilities is lost; electrons are like bullets. More interesting is the situation when some off-diagonal elements of the matrix are not zero, and mean interference between possible states (for example, the passage of an electron through the left and through the right slit). Quantum mechanics tells us that, in general, it is non-diagonal, but as we move from the microworld to the macroworld, the noise of interaction with many objects erases elements outside the diagonal, so amplitudes are not needed for bullets, and you can get by with probabilities. This is called decoherence; This is exactly what happens when measuring microscopic quantities with macroscopic instruments.
The question of what this means, how an electron can pass through two slots and simultaneously interfere with itself, has been occupied by physicists and philosophers since quantum mechanics was formulated in the 1930s. Connect to the sensor amplifier, solenoid and a gun aimed at the cat. What is a live or dead cat with a certain probability is understandable; the cat is either alive or dead, we just know it not for sure, but with a certain degree of confidence. But a live or dead cat with a certain complex amplitude goes beyond the real meaning. Science not only has no answer to this question, but this question is beyond the scope of science. Science only knows that we are really dealing with amplitudes, not probabilities.
If the gun shoots through the slits in the plate, it informs the system behind the plate one bit of information - a bullet passed through the left slot or through the right one. If the cathode puts an electron in nickel, it informs the system for the crystal one quantum bit or qubit (qubit) of quantum information ā an electron passes through the left slot or through the right one. Suppose we have a hundred of such cathodes; 2100 ā 1030 initial states have the same amplitudes. Let's subject our system to external influence - magnetic fields, microwaves. Perhaps we will make the āinterestingā states constructively interfere, and the āuninterestingā states will be destructive. Then we measure the state of the system; with high probability it will be āinterestingā. If we can recognize an āinterestingā state, but do not know it, then we will recognize it. We built a quantum computer.
Why do you need a quantum computer? He cannot compute anything that the classical cannot compute, i.e. non-quantum computer. The gods of quantum mechanics multiply matrices; a classic computer does the same thing beautifully. And what can he do? It can use constructive and destructive interference in order to compute in parallel what a classical computer should calculate sequentially.
In 1992, David Deutsch and Richard Yozha invented an algorithm for the Alice and Bob problem from the previous record ā Bob sends all possible positions to Alice and another qubit, Alice performs some manipulations on them and responds, and Bob measures the additional qubit and gets the correct answer. In 1994, Peter Shor from Bell Labs discovered the quantum factor-expansion algorithm for an integer, the running time of which is proportional to the cube of the number of digits of a number; The classical algorithms for this problem are now unknown, the running time of which is proportional to any polynomial based on the number of digits of a number. Shor's algorithm can be generalized to other problems using the concepts of group theory. In 1996, Lov Kumar Grover from there also invented the quantum search algorithm. If among 2n lines of n bits, one satisfies some criterion (for example, it encodes the route of a traveling traveling salesman shorter than 1000 kilometers), then the brute force algorithm on a classical computer requires 2n steps; if we can expose a quantum computer to an effect that changes the sign of the amplitude of the state corresponding to this line and another effect, then after 2n / 2 steps, all states except our destructively interfere; measurement will give us our condition. In the 2000s, they invented a fast quantum algorithm to solve the equation x2 - n * y2 = 1 and several other mathematical problems.
No one has yet been able to build a non-toy quantum computer, and will not be able to in the near future. Using parallel spins of trillions of trillions of nuclei for qubits and nuclear magnetic resonance for measurements, in 2001 researchers from IBM and Stanford executed Shoreās algorithm and factorized the number 15. There are a number of exotic proposals like using two-dimensional quasiparticles that are neither fermions nor bosons, but Something third, with strange topological properties, but to their implementation is also very far. Perhaps even if it is impossible to build a non-toy quantum computer, studying quantum algorithms somehow helped in studying classical algorithms, and thus was not useless, but I am not competent enough to decide whether this is so or not.
Source: https://habr.com/ru/post/3496/
All Articles