Option to count Toffolis instead of counting T gates

[Strilanc]

Using current techniques, it is cheaper to perform a Toffoli gate directly via a CCZ state instead of via multiple T states. As a result, I often want to count Toffoli gates instead of T gates.

I have Q# code that counts Toffolis by instead counting Ts then dividing by 7 in order to compute the Toffoli count, but this code will break as soon as e.g. the trace simulator is updated to use the actual T count of 4 per Toffoli. I would rather more directly express my intent, so that my code will continue to work in the future.

(Also, counting Toffolis is nominally cheaper than counting Ts because fewer decomposition steps are needed.)

[cpalmer2020]

Thanks. This is an interesting idea to consider.

[IrinaYatsenko]

@Strilanc : Craig, would you mind taking a look at #475 to see if the design of the QIR-based tracer meets your needs? The design is outlined in src/QirRuntime/lib/Tracer/README.md and src/QirRuntime/test/QIR-tracer/tracer-intrinsics.qs shows how mapping from intrinsics to counters might be done. Your feedback will be much appreciated.

[Strilanc]

I looked it over. I'm not sure I have anything useful to say about it; it's much more in the details of Q# than what I'm familiar with. It mostly went over my head.

[IrinaYatsenko]

The idea there is that when compiling a Q# program for the tracer, you'll provide a target.qs file that would "instruct" the tracer how to count each of the Q# operations. For example, the tracer-target.qs I'm using for testing has the following mapping for the X operator:

    operation X(qb : Qubit) : Unit
    is Adj + Ctl {
        body  (...) { Phys.single_qubit_op(0, 1, qb); }
        adjoint (...) { Phys.single_qubit_op(0, 1, qb); }
        controlled (ctls, ...)
        {
            if (Length(ctls) == 1) { Phys.single_qubit_op_ctl(1, 1, ctls, qb); }
            else { Phys.single_qubit_op_ctl(2, 1, ctls, qb); }
        }
        controlled adjoint (ctls, ...)
        {
            if (Length(ctls) == 1) { Phys.single_qubit_op_ctl(1, 1, ctls, qb); }
            else { Phys.single_qubit_op_ctl(2, 1, ctls, qb); }
        }
    }

To count Toffoli's separately, one can add if (Length(ctls) == 2) { Phys.single_qubit_op_ctl(101 /*id*/, 4 /*weight*/, ctls, qb); }.