Quantum advantages for Pauli channel estimation

Abstract

We show that entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and a practically important subroutine for benchmarking near-term quantum devices. The specific task we consider is to simultaneously learn all the eigenvalues of an $n$-qubit Pauli channel to $\pm \epsilon$ precision. We give an estimation protocol with an $n$-qubit ancilla that succeeds with high probability using only $O(n/{\epsilon }^2)$ copies of the Pauli channel, while prove that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least $\Omega (2^{n/3})$ rounds of measurement. We further study the advantages provided by a small number of ancillas. For the case that a $k$-qubit ancilla ($k\le n$) is available, we obtain a sample complexity lower bound of $\Omega (2^{(n-k)/3})$ for any non-concatenating protocol, and a stronger lower bound of $\Omega (n{2}^{n-k})$ for any non-adaptive, non-concatenating protocol, which is shown to be tight. We also show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task in a noise-resilient and sample-efficient manner, given reasonable noise assumptions. Our results provide a practically-interesting example for quantum advantages in learning and also bring new insight for quantum benchmarking.

21 pages, 5 figures. Introduction rewritten, additional references added, typo corrected

References in corpus (13)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Randomized Benchmarking of Quantum Gates
• Dynamical decoupling and noise spectroscopy with a superconducting flux qubit
• Robust randomized benchmarking of quantum processes
• Quantum Process Tomography: Resource Analysis of Different Strategies
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Pauli error estimation via Population Recovery
• Benchmarking near-term quantum computers via random circuit sampling
• Mixed state Pauli channel parameter estimation
• Quantum advantage for noisy channel discrimination
• Toward Instance-Optimal State Certification With Incoherent Measurements

Cited by in corpus (34)

• Quantum advantage in learning from experiments
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Out-of-distribution generalization for learning quantum dynamics
• The learnability of Pauli noise
• Robust and Efficient Hamiltonian Learning
• Classical shadows with Pauli-invariant unitary ensembles
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Learning shallow quantum circuits
• Entanglement-enabled advantage for learning a bosonic random displacement channel
• Iso-entangled bases and joint measurements
• Tight bounds on Pauli channel learning without entanglement
• Limits of noisy quantum metrology with restricted quantum controls
• Achieving metrological limits using ancilla-free quantum error-correcting codes
• Mitigating Quantum Errors via Truncated Neumann Series
• Virtual distillation with noise dilution
• Quantum learning advantage on a scalable photonic platform
• Mixing Time of Open Quantum Systems via Hypocoercivity
• Quantum algorithm for evaluating operator size with Bell measurements
• Demonstrating quantum error mitigation on logical qubits
• Ansatz-free Hamiltonian learning with Heisenberg-limited scaling
• Efficient self-consistent learning of gate set Pauli noise
• Sample-Optimal Quantum Process Tomography with Non-Adaptive Incoherent Measurements
• Lower Bounds on Learning Pauli Channels with Individual Measurements
• Frozen condition of quantum coherence
• Theory of quantum error mitigation for non-Clifford gates
• Agnostic Process Tomography
• Noise-Agnostic Unbiased Quantum Error Mitigation for Logical Qubits
• State convertibility under genuinely incoherent operations
• Adaptivity is not helpful for Pauli channel learning
• On the Fundamental Resource for Exponential Advantage in Quantum Channel Learning
• On the query complexity of unitary channel certification
• Disambiguating Pauli noise in quantum computers
• Probabilistic Coherence Transformation Under Strictly Incoherent Operation
• Decoded Quantum Interferometry Under Noise