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.


Here's a really old reference:

"Quantum Networks for Elementary Arithmetic Operations" by Vedral et al (1995)

And here's some state of the art stuff:

Sorry for the number of self-cites. I got really interested in this problem for awhile.

There's also some cool papers like "Addition on a quantum computer" by Draper (2000) which uses a totally-unique-to-quantum method for performing an addition, but unfortunately the overhead of doing it fault tolerantly is extremely high.


There are some common Quantum Arithmetic Circuits such as Basic Quantum Adders and Multipliers, QFT based circuits, Integer adders, Galois Field Multipliers etc. are used in various quantum algorithms and implementations. Among these, QFT focused circuits are studied in various quantum arithmetic circuit complexity related discussions. The measures of the complexity of a quantum circuit are the size of the circuit, the depth of the circuit, and the number of qubits in the circuit.

We can find a seminal research paper on Quantum Arithmetic Circuits by Takahashi Yasuhiro quite relevant to this topic. There is a recent research paper on the Arithmetic of QFT that approaches various aspects of circuit complexity. QFT provides an alternative way to perform arithmetic operations on a quantum computer. There is another research paper published in nature about Automated Optimisation of large quantum circuits with continuous parameters which talks about the complexity of quantum arithmetic circuits.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.