Add `uncompute` blocks to operations

[Strilanc]

It is often cheaper to uncompute an operation if you know that the result will be in the 0 state.

For example, if you know that the target qubit involved in a Toffoli operation will end up 0, you can perform the Toffoli with an X-basis measurement and a classically controlled CZ. This reduces the number of magic states required to perform an operation.

It is tedious to have to specify different names for the uncompute variants of operations. They should be merged, same as for adjoint and controlled operations.

(The tricky part of this, in terms of language design, is how to designate which qubits are being uncomputed.)

[vadym-kl]

Using current Q# capabilities it is possible to express the example you refer to by using a combination of Assert and adjoint ( which seems like what uncompute should do):

namespace CCXwithQubitInZero
{
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Extensions.Testing;

    /// # Summary
    /// Applies doubly controlled X to qubits assuming the target qubit is in zero state.
    /// For Adjoint version assumes that target qubit is returned back to zero
    /// after applying CCX.
    /// # Remarks 
    /// See Figure 3 in https://arxiv.org/pdf/1709.06648.pdf#page=3
    operation CCXwithTargetZero( control1 : Qubit, control2 : Qubit, target : Qubit ) : Unit {
        body(...) {
            AssertAllZero([target]);
            TStateFromZeroSt(target);
            CNOT(control1,target);
            CNOT(control2,target);

            CNOT(target,control1);
            CNOT(target,control2);
            
            Adjoint T(control1);
            Adjoint T(control2);
            T(target);

            CNOT(target,control1);
            CNOT(target,control2);

            H(target);
            S(target);            
        }
        adjoint(...) {
            AssertCCXTargetIsBackToZero(control1,control2,target);
            H(target);
            AssertProb([PauliZ],[target],One,0.5, "Probability of the measurement must be 0.5", 1e-10);
            if ( M(target) == One ) {
                Controlled Z([control1], control2); 
                X(target);
            }
        }
    }

    /// #Summary 
    /// Assert that target is going to be returned back to zero 
    /// after applying CCX
    operation AssertCCXTargetIsBackToZero( control1 : Qubit, control2 : Qubit, target : Qubit ) : Unit
    {
        With(
            ApplyToFirstThreeQubitsA(CCNOT,_),
            Assert([PauliI,PauliI,PauliZ],_,Zero,""),
            [control1,control2,target]);
    }

    /// # Summary 
    /// Uses CCXwithTargetZero to implement CCX with 4 T gates
    operation CCX( control1 : Qubit, control2 : Qubit, target : Qubit ) : Unit {
        body(...) {
            using( anc = Qubit() ) {
                WithA(CCXwithTargetZero(control1,control2,_),CNOT(_,target),anc);
            }
        }
        adjoint auto;
    }

    /// # Summary
    /// Creates |T⟩ state starting zero state
    operation TStateFromZeroSt ( target : Qubit ) : Unit {
        AssertAllZero([target]);
        H(target);
        T(target);
    }

    /// Test the correctness of CCX implementation
    operation CCXTest () : Unit {
        for( i in 0 .. 10 ) {
            AssertOperationsEqualReferenced(
                ApplyToFirstThreeQubitsA(CCX,_),
                ApplyToFirstThreeQubitsA(CCNOT,_),3);
        }        
        Message("Test passed");
    }
}

Note that AssertCCXTargetIsBackToZero must be replaced by NoOp for resource estimation purposes to get accurate gate counts.

[Strilanc]

I see. Yes, that is a good strategy for performing these kinds of operations-for-specific-states. Have a separate operation with an understood precondition (and postcondition for adjoint).