Methods, systems and apparatus for producing quantum circuits with low T gate counts. In one aspect, a method for performing a temporary logical AND operation on two control qubits includes the actions of obtaining an ancilla qubit in an A-state; computing a logical-AND of the two control qubits and storing the computed logical-AND in the state of the ancilla qubit, comprising replacing the A-state of the ancilla qubit with the logical-AND of the two control qubits; maintaining the ancilla qubit storing the logical-AND of the two controls until a first condition is satisfied; and erasing the ancilla qubit when the first condition is satisfied.