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.
This task focuses on the implementation of the MCX gate with a limited qubit count and circuit depth.
Decompose an MCX gate with 14 control qubits into single-qubit and double-qubit CX gates. You may use up to five clean auxiliary qubits and should release (uncompute) them at the end of the circuit. Thus, the circuit can use no more than 20 total qubits: 14 control qubits, one target qubit, and up to five auxiliary qubits.
Important: Make sure that when you submit a circuit, the order of the qubits is indeed as follows: first the 14 control qubits, then the target qubit, then any auxiliary. This will help us validate the circuit.
The winning solution will achieve this using a circuit of minimal depth.
Post your questions or see what others have asked on our Competition support site.
Here is a naive (non-optimized) example of an MCX gate with four control qubits using two auxiliary qubits
As an interim step, we could decompose it into a circuit with 5 CCX gates. in two different ways.
Notice that the second decomposition has a shorter depth than the first one because the first and second CCX can be applied simultaneously.
The CCX gate (i.e. Toffoli gate) can then be decomposed to single-qubit and CX gates in the following manner:
We look forward to reviewing your solution. Here are some things to know:
.svg)
