microsoft / qsharp-language

Official repository for design of the quantum programming language Q# and its core libraries
MIT License
235 stars 56 forks source link

Add "if running forward" conditioning #60

Closed Strilanc closed 3 years ago

Strilanc commented 3 years ago

Here is an operation that I've found myself defining:

    operation ForwardOnlyCCNot(a: Qubit, b: Qubit, c: Qubit) : Unit {
        body (...) {
            CCNOT(a, b, c);
        }
        adjoint (...) {
        }
    }

So that I can write code like this:

            within {
                for (t in 0..CeilLg2(n)-2) {
                    for (a in 0..2 <<< t..n) {
                        let b = a + (1 <<< t);
                        let c = a + (2 <<< t);
                        if (c < n) {
                            ...
                            init_and(t_b2c, t_a2b, centered_thresholds[b]);
                            ForwardOnlyCCNot(t_b2c, _range_g(a, b, out_c), _range_g(b, c, out_c));
                        }
                        if (b < n) {
                            ...
                            Adjoint ForwardOnlyCCNot(t_a2b, out_c![a], _range_g(a, b, out_c));
                        }
                    }
                }
            } apply {
            }

The idea here is that reversible code often runs forwards and then backwards almost identically. The variations between the backward and forward pass are not always directly in the center of the execution. When that happens, being able to make a few tweaks between the forward and backward pass can allow significantly more code reuse.

It seems silly to define a custom operation for this. It feels like it should be a language feature. Perhaps I should be able to say something like:

if [runningforward] {
    ...
} else {
    ...
}

This could also be used to make some manual adjoint implementations more compact, since they could be a slight if runningbackward tweak within the body.

Affidavit (please fill out)

Please add ticks by placing a cross in the box:

Please tick all that apply:

Strilanc commented 3 years ago

So, after having completely confused myself due to a bug that resulted from doing this sort of thing, I have switched to thinking it's a terrible idea.

The basic problem is that this assumes that if you have a method like

    operation E() : Unit is Adj {
        Asymmetric();
        Adjoint Asymmetric();
    }

Where the operations applied within the body of Asymmetric are self-inverse, then you want the inverse of E to be

        Adjoint Asymmetric();
        Asymmetric();

But it's actually, correctly, computed to be

        Asymmetric();
        Adjoint Asymmetric();

Basically it doesn't compose right.