I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its degree? Can you please provide references for both classical and quantum algorithms? What happens if we can compute polynomial in any $\mathbb{Z}_p$ through the black box. What happens if we have access to polynomial at real $\mathbb{R}$ points.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.