We study distributed similarity estimation of quantum channels (DSEC), a primitive for cross-platform verification where two remote quantum devices are compared by estimating the inner product of their Choi states. We show that the optimal channel query complexity of DSEC for two $d$-dimensional quantum channels is $Θ(\max\{\sqrt{d}/\varepsilon, 1/\varepsilon^2\})$, where $\varepsilon$ is the additive error. We first prove an information-theoretic lower bound with this scaling, which holds even in the strongest setting, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the weakest setting, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement protocol achieving this bound. Finally, we show that our protocol achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical methods for cross-platform verification, quantum device benchmarking, and distributed quantum learning.
We study distributed similarity estimation of quantum channels (DSEC), a primitive for cross-platform verification where two remote quantum devices are compared by estimating the inner product of their Choi states. We show that the optimal channel query complexity of DSEC for two d-dimensional quantum channels is Θ(max{d/ε,1/ε2}), where ε is the additive error. We first prove an information-theoretic lower bound with this scaling, which holds even in the strongest setting, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the weakest setting, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement protocol achieving this bound. Finally, we show that our protocol achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical methods for cross-platform verification, quantum device benchmarking, and distributed quantum learning.
As small quantum computers are becoming available on different physical platforms, a benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. This task is fundamentally distributed, as no quantum communication can be performed between the two physical platforms due to hardware constraints, which prohibits a joint SWAP test. In this paper we settle the sample complexity of this task across all measurement and communication settings. The essence of the task, which we call distributed quantum inner product estimation, involves two players Alice and Bob who have k copies of unknown states ρ,σ (acting on ℂd) respectively. Their goal is to estimate Tr(ρσ) up to additive error ε∈(0,1), using local quantum operations and classical communication. In the weakest setting where only non-adaptive single-copy measurements and simultaneous message passing are allowed, we show that k=O(max{1/ε2,√d/ε}) copies suffice. This achieves a savings compared to full tomography which takes Ω(d3) copies with single-copy measurements. Surprisingly, we also show that the sample complexity must be at least Ω(max{1/ε2,√d/ε}), even in the strongest setting where adaptive multi-copy measurements and arbitrary rounds of communication are allowed. This shows that the success achieved by shadow tomography, for sample-efficiently learning the properties of a single system, cannot be generalized to the distributed setting. Furthermore, the fact that the sample complexity remains the same with single and multi-copy measurements contrasts with single system quantum property testing, which often demonstrate exponential separations in sample complexity with single and multi-copy measurements.
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 Θ(din3dout3/ε2), where din and dout are the channel input and output dimensions, respectively, and ε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires Ω(din3dout3/ε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(din3dout3/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case din=1. By contrast, coherent protocols with quantum memory achieve query complexity Θ(din2dout2/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
Estimating the unitarity of an unknown quantum channelEprovides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that useO(ϵ−2)andO(d⋅ϵ−2)calls toEwith coherent and incoherent accesses, respectively, wheredis the dimension of the system thatEacts on and$\epsilon istherequiredprecision.Wefurthershowthatboththed−dependenceand\epsilon −dependenceofouralgorithmsareoptimal.Aspartofourresults,wesettlethequerycomplexityofthedistinguishingproblemfordepolarizingandunitarychannelswithincoherentaccessbygivingamatchinglowerbound\Omega (\sqrt {d}),improvingthepriorbestlowerbound\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).
Full tomography of an unknown quantum evolution is resource-intensive and often unnecessary when the goal is only to predict selected properties. This motivates the study of classical shadow estimation of unitary channels (CSEU), a task in which one queries an unknown d-dimensional unitary U and stores classical data that can later be used to predict expectation values tr[OUρU†] for arbitrary input states ρ and observables O. Here we propose a parallel and non-adaptive CSEU protocol that uses O(min{dε−2,d3/2ε−1}) queries to U when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error ε and is query-optimal, as we prove a matching lower bound Ω(min{dε−2,d3/2ε−1}) for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.
Quantum process tomography, the task of estimating an unknown quantum channel, is a central problem in quantum information theory. A long-standing open question is how many uses of an unknown channel are required to learn it in diamond distance, the standard metric for distinguishing quantum processes. While quantum state tomography is well understood, for general channels the problem remained open beyond the unitary case. Here we establish the query complexity of channel tomography with optimal dependence on the dimension parameters, at any fixed constant accuracy. We design an algorithm showing that any channel with input/output dimensions din,dout and Kraus rank at most k can be learned to accuracy ε using O(dindoutk/ε2) channel uses. Conversely, we prove that Ω(dindoutk) uses are necessary at constant accuracy and that, for non-minimal Kraus rank, a separate Ω(1/ε2) contribution is unavoidable. Since channels subsume states, unitaries, isometries, and measurements as special cases, our protocol provides a unified framework for these tomography tasks, yielding new guarantees for isometry and measurement tomography while recovering known optimal scalings for state and unitary tomography. Our algorithm follows the natural strategy of performing optimal tomography on the Choi state. The main technical contribution is to show that this suffices to control the induced diamond-distance error, avoiding the dimension loss incurred by a naive conversion from Choi-state trace distance to channel diamond distance. The protocol uses the channel non-adaptively to prepare Choi-state copies, purifies them in parallel, and performs optimal pure-state tomography on the resulting purifications. Hence, we reduce channel tomography to pure-state tomography.
Quantum channels can be characterized by their action on an orthogonal operator basis, where these operators are related to observable properties of the quantum system. For qudit and multimode bosonic systems, this is encoded respectively in the Heisenberg--Weyl transfer matrix estimated from the Choi-state, and in the characteristic-function transfer map estimated from a two-mode squeezed vacuum based Choi-state. We derive sample-complexity bounds for estimating entries of the transfer matrix/map to additive accuracy ε with success probability ≥1−δ, under different resources: access to the complex-conjugate channel E∗ and/or parallel access to c copies. In all settings, the learner uses parallel channel calls with adaptively chosen, ancilla-assisted input states and measurements. Absolute values of transfer-matrix entries can be learned efficiently with simultaneous access to E and E∗, with tight scaling ε−4. Without conjugate access, any c<d copies are insufficient for efficient learning, requiring sample complexity exponential in the number of (d-level) qudits n (for prime d). Efficiency is recovered at c=d, with tight scaling ε−2d. For bosonic systems, exponential sample complexity holds in terms of an effective dimension induced by an energy constraint for all c=O(1/ε). Although the task is learning a particular state, these bounds carry stronger implications than standard state-learning bounds since the learner controls the inputs and has ancillary assistance. This establishes a hierarchy of channel-learning resources: self-complex-conjugate channels require two-copy ancilla-assisted access for efficient learning, while for every square-free d, some channels require d-copy access. As a corollary, we derive tighter lower bounds for state learning with limited multi-copy access.