Replanning

A run that overran its time budget is abandoned at a safe boundary and restarted under a different plan.

"""Runtime monitoring and replanning when a run overruns its time budget.

The planner estimates a run's cost from a model. When the model is too
optimistic, a run can overrun its budget; MENOS then stops it at a safe
boundary, feeds what it observed back into the planner, and restarts under a
different plan -- or refuses the job if no plan fits.

This job is one where the model underestimates matrix-product-state (MPS)
execution, so the outcome depends on how fast your machine is. Every outcome
below is a correct result; the script checks the invariants that hold in all of
them and prints which one happened.
"""

from menos import Circuit, Opcode, RunOptions, run
from menos.exceptions import ResourceExceededError

n, layers, shots = 16, 8, 64
circuit = Circuit(n, n)
for layer in range(layers):
    for q in range(n):
        circuit.append(Opcode.H, [q])
    circuit.append(Opcode.T, [0])
    for q in range(layer % 2, n - 1, 2):
        circuit.append(Opcode.CX, [q, q + 1])
for q in range(n):
    circuit.append_measure(q, q)

options = RunOptions()
options.shots = shots
options.seed = 5
options.time_budget_seconds = 0.2  # bounds ONE execution attempt, not the whole job

try:
    result = run(circuit, options)
except ResourceExceededError as error:
    print("outcome: refused -- the budget was overrun and no other plan fits")
    print(str(error)[:160], "...")
else:
    assert sum(result.counts.values()) == shots and result.exact
    report = result.explain()
    if "replan 0" in report:
        print("outcome: a run overran its budget and was restarted under a new plan")
        print("\n".join(line for line in report.splitlines() if "replan" in line or line.startswith(" ")))
    else:
        print("outcome: the first plan finished inside the budget; nothing was replanned")
    print(next(line for line in report.splitlines() if line.startswith("strategy")))

Output

This is real output from the development machine:

outcome: a run overran its budget and was restarted under a new plan
replan 0   threshold=0.2 s crossed at elapsed=0.224734 s
           abandoned after 194 safe boundaries on engine=mps backend=cpu
           was  strategy=direct_mps predicted=0.000835369 s
           reason="observed runtime exceeded the time budget; mps on cpu is excluded by an observed floor of 0.224734 s"
           now  strategy=direct_dense
strategy   direct_dense (exact)

The model predicted the MPS engine would need under a millisecond. It was still running at 0.2247 s, so it was abandoned, the planner was asked again with that observation, dense was estimated to fit, and the job completed correctly. The whole job took about 0.44 s, more than the 0.2 s budget, because the budget bounds one attempt.

The outcome depends on your hardware

This job is one where the planner's model is far too optimistic, so the result depends on how fast your machine is. On a faster machine the MPS run may finish inside the budget and nothing is replanned; on a slower one the replacement may also overrun and the job be refused with ResourceExceededError. The script accepts every outcome and prints which happened. All of them are correct.

See also

Replanning · Monitoring · Time Budgets