ResourceCounter May Underestimates Circuit Width with Dynamic Ancilla Allocation and Deallocation

[YuanYufeiISCAS]

The ResourceCounter backend in ProjectQ appears to calculate the circuit width based on the maximum number of simultaneously active qubits. However, it seems to reuse the indices of qubits that have been deallocated. This behavior can lead to an underestimation of the total number of unique qubits required to run an entire algorithm, even if they are not all active at the same time.

Consider the following sub-circuit, which allocates and then deallocates an ancilla qubit:

def op1_circuit(eng, control1, control2, target):
    ancilla = eng.allocate_qureg(1)
    H | target
    CNOT | (control2, ancilla[0])
    CNOT | (target, control1)
    CNOT | (control2, ancilla[0])
    H | target
    S | target

    eng.deallocate_qubit(ancilla[0])
    return

If we call this sub-circuit sequentially, my expectation is that each call should use a logically distinct ancilla qubit, thus increasing the total number of required qubit indices.
When I run the following code:

‘’‘
circuit_backend = _resource.ResourceCounter()
eng = MainEngine(backend=circuit_backend)
State = eng.allocate_qureg(6)

op1_circuit(eng, State[0], State[1], State[2])
op1_circuit(eng, State[3], State[4], State[5])

eng.flush()

’‘’

Return: the reported max_width is 7.
The result of 7 indicates that the backend is reusing the qubit index for the ancilla. However, the total depth will keep the same with only one subcircuit 'op1_circuit(eng, State[0], State[1], State[2])'. Therefore, it might not count the ancilla in reusing the qubit but omit the deallocate qubit.

So, my question is, is this the correct and intended way to use dynamic allocation and deallocation in ProjectQ?
My goal is to estimate the total number of unique physical qubits required to run the entire algorithm from start to finish.

[damiansteiger]

Thank you for your detailed question with example code.

Let's turn off any optimisation in the compiler as otherwise the ancilla qubit will be optimized away

eng = MainEngine(backend=circuit_backend, engine_list=[])

Then the max_width returned is 7. The current ResourceCounter is very simple and does not construct a DAG of the quantum program (each compiler engine sends a linear order of the DAG of the quantum program to the next compiler engine, i.e., a compiler engine receives quantum operations sequentially). In the example, it receives sequentially all the gates of op1_circuit(eng, State[0], State[1], State[2]) so it requires 7 qubits but then it is back to 6 active qubits so when it receives the call op1_circuit(eng, State[3], State[4], State[5]) it again requires one ancilla and has 7 active qubits. Therefore max_width == 7

Note: in this example, it is possible that an added compiler engine could serialize the circuit differently so that the resource counter would receive the two ancilla allocation before the two ancilla are deallocated. In that case it would result in Max. width (number of qubits) : 8.

Take away: the current implementation of max width is dependent on the linear order of the quantum program, i.e., it provides only an upper bound on the required qubits.

circuit_backend.depth_of_dag provides the depth of the DAG of the quantum program. Note that it may not be possible to implement the quantum program with max_width qubits and simultaneously a depth of depth_of_dag. For that one would need to implement a new compiler engine which builds up the DAG and performs the scheduling of the gates (i.e. explores the tradeoff of number of qubits vs program depth)

Regarding your goal:
total number of unique physical qubits required to run the entire algorithm from start to finish. I assume you don't want to reuse qubits? in that case the number of allocate gates gives you the correct number (in this example: print(circuit_backend) -> AllocateQubitGate : 8)

Does this work for your intended purpose?

[YuanYufeiISCAS]

Thanks a lot for the detailed reply and tips.
Just to confirm my understanding:

1. The max_width reported by ResourceCounter is the peak number of simultaneously active qubits for the specific linearized (topologically sorted) order that reaches the backend. Therefore it serves as an upper bound on the minimal concurrent qubit count achievable under an optimal scheduling of the DAG (not necessarily tight), while it cannot achieve the best depth at same time.
2. Because the counter tracks liveness, once an ancilla is Deallocated it becomes eligible for reuse. So releasing an ancilla earlier shortens its live range and can keep the observed max_width lower; conversely, if two Allocates overlap before either is Deallocated, max_width can increase (e.g., from 7 to 8 in my toy example).

Thanks again for the guidance!

[damiansteiger]

1. Correct.
   FYI: If you want to check the linear order received by the resource counter, one can use a CommandPrinter to observe the linear order for small examples:

from projectq import MainEngine
from projectq.backends import ResourceCounter, CommandPrinter
from projectq.ops import X

resource_counter_backend = ResourceCounter()
eng = MainEngine(backend=resource_counter_backend, engine_list=[CommandPrinter()])

ancilla = eng.allocate_qubit()
X | ancilla
eng.flush()

2. Correct. The resource counter assumes that qubits can be reused after they are deallocated. By the way, it is useful to have at least one LocalOptimizer in the compiler engine list. It caches gates for optimization and in particular it forwards gates of the class FastForwardingGate as soon as possible, like measurements and qubit deallocation gates, so that these qubits can be reused.