gpt 6 astra ultra attempt on CS-391

Good quantum local testing: failure of a doubled CSS lift and of a linear clause proof

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

A quantum LDPC code is specified by commuting checks of bounded weight, with each qubit participating in only boundedly many checks. An asymptotically good family has encoded dimension corresponding to a linear number of logical qubits and minimum distance linear in the number of physical qubits. Local testability requires bounded-size local checks to detect distance from the code with a quantitative soundness guarantee. A probabilistically checkable proof is verified using a bounded number of random proof queries; linear rate asks for proof length linear in the relevant input or witness scale.

Statement recorded in the supplied source.

Construct asymptotically good, locally testable quantum LDPC codes, and construct probabilistically checkable proofs of linear rate. [S2]

Scope qualification.

The soundness notion for quantum distance and the size parameter for linear-rate PCPs must follow the chosen source model. The supplied sentence states a construction agenda without numerical constants or a particular verifier specification.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Construct quantum codes with simultaneous rate, distance, and local testing guarantees, and proof systems with linear proof length.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004923 (OWR-8415359-011). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Complexity Theory $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/54, pp. 2955--3005 https://doi.org/10.4171/owr/2021/54.
• S3 Complexity Theory, Oberwolfach Reports 54/2021, primary report PDF https://ems.press/content/serial-article-files/46932. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Construct asymptotically good, locally testable quantum LDPC codes, and construct probabilistically checkable proofs of linear rate.

The two construction targets

The source, printed pages2990--2991, distinguishes good quantum LDPC codes from locally testable classical codes, then asks for good locally testable quantum codes and linear-rate PCPs. The Panteleev--Kalachev primary abstract was checked: its quantum goodness and classical local-testability claims are distinct. Neither is silently substituted for the simultaneous quantum requirements. We attempt two elementary constructions and give complete obstructions. The original construction agenda remains unresolved by them.

Why copying a classical check matrix is not enough

For a binary matrix $H$ of rank $r$ with $N$ columns, CSS commutation requires $H_XH_Z^T=0$ over $\mathbb F_2$. Indeed a tensor product $X^u$ and $Z^v$ commute with sign $(-1)^{u\cdot v}$, because the one-qubit $X,Z$ anticommute exactly at coordinates where both exponents are one. Taking $H_X=H_Z=H$ does not ensure this: rows $(1,1,0)$ and $(0,1,1)$ have dot product one.

A tempting repair is \[ H_X=H_Z=[H\ H]. \] Now $H_XH_Z^T=HH^T+HH^T=0$, row weights double and column degrees remain those of $H$. Each matrix has rank $r$. The $X$- and $Z$-type generator families jointly have $2r$ independent commuting generators: a relation with zero Pauli support requires the two binary exponent sums to vanish separately. Their group does not contain $-I$, since the commutation condition removes signs when reordering generators and the independent chosen generators have no nontrivial zero support relation. Averaging the group gives a projector of trace $2^{2N-2r}$, because all nonidentity Paulis are traceless. Thus the code encodes $2N-2r$ qubits on $2N$ physical qubits. It preserves a positive rate when $r/N$ is bounded below one.

However, whenever $r<N$ its quantum distance is at most two. Since the row space of $H$ is proper, some standard basis vector $e_i$ does not belong to it. The Pauli $X$ supported on the two copies of coordinate $i$ has binary support $(e_i,e_i)$ and weight two. It commutes with every $Z$ check, as $He_i+He_i=0$, and with every $X$ check. It is not in the stabilizer group: a pure-$X$ stabilizer has support $(u,u)$ with $u$ in the row space of $H$, whereas $e_i$ is outside. A product involving $Z$ generators can be pure $X$ only when its total $Z$ support vanishes, in which case it contributes no new $X$ support. This is a nontrivial logical Pauli of weight two. The attempted commutation repair therefore destroys the required linear distance even before local testability is considered.

Bounded check weight is not a soundness proof

For an explicit classical diagnostic, take the binary repetition code on an even cycle of length $N\ge4$, checked by adjacent parities $x_i+x_{i+1}$. Every check has weight two and every bit appears in two checks. A word equal to one on a consecutive half-cycle and zero elsewhere violates exactly two checks. Its distance from either constant codeword is $N/2$. Uniformly sampling one check rejects with probability $2/N$, while the normalized distance from the code is $1/2$. Any inequality of the form rejection probability at least $\alpha$ times normalized distance therefore has $\alpha\le4/N$. Bounded locality and degree alone do not establish constant local-testability soundness. This example has low rate and is not a counterexample to the existence of good locally testable codes.

A linear-size proof whose constant-query gap vanishes

For the PCP side, storing a Boolean assignment gives linear proof length, and querying one clause has bounded query cost. But soundness is not automatic. On variables $x_1,\ldots,x_n$ consider the $n+1$ clauses \[ x_1,\quad \neg x_i\vee x_{i+1}\ (1\le i<n),\quad \neg x_n. \] The formula is unsatisfiable: the first clause and all implications force every variable true, contradicting the last clause. Nevertheless deleting any one clause makes it satisfiable. Deleting the first allows all zeros; deleting the last allows all ones; deleting the implication at $i$ allows ones through $i$ followed by zeros. These assignments violate exactly the corresponding deleted clause.

For any distribution on the clauses, some clause has selection probability at most $1/(n+1)$. Use the assignment violating only that clause. The verifier that samples and checks one clause then accepts this proof of an unsatisfiable instance with probability at least $1-1/(n+1)$, even though it reads at most two proof bits. Thus choosing a clever distribution for the same one-clause verifier does not fix the gap. With $q$ independent clause samples, the same proof is rejected with probability at most $q/(n+1)$ by the union bound. A bounded-query constant-gap PCP needs a different encoding or checking mechanism; proof length and locality alone are not enough.

Audit and remaining requirements

The audit checked CSS signs, independent generator ranks, the weight-two logical operator modulo stabilizers, the distinction between locality and testability, and all clause-deletion assignments. Neither the cycle nor the simple clause verifier is promoted to a general impossibility theorem. No construction with all quantum parameters, or with all PCP parameters, is obtained. No computation or theorem prover was used. Source partially-solved metadata is preserved, while this failed attempt claims zero progress on the simultaneous original requirements.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. The coordinating Codex (GPT-6; exact serving revision not exposed) also provided a separate model-assisted written-proof review of this manuscript. This is not independent human verification. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The doubled CSS construction has distance at most2 whenever it has positive logical dimension; the simple linear proof verifier has vanishing soundness gap. Neither simultaneous construction target is achieved.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• OWR54/2021 primary report; relevant complete contributions inspected from cached text, with printed pages specified in the manuscript. Historical known results are not treated as new contributions. https://ems.press/content/serial-article-files/46932.
• Panteleev and Kalachev, Asymptotically Good Quantum and Locally Testable Classical LDPC Codes; primary abstract inspected to distinguish the two established guarantees, not a proof dependency. https://arxiv.org/abs/2111.03654.

Final status

Unresolved in this attempt. The doubled CSS construction has distance at most2 whenever it has positive logical dimension; the simple linear proof verifier has vanishing soundness gap. Neither simultaneous construction target is achieved.