Complexity of quantum circuits via sensitivity, magic, and coherence

Understand

Quantum circuit complexity-a measure of the minimum number of gates needed to implement a given unitary transformation-is a fundamental concept in quantum computation, with widespread applications ranging from determining the running time of quantum algorithms to understanding the physics of black holes.

• In this work, we study the complexity of quantum circuits using the notions of sensitivity, average sensitivity (also called influence), magic, and coherence.
• We characterize the set of unitaries with vanishing sensitivity and show that it coincides with the family of matchgates.
• Since matchgates are tractable quantum circuits, we have proved that sensitivity is necessary for a quantum speedup.