1
$\begingroup$

Famously, the CCZ gate requires 7 T gates to construct unitarily whereas using an ancilla, measurement, and classically-controlled Clifford gates, it can be constructed with only 4 T gates [1212.5069]. Are there any other diagonal gates over the CNOT+T gate set (i.e 3rd level of the Clifford hierarchy, or equivalently the T, CS, CCZ gate set) with protocols like this which are better than the equivalent unitary construction?

Obviously, outside of the CNOT+T gate set, there are some examples (e.g the 6 T gate construction of CCCZ). Also we can generalize the CCZ construction by applying a change of basis using a CNOT circuit, or by stacking it in various ways. But are there any other truly 'different' (for some definition of different) examples?

Reading through Table 2 in [1904.01124] I don't see any other examples for the states considered there. In [1709.06648] there are constructions based on the CCZ only. Likewise in [1303.6971] there are some gate-teleportation based constructions but they don't save on T-count compared to the unitary versions.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

My intuition is that ancilla qubits and feedback are almost always useful for reducing T count. Pick any gate, and preventing yourself from using workspace will make it less efficient to implement. The fact it's already true for Toffolis means this applies to essentially every reversible classical circuit. Addition, multiplication, sorting, everything that uses a Toffoli. Honestly I'd consider it harder to find examples where giving yourself extra workspace doesn't give any benefits.

It's also clear that the structure of these improvements is non-trivial. For example, doing a CCCX is slightly cheaper compared to the decomposition into two CCX gates, by using more complicated feedback. E.g. this CCCZ from https://arxiv.org/abs/2106.11513 :

enter image description here

And when doing arbitrary rotations you can make them more efficient by using catalysis from https://arxiv.org/abs/1812.01238 or Hamming weight phasing from https://arxiv.org/abs/1709.06648 or repeat-until-success circuits from https://arxiv.org/abs/1311.1074

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yeah I agree that this is very useful in general, but i'm only interested in specifically diagonal CNOT+T circuits for this question (i.e the {T, CS, CCZ} gate set). It seems that all optimizations for these circuits are ultimately based on your temporary-logical-and construction for CCZ because there is no ancilla+feedback optimization for CS gates. Are there any protocols for {T, CS, CCZ} circuits that aren't based on the TLA? $\endgroup$
    – Tuomas Laakkonen
    Jun 9 at 14:48
  • $\begingroup$ Literally the first example I gave is not based on that construction. The CCCX isn't decomposed into TLAs. $\endgroup$
    – Craig Gidney
    Jun 9 at 14:59
  • $\begingroup$ I know, but I'm only interested in circuits over {T, CS, CCZ}... CCCX (or CCCZ) is not such a circuit $\endgroup$
    – Tuomas Laakkonen
    Jun 9 at 15:00
  • $\begingroup$ @TuomasLaakkonen ah, fair enough $\endgroup$
    – Craig Gidney
    Jun 9 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.