Pseudoentanglement Ain't Cheap

Abstract

We show that any pseudoentangled state ensemble with a gap of $t$ bits of entropy requires $\Omega (t)$ non-Clifford gates to prepare. This bound is tight up to polylogarithmic factors if linear-time quantum-secure pseudorandom functions exist. Our result follows from a polynomial-time algorithm to estimate the entanglement entropy of a quantum state across any cut of qubits. When run on an $n$-qubit state that is stabilized by at least $2^{n-t}$ Pauli operators, our algorithm produces an estimate that is within an additive factor of $\frac{t}{2}$ bits of the true entanglement entropy.

15 pages; v2: slight edits to concurrent work section

References in corpus (17)

• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence
• Improved classical simulation of quantum circuits dominated by Clifford gates
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• Stabilizer Rényi entropy
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Learning t-doped stabilizer states
• Pseudomagic Quantum States
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Learning quantum circuits of some $T$ gates
• Magic-induced computational separation in entanglement theory
• Bell sampling from quantum circuits
• Efficient learning of $t$-doped stabilizer states with single-copy measurements
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates