New quantum algorithms that have made a breakthrough in nonlinear equations

Hi, Habr. For future students of the course “Mathematics for Data Science” prepared a translation of interesting material.

We also invite everyone to attend an open webinar on the topic “Statistical dependence”… At the webinar, together with an expert, you will learn about different types of dependencies between quantitative and nominal features, learn not to confuse a statistical relationship with a causal one, learn about methods for identifying statistical dependencies.


The two teams found two different ways for quantum computers to process nonlinear systems by representing them as linear.

Sometimes a computer can predict the future very easily. Simple phenomena such as sap running down a tree trunk are uncomplicated and can be captured in a few lines of code using what mathematicians call linear differential equations. But in nonlinear systems, interactions can influence themselves: when air flows past the wings of an aircraft, the air flow changes the molecular interactions that change the air flow, and so on. This feedback loop creates real chaos, when small changes in the initial conditions lead to completely different behavior later on, making predictions almost impossible – no matter how powerful the computer is.

“This is one of the reasons why we still find it difficult to predict the weather or understand complex fluid flow,” says Andrew Childs, a quantum informatics researcher at the University of Maryland. “There are complex computational problems that could be solved if this nonlinear dynamics were solved.”

But it may soon be possible. In independent studies published in November, two groups – one led by Childs, and the other from Massachusetts Institute of Technology (MIT) – described powerful tools that will enable quantum computers to better simulate nonlinear dynamics.

Quantum computers take advantage of quantum phenomena to perform certain computations much more efficiently than their classical counterparts. Thanks to these abilities, they can already solve the most complex linear differential equations exponentially faster than classical computers. Researchers have long hoped to be able to solve nonlinear problems in the same way using clever quantum algorithms.

Newer approaches present this nonlinearity as a more convenient set of linear approximations, although their methods differ significantly. As a result, researchers now have two different approaches to solving nonlinear problems using quantum computers.

“What is especially interesting about these two works is that they found a regime in which, with some assumptions, they have an efficient algorithm,” says Maria Kiferova, a quantum computing researcher at the University of Technology of Sydney who is not affiliated with any of these studies. “It’s really impressive and it means that both of these studies use very good methods.”

The cost of chaos

For over a decade, quantum computer scientists have tried to use linear equations as a key to nonlinear differential equations. An important breakthrough came in 2010 when Dominic Berry, now at Macquarie University in Sydney, created the first algorithm for solutions of linear differential equations, which runs exponentially faster on quantum computers than on classical computers. Berry’s attention soon turned to nonlinear differential equations.

“We’ve tried working on this before,” says Berry. “But it was very ineffective.”

Andrew Childs of the University of Maryland has spearheaded one of two attempts to enable quantum computers to better simulate nonlinear dynamics. His team’s algorithm turned these chaotic systems into an array of easier-to-understand linear equations using a technique called Carleman linearization.

John T. Console / University of Maryland

The problem is that the physics behind quantum computers is fundamentally linear in its own right. “It’s like teaching a car to fly,” says Bobak Kiani, co-author of the MIT study.

The trick is to mathematically convert a nonlinear system to a linear one. “We want to have some kind of linear system because that’s exactly what we have in our toolbox,” says Childs. The research teams did this in two different ways.

Childs’ team used Carleman’s linearization, an old-fashioned mathematical technique from the 1930s that can transform non-linear problems into an array of linear equations.

Unfortunately, the resulting list of equations is endless. Researchers must decide where to chop it off to get a good enough approximation. “Should I stop at equation number 10? Number 20? ” – is talking Nuno lureiro, a plasma physicist at Massachusetts Institute of Technology and research co-author in Maryland. The team proved that for a certain range of nonlinearities, their method can truncate this endless list and solve equations.

The work, carried out under the auspices of the Massachusetts Institute of Technology, took a different approach. She modeled any nonlinear problem as a Bose-Einstein condensate. It is a state of matter in which interactions within an ultracold group of particles cause each individual particle to behave the same. Since all particles are interconnected, the behavior of each particle affects the others, returning back to the same particle in a closed loop, characteristic of nonlinearity.

The MIT algorithm simulates this nonlinear phenomenon on a quantum computer, using Bose-Einstein mathematics to combine nonlinearity and linearity. Thus, working with a simulation of a Bose-Einstein pseudo-condensate created for a nonlinear problem, this algorithm produces a useful linear approximation. “Give me your favorite nonlinear differential equation and I’ll build you a Bose-Einstein condensate that will simulate it,” says Tobias Osborne, a quantum computer scientist at Leibniz University of Hanover who is not associated with any of the studies. “This is an idea that I really liked.”

The team’s algorithm, led by the Massachusetts Institute of Technology, models any nonlinear problem as a Bose-Einstein condensate, an exotic state of matter in which all interconnected particles behave the same.

NIST

Berry believes that both works are important in different ways (he has not participated in either of them). “But ultimately their importance lies in demonstrating that there are methods that bring us closer to understanding non-linear behavior,” he says.

Realizing your limits

While these are important steps, they are still among the first in taking the top of nonlinear systems. A huge number of researchers are likely to analyze and refine each method – even before the equipment needed to implement them becomes a reality. “With both of these algorithms, we are really looking into the future,” says Kiferova. Using them to solve practical nonlinear problems requires quantum computers with thousands of qubits to minimize errors and noise – much more than is possible today.

And both algorithms can only handle slightly non-linear problems. A Maryland study pinpoints exactly how much nonlinearity it can handle with a new parameter, R, which is the ratio of a problem’s nonlinearity to linearity — its tendency to chaos compared to the friction that keeps the system on the rails.

“Childs’ research is mathematically rigorous. It gives a very clear idea of ​​when it will work and when it will not work, ”says Osborne. “I think it’s really very interesting. This is a fundamental contribution. “

The MIT-led study does not rigorously prove any theorems limiting his algorithm, Kiani said. But the team plans to learn more about the limitations of the algorithm by running small-scale tests on a quantum computer before moving on to more complex problems.

The most important caveat for both methods is that quantum solutions fundamentally different from classic. Quantum states correspond to probabilities, not absolute values, so instead of visualizing the airflow around each fuselage segment, for example, you extract average velocities or find pockets of stagnant air. “The fact that the output signal is quantum mechanical means that you still have to do a lot of work to analyze this state,” says Kiani.

It’s important not to exaggerate the capabilities of quantum computers, Osborne said. But the researchers are going to test many successful quantum algorithms on practical problems in the next five to ten years. “We’re going to try a lot of things,” he says. “And if we focus on limitations, it can also limit our creativity.”


Learn more about the course “Mathematics for Data Science”

Sign up for an open webinar on “Statistical dependence”

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *