Efficient Pauli channel estimation with logarithmic quantum memory

• URL: http://arxiv.org/abs/2309.14326v3
• Date: Fri, 15 Nov 2024 03:40:41 GMT
• Title: Efficient Pauli channel estimation with logarithmic quantum memory
• Authors: Sitan Chen, Weiyuan Gong,
• Abstract summary: We show that a protocol can estimate the eigenvalues of a Pauli channel to error $epsilon$ using only $O(log n/epsilon2)$ ancilla and $tildeO(n2/epsilon2)$ measurements. Our results imply, to our knowledge, the first quantum learning task where logarithmically many qubits of quantum memory suffice for an exponential statistical advantage.
• Score: 9.275532709125242
• License:
• Abstract: Here we revisit one of the prototypical tasks for characterizing the structure of noise in quantum devices: estimating every eigenvalue of an $n$-qubit Pauli noise channel to error $\epsilon$. Prior work [14] proved no-go theorems for this task in the practical regime where one has a limited amount of quantum memory, e.g. any protocol with $\le 0.99n$ ancilla qubits of quantum memory must make exponentially many measurements, provided it is non-concatenating. Such protocols can only interact with the channel by repeatedly preparing a state, passing it through the channel, and measuring immediately afterward. This left open a natural question: does the lower bound hold even for general protocols, i.e. ones which chain together many queries to the channel, interleaved with arbitrary data-processing channels, before measuring? Surprisingly, in this work we show the opposite: there is a protocol that can estimate the eigenvalues of a Pauli channel to error $\epsilon$ using only $O(\log n/\epsilon^2)$ ancilla and $\tilde{O}(n^2/\epsilon^2)$ measurements. In contrast, we show that any protocol with zero ancilla, even a concatenating one, must make $\Omega(2^n/\epsilon^2)$ measurements, which is tight. Our results imply, to our knowledge, the first quantum learning task where logarithmically many qubits of quantum memory suffice for an exponential statistical advantage. Our protocol can be naturally extended to a protocol that learns the eigenvalues of Pauli terms within any subset $A$ of a Pauli channel with $O(\log\log(|A|)/\epsilon^2)$ ancilla and $\tilde{O}(n^2/\epsilon^2)$ measurements.

Related papers

• Circuit Complexity of Sparse Quantum State Preparation [0.0]
  We show that any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(fracdnlog d)$ and depth $Theta(log dn)$ using at most $O(fracndlog d )$ ancillary qubits. We also establish the lower bound $Omega(fracdnlog(n + m) + log d + n)$ on the circuit size with $m$ ancillary qubits available.
  arXiv  Detail & Related papers  (2024-06-23T15:28:20Z)
• Optimal tradeoffs for estimating Pauli observables [13.070874080455862]
  We revisit the problem of Pauli shadow tomography: given copies of an unknown $n$-qubit quantum state $rho$, estimate $texttr(Prho)$ for some set of Pauli operators $P$ to within additive error $epsilon$. We show any protocol that makes $textpoly(n)$-copy measurements must make $Omega (1/epsilon4)$ measurements. The protocols we propose can also estimate the actual values $texttr(Prho)$, rather than just their absolute values
  arXiv  Detail & Related papers  (2024-04-29T20:57:05Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Quantum advantages for Pauli channel estimation [2.5496329090462626]
  entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation. We show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task.
  arXiv  Detail & Related papers  (2021-08-19T04:10:28Z)
• Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error [1.6522364074260811]
  We investigate the randomized and quantum communication complexities of the Equality function with small error probability $epsilon$. We show that any $log(n/epsilon)-loglog(sqrtn/epsilon)+3$ protocol communicates at least $log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubits.
  arXiv  Detail & Related papers  (2021-07-25T13:52:42Z)
• Pauli error estimation via Population Recovery [1.52292571922932]
  We study the problem of learning a Pauli channel, or more generally the Pauli error rates of an arbitrary channel. We give an extremely simple algorithm that learns the Pauli error rates of an $n$-qubit channel to precision $epsilon$ in $ell_infty$ We extend our algorithm to achieve multiplicative precision $1 pm epsilon$ (i.e., additive precision $epsilon eta$) using just $Obigl(frac1epsilon2 etabigr)
  arXiv  Detail & Related papers  (2021-05-06T18:00:02Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
  arXiv  Detail & Related papers  (2020-07-23T10:50:42Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.