# Uniform way of quantifying “branching” in nondeterministic, probabilistic, and quantum computation?

The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is represented by a father-child link in this tree.

Similar trees can also be constructed for visualising the computations of probabilistic and quantum machines as well. (Note that it is better for some purposes not to view the related graph for quantum computations as a tree, since two nodes representing identical configurations at the same level of the tree can "cancel" each other out, due to quantum interference, but this doesn't have anything to do with the present question.)

Of course, deterministic computations are not like that; there is a single "branch" in the corresponding "tree" for any run of a deterministic machine.

In all the three cases mentioned above, what sometimes makes these computations "difficult" for deterministic computers is not really that there is branching going on, rather, it is a matter of how much branching is present in the tree. For instance, a polynomial-time nondeterministic Turing machine which is guaranteed to produce computation trees whose "widths" (i.e. number of nodes in the most crowded level) are also bounded above by a polynomial function of the input size can be simulated by a polynomial-time deterministic TM. (Note that this "polynomial width" condition is equivalent to restricting the NTM to make at most a logarithmically bounded number of nondeterministic guesses.) The same thing is true when we put similar width bounds on probabilistic and quantum computations.

I know that this issue has been examined in detail for nondeterministic computations. See, for example, the survey "Limited Nondeterminism" by Goldsmith, Levy, and Mundhenk. My question is, has this phenomenon of "limited branching" or "limited width" been studied in a common framework encompassing all of the nondeterministic, probabilistic, and quantum models? If so, what is the standard name for it? Any links to resources will be appreciated.

Nondeterministic computations can also be viewed as verification of claims using short proofs. That is, the class NTIME(t) can also be viewed as the class of languages $L$ such that a claim of the form $x \in L$ can be verified in time $t(|x|)$ by reading a short proofs. In this model, "quantifying the braching" is analogous to studying how short the proofs can be. While I don't know of papers that studied this question, this could give you a direction of where to look for them. One paper that studied a related question in the context of interactive proofs is "On Interactive Proofs with Laconic prover", by Goldreich, Vadhan, and Wigderson: http://www.wisdom.weizmann.ac.il/~oded/p_laconic.html
Regarding probabilistic computation: The amount of "branching" used in the computation is exactly the number of random bits/coin tosses that the algorithm uses. Quantifying this number and minimizing it is studied extensively in the area of "Derandomization". You can read about it in Chapters 20 and 21 of the Arora-Barak book (http://www.cs.princeton.edu/theory/index.php/Compbook/Draft) or in Chapter 8 of Goldreich's book (http://www.wisdom.weizmann.ac.il/~oded/cc-book.html). It should also be mentioned that the common belief in this area is that $P=BPP$. If this is true, then the number of random bits a computation uses does not affect its power, as long as this number is polynomial.