Papers
arxiv:2407.12768

A polynomial-time classical algorithm for noisy quantum circuits

Published on Oct 14, 2024
Authors:
,
,
,

Abstract

A polynomial-time classical algorithm computes expectation values for noisy quantum circuits by leveraging noise-induced damping of non-local correlations, enabling efficient simulation and sampling under certain conditions.

AI-generated summary

We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g. the computational basis). Our approach is based upon the intuition that noise exponentially damps non-local correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by only keeping track of the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasi-polynomial time, so long as the distribution anti-concentrates. A number of practical implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: for constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.

Community

Sign up or log in to comment

Get this paper in your agent:

hf papers read 2407.12768
Don't have the latest CLI?
curl -LsSf https://hf.co/cli/install.sh | bash

Models citing this paper 0

No model linking this paper

Cite arxiv.org/abs/2407.12768 in a model README.md to link it from this page.

Datasets citing this paper 0

No dataset linking this paper

Cite arxiv.org/abs/2407.12768 in a dataset README.md to link it from this page.

Spaces citing this paper 0

No Space linking this paper

Cite arxiv.org/abs/2407.12768 in a Space README.md to link it from this page.

Collections including this paper 0

No Collection including this paper

Add this paper to a collection to link it from this page.