Multi-Controlled Quantum Gates in Linear Nearest Neighbor

Understand

Multi-controlled single-target (MC) gates are some of the most crucial building blocks for varied quantum algorithms.

• How to implement them optimally is thus a pivotal question.
• To answer this question in an architecture-independent manner, and to get a worst-case estimate, we should look at a linear nearest-neighbor (LNN) architecture, as this can be embedded in almost any qubit connectivity.
• Motivated by the above, here we describe a method which implements MC gates using no more than $\sim 4k+8n$ CNOT gates -- up-to $60\%$ reduction over state-of-the-art -- while allowing for complete flexibility to choose the locations of $n$ controls, the target, and a dirty ancilla out of $k$ qubits.