Physics – Quantum Physics
Scientific paper
2012-04-20
Physics
Quantum Physics
19 pages
Scientific paper
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\theta 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.
den Nest Maarten Van
Ni Xiaotong
No associations
LandOfFree
Commuting quantum circuits: efficient classical simulations versus hardness results does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Commuting quantum circuits: efficient classical simulations versus hardness results, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Commuting quantum circuits: efficient classical simulations versus hardness results will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-5444