In: Statistics and Probability
Consider 2-bit input functions that has either constant output (0 or 1) or balanced output (the number of {0,1} outputs are equal to each other). First a class is selected with1/2 probability and then one of the functions that belong to the chosen class is selected uniform randomly. We would like to guess the class of the function with minimum function evaluations.
• What is the average number of guesses before we identify the chosen class using classical bits?
• Draw the quantum circuit that can predict the class using only one function evaluation.