Commuting quantum circuits: efficient classical simulations versus hardness results

Abstract

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. In contrast, we prove that such strong simulations are hard for 3-local circuits. Using sampling methods we further show that all commuting circuits composed of exponentiated Pauli operators e^{iθP} can be simulated efficiently classically when followed by single-qubit measurements. Finally, we show that commuting circuits can efficiently simulate certain non-commutative processes, related in particular to constant-depth quantum circuits. This gives evidence that the power of commuting circuits goes beyond classical computation.

19 pages

References in corpus (7)

• Efficient classical simulation of slightly entangled quantum computations
• Persistent entanglement in arrays of interacting particles
• Randomizing quantum states: Constructions and applications
• Instantaneous Quantum Computation
• On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems
• Permutational Quantum Computing
• Trivial Low Energy States for Commuting Hamiltonians, and the Quantum PCP Conjecture

Cited by in corpus (7)

• Average-case complexity versus approximate simulation of commuting quantum computations
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• The principle of majorization: application to random quantum circuits
• Power of Uninitialized Qubits in Shallow Quantum Circuits
• The computational power of normalizer circuits over black-box groups
• Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
• Phase context decomposition of diagonal unitaries for higher-dimensional systems