# Decomposing a Multi-controlled Toffoli gate

## Background

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.

## The Problem

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.

## Metric

The winning solution will achieve this using a circuit of minimal depth.

## Questions?

Post your questions or see what others have asked on our Competition support site.

## Example

Here is a naive (non-optimized) example of an MCX gate with four control qubits using two auxiliary qubits

Original circuit:

As an interim step, we could decompose it into a circuit with 5 CCX gates. in two different ways.

Here is one option:
And here is another:

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:

You are welcome to submit multiple solutions. If you submit something today, and find an improvement later on, you're welcome to submit the new solution as well.
Each problem requires slightly different information. Please make sure you carefully review the problem instructions.
The description of the approach is very helpful to the judges in understanding your work. Please include as much detail as you wish. We're interested in how you approached this problem, how your solution works, how long it took you to develop it, and whether there were particular problems that you overcame. We'd love to hear as much as you want to tell us. You can submit this in the 'description' field or include it as the 'Additional file (optional)' attachment.
The QASM code is how we can verify the 2-qubit gate count and/or circuit depth. It should include only CX and single-qubit unitary gates. This note on our Discourse support site might help.
If you created the circuit in something other than QASM, please submit the source code as well.
You will receive an email confirming the submission within a few minutes.
Submissions are closed. the results are here. Thank you!
0
DAYS
:
0
Hours
:
0
Minutes
:
0
Seconds
Oops! Something went wrong while submitting the form.
Submission
*QASM Code