search

microsoft / qsharp

Azure Quantum Development Kit, including the Q# programming language, resource estimator, and Quantum Katas
https://microsoft.github.io/qsharp/
MIT License
369 stars 73 forks source link

Expand support for the `Microsoft.Quantum.Arrays` namespace. #315

Open cesarzc opened 1 year ago

cesarzc commented 1 year ago 
### Tasks
- [x] Implement functions that do would not benefit from lambdas (#324)
- [x] Implement functions for which lambdas would be useful (#350).
cesarzc commented 1 year ago

The documentation for the function in the Microsoft.Quantum.Arrays namespace can be found here.

Regarding the Microsoft.Quantum.Arrays namespace, the following functions are the ones that I think we should support:

The ones that I think we should not support in the short term are the following:

The ones that might belong to a different namespace:

The ones that we should slightly modify:

The ones that I think we should no longer support are the following:

Functions that we could add besides the ones that are already present in the current public version:

@DmitryVasilevsky, @swernli what do you think about these lists?

DmitryVasilevsky commented 1 year ago

Minor note. I'm a bit puzzled that Mapped and ForEach are the same except that one is a function and another is an operation. Kind of hard to discover.

bamarsha commented 1 year ago

About naming conventions, you should read: https://learn.microsoft.com/en-us/azure/quantum/contributing-style-guide?tabs=guidance. The suffixes (A, C, CA, I, L, D) were chosen to be short (1-2 letters) because of how common they are. Although I agree that eventually they can go away given type system improvements.

  • EqualA: we could consider renaming it to just Equal?

I think we can drop this. EqualA was needed because a lot of types in Q# didn't support ==. The new compiler lets you use == for most types, including arrays. UDTs still don't allow it, but that can be added easily as well.

  • IndexOf: we could consider renaming it to First to align with the naming used in other languages and libraries.

First sounds like it returns the first element of the array, not the first index matching a predicate.

  • ConstantArray: the new array syntax effectively does this let array = [Zero, size=10]

I think this array fill syntax was a mistake. (I have a lot of reasons for this, if you want me to explain.) I would prefer to remove the syntax and keep the library function (possibly with a different name).

  • EmptyArray: the new array syntax allows users to do this: let array = [Zero, size=0].

[] is the syntax for empty array.

  • _SwapOrderToPermuteArray: the justification to not support this one is also a bit subjective. IMO, this seems overly specific.

This is an internal function. Note the _ prefix.

DmitryVasilevsky commented 1 year ago

Agree with @samarsha on the following: First - does sound like the first element of the array. I even confused it with Head and thought it was used. [] - is an excellent syntax for an empty array. Type can be derived by its use (or provided on a variable it is assigned to). As for constant array, I have mixed feelings. Seems like a common case to allocate an array with each element initialized to some value.

bamarsha commented 1 year ago

As for constant array, I have mixed feelings. Seems like a common case to allocate an array with each element initialized to some value.

I definitely agree that it's a common case that we should support concisely. But creating custom syntax should be reserved for things that can't easily be accomplished with a standard library function. For example, something like Repeated(count, value) can do the same thing as [value, size = count].

DmitryVasilevsky commented 1 year ago

Also there's a pattern to populate arrays like this:

        mutable retval = [f(array[0]), size = length];
        for idx in 1..length - 1 {
            set retval w/= idx <- f(array[idx]);
        }

It's kind of unnatural and doesn't work for empty arrays. Would like to see something like this:

        mutable retval = [size = length];
        for idx in 0..length - 1 {
            set retval w/= idx <- f(array[idx]);
        }

I'm not talking about exact syntax. What I don't like is treating the first element in a special way, and putting it into every element of the array. Can we do better?

swernli commented 1 year ago

Array concatenation is more costly in terms of reallocations but avoids special handling:

mutable retval = [];
for elem in array {
    set retval += [f(elem)];
}
bamarsha commented 1 year ago

Yeah, since unfolding a sequence is such a common pattern, I think having some standard library support for it would make sense. You could have InitArray(length, idx -> f(array[idx])) for this case. (Although in this specific example, it's just Mapped(f, array)...) In general, there could be accumulated state, for which you'd need something more powerful like UnfoldArray(length, init, (acc, idx) -> (f(array[idx] * acc), acc + 1)).

We could have syntactic sugar for this in the form of array comprehensions, so that you could write something that looks more like a for loop but has the same semantics as unfolding.

I think we should avoid allowing users to create arrays with uninitialized memory, though, like in this example:

mutable retval = [size = length];
DmitryVasilevsky commented 1 year ago

@swernli, array concatenation is the cleanest pattern, but can we implement it efficiently?

DmitryVasilevsky commented 1 year ago

@samarsha, some environments have array size and array capacity. This way 'uninitialized' part of the array is inaccessible to the user.

bamarsha commented 1 year ago

Part of the problem in talking about performance is that arrays are immutable. If you could create an array with reserved capacity, you could never write into that extra memory, because that array can never change. Like in this example:

        mutable retval = [f(array[0]), size = length];
        for idx in 1..length - 1 {
            set retval w/= idx <- f(array[idx]);
        }

It isn't actually mutating the original array. It's copying it to a new array with one index changed, then reassigning the new array to retval, and repeating.

This can be optimized away. With QIR, LLVM is doing static optimization. With .NET, it was a runtime check if the array had a ref count of one. But it's not guaranteed by the language. So it's difficult to talk about having the language guarantee that capacity in an array is reserved when it can't even guarantee that you can mutate that array.

That's why I see two options:

  1. Embrace immutability and require you to create an array in one shot, with an initialization function.
  2. Embrace mutability and allow you to reserve capacity in an array, then mutate it to fill that capacity.
DmitryVasilevsky commented 1 year ago

From @swernli : we have MeasureEachZ that does a non-resetting measure across a qubit array, should we have something like a MResetEachZ to have a version of this that doesn't require passing an operation across a call boundary?

filipw commented 11 months ago

The ones that I think we should no longer support are the following:

I think it would much nicer if they were all there, but simply marked with a deprecated attribute (and then can be removed at some point later). There is quite some content out there already and having things compile with the existing QDK and not with the new compiler is not great. Backwards compatibility is important, especially where it's not too problematic (no intrinsic implementations). Alternatively, it would be good to have at least an optional bridge/polyfill package that one can include to restore backwards compatibility.

Already now having https://quantum.microsoft.com/en-us/experience/quantum-coding some of the code from the QDK not be able to compile existing stuff that worked with QDK is very confusing. And the site could be flagged with a warning that your existing code might not work.