Probing quantum complexity via universal saturation of stabilizer entropies

• URL: http://arxiv.org/abs/2406.04190v2
• Date: Fri, 12 Jul 2024 10:59:03 GMT
• Title: Probing quantum complexity via universal saturation of stabilizer entropies
• Authors: Tobias Haug, Leandro Aolita, M. S. Kim,
• Abstract summary: Nonstabilizerness or magic' is a key resource for quantum computing. We show that stabilizer R'enyi entropies (SREs) saturate their maximum value at a critical number of non-Clifford operations.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonstabilizerness or `magic' is a key resource for quantum computing and a necessary condition for quantum advantage. Non-Clifford operations turn stabilizer states into resourceful states, where the amount of nonstabilizerness is quantified by resource measures such as stabilizer R\'enyi entropies (SREs). Here, we show that SREs saturate their maximum value at a critical number of non-Clifford operations. Close to the critical point SREs show universal behavior. Remarkably, the derivative of the SRE crosses at the same point independent of the number of qubits and can be rescaled onto a single curve. We find that the critical point depends non-trivially on R\'enyi index $\alpha$. For random Clifford circuits doped with T-gates, the critical T-gate density scales independently of $\alpha$. In contrast, for random Hamiltonian evolution, the critical time scales linearly with qubit number for $\alpha>1$, while is a constant for $\alpha<1$. This highlights that $\alpha$-SREs reveal fundamentally different aspects of nonstabilizerness depending on $\alpha$: $\alpha$-SREs with $\alpha<1$ relate to Clifford simulation complexity, while $\alpha>1$ probe the distance to the closest stabilizer state and approximate state certification cost via Pauli measurements. As technical contributions, we observe that the Pauli spectrum of random evolution can be approximated by two highly concentrated peaks which allows us to compute its SRE. Further, we introduce a class of random evolution that can be expressed as random Clifford circuits and rotations, where we provide its exact SRE. Our results opens up new approaches to characterize the complexity of quantum systems.

Related papers

• Single-copy stabilizer testing [0.0]
  We consider the problem of testing whether an unknown $n$-qubit quantum state $|psirangle$ is a stabilizer state. We give an algorithm solving this problem using $O(n)$ copies, and conversely prove that $Omega(sqrtn)$ copies are required for any algorithm.
  arXiv  Detail & Related papers  (2024-10-10T14:39:47Z)
• 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)
• Resource-efficient shadow tomography using equatorial stabilizer measurements [0.0]
  equatorial-stabilizer-based shadow-tomography schemes can estimate $M$ observables using $mathcalO(log(M),mathrmpoly(n),1/varepsilon2)$ sampling copies. We numerically confirm our theoretically-derived shadow-tomographic sampling complexities with random pure states and multiqubit graph states.
  arXiv  Detail & Related papers  (2023-11-24T17:33:44Z)
• Efficient quantum algorithms for stabilizer entropies [0.0]
  We efficiently measure stabilizer entropies (SEs) for integer R'enyi index $n>1$ via Bell measurements. We provide efficient bounds of various nonstabilizerness monotones which are intractable to compute beyond a few qubits. Our results open up the exploration of nonstabilizerness with quantum computers.
  arXiv  Detail & Related papers  (2023-05-30T15:55:04Z)
• Quantifying nonstabilizerness of matrix product states [0.0]
  We show that nonstabilizerness, as quantified by the recently introduced Stabilizer R'enyi Entropies (SREs), can be computed efficiently for matrix product states (MPSs) We exploit this observation to revisit the study of ground-state nonstabilizerness in the quantum Ising chain, providing accurate numerical results up to large system sizes.
  arXiv  Detail & Related papers  (2022-07-26T17:50:32Z)
• Magic-state resource theory for the ground state of the transverse-field Ising model [0.0]
  We study the behavior of the stabilizer R'enyi entropy in the integrable transverse field Ising spin chain. We show that the locality of interactions results in a localized stabilizer R'enyi entropy in the gapped phase.
  arXiv  Detail & Related papers  (2022-05-04T18:00:03Z)
• Stability and Risk Bounds of Iterative Hard Thresholding [41.082982732100696]
  We introduce a novel sparse generalization theory for IHT under the notion of algorithmic stability. We show that IHT with sparsity level $k$ enjoys an $mathcaltilde O(n-1/2sqrtlog(n)log(p))$ rate of convergence in sparse excess risk. Preliminary numerical evidence is provided to confirm our theoretical predictions.
  arXiv  Detail & Related papers  (2022-03-17T16:12:56Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
  We show how to efficiently simplify stabilizer states to canonical form. We characterize all linearly dependent triplets, revealing symmetries in the inner products. Using our novel controlled-Pauli $Z$ algorithm, we improve runtime for inner product computation from $O(n3)$ to $O(nd2)$ where $d$ is the maximum degree of the graph.
  arXiv  Detail & Related papers  (2021-09-20T05:56:25Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54: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.