New quantum algorithm is a perfect "fit"
A team of researchers including IQC postdoctoral fellow Nathan Wiebe demonstrated a powerful new quantum algorithm for data analysis.
IQC postdoctoral fellow Nathan Wiebe, in collaboration Seth Lloyd (MIT) and Daniel Braun (Université de Toulouse), have demonstrated a quantum algorithm that applies to a widely used data analysis technique.
The research team described in Physical Review Letters an algorithm to improve "least-squares fitting" using a quantum computer. The work was also highlighted on the American Physical Society website.
Building upon earlier work that proposed an algorithm for solving linear systems of equations, Wiebe and colleagues adapted it to efficiently estimate the quality of a data-fit without needing to obtain a full solution first, or needing to fully characterize the state of the quantum computer.
This would enable rapid searches for simple, accurate approximations to massive quantum data sets.
"Our work shows that an everyday computational problem can, under certain circumstances, be performed exponentially faster using a quantum computer than using existing classical algorithms," explains Wiebe.
"It provides an alternate way of learning the quantum state that comes out of quantum computations."
Wiebe says this work could lead to better methods for certifying the output of quantum computers and/or quantum simulators — a difficult outstanding problem in quantum information research.
"It's an enabling tool for subsequent work," says Wiebe. "It's particularly intriguing because it suggests that quantum computers may be useful — perhaps even necessary — to build truly massive quantum information processors."