4
$\begingroup$
  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

enter image description here

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:

enter image description here

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.
$\endgroup$

1 Answer 1

2
$\begingroup$

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

Yes! This blog post series by Craig Gidney describe how to do that.

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

Form the code here, this method is implemented in tket. So, you can use it in Python with pytket.

$\endgroup$
2
  • $\begingroup$ Awesome, thank you!! No wonder he's a coauthor of this paper. $\endgroup$
    – mavzolej
    Dec 7, 2023 at 9:16
  • 1
    $\begingroup$ Please see the updated question. $\endgroup$
    – mavzolej
    Dec 8, 2023 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.