Code for "A Classical-Quantum Adder with Constant Workspace and Linear Gates"

This repository contains code for generating inplace classical-quantum adder circuits. The main circuit uses O(n) gates, and specifically 4n +- O(1) Toffolis, and at most 3 clean ancilla qubits.

Usage Examples

These examples assume you're on a Linux system with python working.

1. Setup a Python virtual environment and verify the tests pass:

python -m venv .venv
source .venv/bin/activate
pip install -e .
pytest src

2. Generate a circuit diagram for a 10-qubit adder.

make_adder --n 10 --output_type svg > example.svg

Outputs:

3. Generate a list of operations for a 5 qubit controlled adder specialized to an offset of 11, with a coherent carry input:

make_adder \
    --n 7 \
    --output_type ops \
    --offset 11 \
    --controlled \
    --carry_in qubit

Outputs:

qubit control
qubit carry_in
qubit target0
qubit target1
qubit target2
qubit target3
qubit target4
qubit target5
qubit target6
qubit _clean0
qubit _clean1
qubit _clean2
reset_z _clean0
reset_z _clean1
reset_z _clean2
_clean1 ^= control
_clean2 ^= control
target0 ^= control
target1 ^= control
_clean1 ^= target0 & (carry_in ^ control)
_clean2 ^= target1 & (_clean1 ^ control)
_clean0 ^= target2 & _clean2
target2 ^= _clean2
bit m1 = mx _clean2
zif m1 & control
zif m1 & target1 & (_clean1 ^ control)
target1 ^= _clean1
bit m2 = mx _clean1
zif m2 & control
zif m2 & target0 & (carry_in ^ control)
target0 ^= carry_in
reset_z _clean1
reset_z _clean2
_clean1 ^= control
target3 ^= control
_clean1 ^= target3 & (_clean0 ^ control)
_clean2 ^= target4 & _clean1
target6 ^= target5 & _clean2
target5 ^= _clean2
bit m3 = mx _clean2
zif m3 & target4 & _clean1
target4 ^= _clean1
bit m4 = mx _clean1
zif m4 & control
zif m4 & target3 & (_clean0 ^ control)
target3 ^= _clean0
bit m0 = mx _clean0
target0 ^= 1
target1 ^= 1
target2 ^= 1
zif target5 & m0
target5 ^= target2 & target4
target4 ^= (control ^ target1) & target3
target3 ^= control
target4 ^= control
target3 ^= (control ^ target0) & (carry_in ^ control)
target4 ^= (control ^ target1) & (control ^ target3)
target5 ^= target2 & target4
zif target5 & m0
target5 ^= target2 & target4
target4 ^= (control ^ target1) & target3
target3 ^= control
target4 ^= control
target3 ^= (control ^ target0) & (carry_in ^ control)
target4 ^= (control ^ target1) & (control ^ target3)
target5 ^= target2 & target4
target0 ^= 1
target1 ^= 1
target2 ^= 1

4. Print toffoli counts for the family:

for i in {0..20}; do
    echo "${i}: $(make_adder --n $i --output_type tof)";
done

Outputs:

0: 0
1: 0
2: 1
3: 2
4: 3
5: 4
6: 11
7: 16
8: 22
9: 27
10: 30
11: 35
12: 38
13: 43
14: 46
15: 51
16: 54
17: 59
18: 62
19: 67
20: 70

5. Output QASM implementing an 8 qubit incrementer:

make_adder \
    --n 8 \
    --offset 1 \
    --carry_in 0 \
    --output_type qasm

Outputs:

OPENQASM 2.0;
include "qelib1.inc";
qreg q_target0[1];
qreg q_target1[1];
qreg q_target2[1];
qreg q_target3[1];
qreg q_target4[1];
qreg q_target5[1];
qreg q_target6[1];
qreg q_target7[1];
qreg q__clean0[1];
qreg q__clean1[1];
qreg q__clean2[1];
reset q__clean0[0];
reset q__clean1[0];
reset q__clean2[0];
x q__clean1[0];
x q_target0[0];
CX q_target0[0], q__clean1[0];
ccx q_target1[0], q__clean1[0], q__clean2[0];
ccx q_target2[0], q__clean2[0], q__clean0[0];
CX q__clean2[0], q_target2[0];
creg b_m1[1];
h q__clean2[0];
measure q__clean2[0] -> b_m1[0];
if (b_m1 == 1) cz q_target1[0], q__clean1[0];
CX q__clean1[0], q_target1[0];
creg b_m2[1];
h q__clean1[0];
measure q__clean1[0] -> b_m2[0];
if (b_m2 == 1) z q_target0[0];
reset q__clean2[0];
ccx q_target3[0], q__clean0[0], q__clean2[0];
CX q__clean0[0], q_target3[0];
reset q__clean1[0];
ccx q_target4[0], q__clean2[0], q__clean1[0];
CX q__clean2[0], q_target4[0];
CX q__clean2[0], q_target0[0];
creg b_m3[1];
h q__clean2[0];
measure q__clean2[0] -> b_m3[0];
reset q__clean2[0];
ccx q_target5[0], q__clean1[0], q__clean2[0];
CX q__clean1[0], q_target5[0];
CX q__clean1[0], q_target1[0];
creg b_m4[1];
h q__clean1[0];
measure q__clean1[0] -> b_m4[0];
ccx q_target6[0], q__clean2[0], q_target7[0];
CX q__clean2[0], q_target6[0];
CX q__clean2[0], q_target2[0];
creg b_m5[1];
h q__clean2[0];
measure q__clean2[0] -> b_m5[0];
x q_target3[0];
x q_target4[0];
x q_target5[0];
x q_target6[0];
x q_target7[0];
if (b_m3 == 1) z q_target0[0];
if (b_m4 == 1) z q_target1[0];
if (b_m5 == 1) z q_target2[0];
ccx q_target5[0], q_target1[0], q_target2[0];
ccx q_target4[0], q_target0[0], q_target1[0];
ccx q_target3[0], q__clean0[0], q_target0[0];
ccx q_target4[0], q_target0[0], q_target1[0];
ccx q_target5[0], q_target1[0], q_target2[0];
if (b_m3 == 1) z q_target0[0];
if (b_m4 == 1) z q_target1[0];
if (b_m5 == 1) z q_target2[0];
x q_target3[0];
x q_target4[0];
x q_target5[0];
x q_target6[0];
x q_target7[0];
creg b_m0[1];
h q__clean0[0];
measure q__clean0[0] -> b_m0[0];
x q_target0[0];
x q_target1[0];
x q_target2[0];
if (b_m0 == 1) z q_target5[0];
ccx q_target2[0], q_target4[0], q_target5[0];
ccx q_target1[0], q_target3[0], q_target4[0];
x q_target3[0];
x q_target0[0];
CX q_target0[0], q_target3[0];
x q_target0[0];
ccx q_target1[0], q_target3[0], q_target4[0];
ccx q_target2[0], q_target4[0], q_target5[0];
if (b_m0 == 1) z q_target5[0];
ccx q_target2[0], q_target4[0], q_target5[0];
ccx q_target1[0], q_target3[0], q_target4[0];
x q_target3[0];
x q_target0[0];
CX q_target0[0], q_target3[0];
x q_target0[0];
ccx q_target1[0], q_target3[0], q_target4[0];
ccx q_target2[0], q_target4[0], q_target5[0];
x q_target0[0];
x q_target1[0];
x q_target2[0];

6. Generate a diagram of the carry-xor subroutine:

make_adder \
    --n 5 \
    --circuit_type carry-xor \
    --output_type svg \
    > example2.svg

Outputs:

7. Regenerate the circuit diagrams shown in the paper:

./make_plots.sh