{"id":"8fb88d30-5d64-4fee-a2e7-f08f1d1c6128","arxiv_id":"2507.19018","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces epsilon-approximate k-uniform states, proves Haar-random states and shallow random circuits produce them, and connects them to approximate quantum error-correcting codes and information masking.","lead":"Quantum states called k-uniform states have all their small pieces look maximally random, and this paper defines and studies approximations of them that are almost as useful but much easier to create. It proves random states and shallow random circuits can make these approximations, and uses them to build approximate quantum error-correcting codes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised no-go for shallow random circuits is unsupported: Section II F's Eq. (82) only upper-bounds failure probability; it cannot imply a depth lower bound, so Theorem 9's conclusion about linear-rate codes does not follow.","rationale":"The reader's verdict identified the same gap I find most load-bearing. Section II F is the only place where the paper draws a negative conclusion about shallow random circuits, and the abstract and summary advertise it. The proof of Theorem 9 is an upper bound on the depth needed for a particular epsilon-net certification strategy; it does not rule out alternative strategies or constant-t circuits. Eq. (82) lower-bounds -log Prob(fail), which is equivalent to upper-bounding Prob(fail); when t is small the bound is vacuous. There is no complementary upper bound on -log Prob(fail). Hence the statement 'circuit depth has to grow exponentially with k' is not a theorem. This matters because the claimed separation between Haar-random subspaces and shallow random circuits is a headline application. The positive results (Theorems 1, 2, 4, 5, 8, 10) appear internally consistent; I did not find a concrete algebraic error in the concentration calculations, though the numerical table lacks reproducibility. The correct verdict remains CONDITIONAL: the paper should either remove or explicitly weaken the no-go claim, or supply a genuine lower bound on failure probability for t < cK.","tokens_in":24154,"tokens_out":20357,"duration_ms":218137,"concrete_test":"Analytical check: re-derive Section II F while attempting to prove a matching lower bound on Prob(fail) for t < cK. Since Eq. (82) is obtained by a union bound, it upper-bounds Prob(fail); verify whether any other inequality in the section supplies a lower bound on Prob(fail) or an upper bound on -log Prob(fail). If none exists, the no-go is unproven. Numerical corroboration: set d=2, n=16, delta=6 (alpha about 0.31), K=32 (k=5), epsilon=0.05; sample 100 random 1D circuits of depth L=4n (t around 2-4, far below t=Theta(K)); for each, generate the K-dimensional code subspace and estimate P_fail = Prob(max_{|psi> in C, |S|=5} Tr(rho_S^2) > 1/2^5 + epsilon^2) by sampling 10^3 code states and all C(16,5) subsystems. If P_fail is small, the t=Theta(K) condition is not necessary and the no-go is false; if P_fail is large, this supports the no-go but still does not prove it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing unsupported step is the no-go claim in Section II F (abstract, Theorem 9 caveat, and Summary). Theorem 9 proves only a positive statement: a particular certification argument (epsilon'-net plus approximate t-design concentration) succeeds with vanishing failure when the design order t is Omega(K), yielding circuit depth L = O(nK^2 poly(k)). The subsequent sentence in Section II F, 'the circuit depth has to grow exponentially with k,' converts this sufficient condition into a necessary one without proof. In Eq. (82), -log Prob(fail) is lower-bounded by n log d (-2K(1-alpha) - S_d(alpha) + (1/4 + lambda)t). This is an upper bound on Prob(fail): when the RHS is positive, Prob(fail) <= e^{-RHS}. When t < cK, the RHS is negative, and the inequality is vacuous because -log Prob(fail) >= 0 automatically; it does not imply that Prob(fail) is large. Nothing in the section upper-bounds -log Prob(fail) (equivalently, lower-bounds Prob(fail)), so no depth lower bound follows. A constant-t shallow circuit might still produce a good approximate QECC whose code subspace is certified by another argument (e.g., stabilizer structure or direct enumerator computation). Thus the advertised distinction between Haar-random subspaces and shallow random circuits is not established by the stated inequalities.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper defines epsilon-approximate k-uniform states, where every k-partite reduced density matrix has purity within epsilon^2 of the maximally mixed value, and shows that such states are locally almost indistinguishable from exact k-uniform states. The main existence results are concentration bounds: Theorem 2 proves that a Haar-random state is an epsilon-approximate k-uniform state with high probability, and Theorem 4 extends this to states generated by low-depth random circuits that form approximate t-designs. The paper also introduces a definition of approximate pure QECCs, proves equivalence with approximate uniform states (Theorem 5), derives weight-enumerator bounds for approximate codes (Theorems 6 and 7), proves existence of good approximate QECCs from Haar-random subspaces (Theorem 8), and connects approximate QECCs with approximate quantum information masking (Theorem 10). Numerical optimization results for small systems are reported in Table I.","tokens_in":24412,"tokens_out":17136,"duration_ms":180984,"significance":"If the central results hold, approximate k-uniform states are a useful and experimentally accessible relaxation of exact k-uniform states, and the connection to approximate QECCs is a valuable conceptual bridge. The paper's positive contributions are substantial: Theorem 2 and Corollary 1 give explicit, parameter-free concentration bounds with stated constants; Theorem 8 extends this to random code subspaces via an epsilon-net argument; Theorems 6 and 7 provide clean weight-enumerator inequalities for approximate codes; and Theorem 10 gives a simple but useful implication for approximate quantum information masking. The numerical table supports the theoretical nonexistence/existence bounds in a small case. However, the advertised no-go claim about shallow random circuits in Section II.F is not supported by the derived inequalities, and Corollary 1 as stated omits a necessary constraint. These issues affect load-bearing claims in the abstract and summary, so the paper needs revision before the results can be accepted as stated.","major_comments":[{"comment":"The advertised no-go conclusion that shallow random circuits cannot generate good approximate QECCs is not justified. Equation (82) is a lower bound on -log Prob(fail), i.e. an upper bound on the failure probability; it gives a sufficient condition, t = Omega(K), for the net-based certification argument to have small failure probability. It does not give a lower bound on the failure probability for smaller t, because when the right-hand side of (82) is negative the inequality is vacuous. The sentence 'the circuit depth has to grow exponentially with k' and the abstract/summary claim that random circuits cannot construct codes with linear rate in shallow depth therefore do not follow from the stated inequalities. Please rephrase Theorem 9 and the related claims as positive depth guarantees for the proposed construction, or provide a genuine lower bound on the failure probability of any shallow-circuit construction.","section":"II.F, Eq. (82), Theorem 9, abstract, and Summary"},{"comment":"Corollary 1 states the asymptotic bound gamma >= d^n epsilon^4/(72 pi^3 log 2) under only the constraint epsilon = omega(d^{-n(1-alpha)/2}). For alpha < 1/2 this condition alone does not force d^n epsilon^4 to diverge; for example, epsilon = d^{-n(1-alpha)/2} log n gives d^n epsilon^4 = d^{n(2 alpha - 1)} (log n)^4 -> 0. Hence gamma = omega(1) and vanishing failure probability are not implied. The text immediately before the corollary correctly requires both epsilon = omega(d^{-n(1-alpha)/2}) and epsilon = omega(d^{-n/4}); the corollary should state both constraints explicitly.","section":"II.B, Corollary 1, Eq. (20)"},{"comment":"In the first case of the proof, after assuming log(1/epsilon') >= (sigma + 1/4) n t log d, the displayed lower bound gamma >= -n S(alpha) + t log epsilon + (n/4) t log d drops the nonnegative term max(0, -log(1/epsilon') + (sigma + 1/4) n t log d). Dropping a positive term strengthens the inequality, so the stated bound is not a valid consequence of Eq. (44) for all parameter choices in that case. The argument works when log(1/epsilon') is chosen so that the max term is O(1), but this choice should be stated explicitly and the lower bound written with the max term retained.","section":"II.C, proof of Theorem 4, Eq. (44)"},{"comment":"The step bounding the maximum over the epsilon'-net by |N_C| times a full-space Haar probability is not fully justified as written, because the net N_C depends on the randomly chosen subspace C. The argument can be repaired by constructing N_C as the image under the random isometry of a fixed net of the reference subspace, so that each net element is Haar-distributed over the full space, but this construction should be stated explicitly. As written, the inequality 'Prob(max over net...) <= |N_C| Prob_{|psi>~mu_H}(...)' relies on an unstated property of the net.","section":"II.E, Eq. (77), proof of Theorem 8"},{"comment":"The proximity constraint in Theorem 9 is stated as epsilon = omega(d^{-(n-k)/2}), where k = log_d K is the number of logical qudits. However, the proof applies Theorem 4 with alpha = (delta-1)/n, so the needed constraint is on the code distance delta, e.g. epsilon = omega(d^{-(n-delta)/2}), together with epsilon = omega(d^{-n/4}). The statement as written therefore does not match the proof and should be corrected.","section":"II.F, Theorem 9 statement"}],"minor_comments":[{"comment":"The symbol k is used both for the uniformity parameter in Definition 1 and for the logical qudit number k = log_d K in Theorem 9. This overloaded notation is confusing; please use a different symbol, such as r or k_log, for the logical qudit count.","section":"II.F and Definition 1"},{"comment":"The displayed denominator surrounding the AME(4,2) example is mis-formatted: 1*2^4 + 6*2^0 + 1*2^4 equals 38, not 76, and the bound is 1/76 = (1/2)/38. Please correct the fraction so that the arithmetic is clear.","section":"II.A, Eq. (15)"},{"comment":"Reference [36] lists arXiv:2410.10116 in brackets but arXiv:1609.08172 in the arXiv field, and this number appears again as reference [58]. Please reconcile the reference entries.","section":"References"},{"comment":"The phrase 'given the constraint that epsilon = omega(d^{-n(1-alpha)/2})' in Corollary 1 is inconsistent with the preceding discussion, which also imposes epsilon = omega(d^{-n/4}); please unify the statement, as noted in the major comments.","section":"II.B, Corollary 1"},{"comment":"In Eq. (44), the notation '≃' is used inside a chain of inequalities for -log Prob(fail); please clarify which steps are asymptotic equalities and which are upper or lower bounds, since the direction of the bounds is important for the final depth claim.","section":"II.C, proof of Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The positive construction results (Haar-random approximate uniform states and approximate QECCs, weight-enumerator bounds, and the QIM connection) appear sound and publishable after revision. The main problem is the unsupported no-go claim about shallow random circuits, which is prominent in the abstract and summary; I would ask the authors either to prove a lower bound or to rescope the claim explicitly to the proposed net-based construction. The Corollary 1 constraint and Theorem 9 statement issues are technical but should be fixed in the same revision. No concerns about novelty or citation practices beyond the minor reference inconsistency."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You asked about the arXiv paper by Guo, Shi, Zhou, and Zhao on approximate k-uniform states. I've read the full text. The short version: the core definition and the Haar-random existence results are solid and worth engaging with; the headline claim about shallow random circuits is over-claimed and should be fixed before publication.\n\nWhat is actually new: they give a clean definition of epsilon-approximate k-uniform states in terms of purity, show it is equivalent to a Hilbert-Schmidt closeness condition, and prove local indistinguishability from the maximally mixed state unless many measurements are made. Theorem 2 — a Haar random state is an epsilon-approximate (alpha n)-uniform state with failure probability roughly exp(-d^n epsilon^4) — is a straightforward Levy concentration argument and it checks out. The connection to approximate QECCs (Theorem 5) is also natural and correctly derived: a subspace is an approximate pure QECC iff every pure state in it is an approximate uniform state. The weight-enumerator bounds in Theorems 6 and 7 are plausible and I did not find a gap. The numerical table is illustrative, though I could not reproduce it from the preprint.\n\nThe soft spot is the no-go statement in Section II F. The stress-test note is correct: Eq. (82) upper-bounds the failure probability, and when t is small the bound becomes vacuous. It never lower-bounds failure probability, so it cannot imply that shallow circuits fail. The claim that 'circuit depth has to grow exponentially with k' for linear-rate codes does not follow from the stated inequalities. This is a load-bearing advertised distinction, so it matters. The authors should either prove a genuine lower bound or soften the claim to something like 'the current net-and-concentration argument cannot certify good codes at shallow depth.'\n\nMinor issues: the conversion between design definitions relies on cited lemmas without full re-derivation, and the numerical optimization lacks algorithm details. Neither is a dealbreaker.\n\nOverall, this is a paper I would cite for the definition and the Haar-random construction. It deserves a serious referee: the main positive results are new and likely correct, and the flaws are localized. I would recommend sending it to peer review with a request to revise the no-go section. A reader who cares about approximate entanglement resources, AQECCs, or random-circuit constructions will get real value from this paper.","headline":"A genuinely useful new framework for approximate k-uniform states with a clean Haar-random existence proof, but the advertised no-go for shallow random circuits is not supported and the numerics are not reproducible.","tokens_in":24916,"tokens_out":1596,"would_cite":true,"duration_ms":19322,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P45","81P68"],"pacs":["03.67.-a","03.67.Pp"],"model":"deepseek-v4-flash","headline":"This paper defines epsilon-approximate k-uniform states, proves Haar-random and shallow-circuit constructions, and derives approximate quantum error-correcting codes from them.","keywords":["approximate k-uniform states","quantum error-correcting codes","Haar random states","random quantum circuits","unitary t-designs","quantum information masking","absolutely maximally entangled states","concentration of measure"],"falsifier":"Construct a family of one-dimensional random circuits of depth $o(nK^2)$, with $K = d^{\\Theta(n)}$ and $\\delta = \\Theta(n)$, that produces an $\\epsilon$-approximate pure $((n,K,\\delta))_d$ QECC with $\\epsilon \\to 0$ and high probability; such a family would refute Theorem 9's separation. Alternatively, compute the actual failure probability in Eq. (82) for design orders $t$ below the stated threshold and show it still vanishes, which would break the claimed circuit-depth lower bound.","tokens_in":23950,"feed_emoji":"🎲","tokens_out":8642,"duration_ms":80100,"temperature":0.7,"pith_summary":"This paper introduces $\\epsilon$-approximate $k$-uniform states, pure states whose $k$-body reduced density matrices are nearly maximally mixed, and argues that these relaxed states replace exact $k$-uniform states in practice. Exact $k$-uniform states are often nonexistent or experimentally inaccessible, while approximate ones are locally indistinguishable from the exact ideal unless a massive number of measurements are made. The paper proves that Haar random states are $\\epsilon$-approximate $k$-uniform with probability close to one, and that low-depth random circuits achieve the same under broad parameter choices. It defines approximate quantum error-correcting codes through the same $\\epsilon$, shows random subspaces yield codes with linear rate and distance, and argues shallow random circuits cannot match that performance. The results make $k$-uniform resources available under noise and connect them to approximate quantum information masking.","feed_headline":"Random states yield near-perfect k-uniform entanglement","feed_subtitle":"Haar random states and shallow circuits generate these states, opening approximate quantum error-correcting codes.","key_machinery":"The load-bearing object is the purity-based definition of approximate $k$-uniformity: a state is $\\epsilon$-approximate $k$-uniform when every $k$-body reduced density matrix has purity at most $1/d^k + \\epsilon^2$, equivalently Hilbert-Schmidt distance at most $\\epsilon$ from the maximally mixed state. The proof machinery combines concentration of measure (Levy's lemma) applied to the reduced purity function, whose Lipschitz constant is bounded by $4$, with an $\\epsilon$-net argument that lifts the single-state bound to an entire $K$-dimensional subspace; the circuit construction passes through approximate unitary $t$-designs and a monomial-based deviation bound. Weight enumerators provide the bridge from approximate uniformity to approximate QECCs, and shadow inequalities give non-existence thresholds for approximate AME states.","core_discovery":"The paper's central claim is that relaxing 'k-uniform' to '$\\epsilon$-approximate' turns a fragile, often nonexistent ideal into an abundant resource. Theorem 2 and Corollary 1 state that a Haar random state is an $\\epsilon$-approximate $(\\alpha n)$-uniform state, with the negative logarithm of the failure probability asymptotically at least $d^n \\epsilon^4 / (72\\pi^3 \\log 2)$, provided $\\epsilon = \\omega(d^{-n(1-\\alpha)/2})$; the failure probability vanishes quickly when $\\epsilon = \\omega(d^{-n/4})$. Theorem 5 makes $\\epsilon$-approximate pure $((n,K,\\delta))_d$ QECCs equivalent to code subspaces whose every state is an $\\epsilon$-approximate $(\\delta-1)$-uniform state. Theorem 8 shows that a random $K$-dimensional subspace is such a code with high probability whenever $K \\ll d^n \\epsilon^4$, giving linear rate and linear distance, while Theorem 9 shows that a one-dimensional random circuit requires depth $O(nK^2\\, \\mathrm{poly}(k))$, so shallow circuits cannot produce constant-rate, linear-distance approximate codes.","pith_inferences":["One consequence the authors leave implicit is that unresolved existence questions for exact AME states become less practically relevant: if the abundance results hold, approximate AME states would inherit most operational value, and the numerical data suggest such states exist in many dimensions.","The separation between Haar-random and shallow-circuit approximate QECCs points to a sharp resource distinction: constant-order approximate $t$-designs suffice for uniform states but not for codes, a distinction that could be probed experimentally by measuring code distance versus circuit depth.","The no-go strength rests on the technical gap in Eq. (82): a tighter analysis of the $\\epsilon$-net bound could either confirm linear-depth-in-$K$ as fundamental or show that much shallower circuits reach good codes.","Through the approximate QIM connection, any good approximate code yields approximate masking, which may lead to noise-tolerant secret-sharing protocols; this application is suggested by the paper but not developed."],"forward_implications":["Approximate AME(4,2) states exist with $\\epsilon \\approx 0.2887$ even though exact AME(4,2) states do not, so the relaxation opens parameter regimes that are closed exactly.","A Haar random state on $n$ qudits is an $\\epsilon$-approximate $(\\alpha n)$-uniform state with $\\log$ failure probability at least $\\Omega(d^n \\epsilon^4)$ under the stated constraints, making such states essentially free in large systems.","A random $K$-dimensional subspace is an $\\epsilon$-approximate pure $((n,K,\\delta))_d$ QECC with high probability whenever $K \\ll d^n \\epsilon^4$, yielding codes with linear rate and linear distance.","Approximate $k$-uniform states are locally indistinguishable from maximally mixed states unless on the order of $2/(d^k \\epsilon^2)$ measurements are performed.","Low-depth random circuits generate $\\epsilon$-approximate $k$-uniform states in linear depth, but the same circuit model cannot produce good approximate QECCs with constant rate and linear distance in shallow depth."],"supporting_citations":[{"why":"Supplies Levy's lemma, the Lipschitz bound for purity, and the epsilon-net machinery used in Theorems 2 and 8.","marker":"[28]"},{"why":"Provides the low-depth random-circuit construction of approximate unitary t-designs (Theorem 3) that underlies the circuit results.","marker":"[27]"},{"why":"Supplies the monomial-based deviation bound (Lemma 6) for approximate t-designs used in Theorems 4 and 9.","marker":"[43]"},{"why":"Gives the shadow inequalities behind the non-existence threshold for approximate AME states in Theorem 1.","marker":"[39]"},{"why":"Supplies the weight-enumerator framework and the relation in Eq. (56) used to bound code performance in Theorems 6 and 7.","marker":"[18]"},{"why":"Provides the small epsilon-net cardinality bound (Lemma 7) used to lift single-state concentration to subspaces.","marker":"[54]"},{"why":"Establishes the exact QECC-to-k-uniform and k-uniform-to-QIM connections that the paper generalizes to the approximate setting.","marker":"[4]"},{"why":"Provides the Haar-average formula for subsystem purity used in Lemma 3.","marker":"[41]"}],"fun_headline_variants":["Approximate k-uniform states are abundant and practical","Haar random states yield practical approximate k-uniformity","Relaxing k-uniformity unlocks quantum error-correcting codes","Shallow circuits build approximate k-uniform states, not codes","Approximate k-uniform states: near-perfect, locally indistinguishable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The no-go claim that shallow random circuits cannot build good approximate codes assumes the $\\epsilon$-net failure bound in Eq. (82) is tight enough to force circuit depth to grow with the logical dimension $K$; the proof only rules out the regime where the design order $t$ is as large as $K$, not every smaller $t$.","fun_headline_variants_meta":{"raw":{"variants":["Approximate k-uniform states are abundant and practical","Haar random states yield practical approximate k-uniformity","Relaxing k-uniformity unlocks quantum error-correcting codes","Shallow circuits build approximate k-uniform states, not codes","Approximate k-uniform states: near-perfect, locally indistinguishable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000712,"raw_usage":{"total_tokens":3222,"prompt_tokens":983,"completion_tokens":2239,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":2158}},"tokens_in":599,"tokens_out":2239,"duration_ms":16020,"temperature":1.0,"reasoning_tokens":2158,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:04:19.208140+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a family of one-dimensional random circuits of depth $o(nK^2)$, with $K = d^{\\Theta(n)}$ and $\\delta = \\Theta(n)$, that produces an $\\epsilon$-approximate pure $((n,K,\\delta))_d$ QECC with $\\epsilon \\to 0$ and high probability; such a family would refute Theorem 9's separation. Alternatively, compute the actual failure probability in Eq. (82) for design orders $t$ below the stated threshold and show it still vanishes, which would break the claimed circuit-depth lower bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Levy's lemma, the Lipschitz bound for purity, and the epsilon-net machinery used in Theorems 2 and 8."},{"cited_title":"Huber, C","cited_arxiv_id":null,"evidence_quote":"Provides the low-depth random-circuit construction of approximate unitary t-designs (Theorem 3) that underlies the circuit results."},{"cited_title":"Vedral, M","cited_arxiv_id":null,"evidence_quote":"Supplies the monomial-based deviation bound (Lemma 6) for approximate t-designs used in Theorems 4 and 9."},{"cited_title":"Goyeneche, D","cited_arxiv_id":null,"evidence_quote":"Supplies the weight-enumerator framework and the relation in Eq. (56) used to bound code performance in Theorems 6 and 7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the small epsilon-net cardinality bound (Lemma 7) used to lift single-state concentration to subspaces."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the exact QECC-to-k-uniform and k-uniform-to-QIM connections that the paper generalizes to the approximate setting."},{"cited_title":"Webb, Quantum Information and Computation 16 (2015)","cited_arxiv_id":null,"evidence_quote":"Provides the Haar-average formula for subsystem purity used in Lemma 3."}],"review_version":1}