Classical simulation of peaked shallow quantum circuits
- URL: http://arxiv.org/abs/2309.08405v1
- Date: Fri, 15 Sep 2023 14:01:13 GMT
- Title: Classical simulation of peaked shallow quantum circuits
- Authors: Sergey Bravyi, David Gosset, Yinchen Liu
- Abstract summary: We describe an algorithm with quasipolynomial runtime $nO(logn)$ that samples from the output distribution of a peaked constant-depth circuit.
Our algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error.
- Score: 2.6089354079273512
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An $n$-qubit quantum circuit is said to be peaked if it has an output
probability that is at least inverse-polynomially large as a function of $n$.
We describe a classical algorithm with quasipolynomial runtime $n^{O(\log{n})}$
that approximately samples from the output distribution of a peaked
constant-depth circuit. We give even faster algorithms for circuits composed of
nearest-neighbor gates on a $D$-dimensional grid of qubits, with polynomial
runtime $n^{O(1)}$ if $D=2$ and almost-polynomial runtime
$n^{O(\log{\log{n}})}$ for $D>2$. Our sampling algorithms can be used to
estimate output probabilities of shallow circuits to within a given
inverse-polynomial additive error, improving previously known methods. As a
simple application, we obtain a quasipolynomial algorithm to estimate the
magnitude of the expected value of any Pauli observable in the output state of
a shallow circuit (which may or may not be peaked). This is a dramatic
improvement over the prior state-of-the-art algorithm which had an exponential
scaling in $\sqrt{n}$.
Related papers
- Do you know what q-means? [50.045011844765185]
Clustering is one of the most important tools for analysis of large datasets.
We present an improved version of the "$q$-means" algorithm for clustering.
We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
arXiv Detail & Related papers (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis.
Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
arXiv Detail & Related papers (2021-12-15T21:44:05Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
We prove under the theoretical complexity of the non-concentration hierarchy that approximating the output probabilities to within $2-Omega(nlogn)$ is hard.
We show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including trivial circuit with identity gates.
arXiv Detail & Related papers (2021-02-03T09:20:32Z) - Fast estimation of outcome probabilities for quantum circuits [0.0]
We present two classical algorithms for the simulation of universal quantum circuits on $n$ qubits.
Our algorithms complement each other by performing best in different parameter regimes.
We provide a C+Python implementation of our algorithms and benchmark them using random circuits.
arXiv Detail & Related papers (2021-01-28T19:00:04Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$.
The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
arXiv Detail & Related papers (2020-09-09T18:00:09Z) - Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
Google's noisy quantum simulation of a 53 qubit circuit $C$ achieved a fidelity value of $(2.24pm0.21)times10-3$.
Our results can be considered as an evidence that fooling the linear XEB test might be easier than achieving a full simulation of quantum circuit.
arXiv Detail & Related papers (2020-05-05T18:01:48Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.