Allocating qubits in repeat-until loop body changes visibility of other variables

[tcNickolas]

Describe the bug

I can run the following code

use a = Qubit();
repeat {
    let res = MResetZ(a);
}
until res == Zero;

but I cannot run the same code if the qubit is allocated in the repeat loop body because variable res becomes undefined:

repeat {
    use a = Qubit();
    let res = MResetZ(a);
}
until res == Zero;

I suspect qubit allocation creates an implicit scope for all variables until the end of the block, which should not be the case for repeat-until loop.

Expected behavior

I expect to be able to allocate qubits in the repeat-until loop body, and this to not change the scope of other variables.

System information

• QDK 0.18.2107153439 and 0.18.2106148911
• Linux and Windows, .NET Core 3.1.407

[bettinaheim]

@samarsha This looks like a bug with the implicit qubit scopes. Could you please take a look?

[bamarsha]

I don't think it's a bug with the implicit scope per se, but it is a bad interaction between the implicit scope and the scope rules for repeat-until.

The example indeed desugars to:

repeat {
    use a = Qubit() {
        let res = MResetZ(a);
    }
} until res == Zero;

According to the scoping rules for repeat-until, the until condition uses the top-level scope of the repeat block, but res is not visible there. That's by design. You see the same behavior with:

repeat {
    if x {
        let stop = true;
    }
} until stop; // error: stop not defined

So I see three options:

1. Change the use statement to not create an implicit scope, like let and mutable.
2. Change the scoping rules for the until condition to not have access to the scope of the repeat block.
3. Change the scoping rules for the until condition to have access to the innermost scope of the last statement inside the repeat block.

I want to point out that the current scoping rules for repeat-until are very weird and counterintuitive. They violate the basic assumption about scopes (that anything declared within { ... } is not visible outside the { ... }) and this bug is happening because the implicit use scope relied on that assumption. I would strongly recommend trying to find an alternative design that still lets you pass information from inside the repeat block to the until condition, but without violating basic scoping rules.

[bamarsha]

Another way to think about this from a design perspective is that we have two features that are not orthogonal, which led to an unexpected interaction with a third feature.

Feature 1: Bindings are only visible within the scope { ... } in which they are declared.

Feature 2: repeat-until can execute a block until a condition is true. However, for convenience, we wanted to be able to access bindings from the repeat block in the until condition, even though Feature 1 forbids it. So we bent the rules for Feature 1 to make Feature 2 more convenient - they are no longer orthogonal.

For that reason I'd argue that the bug is in the behavior of repeat-until, rather than the implicit use scope (which was relying on Feature 1 holding in every situation).

[tcNickolas]

I understand where this behavior comes from, and I can come up with a workaround.

I stumbled upon this example thinking of it from the point of view of a user who is not familiar with the compiler internals and the history of using statement (i.e., writing new code rather than migrating old code to the new syntax). From that point of view the behavior of repeat-until statement is nice and user-friendly - it allows to use a variable from the body without declaring it as mutable before the loop. And the behavior of use looks like it should be similar to that of let and mutable - it feels like declaring another variable, only quantum this time.

I'm in favor of option #1, since it will make all variables declared, classical or quantum, feel the same. #3 feels weird to me, since it would violate the rules of explicit scopes noticeably. And #2 will mean less usability for repeat-until loop (and a fair amount of work rewriting existing loops to not rely on a variable declared in loop body).

[bamarsha]

it allows to use a variable from the body without declaring it as mutable before the loop. ... And #2 will mean less usability for repeat-until loop (and a fair amount of work rewriting existing loops to not rely on a variable declared in loop body).

To clarify, requiring a mutable is not the only alternative within option 2. Just as a rough example made up on the fly:

repeat {
    use a = Qubit();
    yield MResetZ(a);
} until result == Zero;
// Where "result" is a keyword referring to the value yielded from the repeat block.

There are probably other designs. So for option 2 I'm just suggesting exploring the alternative design space, not necessarily requiring a mutable variable.

[bamarsha]

Another design idea that uses lambdas, and removes the need for a new keyword, is to make the type of the until condition 'a -> Bool for some 'a yielded by the repeat block:

repeat {
    use q = Qubit();
    yield MResetZ(q);
} until result -> result == Zero;

Alternatively, using partial application:

} until EqualR(_, Zero);

Or, if partial operators are supported:

} until _ == Zero;

[alan-geller]

I think @tcNickolas's point is that using a mutable is the only solution without a language change. Adding a yield statement to Q# has its own issues.

While it might make sense to add yield, it seems a bigger change than option #1. Might it make sense to change the behavior of use to address this issue and then propose adding a yield statement (or some other solution) to Q#? I think the current behavior is likely to be surprising to existing users.

[bamarsha]

The yield statement was mostly a workaround for not being expression-based... If Q# was expression based, then the value passed to the condition could simply be the value of the repeat block (i.e. the last expression evaluated in the block):

repeat {
    use q = Qubit();
    MResetZ(q)
} until result -> result == Zero;

[bamarsha]

Also, to clarify some more... I predict that future language features (in particular, match expressions) will force Q# to choose one of (a) becoming expression-based, or (b) adding a way to get a value out of a statement block, like a yield statement. Because the alternative is needing to add two versions of match (expression and statement), which is undesirable.

So my thinking here is really just to piggyback off of this future addition, whichever one it is - the concept of getting a value "out of" an inner block is too useful not to have, and that's all we need to make repeat-until behave better.