References on quantum arithmetic circuit complexity

Question

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.}

Answer 1

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:

• In-place ripply carry adder: "A new quantum ripple-carry addition circuit " by Cuccaro et al 2004
• Optimal Toffoli count ripply carry adder: Halving the cost of quantum addition by Gidney 2017
• Carry lookahead adder: "A logarithmic-depth quantum carry-lookahead adder" by Draper et al 2004
• Carry save adder (sortof): "Approximate encoded permutations and piecewise quantum adders" by Gidney 2019
• Karatsuba multiplier: "Asymptotically Efficient Quantum Karatsuba Multiplication" by Gidney 2019
• Multiplier w/ table lookup acceleration: "Windowed quantum arithmetic" by Gidney 2019
• Nearly inline incrementing using dirty qubits: "Factoring using 2n+2 qubits with Toffoli based modular multiplication " by Haner et al and also "Factoring with n+2 clean qubits and n-1 dirty qubits" by Gidney (2017)

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.

Answer 2

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.