Better MCX Decomposition with logarithmic Toffoli Depth

[patelvyom]

Feature details

The recent paper Rise of conditionally clean ancillae for optimizing quantum circuits presents an improved decomposition of MCX gates using conditionally clean ancilla qubits. The proposed method achieves the following trade-offs in terms of Toffoli gate count and circuit depth:

• 2n − 3 Toffoli and O(n) depth using 1 clean ancilla
• 2n − 3 Toffoli and O(log(n)) depth using 2 clean ancilla
• 4n − 8 Toffoli and O(n) depth using 1 dirty ancilla
• 4n - 8 Toffoli and O(log(n)) depth using 2 dirty ancilla

This approach is optimal in terms of Toffoli count (for 1 and 2 ancillae) and significantly improves circuit depth.

I was hoping I could implement this and add new functions in pennylane/pennylane/ops/op_math/controlled_decompositions.py. Current implementation works either for len(work_wires) == 1 or len(work_wires) == n-2 whereas this new approach will work for len(work_wires) == 2 and provide a better decomposition for len(work_wires) == 1.

Implementation

I would like to implement this decomposition in PennyLane by adding new functions to pennylane/ops/op_math/controlled_decompositions.py.

Currently, the existing implementation supports:

• len(work_wires) == 1
• len(work_wires) == n-2

The new approach will extend support to:

• len(work_wires) == 2, enabling a more efficient decomposition
• Improved decomposition for len(work_wires) == 1, reducing circuit depth

How important would you say this feature is?

2: Somewhat important. Needed this quarter.

Additional information

No response

[CatalinaAlbornoz]

Hi @patelvyom,

Thank you for opening this enhancement request. Our team is quite excited about it!

Feel free to open a Pull Request and mention this issue. Our team will be available in the PR comments if you want to discuss implementation details or if you have any questions.

[albi3ro]

Thanks for opening this issue @patelvyom .

Would you be interested in making this contribution?

As this involves writing several algorithms and integrating them into decompose_mcx, trying to do everything in one PR may be harder to write, quality check, and review.

I would propose breaking this entire task into several PRs. All of this would be added to the controlled_decompositions.py file as you suggested.

1. Adding a _mcx_one_clean_work private function and calling it in decompose_mcx under the correct circumstances
2. Adding a _mcx_two_clean_work private function and calling it in decompose_mcx under the correct circumstances
3. Adding a _mcx_one_dirty_work private function.
4. Adding a _mcx_two_dirty_work private function

I assume Barenco paper Lemma 7.2 is still better for many workers, and it's just one and two that are more efficient?

We don't really have a good way of distinguishing dirty, clean, conditionally clean, etc. work wires at the moment, though this is one our roadmap to figure out. At the moment, I would recommend adding a work_wire_type : Literal["clean", "dirty"]="clean" keyword argument to decompose_mcx for the moment if we wanted to add the two dirty work wire algorithms. That way we should be able to immediately integrate the dirty algorithms once we have a way of keeping track of that information.

We will also consider adding a work_wire_type kwarg to MultiControlledX as a temporary measure.

Feel free to ask any questions here, or open up a draft PR for feedback.