ALAP/ASAP scheduler produces incorrect delays for circuits with classically controlled gates

[Lolcroc]

Information

• Qiskit Terra version: 0.18.1
• Python version: 3.8.3
• Operating system: Windows 10

What is the current behavior?

The ALAP and ASAP schedulers give wrong delays for circuits with gates with a classical condition. This is because the passes do not respect topological order of classical bit lines, which they should.

Steps to reproduce the problem

from qiskit.circuit import QuantumCircuit
from qiskit import QuantumRegister, ClassicalRegister

from qiskit.transpiler.passes import ALAPSchedule
from qiskit.transpiler import PassManager, InstructionDurations

# Initialize a pass for an ALAP schedule
durations = InstructionDurations([('measure', None, 1), ('x', None, 1)])
alap = ALAPSchedule(durations)
pm_alap = PassManager(alap)

# Create test circuit
qreg = QuantumRegister(2, "q")
creg = ClassicalRegister(1, "c")
qc = QuantumCircuit(qreg, creg)
qc.measure(0, 0)
qc.x(1).c_if(creg, 1)
qc.x(1)
print(qc) # Optional: print the circuit as a reference

# Run ALAP on test circuit
qc_bad = pm_alap.run(qc)

# Beware: the circuit renderer might be confusing, since the conditional X gate is rendered after the measurement.
# However according to the delay gates, the X gate conditioned on the classical bit happens before the measurement.
print(qc_bad)

What is the expected behavior?

The passes need to insert delays on qubits with gates conditioned on classical bits, such that those gates are always done later than the measurement producing the classical bit outcome. The correct topological order for conditional gates is already present in the DAGCircuit, so one should only need to fix the passes.

Suggested solutions

Treat qubits and clbits on equal footing. This means variables such as qubit_time_available in the pass run method should keep track of time for clbits too.

[kdk]

Thanks for reporting this @Lolcroc , agree this is a bug. The timeline_viewer shows this a bit clearer than the circuit drawer:

[Lolcroc]

This also happens for measurements after measurements (not just conditional gates). In the following example, ASAP schedules measurement on qubit 1 before qubit 0:

qc = QuantumCircuit(2, 1)
qc.x(0)
qc.measure(0, 0)
    
# Should come after first measurement, yet ASAP schedules before
qc.measure(1, 0)

The suggested solution should fix both cases.

[itoko]

I've started working on this and recognized fixing the spec of ASAP/ALAP scheduler for circuits touching classical registers is more complicated than I thought.

As far as I understand, in typical backends, measure locks clbits to be written at its end and c_if locks clbits to be read at its beginning. That means neither of them locks clbits for entire instruction time and they lock clbits for little time. However, current backends do not report how much time it takes for such an I/O operation on clbits. So, for now, I think it would make sense to assume zero time for creg I/O operation.

Considering the above, the following spec (shown by examples) makes most sense to me.

(common setting)
durations = InstructionDuration([("x", None, 200), ("measure", None, 1000)])
qc = QuantumCircuit(2, 1)

# Case measure-c_if
qc.measure(0, 0)
qc.x(1).c_if(0, True)  # starts at 1000

# Case measure-measure
qc.measure(0, 0)
qc.measure(1, 0)  # starts at 0

# Case c_if-c_if (same)  # schedule depends on "condition" (not only clbits)
qc.x(0).c_if(0, True)
qc.x(0).c_if(0, True)  # starts at 200

# Case c_if-c_if (diff)
qc.x(0).c_if(0, True)
qc.x(0).c_if(0, False)  # starts at 0

I also think we should describe that the ASAP/ALAP scheduler may not schedule instructions exactly the same as any real backend does (especially when the circuit has conditional instructions) in docstring.

Any thoughts? @Lolcroc @kdk

[kdk]

As far as I understand, in typical backends, measure locks clbits to be written at its end and c_if locks clbits to be read at its beginning. That means neither of them locks clbits for entire instruction time and they lock clbits for little time. However, current backends do not report how much time it takes for such an I/O operation on clbits. So, for now, I think it would make sense to assume zero time for creg I/O operation.

I think this makes sense, and will fix the problem of out-of-order scheduling. Considering the clbits jointly locked for the duration of the instruction also seems reasonable to me (though maybe unnecessarily defensive). Maybe @taalexander has some thoughts on how to best model the duration of classical operations and their corresponding latencies , and how the calculated delays will impact the backends.

# Case measure-measure
qc.measure(0, 0)
qc.measure(1, 0)  # starts at 0

In this example, do both measurements start at 0, or is one at 0 and one at 1000? I could see an argument for both starting at 0 (in that the result of the first measurement will be unconditionally overwritten by the second), but worry slightly about this introducing race-conditions (if both are scheduled to start at 0, and the second finishes slightly earlier, or communicates its result to clbit 0 slightly earlier, the result of the first measure would persist instead of the second).

[taalexander]

In practice, this depends on how the backend implements conditional operators. There could be latencies following conditional operations, Qiskit is treating scheduling very naively. There are many questions about the qiskit scheduling model that must be answered surrounding control-flow, eg., what if value calculations or decision durations are indeterministic, how does scheduling work? It seems there are two types of control-flow that would be desired - control-flow and calculations with decidable and deterministic outcomes (such as the case of doing dynamical decoupling while calculating a future decision, instead of sitting idle) as well as more sophisticated constructs that do not obey this constraint.

On IBM backends, we merge together measurements on common qubits that are not dominated by other intervening quantum operations under topological ordering. This is due to triggering requirements in hardware which is difficult to communicate to the scheduling layer (and therefore it does not capture). Other hardware might have different requirements or even optimize away the first measurement statement since it is redundant.

[itoko]

[race condition?]
In my understanding, scheduled circuits are compiled to pulse schedules in a backend. For the "measure-measure" circuit, it would be compiled to a pulse schedule like below (in circuit view). Hence the race condition does not occur.

Am I correct? @taalexander

["both start at 0" or "one at 0 and one at 1000"]
IMO, scheduling step in transpilation is an optional step for estimating delay durations as accurately as possible (for purpose of dynamical decoupling, visualization and noisy simulation). Therefore, I think "both start at 0" would be better than "one at 0 and one at 1000" in the sense that it approximate delays better.