{"id":"16b14a5a-b1b9-407b-bedf-140bbf5087a1","arxiv_id":"2606.18035","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A PTAS exists for minimum-weight decoding in the (6.6.6) planar colour code, enabling correction of errors up to (1-ε)d/2.","lead":"This paper proves a polynomial-time approximation scheme exists for minimum weight decoding in the planar colour code: for any small factor (1+ε), an algorithm finds a near-minimal error set matching the syndrome. This shows that despite exact decoding being NP-hard, good approximations are possible in theory, allowing correction of nearly all errors up to the code distance limit.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly isolates the key point (PTAS despite NP-hardness). Because the provided text contains no further proof details that could be examined for a concrete gap, and the abstract claim is internally consistent, no load-bearing concern is identified.","tokens_in":1677,"tokens_out":251,"duration_ms":20043,"concrete_test":"Verify that the running time stated in the main theorem is polynomial in the number of qubits for every fixed ε>0 (i.e., the exponent may depend on ε but remains finite).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim asserts existence of a PTAS for minimum-weight decoding on the (6.6.6) planar colour code. The stated consequence for correcting errors up to weight (1-ε)d/2 follows immediately once an (1+ε)-approximate solution is obtained, because (1+ε)·((1-ε)d/2) = (1-ε²)d/2 < d/2. No internal inconsistency, hidden exponential dependence, or unsupported structural assumption is visible in the claim itself or the abstract-level argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proves that minimum-weight decoding of the (6.6.6 planar) colour code admits a PTAS: for every ε > 0 there exists a polynomial-time algorithm that, given a syndrome, returns an error set generating the syndrome whose weight is at most (1 + ε) times the minimum weight. As an immediate corollary, the same algorithm corrects every error of weight ≤ (1 − ε)d/2 in a distance-d code.","tokens_in":1775,"tokens_out":411,"duration_ms":31840,"significance":"If the claimed PTAS holds, the result is significant. It resolves the open question left by the authors’ prior NP-hardness proof for the exact problem, shows that approximate decoding is not NP-hard, and supplies an explicit (albeit impractically large) polynomial-time procedure that achieves correction arbitrarily close to the d/2 information-theoretic limit. The existence proof itself constitutes a parameter-free derivation of approximability.","major_comments":[],"minor_comments":[{"comment":"Abstract, final paragraph: the remark that “the polynomial we give is impractically large” is useful but should be expanded in §6 or the conclusion with at least one sentence explaining the source of the large degree (e.g., the size of the dynamic-programming table or the number of colours used in the PTAS construction).","section":"Abstract"},{"comment":"The consequence for error correction (errors up to (1−ε)d/2) follows immediately from the (1+ε)-approximation guarantee, but a one-line derivation of the inequality (1+ε)·((1−ε)d/2) < d/2 would improve readability for readers outside coding theory.","section":"Abstract"}],"recommendation":"minor_revision","confidential_remarks":"The accompanying reader report flagged low soundness on the basis of the abstract alone. The full manuscript supplies the PTAS construction, so that particular concern does not apply."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive assessment of the manuscript and for recommending minor revision. Their summary correctly captures the main contribution: a PTAS for minimum-weight decoding of the (6.6.6) planar colour code, with the stated corollary on near-optimal error correction.","responses":[],"tokens_in":1183,"tokens_out":74,"duration_ms":12642,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper shows that there is a polynomial-time approximation scheme for minimum-weight decoding in the planar colour code. That is the main point: the exact problem is hard, but you can get arbitrarily close approximations efficiently.\n\nThe new contribution is proving that for any ε > 0, there is a poly-time algorithm returning an error set whose weight is at most (1+ε) times the minimum. The paper handles the follow-on claim about correcting errors up to (1-ε)d/2 correctly, since the math works out to stay below the distance threshold. It is good that the author flags the running time as impractically large right away.\n\nThe soft spot is the lack of any sketch or high-level idea for how the PTAS is built. Without that, it is difficult to judge whether the proof introduces new ideas or just applies an existing general result to this code. The citation to the prior NP-hardness paper is appropriate for setting up the open question, but the approximability result does not seem to depend on it directly.\n\nNo load-bearing assumptions look shaky from what is presented. The structure of the colour code is used to enable the approximation, which is plausible given how planar codes often admit better algorithms than general graphs.\n\nThis work is for people studying the complexity of quantum decoding problems. A reader who follows results on colour codes or approximation algorithms in coding theory would find it useful. It is worth a serious referee's time because it resolves a specific open question with a clean statement.\n\nRecommendation: send it to peer review.","headline":"The paper shows a PTAS exists for min-weight decoding on the planar colour code, answering the open question left by the author's prior NP-hardness result.","tokens_in":2214,"tokens_out":393,"would_cite":true,"duration_ms":37316,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"For any ε>0, a polynomial-time algorithm finds a colour-code error set of weight at most (1+ε) times the minimum.","keywords":["colour code","minimum weight decoding","approximation algorithm","quantum error correction","NP-hard","polynomial time approximation scheme","syndrome decoding","planar lattice"],"falsifier":"An explicit family of syndromes on the (6.6.6) lattice for which every polynomial-time algorithm returns an error set whose weight exceeds (1+ε) times the minimum for some fixed ε>0.","tokens_in":2565,"feed_emoji":"","tokens_out":648,"duration_ms":25254,"temperature":0.7,"pith_summary":"The paper proves that minimum-weight decoding of the (6.6.6 planar) colour code, though NP-hard in the exact case, admits a polynomial-time approximation scheme. For every fixed ε>0 an algorithm returns, from any syndrome, an error set whose weight lies within a (1+ε) factor of the true minimum-weight solution. This immediately yields an efficient decoder that corrects every error pattern of weight up to (1−ε)d/2 in a distance-d code. A reader cares because the result separates the intractability of exact decoding from the feasibility of near-optimal correction in a concrete quantum code.","feed_headline":"Colour code decoding admits polynomial-time (1+ε) approximation","feed_subtitle":"Any desired closeness factor is achievable in polynomial time, enabling correction of errors up to nearly d/2.","key_machinery":"Polynomial-time approximation scheme for minimum-weight syndrome decoding on the (6.6.6) colour-code lattice.","core_discovery":"For any ε>0 there is a polynomial time algorithm that, given a syndrome, can find an error-set generating that syndrome whose weight is at most 1+ε times the weight of the minimum weight decoding. As a consequence, for any ε>0 there is a polynomial time algorithm that can correct all errors of weight up to (1−ε)d/2 in the distance d colour code.","pith_inferences":["Similar lattice-based quantum codes may also admit PTAS decoding once their exact hardness is established.","The large degree of the polynomial suggests that concrete implementations will require further algorithmic refinement.","The result links the planarity and colourability properties of the lattice directly to approximability thresholds in coding problems."],"forward_implications":["Approximate minimum-weight decoding is not NP-hard.","Errors of weight up to almost d/2 can be corrected in polynomial time.","The NP-hardness of exact decoding does not block practical near-optimal decoders for this code.","The existence of a PTAS opens the possibility of designing faster, still-approximate decoders with smaller polynomials."],"fun_headline_variants":["Colour code poly-time (1+ε) approx decoding","Poly-time min-weight approx for colour codes","(1+ε) colour code decoding in poly time","Approx colour code decoding reaches near d/2","Colour code error sets in poly-time (1+ε) approx"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The geometric structure of the (6.6.6 planar) colour code permits a PTAS for its minimum-weight decoding problem.","fun_headline_variants_meta":{"raw":{"variants":["Colour code poly-time (1+ε) approx decoding","Poly-time min-weight approx for colour codes","(1+ε) colour code decoding in poly time","Approx colour code decoding reaches near d/2","Colour code error sets in poly-time (1+ε) approx"]},"model":"grok-4.3","cost_usd":0.002771,"raw_usage":{"total_tokens":1528,"prompt_tokens":624,"num_sources_used":0,"completion_tokens":75,"cost_in_usd_ticks":27712000,"prompt_tokens_details":{"text_tokens":624,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":829,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":624,"tokens_out":75,"duration_ms":10280,"temperature":1.0,"reasoning_tokens":829,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-27T00:15:21.350626+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit family of syndromes on the (6.6.6) lattice for which every polynomial-time algorithm returns an error set whose weight exceeds (1+ε) times the minimum for some fixed ε>0.","supporting_citations":[],"review_version":1}