From estimation of quantum probabilities to simulation of quantum circuits
Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depend...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2020-01-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2020-01-13-223/pdf/ |
| _version_ | 1818658422000713728 |
|---|---|
| author | Hakop Pashayan Stephen D. Bartlett David Gross |
| author_facet | Hakop Pashayan Stephen D. Bartlett David Gross |
| author_sort | Hakop Pashayan |
| collection | DOAJ |
| description | Investigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of ``classical simulation'' and in particular on the required accuracy. We argue that a notion of classical simulation, which we call EPSILON-simulation (or $\epsilon$-simulation for short), captures the essence of possessing ``equivalent computational power'' as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an $\epsilon$-simulator from one possessing the simulated quantum system. We relate $\epsilon$-simulation to various alternative notions of simulation predominantly focusing on a simulator we call a $\textit{poly-box}$. A poly-box outputs $1/poly$ precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that $\epsilon$-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to $\epsilon$-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution ($\textit{poly-sparsity}$). |
| first_indexed | 2024-12-17T03:57:07Z |
| format | Article |
| id | doaj.art-d2ab30794f394b048ce48c64e85bde2b |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-12-17T03:57:07Z |
| publishDate | 2020-01-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-d2ab30794f394b048ce48c64e85bde2b2022-12-21T22:04:35ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2020-01-01422310.22331/q-2020-01-13-22310.22331/q-2020-01-13-223From estimation of quantum probabilities to simulation of quantum circuitsHakop PashayanStephen D. BartlettDavid GrossInvestigating the classical simulability of quantum circuits provides a promising avenue towards understanding the computational power of quantum systems. Whether a class of quantum circuits can be efficiently simulated with a probabilistic classical computer, or is provably hard to simulate, depends quite critically on the precise notion of ``classical simulation'' and in particular on the required accuracy. We argue that a notion of classical simulation, which we call EPSILON-simulation (or $\epsilon$-simulation for short), captures the essence of possessing ``equivalent computational power'' as the quantum system it simulates: It is statistically impossible to distinguish an agent with access to an $\epsilon$-simulator from one possessing the simulated quantum system. We relate $\epsilon$-simulation to various alternative notions of simulation predominantly focusing on a simulator we call a $\textit{poly-box}$. A poly-box outputs $1/poly$ precision additive estimates of Born probabilities and marginals. This notion of simulation has gained prominence through a number of recent simulability results. Accepting some plausible computational theoretic assumptions, we show that $\epsilon$-simulation is strictly stronger than a poly-box by showing that IQP circuits and unconditioned magic-state injected Clifford circuits are both hard to $\epsilon$-simulate and yet admit a poly-box. In contrast, we also show that these two notions are equivalent under an additional assumption on the sparsity of the output distribution ($\textit{poly-sparsity}$).https://quantum-journal.org/papers/q-2020-01-13-223/pdf/ |
| spellingShingle | Hakop Pashayan Stephen D. Bartlett David Gross From estimation of quantum probabilities to simulation of quantum circuits Quantum |
| title | From estimation of quantum probabilities to simulation of quantum circuits |
| title_full | From estimation of quantum probabilities to simulation of quantum circuits |
| title_fullStr | From estimation of quantum probabilities to simulation of quantum circuits |
| title_full_unstemmed | From estimation of quantum probabilities to simulation of quantum circuits |
| title_short | From estimation of quantum probabilities to simulation of quantum circuits |
| title_sort | from estimation of quantum probabilities to simulation of quantum circuits |
| url | https://quantum-journal.org/papers/q-2020-01-13-223/pdf/ |
| work_keys_str_mv | AT hakoppashayan fromestimationofquantumprobabilitiestosimulationofquantumcircuits AT stephendbartlett fromestimationofquantumprobabilitiestosimulationofquantumcircuits AT davidgross fromestimationofquantumprobabilitiestosimulationofquantumcircuits |