[Q# API Design Discussion] July 24, 2020

[cgranade]

This discussion issue is intended to track topics from the Q# API Design meeting on July 24, 2020, following the notes in #305. Please see complete notes from API Design meeting at https://github.com/microsoft/QuantumLibraries/blob/master/Design/meetings/2020/api-design-2020-07-24.md.

[bamarsha]

Introducing new arithmetic UDTs comes at a large cost: need to support in all future arithmetic APIs. Opportunity to improve existing support to better cover BigInt (https://github.com/microsoft/QuantumLibraries/issues/95).

Could type classes reduce this cost? If APIs that are written in terms of concrete arithmetic types are rewritten using more general type classes, new arithmetic types could get a lot of functions for free by implementing the corresponding type classes.

Also, I am curious why we need both Complex and ComplexPolar, and LittleEndian and BigEndian. It seems like we could pick canonical forms for both of those.

[cgranade]

Could type classes reduce this cost? If APIs that are written in terms of concrete arithmetic types are rewritten using more general type classes, new arithmetic types could get a lot of functions for free by implementing the corresponding type classes.

Great point, @samarsha! In this case, I think it could help some to have a Numeric type class to help ensure that the new distribution concept has complete coverage over types bounded by Numeric. The details get a bit confusing to me here, though, in terms of what would work best out of making distributions a type-parameterized UDT (e.g.: newtype Distribution<'TVariate> = (Sample : (Unit => 'TVariate));) or a type class / concept (e.g.: concept 'TDistribution is Distribution<'TVariate> when { operation Sample(distribution : 'TDistribution) : 'TVariate; }). Trying out the latter way, I get a bit stuck at the end:

concept 'TDistribution is Distribution<'TVariate> when {
    operation Sample(distribution : 'TDistribution) : 'TVariate;
}

concept 'T is Numeric when { ... }
concept 'T is Bounded when {
    function (in)(value : 'T, (lower : 'T, upper : 'T)) : Bool;

    invariant Exclusive(value : 'T) : Unit {
        Contradiction(value in (value, value), "Expected intervals to be exclusive.");
    }
}
concept 'TRegion is SupportRegion<'TDistribution, 'TVariate where 'TVariate is Numeric, 'TDistribution is Distribution<'TVariate>> when {
    function UniformDistribution(region : 'TRegion) : 'TDistribution;
}

// I'm a bit stuck here, it feels like 'TDistribution is acting more like a UDT than a bounded type parameter.
example (Double, Double) of SupportRegion<???, Double> {
     function UniformDistribution(region : (Double, Double)) : 'TDistribution;
}

Modifying to use a type-parameterized UDT:

newtype Distribution<'TVariate> = (
    Sample : (Unit => 'TVariate)
)

concept 'T is Numeric when { ... }
concept 'T is SupportRegion<'TVariate where 'TVariate is Numeric> when {
    function UniformDistribution(region : 'T) : Distribution<'TVariate>;
}

example (Double, Double) of SupportRegion<Double> {
     function UniformDistribution(region : (Double, Double)) : Distribution<Double> {
         // much better with a lambda....
         return Delay(SampleUniformDistribution, region, _);
     };
}

internal operation SampleUniformDistribution(region : (Double, Double)) : Double { ... }

That wouldn't save a lot of work in actually implementing the new API, but would make it much harder to "miss" coverage, and would make it a lot easier to discover and predict how to use the new API.

Also, I am curious why we need both Complex and ComplexPolar, and LittleEndian and BigEndian. It seems like we could pick canonical forms for both of those.

BigEndian has been dropped almost entirely, and is only there for back-compat; we settled on LittleEndian as a single canonical form. As for ComplexPolar, there's a fair point as well; there's a lot of places where the polar representation is much more useful, but that may simply justify an internal UDT rather than increasing API surfaces.

[bamarsha]

Not sure I understand all the details, but at first glance it does seem simpler to have a distribution be an operation type rather than a type class.

BigEndian has been dropped almost entirely, and is only there for back-compat; we settled on LittleEndian as a single canonical form. As for ComplexPolar, there's a fair point as well; there's a lot of places where the polar representation is much more useful, but that may simply justify an internal UDT rather than increasing API surfaces.

What is the benefit to coupling the representation with the type? I would expect, instead of LittleEndian and BigEndian, something like Quint as an extension of Qubit (see microsoft/qsharp-compiler#406).

// Feature request: public types with internal type constructors.
newtype Quint = internal Qubit[];

function LittleEndian(qs : Qubit[]) : Quint { ... }
function BigEndian(qs : Qubit[]) : Quint { ... }
function AsLittleEndian(i : Quint) : Qubit[] { ... }
function AsBigEndian(i : Quint) : Qubit[] { ... }

Similarly with Complex and ComplexPolar, both .NET and Haskell have one type for both Cartesian and polar coordinates.

[cgranade]

BigEndian has been dropped almost entirely, and is only there for back-compat; we settled on LittleEndian as a single canonical form. As for ComplexPolar, there's a fair point as well; there's a lot of places where the polar representation is much more useful, but that may simply justify an internal UDT rather than increasing API surfaces.

What is the benefit to coupling the representation with the type? I would expect, instead of LittleEndian and BigEndian, something like Quint as an extension of Qubit (see microsoft/qsharp-compiler#406).

Compatibility again; we used to have both BigEndian and LittleEndian at one point and in moving away from BigEndian, we didn't take the opportunity to introduce QInt instead.

// Feature request: public types with internal type constructors.
newtype Quint = internal Qubit[];

That would definitely be nice, though would leave how to allocate a QInt value with a using statement.

function LittleEndian(qs : Qubit[]) : Quint { ... }
function BigEndian(qs : Qubit[]) : Quint { ... }
function AsLittleEndian(i : Quint) : Qubit[] { ... }
function AsBigEndian(i : Quint) : Qubit[] { ... }

I honestly don't think you'd even need these functions, so much as to have most API calls which require bare Qubit[] modified to instead take examples of the UnwrappableTo<Qubit[]> concept, perhaps with one new concept to allow Qubit[] itself to be used:

concept 'T is RegisterLike when {
     function AsRegister(input : 'T) : Qubit[];
}

example <'T> UnwrappableTo<'T where 'T is RegisterLike> of RegisterLike {
     function AsRegister(input : 'T) : Qubit[] {
        return Unwrap(input);
     }
}
example Qubit[] of RegisterLike {
     function AsRegister(input : Qubit[]) : Qubit[] {
        return input;
     }
}

Borrowing an example from https://github.com/microsoft/Quantum/pull/403/files:

function ControlledOnEquality<'Target, 'Control where 'Control is RegisterLike>(op : ('T => Unit is Adj + Ctl)) : (('Control, 'Control, 'T) => Unit is Adj + Ctl)) {
   // ...
}

This would let you do things like ControlledOnEquality(X)(qint0, qint1, target); to flip target when qint0 and qint1 are both in the same state, even if they're represented as QInt instances.

[cgranade]

Closing in lieu of latest discussion thread, #369.