Quantum GCD circuit: On reversibility and clearing ancillae
It looks like they just directly translated the algorithm into a circuit, so it's not too hard to reproduce.


Write out the binary gcd algorithm as a loop:

def gcd(a, b):
    let shift = 0
    while a != 0 or b != 0:
        let pa = a &amp; 1
        let pb = b &amp; 1
        let pc = a &gt;= b

        if pa == 0 and pb == 0:
            a &gt;&gt;= 1
            b &gt;&gt;= 1
            shift++
        elif pa == 0:
            a &gt;&gt;= 1
        elif pb == 0:
            b &gt;&gt;= 1
        elif pc:
            a -= b
            a &gt;&gt;= 1
        else:
            b -= a
            b &gt;&gt;= 1

    return (a | b) &lt;&lt; shift

Keep track of any intermediate values so you can uncompute them instead of leaking them. Also switch to a fixed number of iterations to avoid leaking the size of the inputs.

def gcd(a, b, len_a, len_b):
    let shift = 0
    # Note: &gt;&gt; and &lt;&lt; are now bit rotations instead of bit shifts
    for i in range(len_a + len_b):
        let g = a &gt; b
        let pa = (a &amp; 1) == 0
        let pb = (b &amp; 1) == 0

        if pa and pb and a != 0 and b != 0: shift++
        if pa: a &gt;&gt;= 1
        if pb: b &gt;&gt;= 1
        if not pa and not pb:
            if g:
                a -= b
                a &gt;&gt;= 1
            else:
                b -= a
                b &gt;&gt;= 1

        # We can't clear these yet, so just set them aside until later
        push g, pa, pb

    let result = (a | b) &lt;&lt; shift

    # Uncompute intermediate values
    for i in range(n + m):
        pop pb, pa, g

        if not pa and not pb:
            if g:
                a &lt;&lt;= 1
                a += b
            else:
                b &lt;&lt;= 1
                b += a
        if pb: b &lt;&lt;= 1
        if pa: a &lt;&lt;= 1
        if pa and pb and a != 0 and b != 0: shift--

        unlet pb = (b &amp; 1) == 0
        unlet pa = (a &amp; 1) == 0
        unlet g = a &gt; b

    unlet shift = 0
    return result

Convert to a circuit.

(Edit: oops, I forgot the shift part. You'll have to add that part in yourself.)




It takes $O(n)$ iterations to guarantee the inputs have been reduced all the way down, and each iteration requires $\Omega(\lg n)$ depth and $O(n)$ gates so the overall bound is $O(n^2)$ gates and $O(n \lg n)$ depth.

Now, all that being said, you need to be wary of the fact that the result is not totally coherent. Before doing interference-y stuff with it, I'd want to be a lot more careful about ensuring the stashed ancilla are independent of the computed gcd. Also you'd want to do any computation in the middle so that the result doesn't have to co-exist with the inputs.

But I hope this gives the general idea.