Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits

• URL: http://arxiv.org/abs/2405.06357v1
• Date: Fri, 10 May 2024 09:44:23 GMT
• Title: Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
• Authors: Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos, Miklos Santha,
• Abstract summary: Bell sampling fails when used on quemphdits of dimension $d>2$. We propose new quantum algorithms to circumvent the use of Bell sampling on qudits.
• Score: 0.824969449883056
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unfortunately, however, it is known that Bell sampling fails when used on qu\emph{d}its of dimension $d>2$. In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for $d=p$ prime we devise a quantum algorithm to identify an unknown stabiliser state in $(\mathbb{C}^p)^{\otimes n}$ that uses $O(n)$ copies of the input state and runs in time $O(n^4)$. As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension $d$ using $O(\log{n}/\log{d})$ auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.

Related papers

• Generating multipartite nonlocality to benchmark quantum computers [0.0]
  We show that quantum computers can be used for producing large $n$-partite nonlocality. This allows in return to benchmark nonclassical correlations regardless of the number of qubits or the connectivity.
  arXiv  Detail & Related papers  (2024-06-11T19:03:35Z)
• Pseudoentanglement Ain't Cheap [0.43123403062068827]
  We show that any pseudoentangled state ensemble with a gap of $t$ bits of entropy requires $Omega(t)$ non-Clifford gates to prepare. This is tight up to polylogarithmic factors if linear-time-secure pseudorandom functions exist.
  arXiv  Detail & Related papers  (2024-03-29T19:39:59Z)
• Learning the stabilizer group of a Matrix Product State [0.0]
  We present a novel classical algorithm designed to learn the stabilizer group of a given Matrix Product State (MPS) We benchmark our method on $T$-doped states randomly scrambled via Clifford unitary dynamics. Our method, thanks to a very favourable scaling $mathcalO(chi3)$, represents the first effective approach to obtain a genuine magic monotone for MPS.
  arXiv  Detail & Related papers  (2024-01-29T19:00:13Z)
• 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)
• Improved Stabilizer Estimation via Bell Difference Sampling [0.43123403062068827]
  We study the complexity of learning quantum states in various models with respect to the stabilizer formalism. We prove that $Omega(n)$ $T$gates are necessary for any Clifford+$T$ circuit to prepare pseudorandom quantum states. We show that a modification of the above algorithm runs in time.
  arXiv  Detail & Related papers  (2023-04-27T01:58:28Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• 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)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
  arXiv  Detail & Related papers  (2020-07-23T10:50:42Z)
• 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)
• Using Randomness to decide among Locality, Realism and Ergodicity [91.3755431537592]
  An experiment is proposed to find out, or at least to get an indication about, which one is false. The results of such experiment would be important not only to the foundations of Quantum Mechanics.
  arXiv  Detail & Related papers  (2020-01-06T19:26:32Z)

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.