On additive error approximations to #BQP
On additive error approximations to #BQP
Counting complexity characterizes the difficulty of computing functions related to the number of valid certificates to efficiently verifiable decision problems. Here we study additive approximations to a quantum generalization of counting classes known as #BQP. First, we show that there exist efficient quantum algorithms that achieve additive approximations to #BQP …