In classical computing, arithmetic circuit complexity is apparently a big topic. But I couldn't find much about the complexity of quantum arithmetic circuits. Almost all references like arXiv:1805.12445 talk about the implementation and construction of the quantum circuits for functions like $\frac{1}{x}$, $\sin(x)$, etc. But I'm looking for the quantum analog of the VP vs. VNP problem and complexity analyses of the quantum circuit families used to improve the implementation of those functions.

Is there any existing work on this area? In other words, what are some authoritative references on quantum arithmetic circuit complexity (with a focus on complexity classes)?

P.S: I've asked a very related question on the Theoretical CS site.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.