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.
