Researchers of Polish Beit Project have presented a novel quantum algorithm for solving the unstructured search problem with one marked element.
Their algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover’s algorithm and may be successfully executed on NISQ devices.
They proved that their algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are not in fact unstructured, they also described the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution.
Combining these results has allowed them to use asymptotically smaller number of elementary gates than the Grover’s algorithm in various applications, keeping the number of queries to the oracle essentially the same.
They showed how the results can be applied to solve hard combinatorial problems, for example Unique k-SAT.
Additionally, they showed how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.