Lower Bounds on Learning Pauli Channels
- URL: http://arxiv.org/abs/2301.09192v1
- Date: Sun, 22 Jan 2023 20:01:34 GMT
- Title: Lower Bounds on Learning Pauli Channels
- Authors: Omar Fawzi, Aadil Oufkir and Daniel Stilck Fran\c{c}a
- Abstract summary: We show lower bounds on the sample complexity for learning Pauli channels in diamond norm with unentangled measurements.
In the non-adaptive setting, we show a lower bound of $Omega (23nepsilon-2)$ to learn an $n$-qubit Pauli channel.
In the adaptive setting, we show a lower bound of $Omega (22.5nepsilon-2)$ for $epsilon=mathcalO (2-n)$, and a lower bound of $Omega (22n
- Score: 8.72305226979945
- 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 with unentangled measurements. We consider both adaptive and non-adaptive
strategies. In the non-adaptive setting, we show a lower bound of
$\Omega(2^{3n}\epsilon^{-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}\epsilon^{-2})$ for
$\epsilon=\mathcal{O}(2^{-n})$, and a lower bound of
$\Omega(2^{2n}\epsilon^{-2} )$ for any $\epsilon > 0$. This last lower bound
even applies for arbitrarily many sequential uses of the channel, as long as
they are only interspersed with other unital operations.
Related papers
- 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 [10.95781315121668]
We show that a protocol can estimate the eigenvalues of a Pauli channel to error $epsilon$ using only $O(log n/epsilon2)$ ancilla qubits 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) - 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)
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.