{"id":"e90fd376-6a6b-4794-85b4-3ce6145a63db","arxiv_id":"2411.12482","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A classical simulation framework called MAST, built by adding magic state injection to stabilizer tensor networks, simulates random T-doped Clifford circuits with up to N T-gates in polynomial time and hidden shift circuits with 4000 qubits and 320 T-gates.","lead":"This paper introduces an upgraded classical simulator for quantum circuits, combining tensor networks with a trick from quantum error correction called magic state injection. It reports that random quantum circuits with many non-Clifford gates can be simulated more cheaply than previously thought, up to 200 qubits in one benchmark and 4000 qubits in another.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Scaling proof hinges on unverified tableau block-structure; injection CNOTs can alter the assumed X-probabilities, so the O(poly(N)) claim is not established.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing point: the Appendix C scaling argument assumes a specific block structure for the stabilizer tableau, with independent X entries in the upper-right block at probability ~1/2 and an identity lower-left block. I concur that this is the most critical unproven step. My stress-test sharpens the concern in two ways. First, the paper's one-sentence justification for the block structure is not a proof: magic-state injection necessarily involves entangling CNOT gates between the data and magic registers, and such gates can produce Z entries in the upper-right block and non-identity entries in the lower-left block, depending on the gadget and the tableau convention. The paper does not specify the exact injection circuit used in the numerical implementation, and the code repository is not analyzed in the text. Second, the Appendix C.2 calculation of the X-probability is derived for a uniformly random Clifford group element, but the MAST tableau is a structured object evolving under a specific ensemble of random Cliffords interleaved with fixed injection CNOTs. There is no reason to assume the same statistics without direct verification. The only supporting evidence is the bond-dimension curve, which is an indirect proxy: low bond dimension can result from other effects, such as the order of delayed projections or tensor compression, and the paper reports averages without error bars. A direct test of the tableau statistics is straightforward and would settle whether the central O(poly(N)) claim holds. Since the reader already marked the paper CONDITIONAL on this assumption, and my analysis does not change that assessment, the verdict remains unchanged.","tokens_in":14851,"tokens_out":49377,"duration_ms":469485,"concrete_test":"Run the released MAST code on random T-doped Clifford circuits with N=20, t=10, and instrument it to output the full stabilizer tableau before each magic-register projection, over 1000 random instances. Compute (i) the empirical probability that each entry in the upper-right block of Fig. 4 is X (or Y), and (ii) the empirical probability that the first row anti-commuting with the projected magic operator lies in the data block (k < N) at each step. Compare these against the model's predictions p≈1/2 and P(k<N)≈1−2^{−(N−w)}. If the empirical P(k<N) is not exponentially close to 1, or if the upper-right entries are not independent with p≈1/2, then the polynomial-cost scaling for t≲N is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central scaling claim in Appendix C rests entirely on the assertion that, before any projection, the MAST stabilizer tableau has the block form of Fig. 4: upper-right entries independently equal to X with probability near 1/2, lower-left entries all identity, and lower-right diagonal X. The paper justifies this with one sentence: 'operations on the data register only modify the left half of the tableau, while magic state injection operations only add X terms to the right half of the tableau.' This is not shown, and it is not obviously true. The magic-state injection gadget itself contains CNOT gates between data and magic registers; such gates update both the left and right halves of the tableau and can produce Z entries in the upper-right block and X or Z entries in the lower-left block, depending on the gadget orientation and the reference state. The Appendix C.2 probability calculation applies to a uniformly random Clifford tableau, not to the structured tableau produced by a random Clifford circuit interleaved with injection CNOTs. If the upper-right X-probability is not ~1/2, the probability that the first anticommuting row lies in the data block can degrade significantly, and the claimed O(poly(N)) cost can break. The numerical bond-dimension curves do not directly validate the tableau statistics; they are aggregated over 1000 random instances with no error bars, and low bond dimension could arise from projection order or compression effects even if the probabilistic premise is false.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces MAST, a variant of the Stabilizer Tensor Network (STN) protocol in which non-Clifford T gates are replaced by magic-state injection gadgets and the associated measurements are postponed until the end of the circuit. The central claim is that for random T-doped N-qubit Clifford circuits with t less than or comparable to N T-gates, the simulation cost of MAST is O(poly(N)), whereas the ordinary STN cost grows exponentially. Numerical evidence is reported for random circuits up to N=200 and for the Hidden Bit Shift circuit up to 4000 qubits and 320 T-gates, with bounded MAST bond dimension. Appendix C provides a probabilistic argument intended to explain the polynomial scaling in the t less than or comparable to N regime.","tokens_in":15072,"tokens_out":7043,"duration_ms":78415,"significance":"If the scaling claim were rigorously established, this would be a substantial extension of classical simulation methods for highly entangled circuits with an extensive number of non-Clifford operations. The paper has notable strengths: it releases an implementation, reports concrete benchmarks on two circuit families, and makes falsifiable numerical predictions. The 4000-qubit Hidden Bit Shift demonstration is impressive even if it relies on a known polynomial-time simulation result. However, the theoretical argument in Appendix C is heuristic and depends on an unproven structural assumption about the stabilizer tableau. The absence of fitted parameters in the numerical curves is a strength, but the explanatory model in Figure 5 partly assumes the mechanism it is meant to establish. The central O(poly(N)) claim is therefore not yet proven, although the numerical evidence makes it plausible.","major_comments":[{"comment":"The entire scaling argument rests on the asserted block structure of the stabilizer tableau before projection: upper-right entries independently equal to X with probability near 1/2, lower-left entries all identity, and lower-right diagonal X. The text justifies this with one sentence: \"operations on the data register only modify the left half of the tableau, while magic state injection operations only add X terms to the right half of the tableau.\" This is not a derivation. In particular, the CNOT gates inside the magic-state injection gadget couple the data and magic registers, so they update both halves of the tableau. The claim that the lower-left quadrant is identity is especially suspicious: a CNOT from a data qubit to a magic ancilla updates the ancilla stabilizer row by multiplying it with the data row, which generally creates non-identity entries in the lower-left block. Since the probability that the first anticommuting row lies in the magic register is the load-bearing step, this structure needs either a rigorous proof or a direct numerical check of the actual tableau statistics.","section":"Appendix C, Fig. 4"},{"comment":"The probability p(n) = 2^{n-1}/(2^n - 1) is computed for a uniformly random Clifford tableau. The MAST tableau, however, is not uniformly random: it is produced by interleaving uniformly random data-register Cliffords with injection CNOTs, and it is subsequently modified by projection updates that replace a stabilizer row with the measured operator Z_i. The statement that multiplying two random binary strings preserves the X statistics is asserted without proof. The probability model in Appendix C therefore does not apply in an obvious way to the ensemble that is actually simulated. The authors should either prove that the relevant subtableaux are uniformly random in the required sense or verify the X-probabilities numerically on the actual tableau ensemble.","section":"Appendix C.2, Eq. (C3)"},{"comment":"The appendix concludes that MAST is efficient in the t less than or comparable to N regime, but it does not state the full worst-case complexity as a function of N, t, and bond dimension. The abstract claims O(poly(N)) cost. Even granting the assumed tableau structure, the argument bounds the bond dimension and discusses the location of the first anticommuting row; it does not assemble these ingredients into a formal complexity statement that accounts for all projections and tensor-network contractions. This is not merely a presentation issue: the claimed polynomial scaling is the central quantitative result, so the paper should either state and prove a precise theorem or explicitly separate the proven upper bound from the numerical evidence.","section":"Appendix C, text after Eq. (C2)"},{"comment":"The numerical validation is averaged over 1000 random instances with no reported error bars or distribution. A bounded average bond dimension can be dominated by easy instances, and the curves alone do not directly test the Fig. 4 tableau structure. The model in Fig. 5 assumes that bond dimension increases only through the chi=2 to chi=4 mechanism, which is the same mechanism the numerics are meant to confirm; this is a circularity risk. Reporting the variance or quantiles of the bond dimension, and separately checking the empirical X-probabilities in the upper-right tableau block, would substantially strengthen the evidence.","section":"Fig. 2(b)-(c) and Fig. 5"}],"minor_comments":[{"comment":"The caption says the second decomposition uses \"4 T-gates with no extra ancillas,\" but Appendix D and the surrounding text describe the ancilla-free decomposition as using 7 T-gates. This appears to be a typo and should be corrected.","section":"Fig. 8(a) caption"},{"comment":"For the 4000-qubit Hidden Bit Shift result, only bond dimension is reported, not runtime or operation count. Since the circuit has O(N) gates, bounded bond dimension does not by itself imply a practically small runtime; a wall-clock time or FLOP count for the largest case would make the claim \"efficiently simulate\" more concrete.","section":"Fig. 3(b) and Appendix E"},{"comment":"The text states that replacing T-gates with arbitrary Rz(theta) rotations results in an identical bond-dimension distribution. This is plausible, but the coefficients of the gate decomposition change, and numerical stability can differ; the sentence should be phrased as an empirical observation for the tested instances rather than a general statement.","section":"Results and Discussion, Random Circuits"},{"comment":"The notation n is used for the number of qubits in the symplectic probability argument, while N is used for the data-register size elsewhere. Clarify the relationship between n and N (e.g., whether n is the total number of qubits or the size of the relevant subtableau) to avoid confusion.","section":"Appendix C.2"}],"recommendation":"major_revision","confidential_remarks":"The central claim is plausible and the numerical results are interesting, but the theoretical argument in Appendix C is not yet at the level required for the abstract's O(poly(N)) statement. The unverified tableau block structure is the main load-bearing assumption, and it can be checked relatively cheaply by instrumenting the released code to print the tableau statistics before projection. I would want either a rigorous derivation of the Fig. 4 structure or direct numerical verification of the X-probabilities and lower-left identity claim. The comparison with Ref. [15] and Ref. [48] should also be sharpened, since those results already cover some of the reported capability."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's the short version: this is a real algorithmic idea, and the numerics back the main claim in the average case. MAST takes the STN simulator and pushes all non-Clifford work into delayed measurement of injected magic states, so the Clifford part lives in a stabilizer tableau and the MPS only pays at the end. For random T-doped Clifford circuits with t ≲ N, they report bounded bond dimension (≤3) for up to N=200 qubits over 1000 instances, and they demonstrate a 4000-qubit Hidden Bit Shift simulation with 320 T-gates. That's the kind of concrete benchmark that makes a method worth adopting. It's new for STNs, it avoids the optimization step of CAMPS, and they didn't fit any free parameters to get the scaling.\n\nThe main weakness is the scaling proof in Appendix C. The argument hinges on a particular block structure of the stabilizer tableau (Fig 4) with the upper-right block having independent X entries at probability ~1/2 and the lower-left block being identity. The paper asserts this on the ground that data-only gates modify only the left half and injection operations only add X terms to the right half. That's not shown, and the injection gadget's CNOTs between data and magic registers do mix the halves in the tableau. If the X-probabilities are off, the probability that the first anticommuting row lands in the magic register drops and the O(poly(N)) cost claim can fail. The numerics are consistent with the claim, but they don't directly test the tableau statistics, and the averaged bond-dimension curves have no error bars. The projection order is also under-specified, though the authors admit the cost is path-dependent. The code is on GitHub but with no commit hash or raw data, which is a minor reproducibility hiccup.\n\nThese are real gaps, but they are addressable gaps rather than contradictions. The paper is honest that the appendix gives an upper-bound argument, and it cites the concurrent CAMPS and Pashayan results. I'd send this to a serious referee: the method is useful, the benchmarks are meaningful, and a referee can ask for direct tableau-statistics checks, error bars, and a cleaner statement of the projection-order dependence. I'd also cite it in my own simulation work. The proof isn't complete, but the evidence is good enough to engage with.","headline":"A genuinely useful and plausible simulation method whose numerical evidence is solid, but whose main scaling claim rests on a heuristic tableau-structure assumption that the paper does not prove.","tokens_in":15638,"tokens_out":7474,"would_cite":true,"duration_ms":74222,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"MAST augments stabilizer tensor networks with magic state injection, claiming polynomial-time classical simulation of random T-doped Clifford circuits with up to N T-gates for expectation values.","keywords":["stabilizer tensor networks","magic state injection","classical simulation of quantum circuits","T-doped Clifford circuits","Hidden Bit Shift circuit","bond dimension","non-Clifford operations","matrix product states"],"falsifier":"On a 100-qubit random T-doped Clifford circuit with t equal to 100, write out the stabilizer tableau before any projection and, for each magic-register column, count how often the first row that anticommutes with Z_i is a data-register row. If that probability is not close to 1 - $2^{{-(N-w)}}$ after w projections, or if the X-entry probability in the upper-right block is not near 1/2, then the claimed O(poly(N)) cost is falsified.","tokens_in":1955,"feed_emoji":"⚛️","tokens_out":2310,"duration_ms":87997,"temperature":0.7,"pith_summary":"This paper tries to show that a hybrid classical simulator combining stabilizer tableaux with matrix product states can be made dramatically stronger by moving all non-Clifford operations into magic-state injection gadgets, leaving only final projective measurements as the hard step. If the argument is right, random Clifford circuits doped with up to about N T-gates, a regime generally believed to be classically hard, can have expectation values computed in polynomial time, and the Hidden Bit Shift benchmark can be pushed to 4000 qubits and 320 T-gates. The reason is structural: in the stabilizer tableau of such circuits, the magic-register columns contain random X entries with probability close to 1/2, and the data-register rows that would entangle the tensor network are almost always hit first, so the projections do not grow the bond dimension. The paper also identifies a regime transition beyond t approximately N where the bond dimension begins to grow exponentially, although MAST still outperforms standard STN for a range of depths.","feed_headline":"Random T-doped circuits get classical simulation up to N T-gates","feed_subtitle":"Polynomial-time expectation values for up to N T-gates, shown on 200-qubit random circuits.","key_machinery":"The central object is the stabilizer tableau kept alongside the matrix product state, together with the magic-state injection gadget that replaces each T-gate. The paper's scaling argument rests on the block form of the tableau before projection: the upper-right block (magic-register columns in data-register rows) has independent X entries with probability close to 1/2, the lower-left block is identity, and the lower-right block is diagonal X with identity off-diagonal rows. When a magic-register observable is projected, the first anticommuting destabilizer row lies in the data-register rows with probability 1 - $2^{{-(N-w)}}$ after w projections, so the projection operator simplifies to a non-entangling operation on the unentangled |0>^N register. This keeps the bond dimension bounded as long as t is less than N.","core_discovery":"The central claim is that injecting magic states rather than applying T-gates directly makes the Stabilizer Tensor Network protocol efficient for circuits with extensive non-Clifford content. In MAST, each T-gate is replaced by a gadget that prepares an ancilla magic state, applies Clifford operations, and defers the final projective measurement to the end of the circuit; the paper argues that for random T-doped N-qubit Clifford circuits with t less than or approximately N, the final projections act on the magic register in a way that does not increase the MPS bond dimension, giving an average bond dimension bounded by 3 and an overall cost of O(poly(N)) for expectation values. The paper demonstrates this numerically for random circuits up to 200 qubits and reports efficient simulation of the Hidden Bit Shift circuit with 4000 qubits and 320 T-gates, as well as 160 T-gates on 40 qubits. The authors also show that MAST is largely insensitive to the choice of CCZ decomposition, unlike standard STN.","pith_inferences":["A testable extension is that any circuit family whose pre-projection stabilizer tableau keeps the magic-register columns sparse in the data rows should be efficiently simulable by MAST; structured circuits such as QAOA layers could be probed for this property.","If the scaling holds, the practical reach of MAST is narrower than full classical simulation of quantum advantage, because it targets expectation values rather than outcome distributions; sampling remains expensive when the number of sampled bits w approaches t.","The sharp bond-dimension transition near t approximately N suggests a protocol-specific simulability phase transition, and locating it for other circuit ensembles could yield a quantitative resource measure linking magic, entanglement, and classical simulation cost.","Projection ordering is a free algorithmic choice in MAST; the random-circuit observation that pairing projections from the middle of the ancilla register outward keeps bond dimension near 2 indicates that measurement scheduling can be as important as the circuit itself."],"forward_implications":["For random T-doped Clifford circuits with t <= N, MAST keeps the average MPS bond dimension bounded and computes expectation values with polynomial classical resources, demonstrated up to 200 qubits.","In the intermediate regime N < t < 1.5N, MAST's bond dimension grows exponentially but remains far below the maximal 2^{N/2} reached by STN, so MAST still significantly outperforms STN and standard MPS methods.","For the Hidden Bit Shift circuit, MAST efficiently simulates 4000 qubits with 320 T-gates and 40 qubits with 160 T-gates, exceeding the 64 T-gates on 40 qubits reported for earlier extended stabilizer methods.","MAST's simulation cost is nearly independent of whether a CCZ gate is decomposed into 4 T-gates with ancillas or 7 T-gates without ancillas, whereas STN's cost depends strongly on that decomposition.","When sampling w bits from a circuit with t < N T-gates, MAST scales as O(exp(w)), which is more efficient than stabilizer-based sampling in the regime where w is much smaller than t, and sampling from low-entanglement final states does not increase bond dimension."],"supporting_citations":[{"why":"Supplies the Stabilizer Tensor Network protocol that MAST augments, including the stabilizer-basis representation and the projection operation whose cost MAST reduces.","marker":"[28]"},{"why":"Provides the low-rank stabilizer decomposition benchmark and the 4 T-gate CCZ decomposition used in the Hidden Bit Shift simulations.","marker":"[7]"},{"why":"Defines the improved classical simulation of Clifford-dominated circuits and establishes the T-doped Clifford circuit as a benchmark with exponential-in-t stabilizer cost.","marker":"[13]"},{"why":"Supplies the stabilizer tableau update and projective measurement formalism used to keep track of the stabilizer state inside MAST.","marker":"[40]"},{"why":"Provides the method for generating uniformly random Clifford operations that make up the random T-doped Clifford circuit ensemble.","marker":"[39]"},{"why":"Supplies the uniform measure on the Clifford group via the symplectic group, used to compute the probability that a tableau entry is X or Y in the scaling argument.","marker":"[58]"},{"why":"Gives the recent theoretical polynomial-time simulation of Hidden Shift circuits, which motivates and contextualizes the efficient MAST result for that benchmark.","marker":"[48]"}],"fun_headline_variants":["Magic state injection makes T-doped circuits classically simulable in poly time","MAST beats STN: polynomial cost for N T-gates on 200 qubits","Hidden Bit Shift: 4000 qubits and 320 T-gates simulated efficiently","T-doped Clifford circuits: poly-time simulation via magic injection","MAST protocol: classical simulation of extensive non-Clifford circuits"],"cache_read_input_tokens":17792,"weakest_assumption_plain":"The load-bearing premise is that, before any magic-state projections, the stabilizer tableau of a random T-doped Clifford circuit has the block form where the upper-right block contains independent X entries with probability close to 1/2 and the lower-left block is identity; if the actual circuit ensemble produces different tableau statistics, the first anticommuting row need not lie in the magic register and the claimed polynomial scaling collapses.","fun_headline_variants_meta":{"raw":{"variants":["Magic state injection makes T-doped circuits classically simulable in poly time","MAST beats STN: polynomial cost for N T-gates on 200 qubits","Hidden Bit Shift: 4000 qubits and 320 T-gates simulated efficiently","T-doped Clifford circuits: poly-time simulation via magic injection","MAST protocol: classical simulation of extensive non-Clifford circuits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000311,"raw_usage":{"total_tokens":1761,"prompt_tokens":926,"completion_tokens":835,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":736}},"tokens_in":542,"tokens_out":835,"duration_ms":8448,"temperature":1.0,"reasoning_tokens":736,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:29:02.638501+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a 100-qubit random T-doped Clifford circuit with t equal to 100, write out the stabilizer tableau before any projection and, for each magic-register column, count how often the first row that anticommutes with Z_i is a data-register row. If that probability is not close to 1 - $2^{{-(N-w)}}$ after w projections, or if the X-entry probability in the upper-right block is not near 1/2, then the claimed O(poly(N)) cost is falsified.","supporting_citations":[{"cited_title":"Masot-Llima and A","cited_arxiv_id":null,"evidence_quote":"Supplies the Stabilizer Tensor Network protocol that MAST augments, including the stabilizer-basis representation and the projection operation whose cost MAST reduces."},{"cited_title":"Bravyi and D","cited_arxiv_id":null,"evidence_quote":"Provides the method for generating uniformly random Clifford operations that make up the random T-doped Clifford circuit ensemble."},{"cited_title":"Koenig and J","cited_arxiv_id":null,"evidence_quote":"Supplies the uniform measure on the Clifford group via the symplectic group, used to compute the probability that a tableau entry is X or Y in the scaling argument."},{"cited_title":"Amy and L","cited_arxiv_id":null,"evidence_quote":"Gives the recent theoretical polynomial-time simulation of Hidden Shift circuits, which motivates and contextualizes the efficient MAST result for that benchmark."}],"review_version":1}