Before revision:  We further show that with O(\log(n) ^7 ) many cut queries a quantum algorithm can with high probability output a spanning forest for G. En route to proving these results, we design quantum algorithms for learning a graph using cut queries.
After revision:  We further show that with O(\log(n) ^8 ) many cut queries a quantum algorithm can with high probability output a spanning forest for G. En route to proving these results, we design quantum algorithms for learning a graph using cut queries.