# Questions on multi-controlled Toffolis and their implementation in Qiskit

1. Is it possible to decompose an $$n$$-controlled Toffoli into $$O(n)$$ CNOTs without extra working qubits?

2. If so, is such an decomposition currently available in Qiskit or any other (preferably Python and QASM-friendly) packages?

If not:

1. Has such an impossibility been proven?

2. Is any decomposition into $$O(n)$$ CNOTs available in Qiskit or any other (preferably Python and QASM-friendly) packages?

In 2022, neither 2 nor 4 haven't apparently been implemented yet in Qiskit, see "Implemented by Qiskit:" here.

UPDATE

Using the following tket code (suggested in the answer below)

import qiskit
from pytket.extensions.qiskit import qiskit_to_tk, tk_to_qiskit
import matplotlib.pyplot as plt
import numpy as np
import pytket.transform as tkt

N = 10
qcs = []
cnots = []
x = np.array( range(1,145,9) )
for i,n in enumerate(x):
qc = qiskit.QuantumCircuit(n+1)
qc.mcx( list( range( n ) ), n )
# print(qc)
c = qiskit_to_tk( qc )
tkt.Transform.CnXPairwiseDecomposition().apply( c )
qc = tk_to_qiskit( c )
# print(qc)
if 'cx' not in qc.count_ops(): # At one value of n, instead of CX, controlled RX are produced
qc = qiskit.transpile( qc, basis_gates = [ 'u1', 'u2', 'u3', 'cx' ] )
cnot = qc.count_ops()[ 'cx' ]
print( f'Step {i+1}/{len( x )}; {n} qubits; {cnot} CNOTs' )
qcs.append( qc )
cnots.append( cnot )

fig, axs = plt.subplots( 1, 2 )
fig.suptitle( 'CNOTs' )
fig.set_size_inches( 10, 5 )
axs[ 0 ].plot( x, cnots, label = 'CNOTs')
axs[ 0 ].plot( x, x, label = 'x' )
axs[ 0 ].plot( x, 4*x*x, label = '4*x^2' )
axs[ 0 ].plot( x, 200*x, label = '200*x' )
axs[ 0 ].set_xlabel( 'n of control qubits' )
axs[ 0 ].set_ylabel( 'CNOTs' )
axs[ 0 ].legend()
axs[ 1 ].loglog( x, cnots, label = 'CNOTs' )
axs[ 1 ].loglog( x, x, label = 'x' )
axs[ 1 ].loglog( x, 4*x*x, label = '4*x^2' )
axs[ 1 ].loglog( x, 200*x, label = '200*x' )
axs[ 1 ].set_xlabel( 'n of control qubits' )
axs[ 1 ].set_ylabel( 'CNOTs' )
axs[ 1 ].legend()
plt.show()


gives

The cost is quadratic up to 50 (!!) control qubits and then seems to be linear. This happens because under 50 qubits the tket function multi_controlled_to_2q() calls function CnU_linear_depth_decomp() for simplifying multi-controlled gates, and above 50 it switches to using CnX_normal_decomp(). (They claim that this is the right way to do things — and the plot kinda suggests that this is indeed the case.)

What surprises/upsets me is the factor of 200 in the linear regime — Craig Gidney's post provides a solution with ~16n Toffolis, each of which can be represented by 6 CNOTs.

UPDATE 2

The implementation with $$(n-2)$$ (usual) ancillary qubits, as explained by Craig Gidney, requires $$6(2n-3)=12n-18$$ CNOTs, since each $$n$$-controlled gate is expanded into $$(2n-3)$$ Toffolis, each of which is decomposed into $$6$$ CNOTs:

from qiskit import QuantumCircuit, QuantumRegister, transpile

def mcx_decomposed( qr_c: QuantumRegister,
qr_t: QuantumRegister,
qr_anc: QuantumRegister ) -> QuantumCircuit:
"""
Decomposes the multi-controlled X gate into elementary gates.
:param qr_c: Control registers
:param qr_t: Target register
:param qr_anc: Ancilla registers
:return: Output circuit
"""
n = len( qr_c )
assert n >= 1, "The control register must contain at least one qubit."
assert len( qr_t ) == 1, "The target register must contain a single qubit."
assert n < 3 or len( qr_anc ) == n - 2, "The ancilla register must contain n - 2 qubits."

qc = QuantumCircuit( qr_c, qr_t, qr_anc )

if n == 1:
qc.cx( qr_c[ 0 ], qr_t[ 0 ] )
elif n == 2:
qc.ccx( qr_c[ 0 ], qr_c[ 1 ], qr_t[ 0 ] )
qc = transpile( qc, basis_gates = [ 'u1', 'u2', 'u3', 'cx' ] )
else:
qc.ccx( qr_c[ 0 ], qr_c[ 1 ], qr_anc[ 0 ] )
for i in range( n - 3 ):
qc.ccx( qr_anc[ i ], qr_c[ i + 2 ], qr_anc[ i + 1 ] )
qc.ccx( qr_anc[ n - 3 ], qr_c[ n - 1 ], qr_t[ 0 ] )
for i in range( n - 4, -1, -1 ):
qc.ccx( qr_anc[ i ], qr_c[ i + 2 ], qr_anc[ i + 1 ] )
qc.ccx( qr_c[ 0 ], qr_c[ 1 ], qr_anc[ 0 ] )

qc = transpile( qc, basis_gates = [ 'u1', 'u2', 'u3', 'cx' ], optimization_level = 3 )
return qc


To sum up:

• Without ancillas: $$\approx 4n^2$$ CNOTs for $$n<50$$, then $$\approx 200n$$ CNOTs.
• With $$n-2$$ ancillas: $$12n-18$$ CNOTs.

Is it possible to decompose an $$n$$-controlled Toffoli into $$O(n)$$ CNOTs without extra working qubits?