Optimal lower bound for quantum channel tomography in away-from-boundary regime

• URL: http://arxiv.org/abs/2601.10683v1
• Date: Thu, 15 Jan 2026 18:45:59 GMT
• Title: Optimal lower bound for quantum channel tomography in away-from-boundary regime
• Authors: Kean Chen, Zhicheng Zhang, Nengkun Yu,
• Abstract summary: Heisenberg scaling $(d2/varepsilon)$ is achievable.<n>In particular, this lower bound fully settles the query complexity for the commonly studied case of equal input and output dimensions.
• Score: 32.904052887092284
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider quantum channels with input dimension $d_1$, output dimension $d_2$ and Kraus rank at most $r$. Any such channel must satisfy the constraint $rd_2\geq d_1$, and the parameter regime $rd_2=d_1$ is called the boundary regime. In this paper, we show an optimal query lower bound $Ω(rd_1d_2/\varepsilon^2)$ for quantum channel tomography to within diamond norm error $\varepsilon$ in the away-from-boundary regime $rd_2\geq 2d_1$, matching the existing upper bound $O(rd_1d_2/\varepsilon^2)$. In particular, this lower bound fully settles the query complexity for the commonly studied case of equal input and output dimensions $d_1=d_2=d$ with $r\geq 2$, in sharp contrast to the unitary case $r=1$ where Heisenberg scaling $Θ(d^2/\varepsilon)$ is achievable.

Related papers

• Improved Lower Bounds for Learning Quantum Channels in Diamond Distance [2.1198879079315573]
  We prove that learning an unknown quantum channel with input dimension $d_A$, output dimension $d_B$, and Choi rank $r$ to diamond distance $varepsilon$ requires $!left( fracd_A d_B rvarepsilon log(d_B r / varepsilon) right)$ channel queries when $d_A= rd_B$, and $!left( fracd_A d_B rvarepsilon2 log(d
  arXiv  Detail & Related papers  (2026-01-07T18:48:30Z)
• Quantum channel tomography and estimation by local test [32.904052887092284]
  Heisenberg scaling $O(1/varepsilon)$ can be achieved, even if $mathcalE$ is not a unitary channel.<n>We show that for parallel (possibly coherent) testers, access to dilations does not help.
  arXiv  Detail & Related papers  (2025-12-15T18:07:42Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
  Dicke states represent an important class of entangled quantum states with broad applications in quantum computing.<n>We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints.
  arXiv  Detail & Related papers  (2025-05-21T11:55:17Z)
• Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers [9.136389487369117]
  We significantly improve the sample complexity of estimating $operatornametr(rhoq)$ in both the upper and lower bounds.<n>Our upper bounds are obtained by (non-plug-in) quantum estimators based on weak Schur sampling.
  arXiv  Detail & Related papers  (2025-05-14T17:06:33Z)
• Query-optimal estimation of unitary channels in diamond distance [3.087385668501741]
  We consider process tomography for unitary quantum channels. We output a classical description of a unitary that is $varepsilon$-close to the unknown unitary in diamond norm.
  arXiv  Detail & Related papers  (2023-02-27T19:00:00Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Scattering data and bound states of a squeezed double-layer structure [77.34726150561087]
  A structure composed of two parallel homogeneous layers is studied in the limit as their widths $l_j$ and $l_j$, and the distance between them $r$ shrinks to zero simultaneously. The existence of non-trivial bound states is proven in the squeezing limit, including the particular example of the squeezed potential in the form of the derivative of Dirac's delta function. The scenario how a single bound state survives in the squeezed system from a finite number of bound states in the finite system is described in detail.
  arXiv  Detail & Related papers  (2020-11-23T14:40:27Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

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.