Commuting quantum circuits: efficiently classical simulations versus hardness results
| Autor: | Maarten Van den Nest, Xiaotong Ni |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Nuclear and High Energy Physics
Pure mathematics Computation Structure (category theory) General Physics and Astronomy Boundary (topology) Statistical and Nonlinear Physics Quantum entanglement Topology Theoretical Computer Science Power (physics) Computer Science::Hardware Architecture symbols.namesake Computer Science::Emerging Technologies Pauli exclusion principle Computational Theory and Mathematics symbols Quantum Mathematical Physics Mathematics Electronic circuit |
| Zdroj: | Quantum Information and Computation. 13:54-72 |
| ISSN: | 1533-7146 |
| DOI: | 10.26421/qic13.1-2-5 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|