New functions for singly controlled operations

[cgranade]

Functions for singly controlled operations

Conceptual overview

The Q# language provides the Controlled functor to control operations on quantum registers of arbitrary size. It is often conveinent, however, for operations to accept exactly one control qubit. For example, Controlled X has type (Qubit[], Qubit) => Unit is Adj + Ctl, allowing for an arbitrary number of control qubits, but the shorthand CNOT has type (Qubit, Qubit) => Unit is Adj + Ctl. This shorthand is especially useful together with combinator operations such as ApplyToEachCA:

ApplyToEachCA(CNOT, Zipped(controls, targets));

Current status

For operations other than X, no such shorthand may exist in general. For example, on a recent stream, @crazy4pi314 used the following snippet combining ApplyToEachCA with IncrementByInteger to count the Hamming weight of a control register:

ApplyToEachCA(
    (Controlled IncrementByInteger)(_, (1, target)),
    Mapped(ConstantArray(1, _), controls), 
);

In this example, mapping ConstantArray(1, _) is needed to add another level of nesting to controls, and is only needed because
(Controlled IncrementByInteger)(_, (1, target)) has type Qubit[] => Unit is Adj + Ctl (that is, takes an arbitrary number of control qubits).

User feedback

See above example from @crazy4pi314's stream at https://www.twitch.tv/crazy4pi314.

Proposal

New and modified functions, operations, and UDTs

namespace Microsoft.Quantum.Canon {

    /// # Summary
    /// Given a controllable operation, returns a controlled version of that operation
    /// accepting exactly one control qubit.
    ///
    /// # Input
    /// ## op
    /// The operation to be controlled.
    ///
    /// # Output
    /// A controlled variant of `op` accepting exactly one control qubit.
    ///
    /// # Example
    /// To add the weight (number of "1" bits) of a control register to
    /// a target register:
    /// ```qsharp
    /// ApplyToEachCA(
    ///     (SinglyControlled(IncrementByInteger))(_, (1, target)),
    ///     controls)
    /// );
    /// ```
    ///
    /// # See Also
    /// - Microsoft.Quantum.Canon.SinglyControlledA
    function SinglyControlled<'T>(op : ('T => Unit is Ctl)) : ((Qubit, 'T) => Unit is Ctl ){
        // ..
    }

    /// # Summary
    /// Given a controllable operation, returns a controlled version of that operation
    /// accepting exactly one control qubit.
    ///
    /// # Input
    /// ## op
    /// The operation to be controlled.
    ///
    /// # Output
    /// A controlled variant of `op` accepting exactly one control qubit.
    ///
    /// # Example
    /// To add the weight (number of "1" bits) of a control register to
    /// a target register:
    /// ```qsharp
    /// ApplyToEachCA(
    ///     (SinglyControlledA(IncrementByInteger))(_, (1, target)),
    ///     controls)
    /// );
    /// ```
    ///
    /// # See Also
    /// - Microsoft.Quantum.Canon.SinglyControlled
    function SinglyControlledA<'T>(op : ('T => Unit is Adj + Ctl)) : ((Qubit, 'T) => Unit is Adj + Ctl) {
        // ..
    }

}

Modifications to style guide

No modifications required. New functions in this proposal follow the pattern of CControlled, ControlledOnInt, and so forth by exposing functor-like callables as ordinary functions.

Impact of breaking changes

n / a

Examples

See above.

Relationship to Q# language feature proposals

n/a

Alternatives considered

• Do nothing. We could consider leaving the current state of the libraries as-is.
• New array functionality. Rather than making shorthand for singly controlled operations, we could make it easier to prepare registers of the form [[c0], [c1], ...] by adding new array functions.
• Bounded polymorphism in the Controlled functor. We could consider adopting language proposals such as bounded polymorphism to allow the Controlled functor to accept either single qubits or arrays thereof.

Open design questions and considerations

• Should doubly or triply controlled variants be added as well (i.e.: similar to CCNOT)?

[tcNickolas]

Proposal looks good, a couple of comments:

• In the API docs example for SinglyControlled, should ApplyToEachCA be ApplyToEachC (since there's no adjoint variant defined)?
• I looked through the code of the Katas to see what patterns for control wrappers I use, and while I use single-controlled operations quite often, I couldn't find any doubly or triply controlled calls. I think for now we can add just single-controlled operations.
• A fresh alternative is using lambdas, but it's not something I expect the user to come up with immediately, more listing for completeness:

ApplyToEachCA(
    (Controlled IncrementByInteger)(_, (1, target)),
    Mapped((q -> [q]), controls), 
);

[msoeken]

Resolved by #552