Circuit Cost: Depth, Width, Gate Set, Connectivity

Topology-aware circuit cost calculator#

Nearest-neighbor CNOT router is the executable companion used by this page.

cd labs && python -m unittest tests.test_companion_models.CompanionModelTests.test_line_router_exposes_swap_cost_and_layout -v

Executable reference fixture

Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.

def validate_circuit(qubits, circuit):
    if qubits < 2:
        raise ValueError("routing needs at least two physical qubits")
    for control, target in circuit:
        if control == target or not 0 <= control < qubits or not 0 <= target < qubits:
            raise ValueError("CNOT endpoints must be distinct valid logical wires")

def dependency_depth(circuit, qubits):
    ready = [0] * qubits
    depth = 0
    for left, right in circuit:
        layer = max(ready[left], ready[right]) + 1
        ready[left] = ready[right] = layer
        depth = max(depth, layer)
    return depth

def route_line(qubits, circuit):
    validate_circuit(qubits, circuit)
    placement = list(range(qubits))
    routed = []
    for logical_control, logical_target in circuit:
        control = placement.index(logical_control)
        target = placement.index(logical_target)
        while abs(control - target) > 1:
            step = 1 if target > control else -1
            neighbor = control + step
            routed.append(("SWAP", control, neighbor))
            placement[control], placement[neighbor] = placement[neighbor], placement[control]
            control = neighbor
        routed.append(("CX", control, target))
    return routed, tuple(placement)

def expand_native(routed):
    primitives = []
    for gate, left, right in routed:
        if gate == "SWAP":
            primitives.extend(((left, right), (right, left), (left, right)))
        else:
            primitives.append((left, right))
    return primitives

def report(qubits, circuit, two_qubit_error):
    if not 0 <= two_qubit_error < 1:
        raise ValueError("error probability must lie in [0,1)")
    routed, final_layout = route_line(qubits, circuit)
    assert all(abs(left - right) == 1 for _, left, right in routed)
    primitives = expand_native(routed)
    swaps = sum(gate == "SWAP" for gate, _, _ in routed)
    exact_success = (1 - two_qubit_error) ** len(primitives)
    first_order_success = 1 - len(primitives) * two_qubit_error
    return {
        "logical_depth": dependency_depth(circuit, qubits),
        "routed_depth": dependency_depth(primitives, qubits),
        "swaps": swaps,
        "native_two_qubit_gates": len(primitives),
        "final_layout": final_layout,
        "exact_success": exact_success,
        "first_order_success": first_order_success,
    }

scenarios = (
    (5, ((0, 4),), 0.002),
    (5, ((0, 3), (1, 4), (0, 2)), 0.005),
    (4, ((0, 1), (2, 3)), 0.01),
)
reports = [report(*scenario) for scenario in scenarios]
assert reports[0]["swaps"] == 3 and reports[0]["native_two_qubit_gates"] == 10
assert reports[2]["logical_depth"] == 1 and reports[2]["swaps"] == 0
for result in reports:
    assert result["native_two_qubit_gates"] == 3 * result["swaps"] + len(scenarios[reports.index(result)][1])
    assert 0 < result["exact_success"] <= 1
    assert abs(result["exact_success"] - result["first_order_success"]) < 0.02

naive_nonlocal = ((0, 4),)
assert any(abs(left - right) != 1 for left, right in naive_nonlocal)
assert reports[0]["native_two_qubit_gates"] > len(naive_nonlocal)
invalid_rejected = False
try:
    report(5, ((2, 2),), 0.001)
except ValueError:
    invalid_rejected = True
assert invalid_rejected
bad_rate_rejected = False
try:
    report(5, ((0, 1),), 1.0)
except ValueError:
    bad_rate_rejected = True
assert bad_rate_rejected
total_swaps = sum(result["swaps"] for result in reports)
print(f"PASS: 22 topology calculator routes {len(scenarios)} circuits with total SWAPs={total_swaps}, native two-qubit counts={[result['native_two_qubit_gates'] for result in reports]}, depths={[(result['logical_depth'], result['routed_depth']) for result in reports]}, success={[round(result['exact_success'], 4) for result in reports]}")