Simplicity at its Peak, Extraordinary in its Simplicity.

In the realm of physics, many models can be represented using concise formulas that carry profound meanings, such as the mass-energy equivalence equation (E=mc2) and Newton's second law (F=ma), which are both straightforward yet remarkably significant.

With the rapid development of quantum technology, the pursuit of concise and efficient algorithms or software for quantum computers has become a dream of many scientists. Recently, the team led by Professor Gui-Lu Long, a jointly appointed researcher at the Beijing Academy of Quantum Information Sciences and a professor at Tsinghua University, has achieved another breakthrough in improving quantum algorithms.

Gui-Lu Long’s team has made further improvements to the previously developed "quantum gradient descent algorithm," significantly reducing its requirements for quantum resources such as quantum circuits. This algorithm has shown superior performance in optimizing complex high-dimensional data compared to classical algorithms, and it is also compatible with future quantum computers. The relevant findings were published on "npj Quantum Information", a partner journal of Nature, on January 29, 2021.

01 The Predicament of Gradient Descent Algorithms

The gradient descent algorithm is a cornerstone of traditional numerical optimization and an essential part of many machine learning algorithms in the field of artificial intelligence.

"The fundamental idea of the gradient descent algorithm can be likened to descending a mountain, continuously seeking the valley while moving downward from the peak," said Gui-Lu Long.

Imagine a scenario: a person is trapped on a mountain and needs to descend, but thick fog obscures visibility, making the path down uncertain. To find the path, the person must use the information around him/her. He/She takes his(her) current position as a reference point and searches for the steepest slope, then moves towards the descending side of the mountain. After covering a certain distance to a lower point, he/she repeats the same method to achieve "gradient descent," ultimately reaching the valley.

Similarly, if the goal is to climb up the mountain, he/she can search for the steepest direction upward. After reaching a higher point, he/she repeatedly employs the same method, eventually reaching the mountain's summit.

Gui-Lu Long explained that the basic idea of the gradient descent algorithm is to evolve the target function along the optimal gradient direction through continuous iteration, much like "repeatedly finding steep slopes for descending the mountain," thus identifying the local minimum of the target function.

However, when dealing with large-scale high-dimensional data, such as image data, remote sensing data, and machine learning data, using the gradient descent algorithm often requires a considerable amount of computational resources. It is difficult to address optimization problems of certain high-dimensional data with even the strongest current classical computational capabilities.

"This is analogous to finding the steepest slope while descending a mountain, which is not an easy task and requires a combination of various tools or measurement methods to determine the steepest direction," Gui-Lu Long said.

02 Quantum "Blessing" for the Algorithm

The development of quantum technology offers a glimmer of hope for overcoming this predicament.

Previously, researchers combined the advantages of quantum computing to propose a quantum version of the gradient descent algorithm.

In the quantum gradient descent algorithm, a practical and fundamental quantum algorithm called quantum phase estimation is employed. However, in the face of massively large-scale data computation, the quantum bit (qubit) requirement for this method increases with the data size. This results in a larger "quantum circuit" depth due to various operations on the quantum information storage units (such as qubits).

"A quantum circuit is composed of quantum bits and quantum gates, where each control operation on a quantum bit is a quantum gate. A quantum circuit is like a musical staff, with quantum bits as the staff lines and quantum gates as the notes. A specific algorithm corresponds to a particular quantum circuit, completed through a 'musical composition of a musical staff,' achieving computational tasks," explained Shijie Wei, a postdoctoral researcher at the Beijing Academy of Quantum Information Sciences.

In the previously proposed quantum gradient descent algorithm, a deep quantum circuit was required due to its high depth quantum linearity. Therefore, it couldn't run on existing quantum computer systems.

The Gui-Lu Long team proposed an improved version of the quantum gradient descent algorithm that allows it to run on existing quantum computer systems.

As early as 2002, Gui-Lu Long introduced the concept of Linear Combination of Unitaries (LCU). In previous quantum computing models, only unitary operations were allowed for multiplication and division. LCU transcends this limitation, enabling unitary operations not only for multiplication and division but also for addition and subtraction, significantly enhancing the effectiveness and scalability of quantum computing.

Using the LCU method, Gui-Lu Long’s team developed the quantum gradient descent algorithm and provided a representation of the quantum circuit. "This is like providing a 'sketch' of quantum bit operations," explained Shijie Wei.

In the team's quantum gradient descent algorithm, the number of quantum state copies required has been reduced from a polynomial order of magnitude to an irrelevant constant of 2 relative to the system size. "In previous calculations, a huge number of quantum state copies were needed, on the order of a polynomial number, whereas in our algorithm, only two quantum states need to be copied," said Shijie Wei.

This improvement significantly reduces the depth of the quantum circuit, leading to a substantial decrease in the number of quantum gate operations. Consequently, the quantum gradient descent algorithm can run on quantum computers with limited qubit quantities.

To verify the feasibility of the improved quantum gradient descent algorithm, Gui-Lu Long's team demonstrated it in a 4-qubit nuclear magnetic resonance system. Experimental results showed that the algorithm can optimize polynomial order problems.

In further experiments, the team demonstrated the algorithm using a two-dimensional vector composed of a single quantum bit state as the optimization problem. Under various initial conditions, the experiment achieved a fidelity greater than 94% for obtaining local minimum values.

"This indicates that the experimental minimum values obtained using the algorithm agree with the theoretical simulation's minimum values, with a degree of overlap exceeding 94%," Shijie Wei said. "This validates the correctness and practicality of the algorithm, highlighting its significant potential in quantum computing."

03 "Compatibility" for Fault-Tolerant Computing

With the development of quantum computer hardware, the improved version of the quantum gradient descent algorithm proposed by Gui-Lu Long's team holds significant application value.

"For example, in fields such as machine learning and image analysis in artificial intelligence, remote sensing data processing, and biochemistry analysis, which all involve complex high-dimensional data optimization problems, our algorithm can offer more efficient solutions," explained Shijie Wei.

Gui-Lu Long emphasized, "It is worth noting that, similar to the full quantum eigenvalue solver constructed using the LCU method by our team before, this algorithm can not only run on current noisy quantum computing devices but can also be directly used as an application software on future fault-tolerant quantum computers."

In 2020, the Gui-Lu Long and Shijie Wei and other team members used the unitary linear combination method to construct a "full quantum eigenvalue solver," effectively developing a quantum computing "application software" that allows quantum computers to calculate molecular ground-state energy levels and corresponding electron structures. Relevant findings were published in the journal "Research," a partner journal of "Science."
       "Currently, the era of noisy quantum computing has arrived," explained Gui-Lu Long. He elaborated that noisy quantum computing refers to "using medium-sized quantum computers with tens to thousands of quantum bits, carrying out computations with 'noise,' where error correction during the calculation process is currently not feasible."

"While they work 'with an ailment,' they are still capable of performing computations that surpass those of the largest current classical electronic computers," Gui-Lu Long stated. He further expressed that with further development, quantum computers that perform calculations in the presence of noise can actively perform error correction during the computation process, eventually giving rise to fault-tolerant quantum computers.

At present, the quantum application algorithm team is developing novel quantum algorithms, designing customized quantum algorithm software, and advancing industrial applications. "In the future, quantum computer hardware will continue to evolve and upgrade. The scale, precision, and speed of computation will continually improve, and quantum algorithms will transform from theoretical advantages to practical quantum benefits when solving real-world problems."

Link to the paper：https://doi.org/10.1038/s41534-020-00351-5