Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States

• URL: http://arxiv.org/abs/2509.24000v1
• Date: Sun, 28 Sep 2025 17:46:43 GMT
• Title: Exponential Advantage from One More Replica in Estimating Nonlinear Properties of Quantum States
• Authors: Qi Ye, Zhenhuan Liu, Dong-Ling Deng,
• Abstract summary: 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$.
• Score: 16.185988658474635
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Inferring nonlinear features of quantum states is fundamentally important across quantum information science, but remains challenging due to the intrinsic linearity of quantum mechanics. It is widely recognized that quantum memory and coherent operations help avoid exponential sample complexity, by mapping nonlinear properties onto linear observables over multiple copies of the target state. In this work, we prove that such a conversion is not only sufficient but also necessary. Specifically, we prove that the estimation of $\mathrm{tr}(\rho^{k} O)$ for a broad class of observables $O$ is exponentially hard for any protocol restricted to $(k-1)$-replica joint measurements, whereas access to one additional replica reduces the complexity to a constant. These results establish, for the first time, an exponential separation between $(k-1)$- and $k$-replica protocols for any integer $k>2$, thereby introducing a fine-grained hierarchy of replica-based quantum advantage and resolving an open question in the literature. The technical core is a general indistinguishability principle showing that any ensemble constructed from large Haar random states via tensor products and mixtures is hard to distinguish from its average. Leveraging this principle, we further prove that $k$-replica joint measurements are also necessary for distinguishing rank-$k$ density matrices from rank-$(k-1)$ ones. Overall, our work delineates sharp boundaries on the power of joint measurements, highlighting resource--complexity trade-offs in quantum learning theory and deepening the understanding of quantum mechanics' intrinsic linearity.

Related papers

• Analytical construction of $(n, n-1)$ quantum random access codes saturating the conjectured bound [0.0]
  Quantum Random Access Codes (QRACs) embody the fundamental trade-off between the compressibility of information into limited quantum resources.<n>We establish an analytical construction method for $(n, n-1)$-QRACs by using an explicit operator formalism.<n>We present a systematic algorithm to decompose the derived optimal POVM into standard quantum gates.
  arXiv  Detail & Related papers  (2026-01-27T04:43:43Z)
• Performance Guarantees for Quantum Neural Estimation of Entropies [31.955071410400947]
  Quantum neural estimators (QNEs) combine classical neural networks with parametrized quantum circuits.<n>We study formal guarantees for QNEs of measured relative entropies in the form of non-asymptotic error risk bounds.<n>Our theory aims to facilitate principled implementation of QNEs for measured relative entropies.
  arXiv  Detail & Related papers  (2025-11-24T16:36:06Z)
• Measuring Less to Learn More: Quadratic Speedup in learning Nonlinear Properties of Quantum Density Matrices [6.701793676773711]
  A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as $mathrmTr(rhok O)$.<n>We present a quadratic quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods.<n>Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information.
  arXiv  Detail & Related papers  (2025-09-01T15:56:49Z)
• Explicit Formulas for Estimating Trace of Reduced Density Matrix Powers via Single-Circuit Measurement Probabilities [10.43657724071918]
  We propose a universal framework to simultaneously estimate the traces of the $2$nd to the $n$th powers of a reduced density matrix.<n>We develop two algorithms: a purely quantum method and a hybrid quantum-classical approach combining Newton-Girard iteration.<n>We explore various applications including the estimation of nonlinear functions and the representation of entanglement measures.
  arXiv  Detail & Related papers  (2025-07-23T01:41:39Z)
• Purest Quantum State Identification [14.22473588576799]
  We introduce the purest quantum state identification, which can be used to improve the accuracy of quantum computation and communication.<n>For incoherent strategies, we derive the first adaptive algorithm achieving error probability $expleft(- Omegaleft(fracN H_1log(K) 2nfracright)$, fundamentally improving quantum property learning.
  arXiv  Detail & Related papers  (2025-02-20T07:42:16Z)
• One-Shot Min-Entropy Calculation Of Classical-Quantum States And Its Application To Quantum Cryptography [21.823963925581868]
  We develop a one-shot lower bound calculation technique for the min-entropy of a classical-quantum state.<n>It offers an alternative tight finite-data analysis for the BB84 quantum key distribution scheme.<n>It gives the best finite-key bound known to date for a variant of device independent quantum key distribution protocol.
  arXiv  Detail & Related papers  (2024-06-21T15:11:26Z)
• 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)
• Quantum tomography of helicity states for general scattering processes [55.2480439325792]
  Quantum tomography has become an indispensable tool in order to compute the density matrix $rho$ of quantum systems in Physics. We present the theoretical framework for reconstructing the helicity quantum initial state of a general scattering process.
  arXiv  Detail & Related papers  (2023-10-16T21:23:42Z)
• A Universal Quantum Certainty Relation for Arbitrary Number of Observables [0.0]
  We derive by lattice theory a universal quantum certainty relation for arbitrary $M$ observables in $N$-dimensional system.<n>It is found that one cannot prepare a quantum state with probability vectors of incompatible observables spreading out arbitrarily.<n>We also explore the connections between quantum uncertainty and quantum coherence, and obtain a complementary relation for the quantum coherence as well.
  arXiv  Detail & Related papers  (2023-08-10T16:44:10Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Unveiling quantum entanglement in many-body systems from partial information [0.0]
  This paper introduces a flexible data-driven entanglement detection technique for uncharacterized quantum many-body states. It is of immediate relevance to experiments in a quantum advantage regime.
  arXiv  Detail & Related papers  (2021-07-08T16:17:02Z)
• 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)

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.