The Exact Replica Threshold for Nonlinear Moments of Quantum States

• URL: http://arxiv.org/abs/2604.22627v1
• Date: Fri, 24 Apr 2026 14:56:59 GMT
• Title: The Exact Replica Threshold for Nonlinear Moments of Quantum States
• Abstract summary: We prove that the exact replica threshold for fixed-order pure moments is $lceil t/2rceil$.<n>For fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between-sample estimation and a-growing regime.
• Score: 1.599072005190786
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as $\operatorname{tr}(ρ^t)$, but whether replica number marks a sharp information-theoretic resource boundary has remained unclear. For every fixed order $t\ge 3$, existing protocols show that $\lceil t/2\rceil$ replicas already suffice for polynomial-sample estimation of $\operatorname{tr}(ρ^t)$, yet it has remained open whether one fewer replica must necessarily incur a sample-complexity barrier growing with the dimension. We prove that this is indeed the case in the sample/copy-access model with replica-limited joint measurements: any protocol restricted to $\lceil t/2\rceil-1$ replicas requires dimension-growing sample complexity, while $\lceil t/2\rceil$ replicas suffice by prior work. Thus the exact replica threshold for fixed-order pure moments is $\lceil t/2\rceil$. Equivalently, for fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between polynomial-sample estimation and a dimension-growing regime in the replica-limited model. We further show that the same threshold law extends to a broad family of observable-weighted moments $\operatorname{tr}(Oρ^t)$, including Pauli observables and other observables with bounded operator norm and macroscopic trace norm. Coherent replica number therefore acts as a genuinely discrete resource for nonlinear quantum-state estimation.

Related papers

• Random Projections for Multi-Copy Quantum Algorithms [3.995502708329505]
  Estimating nonlinear properties of quantum states is a central task in quantum information science.<n>Standard protocols based on swap tests require coherent operations on the full Hilbert space.<n>We introduce a framework for multi-copy measurements based on random projections onto lower-dimensional subspaces.
  arXiv  Detail & Related papers  (2026-06-18T13:49:14Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
  We establish an optimal sample complexity of $O(-2)$ for obtaining an $$-optimal global policy using a single-timescale actor-critic (AC) algorithm.<n>These mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability.
  arXiv  Detail & Related papers  (2026-02-02T00:35:42Z)
• Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States [16.185988658474635]
  We prove that estimation of $mathrmtr(rhok O)$ for a broad class of observables $O$ is exponentially hard for any protocol restricted to $(k-1)$-replica joint measurements.<n>Results establish, for the first time, an exponential separation between $(k-1)$- and $k$-replica protocols for any integer $k>2$.
  arXiv  Detail & Related papers  (2025-09-28T17:46:43Z)
• Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities [51.320599504997745]
  Predictions from statistical physics postulate that recovery of the communities in Block Model (SBM) is possible in time above, and only above, the KestenStigum (KS) threshold.<n>Chin et al.(2025) recently prove that, in a sparse regime, community recovery in time is possible below the KS threshold by counting nonbacktracking paths.
  arXiv  Detail & Related papers  (2025-09-19T09:53:56Z)
• Highly-entangled, highly-doped states that are efficiently cross-device verifiable [0.0]
  We introduce a class of highly entangled real quantum states that cannot be approximated by circuits with $log$-many non-Clifford gates.<n>We prove that Bell sampling enables efficient cross-device verification (or distributed inner product estimation) for these states.<n>We anticipate that these results could have applications in quantum cryptography and verification.
  arXiv  Detail & Related papers  (2025-01-20T19:12:34Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• An optimal tradeoff between entanglement and copy complexity for state tomography [24.737530909081915]
  We study tomography in the natural setting where one can make measurements of $t$ copies at a time. This is the first smooth entanglement-copy protocol known for any quantum learning task. A key insight is to use SchurilonWeyl sampling not to estimate the spectrum of $rho$, but to estimate the deviation of $rho$ from the maximally mixed state.
  arXiv  Detail & Related papers  (2024-02-26T07:18:57Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  This paper studies the fundamental limits of reinforcement learning (RL) in the challenging emphpartially observable setting. For emphmulti-step revealing POMDPs, we show that the latent state-space dependence is at least $Omega(S1.5)$ in the sample complexity.
  arXiv  Detail & Related papers  (2023-02-02T18:59:30Z)
• A Hierarchy for Replica Quantum Advantage [17.763817187554096]
  Given the ability to make entangled measurements on at most $k$ replicas of an $n$-qubit state $rho$ simultaneously, there is a property of $rho$ which requires at least order $2n / k2$ measurements to learn. We introduce a powerful proof technique to establish our results, and also use this to provide new bounds for testing the mixedness of a quantum state.
  arXiv  Detail & Related papers  (2021-11-10T19:00:06Z)
• Distributed quantum inner product estimation [14.222887950206658]
  A benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. No quantum communication can be performed between the two physical platforms due to hardware constraints. We show that the sample complexity must be at least $Omega(max1/varepsilon2,sqrtd/varepsilon)$, even in the strongest setting.
  arXiv  Detail & Related papers  (2021-11-05T05:35:03Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)

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.