Physical mapping of dynamically dereferenced qubits

[dorisraeli]

Hi all! This issue is a continuation of my post in the slack channel (with @taalexander );

OQ3 is an MLIR and its ideology states that it aims to also represent the physical circuits level (e.g., physical qubits, timings).
I'm currently writing a compiler from OQ3 to our open-source pulse-level language QUA and encountered some problems in the target-dependent phase.

In the OQ3 paper, there's an example of a target-dependent compilation flow, and in the 3rd phase ("Physical qubit mapping and routing", page 45) one expects only physical qubits references (and no virtual qubits).
How should the mapping handle arrays of qubits (mainly due to dynamic dereference), e.g.,:

OPENQASM 3;

bit[1] flag = 1;
uint[1] c = 0;
qubit[100] qs;
h qs;

// this (over the top and pathological) code should transform to
// only reference physical qubits, but is it possible in OQ3?
while (flag) {
    flag = measure qs[c];
    cnot qs[c+flag], qs[flag];
    c += 2-flag;
}

Some possible options include:

1. Disregard these as edge cases (unwise IMHO)
2. Deny some cases of dynamic dereferences of qubits
3. Add dynamic dereference of physical qubits? like in $[a+2*c]
4. Add arrays of physical qubits (as per @taalexander 's idea)

What do you think about this?
Thanks, Dor 😃

[jheckey]

The implication here is that the QPU control logic has the ability to evaluate the qs[c], qs[c+flag] and c += 2-flag expressions, and maintain the logical/physical qubit mapping. This example may be able to be statically compiled as a DAG, where each branch (flag == 0 and flag == 1) can be computed beforehand, but that would lead prohibitively large programs (>2^(100+1) operations in this example) and then only if the program halts in all cases.

IMO, this is where OpenQASM needs to be able to be a system-level programming language with clear boundaries between classical and quantum elements; should OpenQASM be executable on the controller, or should it be transpiled/compiled to a natively executable format (binary, Python script, etc.)?

[boschmitt]

@jheckey I think you are addressing a problem that might arise once we solve this one. The issue at hand is that the language allows the construction of a technology-independent OQ3 program that we can't translate to a technology-dependent one. So, if we cannot lower it, why is it allowed?

We can solve this problem by either choosing not to allow such programs and calling it a day or allowing them, which requires creating a way of lowering them. Now, if we decide on the latter, we need to deal with the question of whether today's QPU control logic technology can execute this program or not. (It seems not to be the case.)

At the risk of oversimplification, I think the points you brought have a simple answer. If you are compiling OpenQASM to one particular hardware architecture, then it's your compiler's job to know if the QPU control logic supports this or not.

Ultimately, I think the answer of whether a lowered version of this program is valid OQ3 program boils down to answering the question: "Should an execution environment (i.e., current technology limitations) dictate what is possible to express using OQ3 (or what is valid OQ3)?" If yes, we need to define which technology dictates what is valid OQ3.

TLDR: We need to decide whether this is dynamic dereferencing of physical qubits is valid OQ3 not supported by all (if any this time) QPUs, or if this is invalid OQ3. Either way, a compiler will need to deal with it. It is all a question of which phase.

[dorisraeli]

@jheckey I think you are addressing a problem that might arise once we solve this one. The issue at hand is that the language allows the construction of a technology-independent OQ3 program that we can't translate to a technology-dependent one. So, if we cannot lower it, why is it allowed?

exactly.

This problem also arises in simple cases, for example:

qubit[100] qs;
h qs;

The h-gate will be lowered to 100 h-gate calls instead of maybe a real time for loop over an array of physical qubits with dynamic dereferencing. Moreover, our (Quantum Machines) control system and pulse level language allow for dynamic dereferencing, so we don't have an exponential-blowup like you mentioned.

One could dismiss this example and say that program length is not important, but I disagree. Even still, the functionality problem in my original post still exists.

[jheckey]

I agree with both of you, and I tried to get to N+1 as a way of resolving N, but missed a few steps and edited too much out.

The part that I edited out of my first response was that certain QPUs will require interacted qubits to be adjacent. So, assuming the original example runs to when c is 99 the swap operations to execute the cnot may have made the qs indexes numerically inconsistent from their expected values based on the symbolic reference.

Now, with that out of the way, my votes:

1. Disregard these as edge cases - No. This is likely going to be a requirement for error correction and for sustained quantum computing.
2. Deny some cases of dynamic references - Yes, but under what conditions? The best example I've seen is actually the given example where the cnot will use 0 or 1 for both the target and control in several cases and never advance beyond iteration c == 1. I think this is hard to detect without simulation in OpenQASM with the lack of formalism and bounds checking. Also, not quite sure how this could/would be prevented at run time. At the very least, this would allow for the compiler to both manage the qubit array mapping and the qubit operations and keep them coherent throughout execution (assuming the hardware supported it).
3. Add dynamic dereference of physical qubits - Yes. This does allow for one to implement the example, albeit in a much more complicated way and one that would likely prevent much optimization (no swap inserts, qubits need to either stay in place or return to their original position). Also, this does nothing to prevent the issues with 2.
4. Add arrays of physical qubits - I'm not sure how this would differ functionally from aliasing and concatenation (though the user experience would be better).

[dorisraeli]

OK. So in the surface code quantum memory example ("examples/scqec.qasm"):

/* Declare a sub-circuit for Hadamard gates on ancillas
 */
def hadamard_layer(qubit[n-1] ancilla) {
  // Hadamards in the bulk
  for row in [0: d-2] {
    for col in [0: d-2] {
      bit[32] sum = bit[32](row + col);
      if(sum[0] == 1)
        h ancilla[row * (d - 1) + col];
    }
  }
  // Hadamards on the left and right boundaries
  for i in [0: d - 2] {
    h ancilla[(d - 1)^2 + (d - 1) + i];
  }
}

Should the function be unfolded in compile time to O(d**2) instructions instead?
The problem is that even if we say that "if the HW supports dynamical dereferencing then they could support this", OQ3 is not expressive enough to represent this example with only physical qubits (with dynamical dereferencing).