Make it easier to implement circuits described using mutable arrays

[Strilanc]

I was trying to implement the carry lookahead adder from https://arxiv.org/pdf/2004.01826.pdf . it has a step described like this:

As you can see, their description involves storing a reference to an initialized qubit into an array, which will be used during later steps.

Currently, it is difficult to implement this in Q# because:

1. The syntax for mutating an array-of-arrays is extremely verbose.
2. set lines prevent the creation of an automatic adjoint.
3. Qubits need to be allocated outside the nested loop, requiring you to separately calculate the total number you need to allocate instead of just relying on the loop to do it.

I'm not exactly sure how to fix this, but it's something that I've run into more than once.

Here are some ideas:

1. Have a concept of a "qubit pool", which you can iteratively ask for more qubits from and where all the qubits are deallocated when the pool goes away. Using a pool would prevent the automatic creation of an adjoint:

using (pool = QubitPool()) {
    for (...complicated...) {
        let q = pool.allocate_another();
    }
}

2. Add support for mutable arrays, and/or multi-dimensional arrays, and/or hash maps. Support syntax like set map[(i, j)] = x.

3. Allow the use of set statements inside of auto-adjoint operations as long as they invoke no operation that returns a value (except perhaps for some whitelisted special case operations like allocation). Implement these methods by executing them forwards, with all operations replaced by no-ops, recording the historical state of mutable variables. Then rewind while applying the inverses of the operations.

[cgranade]

Thanks for sharing this feedback! With respect to "the syntax for mutating an array-of-arrays is extremely verbose," would the changes proposed at https://github.com/microsoft/qsharp-language/pull/49 address your usecase?

[Strilanc]

Yes, that would help here.

[bettinaheim]

@Strilanc Would you be able to share an example of the code as it needs to be now? If I understand correctly how you use set, then it would be possible to isolate the isolate the population of the arrays into a function such that you can use automatic adjoint. Array comprehension is another idea we've been thinking about. Chris already mentioned multidimensional arrays that should help with this in the future as well. To understand what we can do for the rest, a code example would be really helpful.

[Strilanc]

@bettinaheim I did manage to rewrite the code into a more functional form with everything pre-allocated https://github.com/Strilanc/quantum-block-lookahead-adder/blob/master/anc/src/adder_lookahead.qs#L135 . But I think it's fair to say that the new form is a bit harder to follow the details of, and it certainly took more work than it would have otherwise.