Stabilizer rank and higher-order Fourier analysis
arXiv:2107.10551 · doi:10.22331/q-2022-02-09-645
Abstract
We establish a link between stabilizer states, stabilizer rank, and higher-order Fourier analysis -- a still-developing area of mathematics that grew out of Gowers's celebrated Fourier-analytic proof of Szemerédi's theorem \cite{gowers1998new}. We observe that -qudit stabilizer states are so-called nonclassical quadratic phase functions (defined on affine subspaces of where is the dimension of the qudit) which are fundamental objects in higher-order Fourier analysis. This allows us to import tools from this theory to analyze the stabilizer rank of quantum states. Quite recently, in \cite{peleg2021lower} it was shown that the -qubit magic state has stabilizer rank . Here we show that the qudit analog of the -qubit magic state has stabilizer rank , generalizing their result to qudits of any prime dimension. Our proof techniques use explicitly tools from higher-order Fourier analysis. We believe this example motivates the further exploration of applications of higher-order Fourier analysis in quantum information theory.
arXiv comment16 pages
References in corpus (15)
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Hudson's Theorem for finite-dimensional quantum systems
- Improved classical simulation of quantum circuits dominated by Clifford gates
- Trading classical and quantum computational resources
- Simulation of quantum circuits by low-rank stabilizer decompositions
- 0.5 Petabyte Simulation of a 45-Qubit Quantum Circuit
- The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
- Many-body quantum magic
- Stabilizer states and Clifford operations for systems of arbitrary dimensions, and modular arithmetic
- qHiPSTER: The Quantum High Performance Software Testing Environment
- Qudit versions of the qubit "pi-over-eight" gate
- Classical Simulation of Intermediate-Size Quantum Circuits
- Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
- Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials
- Lower Bounds on Stabilizer Rank