Add the concept of an rvalue

[Strilanc]

One of the major pains of working with Q# is that a lot of slight variations on operations require special casing. For example, suppose I want to swap two registers if two LittleEndian registers are equal, and I have already written methods to prepare the equality result and do a swap conditioned on a control. Further assume I am trying to be efficient and want to avoid redundant recomputation of ancillae when uncomputation the equality result. Then I am basically forced to write this:

use control_holder = Qubit();
use temporary_ancillae = Qubit[n];
within {
    init_equality_result(a, b, temporary_ancillae, control_holder);
} apply {
    Controlled swap_registers([control_holder], (c, d))
}

What I would like to write instead is this:

if a == b {
    swap(c, d);
}

but that's perhaps a bit ambitious so in this issue I will settle for suggesting this:

Controlled swap_registers([temporary_equals_result(a, b)], (c, d));

The intention here is that temporary_equals_result returns some kind of special type, called something like QubitExpression or QuantumRValue, which defines methods for initializing and uncomputing a result with automatically managed auxilliary storage. The idea is that these explicitly specified methods are explaining things like "there will be n ancillae whose lifetimes is tied to the lifetime of the result" and "you can use measurement based uncomputation when getting rid of the ancillae".

Anyways, I'm sure this needs a lot of refinement, but the inability to plug temporary expressions together and have the compiler automatically make sure they appear and disappear as needed in a LIFO ordering does strike me as one of the major reasons that writing Q# code produces a lot of boilerplate (and feels like such a slog) compared to writing expressions in other languages.

I did actually mock out this idea in https://github.com/Strilanc/quantumpseudocode and it seemed to work well. But it was severely hampered by that library's inability to automatically derive inverses, which is not a problem in Q#.

[Strilanc]

Here's a mockup to give you a sense of what I'm trying to convey here.

Things as they are now:

    operation aa_extract(
            map: AssociativeArray,
            address: LittleEndian,
            output: LittleEndian) : Unit is Adj {
        // Pad an extra entry onto the end of the value and address lists.
        // This is where the match will end up, if it's found.
        use extra_address_raw = Qubit[Length(map::addrs[0]!)];
        let extra_address = LittleEndian(extra_address_raw);
        let addrs = map::addrs + [extra_address];
        let vals = map::vals + [output];

        qi_invert(extra_address);
        qi_verify(output, 0L);

        // Determine if there's a match while moving the match to the end of the list.
        use found = Qubit();

        for k in 0..Length(vals)-2 {
            // Check if the current entry matches the target address.
            use eq = Qubit();
            qb_initΞ_qi_eq_qi(eq, address, addrs[k]);

            // Because we're dragging any match along with us, `eq` is the new value of `found`.
            SWAP(eq, found);

            // Uncompute the old value of `found` using the invariant that the address
            // list was sorted and that we are dragging any match along with us.
            if k > 0 {
                Controlled GreaterThan([found], (addrs[k-1], address, eq));
            }

            // Push any match towards the end of the list.
            Controlled qi_swapfor_qi([found], (vals[k], vals[k+1]));
            Controlled qi_swapfor_qi([found], (addrs[k], addrs[k+1]));
        }

        // Clear the extra address.
        Controlled qi_xorΞ_qi([found], (extra_address, address));
        within {
            X(found);
        } apply {
            Controlled qi_invert([found], (extra_address));
        }

        // Clear `found` using the invariant that only non-zero values are ever stored.
        Adjoint qb_initΞ_qi_nonzero(found, output);
    }

Things as they could be:

    operation aa_extract(
            map: AssociativeArray,
            address: LittleEndian,
            output: LittleEndian) : Unit is Adj {
        assert output == 0;

        // Pad an extra entry to hold the result.
        use extra_address = LittleEndian(-1, Length(map::addrs[0]!));
        let addrs = map::addrs + [extra_address];
        let vals = map::vals + [output];

        use found = Qubit();
        for k in 0..Length(vals)-2 {
            // Check if the current entry matches the target address.
            use eq = Qubit(address == addrs[k]);

            // `eq` is the new `found` because of how we drag the match along.
            swap found, eq;

            // Uncompute the old value of `found` using the invariant that the
            // address list was sorted and that we're dragging the match along.
            del eq = k > 0 and found and addrs[k-1] > address;

            // Push match towards the end of the list.
            if found {
                swap vals[k], vals[k+1];
                swap addrs[k], addrs[k+1];
            }
        }

        del extra_address = found ? address | -1;
        del found = output != 0;
    }