Classic computers adopt quantum ideas

Three-qubit silicon chip created by IBM researchers hoping to someday design such chips with thousands of qubits

Someday, quantum computers will be able to solve complex optimization problems, quickly disassemble huge data sets, simulate physical experiments that currently require billions of particle accelerators, and solve many other problems that are inaccessible to today's computers. If, of course, they can be constructed. But while technical problems do not allow them to appear, theorists apply ideas and technologies inherent in quantum computing to solve serious and old problems of classical computer science, mathematics and cryptography.

“There is a lot of debate about whether quantum computers will ever be created at all,” said Chris Peikert, a specialist in cryptography and computer science at their Georgia Institute of Technology. “But this is one question, and the second is whether quantum techniques or algorithms can help you solve problems in new ways.”

Recently, quantum ideas have helped researchers prove the security of promising encryption technologies called “cryptography on grids,” whose application can help hide sensitive user data, such as their DNA, even from the companies that process this data. Proof through quantum calculations also led to a formula for the minimum length of error correction codes that protect data from damage.
')
Quantum ideas inspired to obtain many important results, such as refuting an erroneous algorithm that supposedly effectively solved the traveling salesman problem.

“If this happened once, it would be a coincidence. But there are so many options in which 'quantum' thinking leads to proof, ”says Oded Regev, an informatics specialist at New York University.


Multidimensional lattices can be used to encrypt data, proof of which was obtained using quantum computations.

This led to the fact that some researchers consider quantum computations not to be an esoteric field of computer science, but a generalization of classical computations - just as polygons are a generalization of triangles. Just as polygons can have any number of sides, while triangles have only three, quantum computers can work with any numbers (positive, negative, real, imaginary), while classic computers use only real positive numbers.

More generally, quantum ideas are powerful tools for solving classical computational problems. “There are several classic problems that have nothing to do with the quantum world, but it’s best to analyze them, summarizing them to the quantum level, proving something with the help of the quantum information theory, and then scaling back to the classical level,” says Ronald de Wolfe. Informatics theorist in the Netherlands Center for Mathematics and Informatics.

According to today's estimates, no more than 5% of scientists working in the field of theoretical informatics study quantum computation. But researchers say that the recent successes of "quantum thinking" have led to an increase in the number of theorists seeking to learn physics. "These amazing branches of quantum computing actually forced scientists using classical computer science to study quantum computing," said Scott Aaronson, a computer science theorist at the Massachusetts Institute of Technology.

The goal of quantum computing is to use the strange behavior of particles on quantum scales to perform calculations that seem impossible for ordinary computers. An ordinary computer stores information bits in transistors, which in the manner of switches can be in one of two states denoting 1 or 0. A quantum computer stores information qubits in subatomic particles, electrons or photons, which can exist in states 1, 0, or in superposition both of them, and they can also become entangled with each other, as a result of which the state of one qubit predetermines the state of another.


Three-qubit IBM Chip

Superposition and entanglement make qubits behave quite differently from bits. A two-bit circuit of a classical computer can be in one of the four states (0.0; 0.0; 0.1; 1.0; 1.1). A pair of qubits can be a combination of all of them. As the number of qubits increases, the number of possible states, and with it the volume of the state contained in the system, grows exponentially. A quantum computer with several hundred qubits could solve problems faster than today's supercomputers.

The only problem is that no one has yet been able to create a quantum computer in which the number of qubits would exceed the number of fingers. Chris Lirakis, a physicist from the group of superconducting quantum calculations at IBM Research, explains that in order to keep a system of entangled qubits from collapse, it must be isolated and cooled down to almost absolute zero. At the same time, qubits need to be spread about a centimeter apart, so that operations with one of them do not affect the others. These restrictions make systems of thousands of qubits too large to be placed in refrigerators capable of maintaining the right temperature.

“We have to solve a lot of very serious engineering problems in order to make this system scalable,” says Lirakis. “All problems play tug-of-war.”

Regev, who worked with Peukert on proving the security of cryptography on grids through quantum principles, says he hopes to see the construction of quantum computers during his lifetime. "But the quantum approach is so influenced by everything that even if no one ever can make a quantum computer, I would not be very upset," he says.

With the increase in the popularity of quantum technologies, we can expect the solution of more and more classical problems. "It was these results that convinced me that even if there were no quantum mechanisms in the universe, specialists in computer science would eventually invent them to solve problems."