unitary transformation into a product of tensor products (i.e. series and parallel circuits) of the available primitive gates. The group U(2q) is the symmetry group for the gates that act on qubits. Factorization is then the problem of finding a path in U(2q) from the generating set of primitive gates. The Solovay–Kitaev theorem shows that given a sufficient set of primitive gates, there exist an efficient approximate for any gate. For the general case with a large number of qubits this direct approach to circuit synthesis is intractable. Because the gates unitary nature, all functions must be reversible and always be bijective mappings of input to output. There must always exist a function such that Functions that are not invertible can be made invertible by adding ancilla qubits to the input or the output, or both. After the function has run to completion, the ancilla qubits can then either be uncomputed or left untouched. Measuring or otherwise collapsing the quantum state of an ancilla qubit (e.g. by re-initializing the value of it, or by its spontaneous decoherence) that have not been uncomputed may result in errors, as their state may be entangled with the qubits that are still being used in computations. Logically irreversible operations, for example addition modulo of two -qubit registers a and b, can be made logically reversible by adding information to the output, so that the input can be computed from the output (i.e. there exist a function In our example, this can be done by passing on one of the input registers to the output: The output can then be used to compute the input (i.e. given the output and we can easily find the input; is given and and the function is made bijective. All Boolean algebraic expressions can be encoded as unitary transforms (quantum logic gates), for example by using combinations of the Pauli-X, CNOT and Toffoli gates. These gates are functionally complete in the Boolean logic domain. There are many unitary transforms available in the libraries of Q#, QCL, Qiskit, and other quantum programming languages. It also appears in the literature. For example, , where is the number of qubits that constitutes the register is implemented as the following in QCL: cond qufunct inc(qureg x) { // increment register int i; for i = #x-1 to 0 step -1 { CNot(x[i], x[0::i]); // apply controlled-not from } // MSB to LSB }