Quantum memory advantage for quantum process tomography

• URL: http://arxiv.org/abs/2607.13476v1
• Date: Wed, 15 Jul 2026 06:09:08 GMT
• Title: Quantum memory advantage for quantum process tomography
• Abstract summary: Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information.<n>We show that quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments.<n>Our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
• Score: 2.956729394666618
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be $Θ(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$, where $d_{\mathrm{in}}$ and $d_{\mathrm{out}}$ are the channel input and output dimensions, respectively, and $\varepsilon$ is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires $Ω(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$ queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound $O(d_{\mathrm{in}}^3 d_{\mathrm{out}}^3/\varepsilon^2)$. Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case $d_{\mathrm{in}}=1$. By contrast, coherent protocols with quantum memory achieve query complexity $Θ(d_{\mathrm{in}}^2 d_{\mathrm{out}}^2/\varepsilon^2)$. Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.

Related papers

• Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning [0.3277163122167433]
  We develop an information-theoretic Occam theory for quantum data generated by finite-size quantum circuits.<n>With $M$ copies, one can learn up to the best $G$-gate approximation error plus a statistical penalty.<n>Our framework turns bounded circuit complexity into a model-selection principle for quantum machine learning.
  arXiv  Detail & Related papers  (2026-06-10T15:28:36Z)
• Optimal learning of quantum channels in diamond distance [0.0]
  We show that a quantum channel acting on a $d$-dimensional system can be estimated to accuracy $varepsilon$ in diamond distance.<n>We obtain, to the best of our knowledge, the first essentially optimal strategies for operator-norm learning of binary POVMs and isometries.
  arXiv  Detail & Related papers  (2025-12-11T02:04:03Z)
• Quantum Homogenization as a Quantum Steady State Protocol on NISQ Hardware [42.52549987351643]
  Quantum homogenization is a reservoir-based quantum state approximation protocol.<n>We extend the standard quantum homogenization protocol to the dynamically-equivalent ($mathttSWAP$)$alpha$ formulation.<n>We show that our proposed protocol yields a completely positive, trace preserving (CPTP) map under which the code subspace is correctable.
  arXiv  Detail & Related papers  (2024-12-19T05:50:54Z)
• 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)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Efficient Pauli channel estimation with logarithmic quantum memory [17.16536262746742]
  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.<n>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)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Exponential separations between learning with and without quantum memory [17.763817187554096]
  We study the power of quantum memory for learning properties of quantum systems and dynamics. Many state-of-the-art learning algorithms require access to an additional external quantum memory. We show that this trade-off is inherent in a wide range of learning problems.
  arXiv  Detail & Related papers  (2021-11-10T19:03:49Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

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.