Rice computer scientists reach finals in global XPRIZE Quantum Applications competition

By John Bogna

Rice University quantum computing researchers have introduced a novel algorithm with the potential to speed up quantum computing. This algorithm landed the team in the finals for the XPRIZE Quantum Applications competition, which aims to “develop quantum algorithms ready for deployment as hardware advances, designed to tackle complex problems in health, climate, energy and materials science with global impact,” according to the XPRIZE foundation.

Postdoctoral researcher Jianqiang Li leads team QuantumforGraphProblem. He is advised by computer science faculty members Nai-Hui Chia, Anastasios Kyrillidis and Tirthak Patel.

The three-year-long global competition — sponsored by Google Quantum AI, Goolge.org and the Geneva Science and Diplomacy Anticipator — was launched in 2024 and runs through 2027 with a $5 million prize awarded to the winner.

Li’s paper, “A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems,” details the algorithm that advanced his team to the finals. In it, Li outlines how he developed a new quantum linear system algorithm and identifies structural conditions under which it achieves polynomial time performance on a graph problem for which no classical polynomial time algorithm is currently known.

Li’s algorithm could eventually mean the next stage of quantum computing, both in speed and applications.

Time complexity, the MIS problem and the new algorithm

As technology advances, computers must handle more complex inputs, and one way to do that is with better algorithms. In computation, time complexity (how long it takes the computer to solve a problem relative to the work involved) is everything. 

Polynomial time, in which the work a computer has to do grows “reasonably” in proportion to the number of inputs, is basically the standard for time complexity. If a computing problem can be solved in polynomial time, it is considered efficient.

But some problems are too huge for conventional computers to solve, since the number of inputs would require a machine to calculate until roughly the heat death of the universe to work it all out. That is where quantum computing and algorithms like Li’s come in.

While quantum computers are not better than classical computers at everything — they still have very specialized use cases for now — there are times when they have more calculating power to take on these bigger problems.

Li’s algorithm uses one of those problems as proof of concept: the maximum independent set (MIS) problem. Classified as a hard problem, or NP problem, it is a graphing computational problem where you need to find the largest possible set of graph vertices where no two vertices are connected by an edge.

Because there are so many possibilities to be explored, it is very difficult to compute quickly; all those possibilities mean the work to find the right solution grows exponentially, also known as exponential time. As a test example for his algorithm, Li identified a new set of structural conditions for the MIS problem under which the algorithm runs in polynomial time.

“The maximum independent set problem can be reformulated as a special form of the polynomial system, so we apply this new linear system algorithm to the maximum independent set,” Li said. “And we show that the quantum algorithm, in a fault-tolerant quantum computer under those conditions, can run in polynomial time.”

This work is still in the early stages, but it has enough promise that it has drawn the attention of the XPRIZE judges. Li still needs more evidence but says he is convinced his algorithm has potential.

“Because these conditions are very special, we don’t know whether it would be classically hard or not,” he said. “But this is just the initial investigation of the new quantum algorithm, so maybe with some more adaptation, we can show more.”

The next step is continued testing on other hard computational problems to see under which conditions they can be solved in polynomial time. He also needs to compare those results to classical computing methods for mathematical proof that the new algorithm really is more efficient.

A ‘detour’ to the right road

Motivated by sheer curiosity, Li began the work that would lead to this algorithm as a doctoral student at Penn State University under the advisement of professor Sean Hallgren.

“He really encouraged me to just pursue my curiosity,” Li said.

Solving polynomial systems using existing quantum linear system algorithms became Li’s first doctoral project. He kept at it for several years before coming to Rice’s Department of Computer Science for postdoctoral work.

“When Jianqiang first told me about his algorithms, we had several meetings and countless debates about whether — and why — this new approach can outperform existing ones across different quantum linear system-related problem settings,” said Chia, assistant professor of computer science and member of the Ken Kennedy Institute at Rice. “Clearly, he has already found very good answers to many of these questions. Still, I believe there are even more interesting insights waiting to be uncovered, and this remains a fascinating question to me. I’m sure we’ll continue to argue and discover more in the future.”

Patel, also a Rice assistant professor of computer science and Ken Kennedy Institute member, said the recognition marked “an important moment for Rice in quantum computing.”

“Reaching the XPRIZE Quantum Applications finals represents Rice on a global stage, and Jianqiang’s work is a big reason why,” Patel said. “His algorithm represents the kind of deep, foundational advance that moves the field forward, and it showcases Rice’s growing leadership in quantum information science.”

Kyrillidis, associate professor of computer science and the Dean Fellow in AI/Computing in Rice’s George R. Brown School of Engineering and Computing, called Li’s achievement “exciting,” saying it “raises the bar on benchmarking: Any claimed speedup — classical or quantum — must be continuously challenged and validated with sharp theory, careful comparisons to the strongest baselines and realistic implementation assumptions.”

“Jianqiang’s selection as an XPRIZE Quantum Applications finalist is a remarkable achievement and a testament to both the originality and rigor of his work,“ said Kyrillidis, who leads the Quantum Theory, Algorithms and Systems (QuanTAS) research cluster at the Ken Kennedy Institute. “We believe that at Rice University, Jianqiang has exactly the right environment to pursue this end-to-end standard — within QuanTAS — where we work to close the gap between promised and deliverable quantum advantage by identifying where quantum systems genuinely help, where they don’t and what advances are still needed for real-world impact.”

Li described the process as a “detour” that eventually led him down his current path. When he first started working on the project, Li said he “was deeply hopeful” about the outcome and “worked relentlessly, day after day and night after night, only to arrive at a negative result: a fundamental limitation of applying existing quantum linear system algorithms.”

The project’s logo, inspired by a Hilma af Klint painting, is a reflection of his experience.

“For me, the research path often leads to results that are the inverse of our original expectations,” Li said, explaining why the mirroring, inverted figure and ground colors of af Klint’s painting resonated in this context. “At the same time, the image also conveys a sense of hope that persistence through failure can open up a way forward. The limitation result I obtained seven years ago ultimately became the seed for a positive breakthrough.

“After a detour into a related pathfinding problem, I gradually accumulated new techniques and insights through collaborations. These tools eventually made the positive result in this paper possible.”

So what could that look like outside the lab?

Algorithms like Li’s that solve linear system equations are everywhere in the modern world. Everything from optimization to shipping logistics — whatever requires calculating results from multiple inputs with multiple possibilities — is handled by an algorithm. Li’s research has the potential to make all those applications more efficient.