Qiskit Transpiler function - Why does Toffoli + Hadamard not work as a Basis Gate set?

Question

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)
qc.cnot(0,1)
qc.h(1)

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

Answer 1

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.

Answer 2

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.