search

microsoft / QuantumLibraries

Q# libraries for the Quantum Development Kit
https://docs.microsoft.com/quantum
MIT License
541 stars 179 forks source link

Library support for multidimensional arrays #408

Open cgranade opened 3 years ago

cgranade commented 3 years ago

Library support for multidimensional arrays

Abstract and conceptual overview

Q# currently provides the array type 'T[] for any type 'T. By using arrays of arrays (i.e.: 'T[][]), Q# allows for representing multidimensional data. As discussed at https://github.com/microsoft/qsharp-language/pull/49, however, using nested arrays in this way presents a number of limitations.

This proposal builds on the work in https://github.com/microsoft/qsharp-language/pull/49 by providing a number of different library functions and operations to support the new multidimensional arrays in the corresponding Q# language proposal. For details on the motivation, justification, and context for both proposals, please see https://github.com/microsoft/qsharp-language/pull/49.

Proposal

New and modified functions and operations

This proposal introduces new functions and operations for creating, manipulating, and transforming multidimensional arrays (i.e.: values of type [|'T|], [||'T||], and so forth), extending the Microsoft.Quantum.Array namespace to support the new types introduced by https://github.com/microsoft/qsharp-language/pull/49. To distinguish functions acting on multidimensional arrays of distinct ranks, suffixes are used to denote the rank each function or operation acts on (e.g.: EmptyArray2 returns a value of type [|'T|] while EmptyArray3 returns a value of type [||'T||]). For brevity, we list only the rank-1, rank-2, and rank-3 variants of each proposed addition here, but the pattern should be continued to include multidimensional arrays of rank up to and including 8. For details on how to remove these suffixes using bounded polymorphism, please see "Relationship to Q# language feature proposals," below.

As an implementation detail, all of the functions and operations proposed here can be written in pure Q#, using the functions described in https://github.com/microsoft/qsharp-language/pull/49 to create and deconstruct multidimensional arrays from their underlying strides, offsets, and sizes.

Note that the list above does not include a few functions common in other frameworks, deferring to language Q# support in such cases (e.g.: np.ones((3, 3)) can be replaced by [| 1.0, size=(3, 3) |]).

Examples

TODO

Relationship to Q# language feature proposals

Bounded polymorphism (microsoft/qsharp-language#149)

The use of rank suffixes could be largely eliminated by using bounded polymorphism to represent common patterns, such as indexing and size.

For example:

concept 'TArray is IndexedBy<'TIndex, 'TElement> when {
    unction ElementAt(index : 'TIndex, array : 'TArray) : 'TElement;f
}
example <'T> ['T] is IndexedBy<Int, 'T> { ... }
example <'T> ['T] is IndexedBy<Range, 'T[]> { ... }
example <'T> [|'T|] is IndexedBy<(Int, Int), 'T> { ... }
example <'T> [|'T|] is IndexedBy<(Range, Int), ['T]> { ... }
example <'T> [|'T|] is IndexedBy<(Int, Range), ['T]> { ... }
example <'T> [|'T|] is IndexedBy<(Range, Range), [|'T|]> { ... }

function Subarray<'TArray, 'TIndex, 'TElement where 'TArray is IndexedBy<'TIndex, 'TElement>>(
    indices : ['TIndex], array : 'TArray
)
: 'TElement {
    return Mapped(ElementAt(_, array), indices);
}

Open design questions and considerations

cgranade commented 3 years ago

Edited to reflect recent changes in https://github.com/microsoft/qsharp-language/pull/49.

msoeken commented 3 years ago

Thanks for the proposal, @cgranade. Here are some comments:

cgranade commented 3 years ago

Thanks for the proposal, @cgranade. Here are some comments:

  • The return type seems broken in Reshaped2To3 and Reshaped3To3

Thanks for catching that typo!

  • Will there be a function called Size for consistency with Size2 and Size3. Would this function be identical to Length?

I'm somewhat reticent to introduce another function that is identical to Length but that has a different name; perhaps it would be worth renaming Length instead?