Improved Stabilizer Estimation via Bell Difference Sampling

Abstract

We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: - We prove that $\Omega (n)$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist. - Given an $n$-qubit pure quantum state $|\psi ⟩$ that has fidelity at least $\tau$ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least $\tau -\epsilon$. The algorithm uses $O(n/({\epsilon }^2{\tau }^4))$ samples and $\exp \left(O(n/{\tau }^4)\right)/{\epsilon }^2$ time. In the regime of $\tau$ constant, this algorithm estimates stabilizer fidelity substantially faster than the naïve $\exp (O(n^2))$-time brute-force algorithm over all stabilizer states. - In the special case of $\tau >{\cos }^2(\pi /8)$, we show that a modification of the above algorithm runs in polynomial time. - We exhibit a tolerant property testing algorithm for stabilizer states. The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory.

41 pages, 2 figures. v3: changed presentation of tolerant testing algorithm and other minor edits

References in corpus (12)

• Randomized Benchmarking of Quantum Gates
• Efficient quantum state tomography
• Information-theoretic bounds on quantum advantage in machine learning
• Scalable measures of magic resource for quantum computers
• Quantum commitments and signatures without one-way functions
• Dynamical phase transitions, temporal orthogonality and the dynamics of observables in one dimensional ultra-cold quantum gases: from the continuum to the lattice
• Quantum Cryptography in Algorithmica
• Learning quantum circuits of some $T$ gates
• Quantum Pseudorandomness and Classical Complexity
• A single $T$-gate makes distribution learning hard
• Improved Stabilizer Estimation via Bell Difference Sampling
• On the Hardness of PAC-learning Stabilizer States with Noise

Cited by in corpus (12)

• Learning shallow quantum circuits
• Improved Stabilizer Estimation via Bell Difference Sampling
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Efficient distributed inner product estimation via Pauli sampling
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Efficient witnessing and testing of magic in mixed quantum states
• Operational interpretation of the Stabilizer Entropy
• Single-copy stabilizer testing
• Agnostic Process Tomography
• Agnostic Tomography of Stabilizer Product States
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond