Blog

Competition Solutions: Decomposing a Multi-Controlled Toffoli Gate

1
July
,
2022

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!

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!

About "The Qubit Guy's Podcast"

Hosted by The Qubit Guy (Yuval Boger, our Chief Marketing Officer), the podcast hosts thought leaders in quantum computing to discuss business and technical questions that impact the quantum computing ecosystem. Our guests provide interesting insights about quantum computer software and algorithm, quantum computer hardware, key applications for quantum computing, market studies of the quantum industry and more.

If you would like to suggest a guest for the podcast, please contact us.

Start Creating Quantum Software Without Limits

contact us