Lower Bounds on Learning Pauli Channels with Individual Measurements

• URL: http://arxiv.org/abs/2301.09192v2
• Date: Fri, 16 May 2025 14:08:44 GMT
• Title: Lower Bounds on Learning Pauli Channels with Individual Measurements
• Authors: Omar Fawzi, Aadil Oufkir, Daniel Stilck França,
• Abstract summary: We show lower bounds on the sample complexity for learning Pauli channels in diamond norm.<n>We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel.
• Score: 6.909352249236339
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Understanding the noise affecting a quantum device is of fundamental importance for scaling quantum technologies. A particularly important class of noise models is that of Pauli channels, as randomized compiling techniques can effectively bring any quantum channel to this form and are significantly more structured than general quantum channels. In this paper, we show fundamental lower bounds on the sample complexity for learning Pauli channels in diamond norm. We consider strategies that may not use auxiliary systems entangled with the input to the unknown channel and have to perform a measurement before reusing the channel. For non-adaptive algorithms, we show a lower bound of $\Omega(2^{3n}\varepsilon^{-2})$ to learn an $n$-qubit Pauli channel. In particular, this shows that the recently introduced learning procedure by Flammia and Wallman is essentially optimal. In the adaptive setting, we show a lower bound of $\Omega(2^{2.5n}\varepsilon^{-2})$ for $\varepsilon=\mathcal{O}(2^{-n})$, and a lower bound of $\Omega(2^{2n}\varepsilon^{-2} )$ for any $\varepsilon> 0$. This last lower bound holds even in a stronger model where in each step, before performing the measurement, the unknown channel may be used arbitrarily many times sequentially interspersed with unital operations.

Related papers

• Pauli measurements are not optimal for single-copy tomography [34.83118849281207]
  We prove a stronger upper bound of $O(frac10Nepsilon2)$ and a lower bound of $Omega(frac9.118Nepsilon2)$. This demonstrates the first known separation between Pauli measurements and structured POVMs.
  arXiv  Detail & Related papers  (2025-02-25T13:03:45Z)
• Pauli quantum computing: $I$ as $|0\rangle$ and $X$ as $|1\rangle$ [0.0]
  We propose a new quantum computing formalism named Pauli quantum computing. In this formalism, we use the Pauli basis $I$ and $X$ on the non-diagonal blocks of density matrices to encode information. We show how to design Lindbladians to realize imaginary time evolutions and prepare stabilizer ground states in Pauli quantum computing.
  arXiv  Detail & Related papers  (2024-12-04T08:15:31Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Efficient Pauli channel estimation with logarithmic quantum memory [9.275532709125242]
  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.
  arXiv  Detail & Related papers  (2023-09-25T17:53:12Z)
• Tight bounds on Pauli channel learning without entanglement [2.2845597309741157]
  We consider learning algorithms without entanglement to be those that only utilize states, measurements, and operations that are separable between the main system of interest and an ancillary system. We show that these algorithms are equivalent to those that apply quantum circuits on the main system interleaved with mid-circuit measurements and classical feedforward.
  arXiv  Detail & Related papers  (2023-09-23T19:12:29Z)
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach [1.806183113759115]
  Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve quantum advantages. We present a novel $gammaPPP method based on the integral path of observables back-propagation on paths. We conduct classical simulations of IBM's zeronoised experimental results on the 127-qubit Eagle processor.
  arXiv  Detail & Related papers  (2023-06-09T10:42:07Z)
• Pauli-based model of quantum computation with higher-dimensional systems [0.0]
  Pauli-based computation (PBC) is a universal model for quantum computation with qubits. We generalize PBC for odd-prime-dimensional systems and demonstrate its universality.
  arXiv  Detail & Related papers  (2023-02-27T12:05:13Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• 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)
• 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 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)
• 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)
• Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
  We study two different methods to prepare excited states on a quantum computer. We benchmark these techniques on emulated and real quantum devices. These findings show that quantum techniques designed to achieve good scaling on fault tolerant devices might also provide practical benefits on devices with limited connectivity and gate fidelity.
  arXiv  Detail & Related papers  (2020-09-28T17:21:25Z)

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.