Allocatable types and generalization of initializers

[bettinaheim]

Suggestion

The suggestion is to generalize the mechanism for [qubit allocations] in Q# to cover the following scenarios by introducing a more general notion of initializers for qubit allocations:

• Creating instances of user defined types containing qubits
• Initializing the allocated qubits with a certain operation upon allocation
• Automatic allocation and deallocation of temporary qubits used during initialization

The suggestion applies to both using- and borrowing statements, and allows to instantiate values of a broad range of allocatable types instead of just values of type Qubit, Qubit[], and tuples thereof. The suggestion involves introducing a new keyword init that allows to elevate adjointable operations to initializers for the sake of supporting the second bullet point above.

Considerations

All of the above is possible to express with the current version of Q#, but the syntax for expressing that is somewhat verbose. Extending the concept of initializers and adding the necessary compiler support for automation of these scenarios allows to express them in a much more natural and readable manner. Any quantum transformations executed upon initializations are automatically reverted upon deallocation.

I believe the concept of initializers can be extended to cover a broader range of types in a consistent manner, without sacrificing any of the guarantees that Q# currently gives and in a way that can be executed on quantum hardware; it should always be possible to bound the number of required qubits by imposing a size limit on the call stack, much like it is the case for the current version of Q#.

The suggested generalizations greatly enhance the expressiveness of Q#. At the same time, it should be possible to translate the additional capabilities and syntax into the current version of the Q# language, such that the suggestion merely involves introducing additional syntax and automation capabilities. The examples below illustrate the suggested mechanism in more detail.

Context

Even though Q# does not currently support defining custom constructors for types, this would be a good addition to the language in the future. As part of a proposal for generalizing initializers, it is hence important to consider how the introduced concepts would work if custom constructors are supported. As part of a potential proposal, it also makes sense to discuss the implementation for supporting the nesting of initializers as part of initializer expressions in detail.

Furthermore, the restrictions that need to be imposed on operations to ensure that they can be elevated to initializers need to be clarified. Besides the requirement that such operations need to be adjointable, it may make sense to impose restrictions on whether or not the operations in question may capture (certain) qubits. If it is possible for such operations to capture qubits, then it giving guarantees regarding whether the un-computation of the allocated qubits is successful would be challenging. Alternatively, it may make sense to distinguish when an operation is (only) intended to be applied upon initialization, versus when its adjoint should also be applied before deallocation.

For the sake of consistency in syntax, it is reasonable to make one breaking change at part of this proposal. Concretely, the suggested breaking change is to replace the current syntax Qubit[n] that is used to initialize an array of qubits with Qubits(n). The exact syntax is to be determined as part of the proposal, and it needs to be possible to potentially extend it to the multi-dimensional case in a consistent manner in the future.

Related suggestions/proposals: https://github.com/microsoft/qsharp-language/issues/14, https://github.com/microsoft/qsharp-language/issues/39.

Examples

I will adopt the simplifications for qubit allocations that are currently under review in the given examples for the sake of convenience, though the examples remain valid also if only the current syntax is available.

Example 1: Initializing values of various types to various states
The following statements are valid within operations if this suggestion is adopted, where init is a newly introduced keyword used to elevate (certain) adjointable operations to initializers:

use q = Qubit();    // q contains a single qubit in a state |0>
use qs = Qubits(3);    // qs contains a 1D array of 3 qubits in a state |000>
use qInt = BigEndian(3);    // qInt contains a BigEndian value containing an array of 3 qubits in a state |000>
use xq = init H;    // xq contains a single qubit  in a state |+>
use xqs = init(3) ApplyToEachA(H, _);    // xqs contains a 1D array of 3 qubits in a state |+++>
use register = init(4) ApproximateQFT(4, _);  

For an operation ApproximateQFT as defined here, register will be bound to a value of type LittleEndian containing an array of 4 qubits initialized to QFT |0000> (i.e. to a uniform superposition). The last line in the example above can be translated into the following upon compilation:

use __var1__ = Qubits(4) {
    let register = LittleEndian(__var1__);
    within { ApproximateQFT(4, register); }
    apply {
        // code within the allocation scope
    }
}

Example 2: Nesting of initializer expressions and potential future syntax enhancements
If we were to allow for elevated operations to capture qubits, then introducing additional syntax sugar for particular operations, such as e.g. a coherent version of a logical AND would allow to express oracles constructed from such operators in the following way, if this suggestion is adopted:

use res = q1 <and> q2 <and> q3; 

where the right hand side is syntactic sugar init And(init And(q1, q2, _), q3, _), and q1, q2, q3 are existing qubits that are in scope. The statement above could be translated into the following upon compilation:

use res = Qubit() {
    within {
        use __var1__ = Qubit() {
            within { And (q1, q2, __var1__); } 
            apply { And (__var1__, q3, res); }
        }
    }
    apply {
        // code within the allocation scope
    }
}

Introducing additional syntax for coherent versions of logical operators is outside the scope of this proposal, but should be considered as part of the discussion on interactions with future modifications.

Affidavit (please fill out)

Please add ticks by placing a cross in the box:

• [x] I have searched both open and closed suggestions and proposals on this site and believe this is not a duplicate.
• [x] I believe that the spirit of this suggestion is aligned with the design principles and general vision for Q#.

Please tick all that apply:

• [ ] This is not a breaking change to the Q# language design
• [x] I or my organization would be willing to help implement and/or test this

[bettinaheim]

@alan-geller @cgranade I could use some additional eyes on the automatic un-computation piece, and what kinds of guarantees, if any, would be good to give. While it is perfectly possible to express the same thing with the current syntax, the proposed abbreviations also hide what it going on, so it may not be as straightforward to realize when qubits are not properly un-computed before deallocation. Please take a look and let me know your thoughts. The same of course goes for anyone else who has a couple of minutes to look at this.

[cgranade]

@alan-geller @cgranade I could use some additional eyes on the automatic un-computation piece, and what kinds of guarantees, if any, would be good to give. While it is perfectly possible to express the same thing with the current syntax, the proposed abbreviations also hide what it going on, so it may not be as straightforward to realize when qubits are not properly un-computed before deallocation. Please take a look and let me know your thoughts. The same of course goes for anyone else who has a couple of minutes to look at this.

Thanks for tagging me in, @bettinaheim! I'm really excited for this one, I think it will really help reduce some difficult-to-read boilerplate for some fairly common use cases (e.g.: allocating qubits that we only want to use in the context of a UDT).

In particular, I really like the uncomputation piece, as it suggests a nice interpretation to use and init: the compiler promises that a register is prepared in a particular state, and the developer promises to return the register to that state or to leave it measured so that the compiler can add the right reset instructions automatically. Taking that view, the "return to |0⟩" interpretation is an important special case. Similarly, borrow then is another important special case; namely, where the developer doesn't know which initializer has been called.

[bettinaheim]

@cgranade Measurements are an interesting question that I hadn't though about enough. Thanks for bringing it up! Thinking about optimizing, it may make sense to have a minimal runtime addition after all. I'll detail it more in the proposal.

[cgranade]

@bettinaheim: One thing that occurs to me with measurement vs coherent unpreparation is that at the moment, there's no ambiguity between the two because developers are never required to return qubits to an entangled state in order to release them. By contrast, this could be a bit fun with the proposal here:

operation ApplyFoo() : Result {
    use (left, right) = init() PrepareEntangledPair;
    return M(left);
}

At the point where result is returned, left can be automatically reset by the compiler, since it has been measured. Even though the state of right is known exactly given the result of measuring left, however, it cannot be automatically reset without explicitly modelling qubit state in the runtime. Should it be an error to release right at that point, since the compiler cannot verify to perform an automatic reset? If so, should the Adjoint PrepareEntangledPair operation be called?

I could imagine resolving by requiring that you measure all of an initialized value in order to take advantage of automatic reset behavior. That would mean that in the above snippet, releasing right would be an error since only left was measured. On the other hand, introducing that rule would mean that if you do something like use query = init(5) ApplyToEach(H, _);, then each qubit in query would need to be measured, even if the final state before releasing is provably not an entangled state.

[bettinaheim]

@bettinaheim: One thing that occurs to me with measurement vs coherent unpreparation is that at the moment, there's no ambiguity between the two because developers are never required to return qubits to an entangled state in order to release them. By contrast, this could be a bit fun with the proposal here:

operation ApplyFoo() : Result {
    use (left, right) = init() PrepareEntangledPair;
    return M(left);
}

At the point where result is returned, left can be automatically reset by the compiler, since it has been measured. Even though the state of right is known exactly given the result of measuring left, however, it cannot be automatically reset without explicitly modelling qubit state in the runtime. Should it be an error to release right at that point, since the compiler cannot verify to perform an automatic reset? If so, should the Adjoint PrepareEntangledPair operation be called?

I could imagine resolving by requiring that you measure all of an initialized value in order to take advantage of automatic reset behavior. That would mean that in the above snippet, releasing right would be an error since only left was measured. On the other hand, introducing that rule would mean that if you do something like use query = init(5) ApplyToEach(H, _);, then each qubit in query would need to be measured, even if the final state before releasing is provably not an entangled state.

Things become even more interesting if we were to allow that the operation that is elevated to serve as initializer captures qubits that are not allocated as part of the allocation statement. In your example above, I believe it would be fair to require that all qubits need to be measured, but in general, what the expected behavior should be to me is not that obvious. It may be worth thinking about whether there should be two distinct ways to initialize qubits; one where the initialization is undone, and one where it's not, but I need to think more about that first.

[swernli]

I wonder if there is any inspiration to be gleaned from the std::unique_ptr from C++11. There you can optionally provide not only the input pointer or function that initializes the pointer but also the Deleter method that will handle the clean-up and deallocation of the memory. By default it is just the std::default_delete, which in our case for qubits is essentially Reset (with the massive caveat that Reset on a qubit that is entangled may have unintended consequences on other parts of the system). The Windows Implementation Library (WIL) then uses this as the design foundation for a number of common RAII resource patterns, including the super flexible wil::scope_exit that allows an arbitrary lambda to be executed when the object goes out of scope.

I know all of those patterns utilize types and inheritance in a way that doesn't match Q#, but they could still be inspiration for whatever we could consider adopting.

[bettinaheim]

I put up a draft for the PR to flesh out the details here: https://github.com/microsoft/qsharp-language/pull/41

[cgranade]

As per offline discussion, I wanted to share an example of how existing Q# syntax is used to solve the same problem. In particular, a very common workflow for code that uses the numerics library is to allocate a register to represent an integer, and then to prepare a particular integer in that register.

let value = 13;
let nQubits = BitSizeI(value);
using (qs = Qubit[nQubits]) {
    let register = LittleEndian(qs);
    within {
         // prepare the new register
        ApplyXorInPlace(value, register);
    } apply {
        // ...
    }
}

If the register is measured or reset at the end, then the above can be simplified a little bit.

let value = 13;
let nQubits = BitSizeI(value);
using (qs = Qubit[nQubits]) {
    let register = LittleEndian(qs);
    ApplyXorInPlace(value, register);
    // ...
    ResetAll(qs); // ← not needed if qs is measured
}

[msoeken]

Could we use this technique for operations that require helper qubits that cannot be cleaned up internally and therefore need to be allocated outside of the operation? If also the number of helper qubits is not known, a typical pattern at the moment is the following:

let (nGarbage, op) = MyOperation(parameters);
using ((garbage, qubits) = (Qubit[nGarbage], Qubit[10])) {
   op(garbage, qubits);
}

A similar paradigm is currently in use in M.Q.Preparation.QuantumROM.

[msoeken]

Manual layout is another use case for which generalization of initializers can be useful. Assume we'd like to allocate a 10 x 20 grid of qubits. We could do this in the following way, assuming that #39 is available:

newtype GridQubits = Qubit[,];

use grid = GridQubits(10, 20);

This is everything from the language point-of-view. Inside a possible runtime implementation, it would be important that qubit allocation can be controlled based on the UDT; in this case, GridQubits. A simulator can then ensure that a continuous array of qubits is returned for the grid, and could impose runtime checks to ensure that grid constraints are obeyed.