Predicting quantum channels over general product distributions

• URL: http://arxiv.org/abs/2409.03684v1
• Date: Thu, 5 Sep 2024 16:39:13 GMT
• Title: Predicting quantum channels over general product distributions
• Authors: Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh, Hsin-Yuan Huang, Jane Lange, Jerry Li,
• Abstract summary: We learn the mapping beginequation* rho mapsto mathrmTr(O E[rho]) endequation* to within a small error for most $rho$ sampled from a distribution $D$. We propose a new approach that achieves accurate prediction over essentially any product distribution $D$, provided it is not "classical" in which case there is a trivial exponential lower bound.
• Score: 19.09244195034539
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an $n$-qubit channel $E$ and an observable $O$, we aim to learn the mapping \begin{equation*} \rho \mapsto \mathrm{Tr}(O E[\rho]) \end{equation*} to within a small error for most $\rho$ sampled from a distribution $D$. Previously, Huang, Chen, and Preskill proved a surprising result that even if $E$ is arbitrary, this task can be solved in time roughly $n^{O(\log(1/\epsilon))}$, where $\epsilon$ is the target prediction error. However, their guarantee applied only to input distributions $D$ invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states $\rho$. In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution $D$, provided it is not "classical" in which case there is a trivial exponential lower bound. Our method employs a "biased Pauli analysis," analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information.

Related papers

• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Here we study the complexity of NGCA in the Sum-of-Squares framework.
  arXiv  Detail & Related papers  (2024-10-28T18:19:13Z)
• Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates [53.66705737169404]
  We consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Our main findings are that the maximum number of messages thus identifiable scales super-exponentially as $2R,nlog n$ with the block length $n$. Results are shown to generalise directly to classical-quantum channels with finite-dimensional output quantum system.
  arXiv  Detail & Related papers  (2024-02-14T11:59:30Z)
• $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
  This work shows that the only prior distribution on $X$ that induces linearity in the conditional median is Gaussian. In particular, it is demonstrated that if the conditional distribution $P_X|Y=y$ is symmetric for all $y$, then $X$ must follow a Gaussian distribution.
  arXiv  Detail & Related papers  (2023-09-17T01:45:13Z)
• No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
  We give an almost complete characterization of the hardness of $c$-coloring $chi$-chromatic graphs with distributed algorithms. We show that these problems do not admit any distributed quantum advantage.
  arXiv  Detail & Related papers  (2023-07-18T17:17:27Z)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  We show that for a large class of symmetric distributions, the same error as in the Gaussian setting can be achieved efficiently. We propose a sequence of efficient algorithms that approaches this optimal error. Our algorithms are based on a generalization of the well-known filtering technique.
  arXiv  Detail & Related papers  (2023-02-21T17:52:23Z)
• Non-Gaussian Component Analysis via Lattice Basis Reduction [56.98280399449707]
  Non-Gaussian Component Analysis (NGCA) is a distribution learning problem. We provide an efficient algorithm for NGCA in the regime that $A$ is discrete or nearly discrete.
  arXiv  Detail & Related papers  (2021-12-16T18:38:02Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• 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)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)
• A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
  We introduce a new type of minimax theorem which can provide a hard distribution $mu$ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, approximate degreelemma, and approximate logrank. We also prove an improved version of Impagliazzo's hardcore.
  arXiv  Detail & Related papers  (2020-02-25T11:46:08Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

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.