Magic determines the hardness of direct fidelity estimation

• URL: http://arxiv.org/abs/2204.02995v3
• Date: Mon, 9 Jan 2023 13:31:41 GMT
• Title: Magic determines the hardness of direct fidelity estimation
• Authors: Lorenzo Leone, Salvatore F.E. Oliviero and Alioscia Hamma
• Abstract summary: We show how the resource theory of magic quantifies the hardness of direct fidelity estimation protocols. We extend our results to quantum evolutions, showing that the resources needed to certify the quality of the implementation of a given unitary $U$ are governed by the magic in the Choi state associated with $U$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we show how the resource theory of magic quantifies the hardness of direct fidelity estimation protocols. In particular, the resources needed for a direct fidelity estimation conducted on generic states, such as Pauli fidelity estimation and shadow fidelity estimation protocols, grow exponentially with the stabilizer R\'enyi entropy [PRL, 128, 050402]. Remarkably, these protocols are shown to be feasible only for those states that are useless to attain any quantum speedup or advantage. This result suggests the impossibility of estimating efficiently fidelity for generic states and, at the same time, leaves the window open to those protocols specialized at directly estimating the fidelity of particular states. We then extend our results to quantum evolutions, showing that the resources needed to certify the quality of the implementation of a given unitary $U$ are governed by the magic in the Choi state associated with $U$, which is shown to possess a profound connection with out-of-time order correlators.

Related papers

• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• A double selection entanglement distillation-based state estimator [0.3613661942047476]
  We show that a double selection distillation protocol alone can be used to efficiently estimate the Bell-diagonal parameters of the undistilled states.<n>We also demonstrate that this novel estimator outperforms the previously proposed distillation-based estimator in terms of resource complexity.
  arXiv  Detail & Related papers  (2025-05-30T06:58:03Z)
• Sampling Groups of Pauli Operators to Enhance Direct Fidelity Estimation [0.0]
  We propose an enhanced direct fidelity estimation protocol that uses fewer copies of the experimental state. Numerical simulations validate our approach, demonstrating that for 8-qubit Haar-random states, our method achieves a one-third reduction in the required number of copies.
  arXiv  Detail & Related papers  (2025-01-31T15:38:09Z)
• General detectability measure [53.64687146666141]
  Distinguishing resource states from resource-free states is a fundamental task in quantum information. We derived the optimal exponential decay rate of the failure probability for detecting a given $n$-tensor product state.
  arXiv  Detail & Related papers  (2025-01-16T05:39:22Z)
• Joint Age-State Belief is All You Need: Minimizing AoII via Pull-Based Remote Estimation [30.838857981082967]
  Age of incorrect information (AoII) is a recently proposed freshness and mismatch metric. Keeping track of AoII requires the knowledge of both the source and estimation processes.
  arXiv  Detail & Related papers  (2024-11-11T17:57:25Z)
• Optimal Fidelity Estimation from Binary Measurements for Discrete and Continuous Variable Systems [6.253919624802852]
  In continuous variable (CV) systems, we utilise the Wigner function, which can be measured via displaced parity measurements. For target states of particular interest, such as Fock and Gaussian states, we find that this sample complexity is characterised by the $L1$-norm of the Wigner function. In a general black box model, we prove that, for any target state, the optimal sample complexity for fidelity estimation is characterised by the smoothed $L1$-norm of the target state.
  arXiv  Detail & Related papers  (2024-09-06T11:07:55Z)
• Off-Policy Evaluation in Markov Decision Processes under Weak Distributional Overlap [5.0401589279256065]
  We re-visit the task of off-policy evaluation in Markov decision processes (MDPs) under a weaker notion of distributional overlap. We introduce a class of truncated doubly robust (TDR) estimators which we find to perform well in this setting.
  arXiv  Detail & Related papers  (2024-02-13T03:55:56Z)
• Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior [51.60683890503293]
  We propose a theoretical framework for studying behavior cloning of complex expert demonstrations using generative modeling. We show that pure supervised cloning can generate trajectories matching the per-time step distribution of arbitrary expert trajectories.
  arXiv  Detail & Related papers  (2023-07-27T04:27:26Z)
• Robust and efficient verification of graph states in blind measurement-based quantum computation [52.70359447203418]
  Blind quantum computation (BQC) is a secure quantum computation method that protects the privacy of clients. It is crucial to verify whether the resource graph states are accurately prepared in the adversarial scenario. Here, we propose a robust and efficient protocol for verifying arbitrary graph states with any prime local dimension.
  arXiv  Detail & Related papers  (2023-05-18T06:24:45Z)
• Uncertainty-Aware Instance Reweighting for Off-Policy Learning [63.31923483172859]
  We propose a Uncertainty-aware Inverse Propensity Score estimator (UIPS) for improved off-policy learning. Experiment results on synthetic and three real-world recommendation datasets demonstrate the advantageous sample efficiency of the proposed UIPS estimator.
  arXiv  Detail & Related papers  (2023-03-11T11:42:26Z)
• Improved Policy Evaluation for Randomized Trials of Algorithmic Resource Allocation [54.72195809248172]
  We present a new estimator leveraging our proposed novel concept, that involves retrospective reshuffling of participants across experimental arms at the end of an RCT. We prove theoretically that such an estimator is more accurate than common estimators based on sample means.
  arXiv  Detail & Related papers  (2023-02-06T05:17:22Z)
• Monotonic Improvement Guarantees under Non-stationarity for Decentralized PPO [66.5384483339413]
  We present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative Multi-Agent Reinforcement Learning (MARL) We show that a trust region constraint can be effectively enforced in a principled way by bounding independent ratios based on the number of agents in training.
  arXiv  Detail & Related papers  (2022-01-31T20:39:48Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)
• Universally Optimal Verification of Entangled States with Nondemolition Measurements [3.014547324345968]
  We present a universally optimal protocol for verifying entangled states by employing the so-called quantum nondemolition measurements. We demonstrate the power of our protocol for the optimal verification of Bell states, arbitrary two-qubit pure states, and stabilizer states.
  arXiv  Detail & Related papers  (2020-05-03T14:48:59Z)

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.