Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2107.10551 · Quantum

Stabilizer rank and higher-order Fourier analysis

Farrokh Labib

Published Feb 9, 2022• 17 citations
arXivHTMLPDF

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 n -qudit stabilizer states are so-called nonclassical quadratic phase functions (defined on affine subspaces of Fpn where p 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 n -qubit magic state has stabilizer rank Ω(n) . Here we show that the qudit analog of the n -qubit magic state has stabilizer rank Ω(n) , 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.

DOI
10.22331/q-2022-02-09-645

Related papers

Lower Bounds on Stabilizer Rank

Shir Peleg, Amir Shpilka, Ben Lee Volk

The stabilizer rank of a quantum state ψ is the minimal r such that |ψ⟩=∑j=1rcj|φj⟩ for cj∈C and stabilizer states φj . The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n -th tensor power of single-qubit magic states.We prove a lower bound of Ω(n) on the stabilizer rank of such states, improving a previous lower bound of Ω(n) of Bravyi, Smith and Smolin \cite{BSS16}. Further, we prove that for a sufficiently small constant δ , the stabilizer rank of any state which is δ -close to those states is Ω(n/log⁡n) . This is the first non-trivial lower bound for approximate stabilizer rank.Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of F2n , and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function.

arXiv:2106.03214•Quantum•Feb 15, 2022•19 citations

Improved bounds on stabilizer extent and Clifford rank

Pulkit Sinha, Benjamin Lovitz

We prove that every pure state of stabilizer rank at most $k$ has stabilizer extent at most $2^{O(\sqrt{k\log(k+1)})}$, and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-$k$ operators. This implies stabilizer fidelity at least $2^{-O(\sqrt{k\log(k+1)})}$, resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an $Ω(n^2/\log n)$ lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of $T$-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank--norm inequality, we obtain an $Ω(n^2/\log n)$ lower bound for exact representations of $n$-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank $O((\log n)^2/\log\log n)$, respectively, a $\log n$ improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most $k$, with $poly(n)2^{O(\sqrt{k\log(k+1)})}$ time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.

quant-pharXiv:2610.06819•Oct 6, 2026•0 citations

Quantum higher-order Fourier analysis and the Clifford hierarchy

Kaifeng Bu, Weichen Gu, Arthur M. Jaffe

We propose a mathematical framework that we call quantum, higher-order Fourier analysis. This generalizes the classical theory of higher-order Fourier analysis, which led to many recent advances in number theory and combinatorics. We define a family of "quantum measures" on linear transformations on a Hilbert space, that reduce in the case of diagonal matrices to the uniformity norms introduced by Timothy Gowers. We show that our quantum measures and our related theory of quantum higher-order Fourier analysis characterize the Clifford hierarchy, an important notion of complexity in quantum computation. In particular, we give a necessary and sufficient analytic condition that a unitary is an element of the [Formula: see text] level of the Clifford hierarchy.

arXiv:2508.15908•Proceedings of the National Academy of Sciences•Nov 7, 2025•9 citations

Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits

Yifei Huang, Peter J. Love

Bravyi and Gosset [S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016)] recently gave classical simulation algorithms for quantum circuits dominated by Clifford operations. These algorithms scale exponentially with the number of $T$ gates in the circuit, but polynomially in the number of qubits and Clifford operations. Here we extend their algorithm to qudits of odd prime dimension. We generalize their approximate stabilizer rank method for weak simulation to qudits and obtain the scaling of the approximate stabilizer rank with the number of single-qudit magic states. We also relate the canonical form of qudit stabilizer states to Gauss sum evaluations and give an $O({n}^{3})$ algorithm for calculating the inner product of two $n$-qudit stabilizer states.

arXiv:1808.02406•Physical Review A•May 6, 2019•18 citations

Agnostic learning of qudit stabilizer states

Wentao Qi, Boyan Xu, Shiguang Feng +1 more

Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown $n$-qudit pure state $|ψ\rangle$ that has fidelity $τ$ with some stabilizer state, our algorithm outputs a stabilizer state $|φ\rangle$ such that $\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon$ with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as $(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)$, where the dimension $d$ is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime $τ> \cos^2(π/8)$, establishing a qudit analogue of the threshold-based approach in prior qubit work.

quant-pharXiv:2607.15559•Jul 20, 2026•1 citation

Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach

Saeed Adel Mehraban, Mehrdad Tahmasbi

The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that the approximate stabilizer rank of a so-called “magic” state like |T⟩⊗ n, up to polynomial factors, is an upper bound on the number of classical operations required to simulate an arbitrary quantum circuit with Clifford gates and n number of T gates. As a result, an exponential lower bound on this quantity seems inevitable. Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the “exact” rank of |T⟩⊗ n, meaning the minimal size of a decomposition that exactly produces the state. For the “approximate” rank, which is more realistically related to the cost of simulating quantum circuits, no lower bound better than Ω(√n) has been known. In this paper, we improve the lower bound on the approximate rank to Ω(n2) for a wide range of the approximation parameters. An immediate corollary of our result is the existence of polynomial time computable functions which require a super-linear number of terms in any decomposition into exponentials of quadratic forms over F2, resolving a question by Williams. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure, a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure, and a result about trading Clifford operations with T gates.

arXiv:2305.10277•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•9 citations
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 n -qudit stabilizer states are so-called nonclassical quadratic phase functions (defined on affine subspaces of Fpn where p 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 n -qubit magic state has stabilizer rank Ω(n) . Here we show that the qudit analog of the n -qubit magic state has stabilizer rank Ω(n) , 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.
The stabilizer rank of a quantum state ψ is the minimal r such that |ψ⟩=∑j=1rcj|φj⟩ for cj∈C and stabilizer states φj . The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n -th tensor power of single-qubit magic states.We prove a lower bound of Ω(n) on the stabilizer rank of such states, improving a previous lower bound of Ω(n) of Bravyi, Smith and Smolin \cite{BSS16}. Further, we prove that for a sufficiently small constant δ , the stabilizer rank of any state which is δ -close to those states is Ω(n/log⁡n) . This is the first non-trivial lower bound for approximate stabilizer rank.Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of F2n , and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function.
We prove that every pure state of stabilizer rank at most kkk has stabilizer extent at most 2O(klog⁡(k+1))2^{O(\sqrt{k\log(k+1)})}2O(klog(k+1)​), and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-kkk operators. This implies stabilizer fidelity at least 2−O(klog⁡(k+1))2^{-O(\sqrt{k\log(k+1)})}2−O(klog(k+1)​), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n2/log⁡n)Ω(n^2/\log n)Ω(n2/logn) lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of TTT-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank--norm inequality, we obtain an Ω(n2/log⁡n)Ω(n^2/\log n)Ω(n2/logn) lower bound for exact representations of nnn-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank O((log⁡n)2/log⁡log⁡n)O((\log n)^2/\log\log n)O((logn)2/loglogn), respectively, a log⁡n\log nlogn improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most kkk, with poly(n)2O(klog⁡(k+1))poly(n)2^{O(\sqrt{k\log(k+1)})}poly(n)2O(klog(k+1)​) time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
We propose a mathematical framework that we call quantum, higher-order Fourier analysis. This generalizes the classical theory of higher-order Fourier analysis, which led to many recent advances in number theory and combinatorics. We define a family of "quantum measures" on linear transformations on a Hilbert space, that reduce in the case of diagonal matrices to the uniformity norms introduced by Timothy Gowers. We show that our quantum measures and our related theory of quantum higher-order Fourier analysis characterize the Clifford hierarchy, an important notion of complexity in quantum computation. In particular, we give a necessary and sufficient analytic condition that a unitary is an element of the [Formula: see text] level of the Clifford hierarchy.
Bravyi and Gosset [S. Bravyi and D. Gosset, Phys. Rev. Lett. 116, 250501 (2016)] recently gave classical simulation algorithms for quantum circuits dominated by Clifford operations. These algorithms scale exponentially with the number of TTT gates in the circuit, but polynomially in the number of qubits and Clifford operations. Here we extend their algorithm to qudits of odd prime dimension. We generalize their approximate stabilizer rank method for weak simulation to qudits and obtain the scaling of the approximate stabilizer rank with the number of single-qudit magic states. We also relate the canonical form of qudit stabilizer states to Gauss sum evaluations and give an O(n3)O({n}^{3})O(n3) algorithm for calculating the inner product of two nnn-qudit stabilizer states.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown nnn-qudit pure state ∣ψ⟩|ψ\rangle∣ψ⟩ that has fidelity τττ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩|φ\rangle∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log⁡(1/τ))⋅poly(n,1/ε)(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)(d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension ddd is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos⁡2(π/8)τ> \cos^2(π/8)τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that the approximate stabilizer rank of a so-called “magic” state like |T⟩⊗ n, up to polynomial factors, is an upper bound on the number of classical operations required to simulate an arbitrary quantum circuit with Clifford gates and n number of T gates. As a result, an exponential lower bound on this quantity seems inevitable. Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the “exact” rank of |T⟩⊗ n, meaning the minimal size of a decomposition that exactly produces the state. For the “approximate” rank, which is more realistically related to the cost of simulating quantum circuits, no lower bound better than Ω(√n) has been known. In this paper, we improve the lower bound on the approximate rank to Ω(n2) for a wide range of the approximation parameters. An immediate corollary of our result is the existence of polynomial time computable functions which require a super-linear number of terms in any decomposition into exponentials of quadratic forms over F2, resolving a question by Williams. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure, a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure, and a result about trading Clifford operations with T gates.