How to simulate quantum measurement without computing marginals

• URL: http://arxiv.org/abs/2112.08499v2
• Date: Thu, 6 Jan 2022 21:34:39 GMT
• Title: How to simulate quantum measurement without computing marginals
• Authors: Sergey Bravyi, David Gosset, Yinchen Liu
• Abstract summary: 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.
• Score: 3.222802562733787
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We describe and analyze algorithms for classically simulating measurement of an $n$-qubit quantum state $\psi$ in the standard basis, that is, sampling a bit string $x$ from the probability distribution $|\langle x|\psi\rangle|^2$. Our algorithms reduce the sampling task to computing poly$(n)$ amplitudes of $n$-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. First we consider the case where $|\psi\rangle=U|0^n\rangle$ is the output state of an $m$-gate quantum circuit $U$. We propose an exact sampling algorithm which involves computing $O(m)$ amplitudes of $n$-qubit states generated by subcircuits of $U$ spanned by the first $t=1,2,\ldots,m$ gates. We show that our algorithm can significantly accelerate quantum circuit simulations based on tensor network contraction methods or low-rank stabilizer decompositions. As another striking consequence we obtain an efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph, generalizing a previous algorithm which was known to be efficient only under restrictive topological constraints on the ordering of single-qubit measurements. Second, we consider the case in which $\psi$ is the unique ground state of a local Hamiltonian with a spectral gap that is lower bounded by an inverse polynomial function of $n$. We prove that a simple Metropolis-Hastings Markov Chain mixes rapidly to the desired probability distribution provided that $\psi$ obeys a certain technical condition, which we show is satisfied for all sign-problem free Hamiltonians. This gives a sampling algorithm which involves computing $\mathrm{poly}(n)$ amplitudes of $\psi$.

Related papers

• Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
  We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms. The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$. The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
  arXiv  Detail & Related papers  (2024-04-08T02:13:40Z)
• Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
  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.
  arXiv  Detail & Related papers  (2023-09-15T14:01:13Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
  We show that a na"ive partitioning and low-order splitting formula can yield, through our divide and conquer formalism, superior scaling to qubitization for large $Lambda$. We also give new algorithmic and circuit level techniques for gate optimization including a new way of implementing a group of multi-controlled-X gates.
  arXiv  Detail & Related papers  (2023-06-19T23:20:30Z)
• Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration [0.0]
  Quantum algorithms for MCMC have been proposed, yielding the quadratic speedup with respect to the spectral gap $Delta$ compered to classical counterparts. We consider not only state generation but also finding a credible interval for a parameter, a common task in Bayesian inference. In the proposed method for credible interval calculation, the number of queries to the quantum circuit to compute $ell$ scales on $Delta$, the required accuracy $epsilon$ and the standard deviation $sigma$ of $ell$ as $tildeO(sigma/epsilon
  arXiv  Detail & Related papers  (2023-03-10T01:05:16Z)
• 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)
• 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 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)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30: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.