We initiate the study of weak Schur sampling (WSS) under noisy inputs. Many optimal quantum learning algorithms rely on this measurement, for instance in quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the $n$ input copies of the target state $ρ$ are identical, i.e. $ρ^{\otimes n}$. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest model the input is a noisy product state: the copies are independent but not necessarily identical and each is $ε$-close in trace distance to the $d$-dimensional target state $ρ$. A naive argument via the data-processing inequality allows the per-copy errors to accumulate to $nε$ on the measurement outcome. We show that for QSE via WSS this does not happen: the expected estimation error in total variation is at most $ε+η(n,d)$, where $η(n,d)=O(d/\sqrt n)$ is the noiseless error, and the additive noise term $ε$ is optimal. The output error does not grow with $n$ even though the input error does; in this sense WSS is robust. Beyond noisy product states, for arbitrary input $ω$ we show that the error is at most $η(n,d)+\frac{1}{n}\|ω-ρ^{\otimes n}\|_{W_1}$, where $W_1$ is the quantum Wasserstein distance of De Palma et al. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Finally, we show that the noise cannot be too bad: within our model of robustness the promise on the input cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, as in both cases some inputs defeat every measurement and estimator.
Comments
v2: minor corrections in the phrasing of the results, abstract revised
We initiate the study of weak Schur sampling (WSS) under noisy inputs. Many optimal quantum learning algorithms rely on this measurement, for instance in quantum spectrum estimation (QSE) and quantum state tomography (QST). The standard analysis of WSS, QSE and QST assumes that the n input copies of the target state ρ are identical, i.e. ρ⊗n. We study what happens when they are not, a more realistic noisy scenario that breaks the very permutation symmetry on which WSS is built. In the simplest model the input is a noisy product state: the copies are independent but not necessarily identical and each is ε-close in trace distance to the d-dimensional target state ρ. A naive argument via the data-processing inequality allows the per-copy errors to accumulate to nε on the measurement outcome. We show that for QSE via WSS this does not happen: the expected estimation error in total variation is at most ε+η(n,d), where η(n,d)=O(d/n) is the noiseless error, and the additive noise term ε is optimal. The output error does not grow with n even though the input error does; in this sense WSS is robust. Beyond noisy product states, for arbitrary input ω we show that the error is at most η(n,d)+n1∥ω−ρ⊗n∥W1, where W1 is the quantum Wasserstein distance of De Palma et al. In particular, our results imply, for the first time, noise-robustness of Keyl and Werner's seminal algorithm for QSE, more than two decades after its introduction. Finally, we show that the noise cannot be too bad: within our model of robustness the promise on the input cannot be weakened to closeness of single-copy marginals or to a global trace-distance budget alone, as in both cases some inputs defeat every measurement and estimator.
With a finite amount of measurement data acquired in variational quantum algorithms, the statistical benefits of several optimized numerical estimation schemes, including the scaled parameter-shift (SPS) rule and finite-difference (FD) method, for estimating gradient and Hessian functions over analytical schemes [unscaled parameter-shift (PS) rule] were reported by the present author [Phys. Rev. A 107, 042421 (2023)]. We continue the saga by exploring the extent to which these numerical schemes remain statistically more accurate for a given number of sampling copies in the presence of noise. For noise-channel error terms that are independent of the circuit parameters, we demonstrate that without any knowledge about the noise channel, using the SPS and FD estimators optimized specifically for noiseless circuits can still give lower mean-squared errors than PS estimators for substantially wide sampling-copy number ranges---specifically for SPS, closed-form mean-squared error expressions reveal that these ranges grow exponentially in the qubit number and reciprocally with a decreasing error rate. Simulations also demonstrate similar characteristics for the FD scheme. Lastly, if the error rate is known, we propose a noise-model-agnostic error-mitigation procedure to optimize the SPS estimators under the assumptions of two-design circuits and circuit-parameter-independent noise-channel error terms. We show that these heuristically optimized SPS estimators can significantly reduce mean-squared-error biases that naive SPS estimators possess even with realistic circuits and noise channels, thereby improving their estimation qualities even further. The heuristically optimized FD estimators possess as much mean-squared-error biases as the naively optimized counterparts and are thus not beneficial with noisy circuits.
There has been significant interest in understanding how practical constraints on contemporary quantum devices impact the complexity of quantum learning. For the classic question of tomography, recent work tightly characterized the copy complexity for any protocol that can only measure one copy of the unknown state at a time, showing it is polynomially worse than if one can make fully-entangled measurements. While we now have a fairly complete picture of the rates for such tasks in the near-term and fault-tolerant regimes, it remains poorly understood what the landscape in between these extremes looks like, and in particular how to gracefully scale up our protocols as we transition away from NISQ. In this work, we study tomography in the natural setting where one can make measurements of t copies at a time. For sufficiently small є, we show that for any t ≤ d2, Θ(d3/√tє2) copies are necessary and sufficient to learn an unknown d-dimensional state ρ to trace distance є. This gives a smooth and optimal interpolation between the known rates for single-copy measurements and fully-entangled measurements. To our knowledge, this is the first smooth entanglement-copy tradeoff known for any quantum learning task, and for tomography, no intermediate point on this curve was known, even at t = 2. An important obstacle is that unlike the optimal single-copy protocol, the optimal fully-entangled protocol is inherently a biased estimator. This bias precludes naive batching approaches for interpolating between the two protocols. Instead, we devise a novel two-stage procedure that uses Keyl’s algorithm to refine a crude estimate for ρ based on single-copy measurements. A key insight is to use Schur-Weyl sampling not to estimate the spectrum of ρ, but to estimate the deviation of ρ from the maximally mixed state. When ρ is far from the maximally mixed state, we devise a novel quantum splitting procedure that reduces to the case where ρ is close to maximally mixed.
We study the sample complexity of shadow tomography in the high-precision regime under realistic measurement constraints. Given an unknown d-dimensional quantum state ρ and a known set of observables {Oi}i=1m, the goal is to estimate expectation values {tr(Oiρ)}i=1m to accuracy ε in Lp-norm, using possibly adaptive measurements that act on O(polylog(d)) number of copies of ρ at a time. We focus on the regime where ε is below an instance-dependent threshold.
Our main contribution is an instance-optimal characterization of the sample complexity as Θ~(Γp/ε2), where Γp is a function of {Oi}i=1m defined via an optimization formula involving the inverse Fisher information matrix. Previously, tight bounds were known only in special cases, e.g. Pauli shadow tomography with L∞-norm error. Concretely, we first analyze a simpler oblivious variant where the goal is to estimate an observable of the form ∑i=1mαiOi with ∥α∥q=1 (where q is dual to p) revealed after the measurement. For single-copy measurements, we obtain a sample complexity of Θ(Γpob/ε2). We then show Θ~(Γp/ε2) is necessary and sufficient for the original problem, with the lower bound applying to unbiased, bounded estimators. Our upper bounds rely on a two-step algorithm combining coarse tomography with local estimation. Notably, Γ∞ob=Γ∞. In both cases, allowing c-copy measurements improves the sample complexity by at most Ω(1/c).
Our results establish a quantitative correspondence between quantum learning and metrology, unifying asymptotic metrological limits with finite-sample learning guarantees.
Quantum state tomography (QST) has attracted considerable attention due to its fundamental role in quantum information processing. In this paper, we develop a unified theoretical framework for analyzing the sample complexity of structured QST under noisy observations arising from state preparation noise, measurement noise, and finite-shot statistical noise. The proposed framework applies to a broad family of structured quantum-state classes, including general mixed states, sparse states, low-rank states, matrix product states (MPSs), matrix product operators (MPOs), projected entangled-pair states (PEPSs), and projected entangled-pair operators (PEPOs), while further introducing physically consistent structured models---including low-rank and sparse states, low-rank MPOs (LR-MPOs), and low-rank PEPOs (LR-PEPOs)---that simultaneously exploit low-dimensional structures and preserve the physical constraint. Within this framework, we derive unified non-asymptotic sample complexity guarantees for two constrained least-squares estimators under noisy observations: a noise-aware estimator that incorporates the calibrated noise model and a noise-unaware estimator based on the ideal Born measurement model. For the noise-aware estimator, we derive unified trace-norm recovery guarantees that explicitly characterize the dependence of the sample complexity on three fundamental quantities: the complexity of the underlying structured state class, the complexity of the measurement ensemble, and the state preparation and measurement noise levels. For the noise-unaware estimator, we establish a unified non-asymptotic recovery guarantee consisting of a statistical error term and an additional deterministic bias term arising from the mismatch between the assumed reconstruction model and the noisy observation process.
Quantum technologies have rapidly advanced over the past decade or so.However, noise and decoherence are still challenges.At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices.However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult.With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years.In this thesis we answer several questions in this vein.First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩ = 1 √ 2 nx |x, c(x)⟩.We show that, if T copies suffice to learn f using entangled measurements, O(nT 2 ) copies suffice to learn f using only separable measurements.Second, we study the Quantum Statistical Query model.We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise).This proves the "quantum analogue" of the seminal result of Blum, Kalai, & Wasserman.[1] that separates classical SQ learning from classical PAC learning with classification noise.To obtain these bounds, we introduce a quantum statistical query dimension (QSD).We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n).We also show that an extension of QSD characterizes the complexity of general search problems.Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model.Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption.Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication.Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ , |ϕ⟩ respectively.They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩| 2 up to constant additive error.We show that k = Θ( √ 2 n-q ) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0).Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M |ϕ⟩| 2 , for arbitrary Hermitian M .For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M |ϕ⟩| 2 when using only classical communication.Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copycomplexity separations.To that end, we prove that estimating Tr[ρ k ], for k a constant, requires Ω(log d) samples with (k -1)-copy measurements.By contrast, O(1) samples suffice with k-copy measurements.To obtain our bounds, we extend Harrow's [5] method of PPT constraints on sums of permutations.This thesis and the work within would not have been possible without the support and encouragement of many people.I would like to start with my PhD advisor Eric Chitambar, whose support and guidance has been invaluable over the past five years.I have been fortunate to have had the opportunity to spend time at both Los Alamos and IBM while a PhD student and want to thank my collaborators and friends at those institutions.In particular, I want to express my gratitude to my close collaborations and mentors Srinivasan
Quantum state learning is a fundamental problem in physics and computer science. As near-term quantum devices are error-prone, it is important to design error-resistant algorithms. Apart from device errors, other unexpected factors could also affect the algorithm, such as careless human read-out error, or even a malicious hacker deliberately altering the measurement results. Thus, we want our algorithm to work even in the worst case when things go against our favor.We consider the practical setting of single-copy measurements and propose the γ-adversarial corruption model where an imaginary adversary can arbitrarily change γ-fraction of the measurement outcomes. This is stronger than the γ-bounded SPAM noise model, where the post-measurement state changes by at most γ in trace distance. Under our stronger model of corruption, we design an algorithm using non-adaptive measurements that can learn an unknown rank- r state up to O~(γr) in trace distance, provided that the number of copies is sufficiently large. We further prove an information-theoretic lower bound of Ω(γr) for non-adaptive measurements, demonstrating the optimality of our algorithm. Our upper and lower bounds also hold for quantum state testing, where the goal is to test whether an unknown state is equal to a given state or far from it. Our results are intriguingly optimistic and pessimistic at the same time. For general states, the error is dimension-dependent and γd in the worst case, meaning that only corrupting a very small fraction (1/d) of the outcomes could totally destroy any non-adaptive learning algorithm. However, for constant-rank states that are useful in many quantum algorithms, it is possible to achieve dimension-independent error, even in the worst-case adversarial setting.