Qualtran
Qualtran copied to clipboard
quantumlib
`t_complexity(cirq.CCX)` and `t_complexity(Toffoli())` don't match
In [7]: t_complexity(cirq.CCX)
Out[7]: TComplexity(t=7, clifford=10, rotations=0)
In [9]: t_complexity(Toffoli())
Out[9]: TComplexity(t=4, clifford=0, rotations=0)
It would be nice to know exactly which Toffoli is being used in decompositions (without looking at source or decomposing fully) - for example when decomposing a MCX gate one can use Toffoli() which has t=4 because each Toffoli that is computed is subsequently uncomputed. However, when decomposing a controlled SWAP() one must use cirq.CCX which has t=7 because there is only one CCX gate in the decomposition to a Fredkin gate.
Yeah, all the qualtran bloqs have a specific decomposition and the t count must match that. We don't have (direct) control over the decompositions in cirq.
As far as I can tell Toffoli() is supposed to be implementing the full CCX gate. This requires T-count: 7 and Clifford: 8 by standard construction (no ancilla). However, according to the reference in Toffoli() source code you can utilize two ancilla and measurement control to yield T-count: 4, Clifford: 14. This is what is implemented in mcmt.multi_control_multi_target_pauli.MultiControlPauli((1,1), target_gate=cirq.X).
In most decompositions that need them CCX gates appear in pairs which means they are actually compute and uncompute AND gates implemented in mcmt.and_bloq.And(). This is why MultiControlPauli((1,1), target_gate=cirq.X) yields the correct count for a full CCX gate. In my work I am always worried about decomposition to the Toffoli level and therefore, in my decompositions, fully specify with And() bloqs or cirq.CCX. I would prefer to have Toffoli() return T_complexity(t=7, clifford=8, rotations=0) with no ancilla so I can use it instead of cirq.CCX as the bloqs will play better with decomposing into base gatesets. Alternatively, if one wants a lower T-count they can call MultiControlPauli((1,1), target_gate=cirq.X) instead of Toffoli() and then there is no need to use cirq.CCX.
TLDR: I want to differentiate compute/uncompute AND() with Toffoli(). My suggestion would be to have Toffoli() use no ancilla and return TComplexity(t=7, clifford=8, rotations=0).
@brempfer Your argument is correct and I agree we should change the build_call_graph and TComplexity methods on the Toffoli gate to yield 7 T-gates and wherever the user needs 4 T gates; they should replace the usage of Toffoli with either a MultiControlPauli((1,1), target_gate=cirq.X) or manually put a CX surrounded by $\text{AND} / \text{AND}^{\dagger}$.
In my work I am always worried about decomposition to the Toffoli level
A lot of this could be solved by extending/changing the resource counting protocol to count Toffolis.
Other parts of the library and previous resource estimates assume 4 T per Toffoli; see e.g. the models in qualtran.surface_code.
A lot of this could be solved by extending/changing the resource counting protocol to count Toffolis.
Depending on whether one is concerned with T or CCZ magic states (there is no stabilizer code with a transversal Toffoli) you may want to count both T and CCX. When concerned with resources estimation there is a potential tradespace between how you are creating T states, CCX gates or the T states that come from CCX.
I think it would be useful to have the resource counting protocol keep track of T gates that are generated separate from CCXs and those generated as a byproduct of AND/AND†/CCX. However, it can definitely get more complicated if the algorithm architect selects certain subroutines to use T magic states and others to use CCZ, for example based on some error correction scheme specific to some hardware architecture.
Keeping track of the other issues where this has come up
- https://github.com/quantumlib/Qualtran/issues/620
- https://github.com/quantumlib/Qualtran/issues/326
- https://github.com/quantumlib/Qualtran/issues/153#issuecomment-1498272111
And here's the OG issue for counting toffolis
- https://github.com/quantumlib/Qualtran/issues/110
cirq.CXX gets converted to our internal Toffoli, which is counted in a factorized form by QECGatesCost. The methods for aggregating the counts like counts.total_t_count() take an optional argument ts_per_toffoli.