Genadder generates a quantum circuit to add two binary numbers of any width. It is implemented in C. The number of bits is given on the command line.
The circuit generated is a ripple-carry adder. It follows the block scheme in Jozef Gruska's Quantum Computing, page 96, and uses optimized implementations by Paul E. Black (unpublished 11 July 2002) using Generate. The circuits were checked with QCSim. For N bit wide arithmetic, the circuit uses 3N qubits: 2N for inputs, N-1 ancilla, and a carry out. One of the inputs serves as the output sums. It is assumed that there is no carry in. Although it uses ancilla, they are reset to 0, thus there is no "garbage". The circuit uses 7N-6 gates, N > 1.
A simple example is a 2-bit wide adder. It uses six qubits: inp0, inp1, sum0, sum1, anc0, and carryOut. The input is inp0/1 and sum0/1. The output is sum0, sum1, and carryOut. The least significant bits are at the top.
Notice that we could save one gate by removing the last gate, cnot(inp0, anc0), and moving the second gate, cnot(inp0, sum0), to the end. This kind of optimization could be folded into the generator, or added as a post-processing step.
Slightly more complex is a 3-bit wide adder. This is the first instance of all three variants of adders circuits: first stage (no carry in), middle stage, and final stage (no need to undo the carry). Following the picture are the jaQuzzi and QHDL files. The jaQuzzi version came from Qhdl2Jaq. Genadder declares the qubits from most to least significant so density matrix rows in QCSim correspond to the binary interpretations. We reversed the order here so the jaQuzzi images correspond with Gruska's diagrams.
