While, DoWhile, and linear states

[aborgna-q]

The While and DoWhile definitions contain to regions internally;

• A loop body with types *state -> *state
• A condition statement with types *state -> bool that decides when to stop the evaluation.

This is problematic when the state is linear; calling the condition forces us to discard the values.

The straightforward solution to this is to change the condition type to *state -> bool, *state.

---

For an alternative definition consider MLIR's scf.while. There we are able to use different types for the inputs and outputs of the loops.
That corresponds roughly to a jeff While where the regions have type:

• while: *in_state -> *out_state
• condition: *in_state -> bool, *out_state
• body: *out_state -> *in_state

Are we happy with the single-state?

[dime10]

Good point, I do think a single state for both regions is easier to think about, but maybe forcing all inputs to also be returned doesn't make too much sense?

The mlir while op can also support both while-do and do-while, which could use instead of two separate ones, but at the time we decided against it.

[burgholzer]

Following up here after today's discussion: Would there be any general objection to refactoring the while support in Jeff to align more closely with MLIR's scf.while for the added flexibility and expressiveness?

[dime10]

My only worry would be that a lot of quantum representations I've come across wouldn't support a "hybrid" while loop (an in between of a do-while and a while-do), even if they support while loops. MLIR describes their while op as follows:

This operation represents a generic “while”/“do-while” loop that keeps iterating as long as a condition is satisfied. There is no restriction on the complexity of the condition. It consists of two regions (with single block each): “before” region and “after” region. The names of regions indicates whether they execute before or after the condition check. Therefore, if the main loop payload is located in the “before” region, the operation is a “do-while” loop. Otherwise, it is a “while” loop.

The fact that our current condition region forces a single bool return guarantees that we cannot produce any new values in it, especially new quantum states. But maybe my concern is less of a problem than I think it is? In which case matching the mlir op 1:1 would certainly simplify things for us.

[burgholzer]

Hm. I would argue that, eventually, hardware won't really see structured control flow. If one compiles down to QIR, all of these constructs simply become conditional jumps anyway. And to the best of my understanding, MLIR already has all the tooling to lower these constructs down to LLVM IR.
But maybe I am overlooking something. Maybe @aborgna-q has opinions here as well?

[denialhaag]

A short summary of today's meeting: We can proceed with one of three options:

1. The condition block does not execute any code and accepts only an int(1). The body block yields this int(1) and the other iteration arguments. The int(1) evaluated by the condition block is the first yielded value.
2. Similarly to the current implementation, the condition block can read the state and compute classical values needed for evaluating the condition. To fix the linearity issue, the condition block no longer accepts linear (i.e., quantum) values. The body block yields all classical and quantum values. It might be necessary to sort the values, separating those required for evaluating the condition from the other iteration arguments.
3. Go with MLIR's definition. The condition and body blocks can read and modify the state. Both blocks yield an arbitrary list of values to each other, with the condition block defining the input and output types of the operation itself.

@aborgna-q, @burgholzer, and @dime10, please correct me if I'm missing something. 🙂

[dime10]

Go with MLIR's definition. The condition and body blocks can read and modify the state. Both yield the same list of values, as they are all iteration arguments.

In MLIR, the two blocks actually yield a (potentially) different set of values. Is the last sentence added as an explicit departure from the MLIR definition, or just an oversight?

[denialhaag]

Go with MLIR's definition. The condition and body blocks can read and modify the state. Both yield the same list of values, as they are all iteration arguments.

In MLIR, the two blocks actually yield a (potentially) different set of values. Is the last sentence added as an explicit departure from the MLIR definition, or just an oversight?

Ohh, no, that's an oversight. I've fixed it now. Thanks!

[denialhaag]

We have agreed on option 3. I'll make the necessary changed next week once unitaryHACK has concluded.