Commuting quantum circuits: efficient classical simulations versus hardness results

Understand

The study of quantum circuits composed of commuting gates is particularly useful to understand the delicate boundary between quantum and classical computation.

• Indeed, while being a restricted class, commuting circuits exhibit genuine quantum effects such as entanglement.
• In this paper we show that the computational power of commuting circuits exhibits a surprisingly rich structure.
• First we show that every 2-local commuting circuit acting on d-level systems and followed by single-qudit measurements can be efficiently simulated classically with high accuracy.