It is a well established fact that Hadamard + Toffoli is a computationally universal gate set. Therefore I thought that the transpiler function in Qiskit would be able to decompose any valid quantum circuit in to a circuit of Hadamard and Toffoli gates. This doesn't seem to be the case however.

For example:

from qiskit import QuantumCircuit
qc = QuantumCircuit(5)

from qiskit import transpile

basis = ['h','ccx','id','swap']
qc_basis = transpile(qc,basis_gates = basis)

returns an error: "Unable to map source basis {('h', 1), ('cx', 2)} to target basis {'ccx', 'barrier', 'measure', 'delay', 'snapshot', 'swap', 'reset', 'id', 'h'}."

Have I interpreted computational universality incorrectly or is this functionality simply outside of the scope of the Qiskit transpile function?

Thank you


2 Answers 2


Although $\{\textrm{CCX}, \textrm{H}\}$ is a universal gate set, it is not universal in the sense that any unitary can be expressed in terms of finite sequence of its elements.

For any quantum circuit, however, you can use $\{\textrm{CCX}, \textrm{H}\}$ to implement another quantum circuit which when measured, will give the same measurement results as the original circuit.

For more details, see the answers here, here, and here.

So, you can not use Qiskit's transpiler to transpile a quantum circuit into this gate set because BasisTranslator (the transpiler pass responsible for translating gates to a given target basis) does not currently support the required kind of tranlations.


CX is a spacial case of CCX when one of the control qubit is $|1\rangle$.

|1⟩─■──     |1⟩───     
  ──■──  =   ──■──     
  ┌─┴─┐      ┌─┴─┐     
  ┤ X ├      ┤ X ├     
  └───┘      └───┘     

One controlled qubit down, X is an special case of CX

|1⟩──■──     |1⟩───   
   ┌─┴─┐      ┌───┐   
   ┤ X ├  =   ┤ X ├   
   └───┘      └───┘   

Similarly, Z is a special case of CX when target $|-\rangle$.

─────■──      ┤ Z ├    
   ┌─┴─┐  =   └───┘    
|-⟩┤ X ├     |-⟩───    

So, while it is true that CCX covers CX, X, and Z, Qiskit does not considers that because there is not general equivalence rule. Therefore, you should extend your basis to basis = ['h','ccx','id','swap', 'cx', 'x', 'z'] to make it work.

  • $\begingroup$ Thanks for the response @luciano! Adding 'cx' to the basis set does indeed work for the circuit I specified in the question. But unfortunately it still doesn't suffice as a Universal Gate Set as in that case if we add say an 'x' or 'z' gate to our circuit this new basis is no longer sufficient. $\endgroup$ Nov 2, 2022 at 10:24
  • $\begingroup$ x and z are special cases of cx. Same story than cx -> ccx applies for x -> cx and z -> cx. Let me extend the answer with that. $\endgroup$
    – luciano
    Nov 2, 2022 at 10:29

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.