# DECOMPOSING A MULTI-CONTROLLED TOFFOLI GATE

## Background:

Each hardware vendor has varying basis gates, with all operations being high-level abstractions composed of one or more basis gates. The Toffoli is an operation composed of a considerable number of single-qubit operations and CX gates.

Many quantum operations include multi-controlled Toffoli (MCX) gates. Among the most notable are Grover Operator, logical AND operator, various state preparation algorithms, and arithmetic comparators.

## Problem:

The challenge for the Classiq Coding Competition was to decompose an MCX gate with 14 control qubits into single-qubit and double-qubit CX gates. Competitors were allowed up to five clean auxiliary qubits that needed to be released (uncomputed) at the end of the circuit.

## Winning Metric:

The winners were chosen based on the minimal depth in their decompositions.

We confirmed the submitted depth and used an equivalence tool to verify circuit validity.

#
FIRST PLACE - *Soshun Naito,* Japan

Soshun manually decomposed the MCX gate into concentration, calculation, and uncomputation steps and searched for the optimal circuit of depth-efficient approximate and exact MCX gates with his Python script. He successfully decomposed a 14 control MCX gate into a 20 qubit circuit composed of only 11 high-level operations with a **depth of 57**.

For a Jupyter Notebook of the first place MCX decomposition, see here.

Read his full explanation here.

#
SECOND PLACE - *Nikita Nemkov*, Russia

Nikita maximized parallelism in his circuit by splitting the 14 controls into four groups with manually-constructed relative phase CCX, CCCX, and CCCCX gates, storing each result in an ancilla qubit, and simultaneously executing an AND on all four ancilla qubits. He successfully decomposed a 14 control MCX gate into a 20 qubit circuit composed of 9 high-level operations with a **depth of 70**.

For a Jupyter Notebook of the second place decomposition, see here.

#
THIRD PLACE - *Team Carnivorous Cacti (Tarushii Goel, Kareem Jaber, Cyril Sharma),* USA

Team Carnivorous Cacti manually constructed an RC4X gate using Qiskitâ€™s RC3X and MCX gates. They successfully decomposed a 14 control MCX gate into a 20 qubit circuit composed of 11 high-level operations with a **depth of 71**.

For a Jupyter Notebook of the third place decomposition, see here.

#
FOURTH PLACE - *Alexander Gramolin,* USA

Alexanderâ€™s submission manually constructs relative phase C3X and C4X gates. The final circuit is composed of 11 high-level operations, matching the first place submission. He successfully decomposed a 14 control MCX gate into a 20 qubit circuit with a **depth of 90**.

For a Jupyter Notebook of the fourth place decomposition, see here.

#
FIFTH PLACE - *Jan TuĹ‚owiecki,* Poland

This submission relies on Qiskitâ€™s RC3XGate, which is a relative phase controlled-controlled-controlled-NOT gate inspired by this paper, and one MCX gate, which is not simplified compared to relative phase gates. Uncomputation is via the `.inverse()`

of the RC3XGate. The `large_toffoli()`

function shows that you can construct a C14X with only 11 lines of code while remaining competitive enough to earn the second honorable mention. Jan successfully decomposed a 14 control MCX gate into a 20 qubit circuit with a **depth of 101**.

For a Jupyter Notebook of the fifth place decomposition, see here.

Read his full explanation here.

#
SIXTH PLACE - *Witold Jarnicki,* Poland

Witold successfully decomposed a 14 control MCX gate into a 20 qubit circuit with a **depth of 140**.

For a Jupyter Notebook of the sixth place decomposition, see here.