Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.16068 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916721002020864 |
|---|---|
| author | González-García, Guillermo Cirac, J. Ignacio Trivedi, Rahul |
| author_facet | González-García, Guillermo Cirac, J. Ignacio Trivedi, Rahul |
| contents | For random quantum circuits on $n$ qubits of depth $Θ(\log n)$ with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method [Aharonov et al. Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023] . This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates $\unicode{x2013}$ going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16068 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Pauli path simulations of noisy quantum circuits beyond average case González-García, Guillermo Cirac, J. Ignacio Trivedi, Rahul Quantum Physics For random quantum circuits on $n$ qubits of depth $Θ(\log n)$ with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method [Aharonov et al. Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023] . This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates $\unicode{x2013}$ going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit. |
| title | Pauli path simulations of noisy quantum circuits beyond average case |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2407.16068 |