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 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.
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.
We give an explicit construction proving that the exact stabilizer rank of m copies of the qubit face-center magic state is 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 improves the previously published exponent log2(3)/4.
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≤log3(2)/2≈0.316 for the Strange state, and γH3,γN≤log3(4)/3≈0.421 for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior γT3≤1/2 baseline. We also prove the first nontrivial Ω(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≤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 prove that every pure state of stabilizer rank at most k has stabilizer extent at most 2O(klog(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(klog(k+1)), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(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 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 Ω(n2/logn) 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((logn)2/loglogn), respectively, a logn improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most k, with 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 consists of Ω(1.4k) terms. Here ∣M⟩ 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 mj bosons in mode j is exactly ∏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.
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.