Competition Solutions: Decomposing a Multi-Controlled Toffoli Gate

In the recent Classiq Coding Competition, one of the challenges was a Multi-Controlled Toffoli Decomposition problem. Below is a brief recap of the problem as well as some of the winning solutions.

‍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.

‍

A graph showing all the solutions is below:

Thank you for everyone who participated in and supported the Spring 2022 Classiq Coding Competition!