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

An explicit ten-term stabilizer decomposition of |T>^{(x)7}: chi(|T>^{(x)7}) <= 10

Harish Santhanalakshmi Ganesan

Published Oct 21, 2026• 0 citations
Publisher

Abstract

Short note with supporting code and data on Open Problem Zoo record op_37f7b003ec78a028 (stabilizer rank of tensor powers of the magic state |T> = (|0> + e^{i pi/4}|1>)/sqrt2). The exact stabilizer rank chi(|T>^{(x)m}) is known for m ≤ 4 (2, 2, 3, 4); at m = 5, 6, 7 only the upper bounds 6, 6, 12 were known, the last being the product of the six-copy and one-copy decompositions (no direct search beyond six copies had been reported). This deposit gives an explicit decomposition of |T>^{(x)7} into ten stabilizer states, hence chi(|T>^{(x)7}) ≤ 10, and by sub-multiplicativity chi(|T>^{(x)13}) ≤ 60 (previously 72). The ten states are symmetric under permutations within the qubit blocks {1,2} and {3,...,7}; they are listed in Dehaene-De Moor normal form with exact coefficients in (1/4) Z[e^{i pi/4}]. The decomposition was found by an autonomous AI research agent (the depositor's EVO harness) that closed three seed states under block-symmetric Clifford gates to obtain a dictionary of a few hundred stabilizer states spanning the relevant symmetric subspace and then ran a subset search over it. Verification: exact Gaussian elimination over Q(e^{i pi/4}) (a proof of the identity), a 40-digit least-squares residual of 1.6e-41, and a brute-force recount of the stabilizer group of every state. Companion searches give evidence, not proof, that chi(|T>^{(x)5}) = 6. Claim boundary: an upper bound with an explicit certificate; no optimality, no asymptotic statement, no priority claim. Files: the note (PDF + LaTeX), the decomposition as JSON and as a readable listing, the exact verifier and the independent check with its log, the agent's search code and notes, the task text, SHA-256 sums.

DOI
10.5281/zenodo.23525752

Related papers

Stabilizer rank bounds for magic-state orbits

Farrokh Labib, Vincent Russo

Distinct Clifford orbits of magic states can exhibit different stabilizer ranks at small tensor powers. We establish this for qutrits, where the single-qutrit Clifford group has four inequivalent orbits of magic states: Strange, Norrell, Hadamard-eigenstate, and the qutrit T-state, but a nontrivial upper bound on the asymptotic exponent had been pinned down for only the qutrit T-state. For the other three orbits we give explicit stabilizer decompositions, yielding upper bounds on the per-copy asymptotic stabilizer-rank exponent: $γ_S \le \log_3(2)/2 \approx 0.316$ for the Strange state, and $γ_{H_3}, γ_N \le \log_3(4)/3 \approx 0.421$ for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior $γ_{T_3} \le 1/2$ baseline. We also prove the first nontrivial $Ω(m / \log m)$ asymptotic lower bounds for the Hadamard-eigenstate and Norrell orbits, and exhibit two-qutrit Clifford circuits that convert two copies of these states into an injectable phase state with constant success probability, enabling constant-overhead injection of one non-Clifford diagonal gate per orbit. In the case of qubits, we give a closed-form decomposition of the qubit T-type orbit at four copies matching the existing $γ_T \le \log_2(3)/4 \approx 0.396$ exponent via a direct algebraic identity rather than an entangled cat-state construction. An open-source library stabrank accompanies the paper, with Lean 4 proof formalizations of all the decompositions.

quant-pharXiv:2605.28586•May 28, 2026•0 citations

Stabilizer rank of the 8-qubit magic cat state: an exact rank-6 decomposition and calibrated evidence against rank 5

James Jardine

We report the stabilizer rank of the 8-qubit magic cat state |cat_8> (the magic-basis cat state of Qassim–Pashayan–Gosset, Quantum 5, 606 (2021)). Result. (i) Upper bound: chi(cat_8) <= 6, PROVEN exactly. An explicit rank-6 decomposition over 6-qubit-stabilizer-derived states is verified with sympy over Q(i): each candidate is checked to be a genuine stabilizer state by exact integer arithmetic (stabilizer group order exactly 2^n), target membership in the span is decided by exact rational rank, coefficients are produced exactly and the identity re-checked, and the whole decomposition is lifted back to 8 qubits and re-verified there. Reproduction: python3 verify.py ckpt_cat8_k6_cd.json (files bundled). (ii) Lower bound: chi(cat_8) >= 6, COMPUTATIONAL EVIDENCE, not a theorem. Two structurally independent searches over 5-tuples of stabilizer states — discrete pool coordinate descent (481 restarts, 30.9 core-hours) and continuous gradient descent with rounding (42 restarts, 1.99 core-hours) — both bottom out at 5-term residual 0.086664036 (9 hits each, never below, 523 restarts total) while both recover planted exact rank-5 witnesses at ~90% rate, calibrating the solvers against the exactness they fail to reach for cat_8. On this basis chi(cat_8)=6 is stated as a conjecture with a proven upper bound. Relation to Qassim–Pashayan–Gosset: their construction already implies chi(cat_8) <= 6; the present work adds the first explicit exact rank-6 decomposition of cat_8 and calibrated evidence against rank 5. The exponent log_2(6)/6 = 0.43083 does not improve their alpha = log_2(3)/4 = 0.39624; no published bound is improved and QPG's open questions remain open. The collapse-engine screen mandated by this machine's protocol was run on the continuation path (24-stage annealing path, one scale): read NULL (control -2.60 sigma = the flat-vector floor; permute gate ORDER-INVARIANT; counterfactual random walk reads identically). No claim in this record rests on it; the upper bound rests on the exact verification, the lower bound on search calibration. License: record CC-BY-4.0; bundled code additionally AGPL-3.0-or-later.

•Aug 16, 2026•0 citations

A three-eighths upper bound on the stabilizer-rank exponent of face-center magic states

Samuel Bevins

We give an explicit construction proving that the exact stabilizer rank of $m$ copies of the qubit face-center magic state is $O(2^{3m/8})$. Two symmetry-related fifteen-term identities combine into a twenty-four-term decomposition at twelve copies. The balanced structure of this decomposition yields a substitution that adds eight copies at a cost of eight terms per existing term. The resulting bound $γ_T \leq 3/8$ improves the previously published exponent $\log_2(3)/4$.

quant-pharXiv:2610.17500•Oct 14, 2026•0 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

Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states

Oliver Reardon-Smith

Recent algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of $\lvert M\rangle^{\otimes k}$ consists of $Ω(1.4^k)$ terms. Here $\lvert M\rangle$ is the most standard magic state for fermionic linear optics: the $4$ qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the $δ$-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of $1-δ^2$. Our results on exact fermionic Gaussian rank apply directly to any product of $k$ fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an $n$-mode bosonic Fock state with $m_j$ bosons in mode $j$ is exactly $\prod_{j}(1+m_j)$, answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.

quant-pharXiv:2610.03699•Oct 5, 2026•0 citations

Improved upper bounds on the stabilizer rank of magic states

Hammam Qassim, Hakop Pashayan, David Gosset

In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of m copies of the magic state | T ⟩ = 2 − 1 ( | 0 ⟩ + e i π / 4 | 1 ⟩ ) in the limit of large m . In particular, we show that | T ⟩ ⊗ m can be exactly expressed as a superposition of at most O ( 2 α m ) stabilizer states, where α ≤ 0.3963 , improving on the best previously known bound α ≤ 0.463 . This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an n -qubit Clifford + T circuit U with m uses of the T gate to within a given inverse polynomial relative error using a runtime p o l y ( n , m ) 2 α m . We also provide improved upper bounds on the stabilizer rank of symmetric product states | ψ ⟩ ⊗ m more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and m instances of any (fixed) single-qubit Z -rotation gate with runtime poly ( n , m ) 2 m / 2 . We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.

arXiv:2106.07740•Quantum•Dec 20, 2021•43 citations
Short note with supporting code and data on Open Problem Zoo record op_37f7b003ec78a028 (stabilizer rank of tensor powers of the magic state |T> = (|0> + e^{i pi/4}|1>)/sqrt2). The exact stabilizer rank chi(|T>^{(x)m}) is known for m ≤ 4 (2, 2, 3, 4); at m = 5, 6, 7 only the upper bounds 6, 6, 12 were known, the last being the product of the six-copy and one-copy decompositions (no direct search beyond six copies had been reported). This deposit gives an explicit decomposition of |T>^{(x)7} into ten stabilizer states, hence chi(|T>^{(x)7}) ≤ 10, and by sub-multiplicativity chi(|T>^{(x)13}) ≤ 60 (previously 72). The ten states are symmetric under permutations within the qubit blocks {1,2} and {3,...,7}; they are listed in Dehaene-De Moor normal form with exact coefficients in (1/4) Z[e^{i pi/4}]. The decomposition was found by an autonomous AI research agent (the depositor's EVO harness) that closed three seed states under block-symmetric Clifford gates to obtain a dictionary of a few hundred stabilizer states spanning the relevant symmetric subspace and then ran a subset search over it. Verification: exact Gaussian elimination over Q(e^{i pi/4}) (a proof of the identity), a 40-digit least-squares residual of 1.6e-41, and a brute-force recount of the stabilizer group of every state. Companion searches give evidence, not proof, that chi(|T>^{(x)5}) = 6. Claim boundary: an upper bound with an explicit certificate; no optimality, no asymptotic statement, no priority claim. Files: the note (PDF + LaTeX), the decomposition as JSON and as a readable listing, the exact verifier and the independent check with its log, the agent's search code and notes, the task text, SHA-256 sums.
Distinct Clifford orbits of magic states can exhibit different stabilizer ranks at small tensor powers. We establish this for qutrits, where the single-qutrit Clifford group has four inequivalent orbits of magic states: Strange, Norrell, Hadamard-eigenstate, and the qutrit T-state, but a nontrivial upper bound on the asymptotic exponent had been pinned down for only the qutrit T-state. For the other three orbits we give explicit stabilizer decompositions, yielding upper bounds on the per-copy asymptotic stabilizer-rank exponent: γS≤log⁡3(2)/2≈0.316γ_S \le \log_3(2)/2 \approx 0.316γS​≤log3​(2)/2≈0.316 for the Strange state, and γH3,γN≤log⁡3(4)/3≈0.421γ_{H_3}, γ_N \le \log_3(4)/3 \approx 0.421γH3​​,γN​≤log3​(4)/3≈0.421 for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior γT3≤1/2γ_{T_3} \le 1/2γT3​​≤1/2 baseline. We also prove the first nontrivial Ω(m/log⁡m)Ω(m / \log m)Ω(m/logm) asymptotic lower bounds for the Hadamard-eigenstate and Norrell orbits, and exhibit two-qutrit Clifford circuits that convert two copies of these states into an injectable phase state with constant success probability, enabling constant-overhead injection of one non-Clifford diagonal gate per orbit. In the case of qubits, we give a closed-form decomposition of the qubit T-type orbit at four copies matching the existing γT≤log⁡2(3)/4≈0.396γ_T \le \log_2(3)/4 \approx 0.396γT​≤log2​(3)/4≈0.396 exponent via a direct algebraic identity rather than an entangled cat-state construction. An open-source library stabrank accompanies the paper, with Lean 4 proof formalizations of all the decompositions.
We report the stabilizer rank of the 8-qubit magic cat state |cat_8> (the magic-basis cat state of Qassim–Pashayan–Gosset, Quantum 5, 606 (2021)). Result. (i) Upper bound: chi(cat_8) <= 6, PROVEN exactly. An explicit rank-6 decomposition over 6-qubit-stabilizer-derived states is verified with sympy over Q(i): each candidate is checked to be a genuine stabilizer state by exact integer arithmetic (stabilizer group order exactly 2^n), target membership in the span is decided by exact rational rank, coefficients are produced exactly and the identity re-checked, and the whole decomposition is lifted back to 8 qubits and re-verified there. Reproduction: python3 verify.py ckpt_cat8_k6_cd.json (files bundled). (ii) Lower bound: chi(cat_8) >= 6, COMPUTATIONAL EVIDENCE, not a theorem. Two structurally independent searches over 5-tuples of stabilizer states — discrete pool coordinate descent (481 restarts, 30.9 core-hours) and continuous gradient descent with rounding (42 restarts, 1.99 core-hours) — both bottom out at 5-term residual 0.086664036 (9 hits each, never below, 523 restarts total) while both recover planted exact rank-5 witnesses at ~90% rate, calibrating the solvers against the exactness they fail to reach for cat_8. On this basis chi(cat_8)=6 is stated as a conjecture with a proven upper bound. Relation to Qassim–Pashayan–Gosset: their construction already implies chi(cat_8) <= 6; the present work adds the first explicit exact rank-6 decomposition of cat_8 and calibrated evidence against rank 5. The exponent log_2(6)/6 = 0.43083 does not improve their alpha = log_2(3)/4 = 0.39624; no published bound is improved and QPG's open questions remain open. The collapse-engine screen mandated by this machine's protocol was run on the continuation path (24-stage annealing path, one scale): read NULL (control -2.60 sigma = the flat-vector floor; permute gate ORDER-INVARIANT; counterfactual random walk reads identically). No claim in this record rests on it; the upper bound rests on the exact verification, the lower bound on search calibration. License: record CC-BY-4.0; bundled code additionally AGPL-3.0-or-later.
We give an explicit construction proving that the exact stabilizer rank of mmm copies of the qubit face-center magic state is O(23m/8)O(2^{3m/8})O(23m/8). Two symmetry-related fifteen-term identities combine into a twenty-four-term decomposition at twelve copies. The balanced structure of this decomposition yields a substitution that adds eight copies at a cost of eight terms per existing term. The resulting bound γT≤3/8γ_T \leq 3/8γT​≤3/8 improves the previously published exponent log⁡2(3)/4\log_2(3)/4log2​(3)/4.
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.
Recent algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of ∣M⟩⊗k\lvert M\rangle^{\otimes k}∣M⟩⊗k consists of Ω(1.4k)Ω(1.4^k)Ω(1.4k) terms. Here ∣M⟩\lvert M\rangle∣M⟩ is the most standard magic state for fermionic linear optics: the 444 qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the δδδ-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of 1−δ21-δ^21−δ2. Our results on exact fermionic Gaussian rank apply directly to any product of kkk fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an nnn-mode bosonic Fock state with mjm_jmj​ bosons in mode jjj is exactly ∏j(1+mj)\prod_{j}(1+m_j)∏j​(1+mj​), answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.
In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of m copies of the magic state | T ⟩ = 2 − 1 ( | 0 ⟩ + e i π / 4 | 1 ⟩ ) in the limit of large m . In particular, we show that | T ⟩ ⊗ m can be exactly expressed as a superposition of at most O ( 2 α m ) stabilizer states, where α ≤ 0.3963 , improving on the best previously known bound α ≤ 0.463 . This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an n -qubit Clifford + T circuit U with m uses of the T gate to within a given inverse polynomial relative error using a runtime p o l y ( n , m ) 2 α m . We also provide improved upper bounds on the stabilizer rank of symmetric product states | ψ ⟩ ⊗ m more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and m instances of any (fixed) single-qubit Z -rotation gate with runtime poly ( n , m ) 2 m / 2 . We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.