Time and Query Optimal Quantum Algorithms Based on Decision Trees
Salman Beigi, Leila Taghavi, Artin Tajdini
It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity O(GT‾‾‾√) where T is the query complexity of the classical algorithm (depth of the decision tree) and G is the maximum number of wrong answers by the guessing algorithm [arXiv:1410.0932, arXiv:1905.13095]. In this paper we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time Õ (GT‾‾‾√). Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph theoretic problems including bipartiteness, cycle detection and topological sort can be solved in time O(n3/2logn) and with O(n3/2) quantum queries. Moreover, finding a maximal matching can be solved with O(n3/2) quantum queries in time O(n3/2logn), and maximum bipartite matching can be solved in time O(n2logn).