Returns a quantum circuit for ripple-carry addition. [Cuccaro2004]_

    Requires two carry qubit (input and output). The result is returned in
    addend1.

    .. [Cuccaro2004]
        A new quantum ripple-carry addition circuit, Steven A. Cuccaro,
        Thomas G. Draper, Samuel A. Kutin, David Petrie Moulton
        arXiv:quant-ph/0410184 (2004)

def addition_circuit(
        addend0: Qubits,
        addend1: Qubits,
        carry: Qubits) -> Circuit:
    """Returns a quantum circuit for ripple-carry addition. [Cuccaro2004]_

    Requires two carry qubit (input and output). The result is returned in
    addend1.

    .. [Cuccaro2004]
        A new quantum ripple-carry addition circuit, Steven A. Cuccaro,
        Thomas G. Draper, Samuel A. Kutin, David Petrie Moulton
        arXiv:quant-ph/0410184 (2004)
    """

    if len(addend0) != len(addend1):
        raise ValueError('Number of addend qubits must be equal')

    if len(carry) != 2:
        raise ValueError('Expected 2 carry qubits')

    def _maj(qubits: Qubits) -> Circuit:
        q0, q1, q2 = qubits
        circ = Circuit()
        circ += CNOT(q2, q1)
        circ += CNOT(q2, q0)
        circ += CCNOT(q0, q1, q2)
        return circ

    def _uma(qubits: Qubits) -> Circuit:
        q0, q1, q2 = qubits
        circ = Circuit()
        circ += CCNOT(q0, q1, q2)
        circ += CNOT(q2, q0)
        circ += CNOT(q0, q1)
        return circ

    qubits = [carry[0]] + list(chain.from_iterable(
        zip(reversed(addend1), reversed(addend0)))) + [carry[1]]

    circ = Circuit()

    for n in range(0, len(qubits)-3, 2):
        circ += _maj(qubits[n:n+3])

    circ += CNOT(qubits[-2], qubits[-1])

    for n in reversed(range(0, len(qubits)-3, 2)):
        circ += _uma(qubits[n:n+3])

    return circ