Quantum algorithm for tree size estimation

22 April 2017

Additional Info

  • Paper Title:

    ”Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games"

  • Paper Authors:

    Andris Ambainis, Martins Kokainis (University of Latvia)

Qu&Co comments on this publication:

In this paper, Ambainis et al. study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. They construct a quantum algorithm which, given a search tree of depth at most n, estimates the size of the tree T with an upper-bound of sqrt(nT) steps. They apply their results to improve the time-complexity of a classical backtracking algorithm and to develop a quantum algorithm for evaluating AND-OR formulas in 2-player game type models.

What's Interesting?

How can we help you?

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Invalid Input

Copyright © Qu & Co BV
close