Quantum advantages for Pauli channel estimation

• URL: http://arxiv.org/abs/2108.08488v2
• Date: Mon, 8 Nov 2021 20:25:49 GMT
• Title: Quantum advantages for Pauli channel estimation
• Authors: Senrui Chen, Sisi Zhou, Alireza Seif, Liang Jiang
• Abstract summary: 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.
• Score: 2.5496329090462626
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\varepsilon$ precision. We give an estimation protocol with an $n$-qubit ancilla that succeeds with high probability using only $O(n/\varepsilon^{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(n2^{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.

Related papers

• On the sample complexity of purity and inner product estimation [8.94496959777308]
  We study the sample complexity of the tasks quantum purity estimation and quantum inner product estimation. In purity estimation, we are to estimate $tr(rho2)$ of an unknown quantum state $rho$ to additive error $epsilon$. For quantum inner product estimation, Alice and Bob are to estimate $tr(rhosigma)$ to additive error $epsilon$ given copies of unknown quantum state $rho$ and $sigma$.
  arXiv  Detail & Related papers  (2024-10-16T16:17:21Z)
• 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)
• 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)
• Lower Bounds on Learning Pauli Channels [8.72305226979945]
  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
  arXiv  Detail & Related papers  (2023-01-22T20:01:34Z)
• 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)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• 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)

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.