Nonstabilizerness determining the hardness of direct fidelity estimation

Abstract

In this work, we show how the resource theory of nonstabilizerness 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ényi entropy. 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 nonstabilizerness in the Choi state associated with $U$, which is shown to possess a profound connection with out-of-time order correlators.

References in corpus (19)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The Quantum Internet
• Randomized Benchmarking of Quantum Gates
• Robust randomized benchmarking of quantum processes
• Efficient quantum state tomography
• Direct Fidelity Estimation from Few Pauli Measurements
• Application of a resource theory for magic states to fault-tolerant quantum computing
• The randomized measurement toolbox
• Magic state distillation with low overhead
• Characterization of addressability by simultaneous randomized benchmarking
• Quantum Simulations of Classical Annealing Processes
• Scalable measures of magic resource for quantum computers
• Measuring magic on a quantum processor
• Directly estimating non-classicality
• Catalysis and activation of magic states in fault tolerant architectures
• Scalable reconstruction of unitary processes and Hamiltonians
• Random Matrix Theory of the Isospectral twirling
• Entanglement of random hypergraph states
• The Learnability of Quantum States

Cited by in corpus (46)

• Computational advantage of quantum random sampling
• Stabilizer entropies and nonstabilizerness monotones
• Many-body magic via Pauli-Markov chains -- from criticality to gauge theories
• Stabilizer entropies are monotones for magic-state resource theory
• Measuring nonstabilizerness via multifractal flatness
• Magic spreading in random quantum circuits
• Efficient quantum algorithms for stabilizer entropies
• Resource theory of quantum scrambling
• Stabilizer entropy dynamics after a quantum quench
• Pseudomagic Quantum States
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Magic-induced computational separation in entanglement theory
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Magic of quantum hypergraph states
• Exact solution of long-range stabilizer Rényi entropy in the dual-unitary XXZ model
• Magic Resources of the Heisenberg Picture
• Quantifying non-stabilizerness via information scrambling
• Probing quantum complexity via universal saturation of stabilizer entropies
• Gravitational back-reaction is magical
• Stabilizer entropy of quantum tetrahedra
• Chaos and magic in the dissipative quantum kicked top
• Entanglement and Stabilizer entropies of random bipartite pure quantum states
• Quantum Complexity Fluctuations from Nuclear and Hypernuclear Forces
• Entanglement complexity of the Rokhsar-Kivelson-sign wavefunctions
• Magic of Random Matrix Product States
• Nonstabilizerness in the unitary and monitored quantum dynamics of XXZ-staggered and SYK models
• Long-range nonstabilizerness and phases of matter
• Nonstabilizerness of a Boundary Time Crystal
• Bridging Entanglement and Magic Resources within Operator Space
• A nonstabilizerness monotone from stabilizerness asymmetry
• Interplay of entanglement structures and stabilizer entropy in spin models
• Efficient distributed inner product estimation via Pauli sampling
• Maximal Magic for Two-qubit States
• Information scrambling and entanglement in quantum approximate optimization algorithm circuits
• Sampling Groups of Pauli Operators to Enhance Direct Fidelity Estimation
• Efficient fidelity estimation: Alternative derivation and related applications
• Robust Estimation of Nonlinear Properties of Quantum Processes
• Sequency Hierarchy Truncation (SeqHT) for Adiabatic State Preparation and Time Evolution in Quantum Simulations
• Rise and fall of nonstabilizerness via random measurements
• Magic of discrete lattice gauge theories
• Invested and Potential Magic Resources in Measurement-Based Quantum Computation
• Harvesting stabilizer entropy and non-locality from a quantum field
• An Algorithm for Estimating $\alpha$-Stabilizer Rényi Entropies via Purity
• Prescriptive preparation and verification of nonstabilizer states
• Van Hove singularities in stabilizer entropy densities
• Quantum Complexity in Rule-Based Constrained Many-Body Models: Scars, Fragmentation, and Chaos