, if for all , then . The certificate complexity of is the maximum certificate complexity over all . The analogous notion where one only requires the verifier to be correct with 2/3 probability is denoted . Quantum decision tree The quantum decision tree complexity is the depth of the lowest-depth quantum decision tree that gives the result with probability at least for all . Another quantity, , is defined as the depth of the lowest-depth quantum decision tree that gives the result with probability 1 in all cases (i.e. computes exactly). and are more commonly known as quantum query complexities, because the direct definition of a quantum decision tree is more complicated than in the classical case. Similar to the randomized case, we define and . These notions are typically bounded by the notions of degree and approximate degree. The degree of , denoted , is the smallest degree of any polynomial satisfying for all . The approximate degree of , denoted , is the smallest degree of any polynomial satisfying whenever and whenever . Beals et al. established that and . Relationships between boolean function complexity measures It follows immediately from the definitions that for all -bit Boolean functions ,, and . Finding the best upper bounds in the converse direction is a major goal in the field of query complexity. All of these types of query complexity are polynomially related. Blum and Impagliazzo, Hartmanis and Hemachandra, and Tardos independently discovered that . Noam Nisan found that the Monte Carlo randomized decision tree complexity is also polynomially related to deterministic decision tree complexity: . (Nisan also showed that .) A tighter relationship is known between the Monte Carlo and Las Vegas models: . This relationship is optimal up to polylogarithmic factors. As for quantum decision tree complexities, , and this bound is tight. Midrijanis showed that , improving a quartic bound due to Beals et al. It is important to note that these polynomial relationships are valid only for total Boolean functions. For partial Boolean functions, that have a domain a subset of , an exponential separation between and is possible; the first example of such a problem was discovered by Deutsch and Jozsa. Sensitivity conjecture For a Boolean function , the sensitivity of is defined to be the maximum sensitivity of over all , where the sensitivity of at is the number of single-bit changes in that