{"id":"023f1186-cf6a-42ba-9b2e-c1d53888de2f","arxiv_id":"2608.09912","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A quasipolynomial-time algorithm finds the closest Clifford unitary to an unknown unitary, enabling tomography of unitaries and Hamiltonians with bounded Clifford decomposition size.","lead":"This paper presents algorithms for learning quantum operations that are close to Clifford circuits, using time that scales quasipolynomially with the desired accuracy. It resolves an open problem in quantum process learning and brings a new class of dense-looking Hamiltonians into the efficiently learnable regime.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.1's proof is incomplete: the binary search over unknown opt from Corollary 3.7 cannot yield the claimed opt-ε guarantee, because a guess τ < opt only guarantees τ-ε < opt-ε and a guess τ > opt has no guarantee; the proposed acceptance test does not certify opt-ε.","rationale":"Reading the strongest_claim: Theorem 1.1 is the paper's central result, and its proof is supposed to follow from Corollary 3.7 plus a binary search over τ. I examined that final step closely. The binary search is not a minor presentation issue: as written, it cannot convert Corollary 3.7's promise-based guarantee into the claimed unknown-opt guarantee. Claim 3.6/Corollary 3.7 output fidelity τ-ε when the input is promised to have fidelity at least τ. With unknown opt, no τ is known; if τ < opt the guarantee is weaker than needed, and if τ > opt the premise fails. The paper's assertion that for τ > opt 'the algorithm will fail to find a Clifford with the desired fidelity' is not a proven consequence, and the proposed acceptance test only checks the lower bound τ-ε, not the target opt-ε. The complexity also depends on τ, so an unconstrained search breaks the stated bound. This is an internal gap, independent of whether the cited stabilizer-bootstrapping black box is valid. I therefore focus on this gap rather than on the reader's weakest_assumption, though I partially agree with the reader: the list-decoding guarantee in [CGYZ25] is also load-bearing and should be checked, but it is an external dependency; the binary-search issue is in this paper's own argument. The reader's CONDITIONAL verdict is appropriate: the gap is concrete but plausibly patchable by adding a certified τ-selection procedure (e.g., a tolerant tester) and analyzing its cost. My test asks for exactly that. I do not see a reason to reject the paper outright; the neighbor-graph argument and the extent-based applications are coherent conditional on the cited theorems.","tokens_in":31881,"tokens_out":12637,"duration_ms":114829,"concrete_test":"Provide a complete, formal algorithm that chooses τ without knowing opt and prove it meets the opt-ε guarantee. Concretely: specify the τ sequence, the exact acceptance test (e.g., estimated fidelity threshold) and a proof that the accepted V satisfies |⟨⟨U|V⟩⟩|² ≥ opt-ε with probability ≥1-δ, while keeping all runs at τ ≥ opt - O(ε) or otherwise bounding the total cost by poly(n,(1/ε)^{log(1/ε)}). If the argument requires a separate tolerant tester to locate opt, state it and include its complexity. A decisive negative check: exhibit U with opt=0.8 and run the proposed binary search as written with ε=0.1; if it can terminate with a Clifford of fidelity <0.7, the gap is real.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 concludes: 'The proof of Theorem 1.1 then follows from Corollary 3.7 by binary search over the choice of τ to handle the unknown optimal fidelity opt. In particular, let τ be a guess for opt... If τ > opt, the algorithm will fail to find a Clifford with the desired fidelity. Thus, one can decrease τ until the algorithm returns a Clifford with fidelity at least τ-ε. At this point, opt is known within a multiplicative factor of 2, and a grid search...' This reasoning is not valid as written. Corollary 3.7's guarantee (and Claim 3.6's) is conditional: given fidelity ≥ τ, output has fidelity ≥ τ-ε. If the true opt exceeds τ but is not known, the output is only guaranteed to have fidelity τ-ε, which can be far below opt-ε. If τ > opt, the premise is false, so Corollary 3.7 provides no guarantee; the assertion that the algorithm 'will fail' is unsupported, and when τ-ε < opt the target fidelity is actually achievable, so failure is not forced. Moreover, the proposed acceptance test ('returns a Clifford with fidelity at least τ-ε') can pass for τ much smaller than opt (since τ-ε is then a weaker bar), and the algorithm may terminate with a state whose fidelity is below opt-ε. The complexity of Claim 3.6 is poly(n,(1/(ετ))^{log(1/τ)},log(1/δ)), so any search that runs with small τ would exceed the stated poly(n,(1/ε)^{log(1/ε)}) bound unless τ is chosen with knowledge of opt. Thus Theorem 1.1 is not proved by the provided argument; a certification procedure for identifying a τ close to opt is missing.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies learning of n-qubit unitaries and Hamiltonians that are dense in the Pauli basis but admit concise Clifford decompositions. Its main contribution is a claimed proper agnostic tomography algorithm for Clifford unitaries: given query access to an unknown unitary U with optimal Clifford fidelity opt, the algorithm outputs a Clifford V with fidelity at least opt - ε in time poly(n,(1/ε)^{log(1/ε)},log(1/δ)). The proof proceeds by studying a stabilizer-neighbor graph, using stabilizer bootstrapping [CGYZ25] as a black box, and then rounding a nearby stabilizer state to a maximally entangled stabilizer state. The paper then applies this protocol, together with the bounded-extent tomography framework of [AD26], to obtain algorithms for learning unitaries and Hamiltonians with bounded Clifford extent, and it gives examples of Pauli-dense Clifford-sparse Hamiltonians.","tokens_in":32285,"tokens_out":19397,"duration_ms":164514,"significance":"If correct, the paper resolves an open question on proper agnostic tomography of Clifford unitaries and extends Hamiltonian learning from Pauli-sparse to Pauli-dense but Clifford-structured dynamics. The overall research direction is timely, and the paper contains useful observations: the stabilizer-neighbor graph analysis in Lemma 3.4 is clean, the dependence on [CGYZ25] is explicit, and the appendix gives a concrete exponential separation between Clifford extent and stabilizer extent of a Choi state. However, the central proof of Theorem 1.1 has a load-bearing gap in how it handles the unknown optimal fidelity opt, and the Hamiltonian application depends on a convention for the extent definition that is not pinned down. The gaps appear repairable, but they need to be addressed before the claims can be accepted.","major_comments":[{"comment":"The reduction from Corollary 3.7 to the unknown-opt setting is invalid. Corollary 3.7 is conditional: if the actual Clifford fidelity opt is at least τ, the algorithm outputs V with |⟨⟨U|V⟩⟩|² ≥ τ−ε. If τ > opt, the premise is false and no guarantee applies; the sentence \"If τ > opt, the algorithm will fail to find a Clifford with the desired fidelity\" is unsupported, and when τ−ε < opt the target fidelity τ−ε is actually achievable, so failure is not forced. Conversely, the proposed acceptance test \"returns a Clifford with fidelity at least τ−ε\" can pass for τ much smaller than opt, in which case the output can have fidelity below opt−ε. The complexity in Claim 3.6 is poly(n,(1/(ετ))^{log(1/τ)},log(1/δ)), so any search that runs at a small τ without knowledge of opt exceeds the stated poly(n,(1/ε)^{log(1/ε)}) bound. A grid search over τ∈[ε,1] with maximum estimated fidelity, and treating opt<ε as trivial, would repair the argument, but this repair is not in the manuscript; as written, Theorem 1.1 and Theorem 3.1 are not proved.","section":"Section 3.2"},{"comment":"The proof uses the inequality \"since 2αt ≤ ε/2\" after setting γ=1/2+α with α≤ε/(12 log(1/ε)) and t≤3 log(1/τ). Substituting gives 2αt ≤ (ε/2)·log(1/τ)/log(1/ε), which is only at most ε/2 when τ≥ε. The statements of Claim 3.6 and Corollary 3.7 allow arbitrary τ∈(0,1). If τ<ε the claimed guarantee τ−ε is negative and the problem is vacuous, but then the complexity expression (1/(ετ))^{log(1/τ)} is not the relevant description of the trivial case. The condition ε≤τ should be stated explicitly, or the vacuous regime should be handled separately, because Corollary 3.7 is the main subroutine in the proof of Theorem 1.1.","section":"Claim 3.6"},{"comment":"The Clifford extent in Definition 2.4 is defined as a minimum over decompositions without specifying whether the support must be finite. The proof of Theorem 4.4 bounds ξ_Cliff(exp(−iHt)) by e^{tξ} using the infinite Taylor series in Eqs. (21)–(22); the series has finite ℓ1 norm but infinite support. If Definition 2.4, and the [AD26] theorems used in Corollary 4.3, require finite decompositions, this bound is not a valid extent bound. If infinite ℓ1 decompositions are intended, that convention must be written into Definition 2.4 and the model-class results must be compatible with it. As written, the Hamiltonian learning theorem relies on an unspecified convention, and the proof needs to either allow infinite decompositions or replace the infinite series by a truncated series with an explicit approximation error.","section":"Definition 2.4"}],"minor_comments":[{"comment":"The normalization factor 1/√(2N) in the definition of dist(A,B) is inconsistent with the note that dist(A,B)² = 1 − |⟨⟨A|B⟩⟩| for unitaries and with the later bound ||V−e^{iθ}U(t)||₂ ≤ √2 ε1 in Eq. (23). If ||·||₂ is the normalized Frobenius norm, the factor should be 1/√2, not 1/√(2N).","section":"Definition 2.1"},{"comment":"The normalized Frobenius norm is written as ||A||₂ = sqrt(Tr(A†A)/√N), which has the wrong dimension; the standard definition is sqrt(Tr(A†A)/N). This typo propagates into Definition 2.1 and should be corrected.","section":"Eq. (1)"},{"comment":"The complexity statements use inconsistent notation: for example, Theorem 1.2 writes \"poly(n,(1/ε)^{log(1/ε)},log(1/δ))\" while Theorem 4.4 writes \"poly(n(ξ/ε)^{log(ξ/ε)} log(1/δ))\" without separating commas. The proof of Theorem 4.4 also produces exponents with extra constant factors, so the paper should state that O(1) factors in the exponent are absorbed.","section":"Theorem 1.2"},{"comment":"Algorithm 1 takes a fidelity lower bound τ as input, while Theorem 3.1 promises an output for unknown optimal fidelity opt. The relationship between τ and opt is never specified in the algorithm statement; this is related to the gap in the proof of Theorem 1.1 and should be clarified when the binary-search argument is repaired.","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is plausible and the approach is interesting, but the proof of Theorem 1.1 as written does not establish the claimed guarantee because of the invalid binary-search reduction. The gap appears repairable by a standard grid search with maximum estimated fidelity, so I recommend major revision rather than rejection. The authors should also clarify the support convention in Definition 2.4 and the τ≥ε condition in Claim 3.6; the applications in Section 4 depend on these fixes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The proper quasipolynomial agnostic tomography result for Clifford unitaries is the real thing, and the stabilizer-neighbor graph plus entropy-controlled rounding is a genuinely new technique. Lemma 3.4 is proven cleanly and Claim 3.6's averaging is algebraically sound. The application to Clifford-extent unitaries and Hamiltonians, including exchange interactions that are exponentially dense in the Pauli basis, is a solid extension of the learnability frontier. This deserves a serious referee.\n\nThe soft spot is exactly where the stress-test says: Theorem 1.1's proof as written does not handle unknown opt. Corollary 3.7 is conditional: given promise fidelity at least tau, it outputs at least tau - epsilon. The Section 3.2 paragraph claims a binary search over tau and an acceptance test \"returns a Clifford with fidelity at least tau - epsilon.\" That test can pass when tau is much smaller than opt, and the algorithm can stop with fidelity below opt - epsilon. When tau > opt there is no guarantee at all, and the claim that the algorithm \"will fail\" is unsupported. Also Claim 3.6's complexity has (1/(epsilon*tau))^{log(1/tau)}; if tau is small the stated poly(n,(1/epsilon)^{log(1/epsilon)}) bound breaks. This is a gap in the proof, not a fatal flaw: one can fix it with a proper certification procedure, e.g., run the protocol for a geometric sequence of tau values, estimate the output fidelity against the true unitary, and take the best certified candidate. But as written the main theorem is not proved.\n\nThe Hamiltonian part has a smaller issue: Theorem 4.4 bounds the Clifford extent of exp(-iHt) using the infinite Taylor series, while Definition 2.4 defines extent via finite decompositions. Need an explicit truncation to finite sums or an approximate-extent lemma. Corollary 4.5 is garbled --- \"O(beta^4 kappa kappa^4 / epsilon^4)\" and \"poly(n(beta kappa kappa/epsilon)^kappa ...)\" look like typos; the proof sketch using Theorem 2.7 is reasonable, but the statement should be cleaned. Dependence on [AD26] is by a same-author group, but not circular: Corollaries 4.2 and 4.3 would stand if replaced by any model-class theorem with those guarantees.\n\nBottom line: the core idea is sound, the flaws are presentation and a missing argument in the opt-handling. Patchable. Send to peer review with a request to fix those points; after that it is a solid paper for the quantum learning theory audience.","headline":"New proper quasipolynomial Clifford agnostic tomography with a genuinely new neighbor-graph technique, but the proof as written leaves the unknown-opt handling unjustified; patchable and worth refereeing.","tokens_in":32813,"tokens_out":3200,"would_cite":true,"duration_ms":29378,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q32"],"pacs":["03.67.Lx","03.67.-a"],"model":"deepseek-v4-flash","headline":"An unknown unitary's closest Clifford can be learned in quasipolynomial time, within any desired accuracy.","keywords":["agnostic tomography","Clifford unitaries","stabilizer bootstrapping","Clifford extent","Hamiltonian learning","quantum process tomography","stabilizer-neighbor graph","Choi state"],"falsifier":"Run the stabilizer-bootstrapping list-decoding routine on a $2n$-qubit state with stabilizer fidelity $\\tau = 0.1$ using $\\gamma = 1/2 + 10^{-3}/(12\\log(10^3))$ and measure how often a known $\\gamma$-approximate local maximizer appears in the output list: a rate below $((\\gamma-1/2)\\tau)^{O(\\log(1/\\tau))}$ would falsify the black-box guarantee on which Theorem 1.1's proof rests.","tokens_in":31701,"feed_emoji":"⚛️","tokens_out":15332,"duration_ms":114123,"temperature":0.7,"pith_summary":"This paper asks whether the Clifford structure of an unknown quantum process can be extracted even when the process is not itself Clifford, and answers that it can. Given query access to any $n$-qubit unitary $U$, an algorithm outputs a Clifford unitary $V$ whose fidelity with $U$ is within $\\varepsilon$ of the best possible Clifford, using $\\mathrm{poly}(n,(1/\\varepsilon)^{\\log(1/\\varepsilon)},\\log(1/\\delta))$ queries and time. This settles, in quasipolynomial time, the open problem of proper agnostic tomography of the Clifford group. Building on this, the paper shows that unitaries and Hamiltonians with concise decompositions over Cliffords—even ones exponentially dense in the Pauli basis—can be learned efficiently. The significance is a new learnable regime for quantum dynamics: structure measured by Clifford extent rather than Pauli sparsity.","feed_headline":"Learn a nearly-closest Clifford to any gate in quasipolynomial time","feed_subtitle":"Dense-in-Pauli dynamics with concise Clifford decompositions are learnable too, with the same technique.","key_machinery":"The stabilizer-neighbor graph: vertices are stabilizer states on $2n$ qubits, with an edge between any two states whose fidelity is exactly $1/2$. The argument uses two properties of this graph—that a fidelity-increasing path from a maximally entangled state reaches a $\\gamma$-approximate local maximizer in at most $O(\\log(1/\\mathrm{opt}))$ steps, and that each step changes entanglement entropy across the Choi cut by at most one (Lemma 3.4). These properties let the algorithm trade fidelity gained along the path (a factor $\\gamma^{-t}$) against fidelity lost in rounding the endpoint to a maximally entangled stabilizer state (a factor $2^t$), with the tradeoff tuned by $\\gamma$ so the net loss is $\\varepsilon$. The graph thus converts a coarse list-decoding guarantee from stabilizer bootstrapping into a strong agnostic learner for Clifford unitaries.","core_discovery":"The central discovery is a path-counting argument on the stabilizer-neighbor graph, whose vertices are $2n$-qubit stabilizer states and whose edges join states of fidelity $1/2$. Starting from any Clifford Choi state $|C\\rangle\\rangle$ with fidelity $\\mathrm{opt}$ to the unknown Choi state $|U\\rangle\\rangle$, the algorithm follows edges that increase fidelity by a factor of at least $1/\\gamma$ until it reaches a $\\gamma$-approximate local maximizer, which stabilizer bootstrapping is guaranteed to output with nonnegligible probability. Because each edge changes entanglement entropy across the Choi cut by at most one, a state reached in $t$ steps is a superposition of at most $t$ maximally entangled stabilizer states, so it can be rounded back to a Clifford Choi state at a cost of at most $2^t$ in fidelity. Choosing $\\gamma = 1/2 + \\varepsilon/(12\\log(1/\\varepsilon))$ balances the fidelity gained along the path against the loss in rounding, yielding an output Clifford with fidelity at least $\\mathrm{opt} - \\varepsilon$. The same protocol, composed with a decomposition algorithm for bounded-extent states, learns unitaries and Hamiltonians of bounded Clifford extent.","pith_inferences":["The stabilizer-neighbor template is general: any state class whose neighbor graph changes the relevant resource by $O(1)$ per edge should admit a strong agnostic learner by the same fidelity-gain/loss-rounding tradeoff; fermionic Gaussian states and low levels of the Clifford hierarchy are natural next targets.","Because the Hamiltonian learner requires short evolution times $t = O(\\varepsilon/\\xi^2)$, the result does not transfer to long-time evolution; the paper's own open question 3 flags this as a real boundary, and a long-time variant would have to avoid the Taylor truncation entirely.","Appendix B's exponential separation between Clifford extent of $U$ and stabilizer extent of its Choi state means the two Hamiltonian-learning algorithms are complementary, not redundant; a practical learner could compute both bounds and take the cheaper one, a hybrid the paper does not explicitly propose.","Corollary 4.2 controls the residual state only through its Clifford fidelity, not its norm; strengthening that residual guarantee to a norm bound would make the bounded-extent unitary tomography proper, which the paper lists as open future work."],"forward_implications":["Proper agnostic tomography of Clifford unitaries is settled in quasipolynomial time, closing the open question left by the improper agnostic baseline and yielding a quasipolynomial-time tolerant tester for Clifford unitaries with $1/\\mathrm{poly}(n)$ additive gap.","Unitaries with Clifford extent at most $\\xi$ can be learned to normalized Frobenius error $\\varepsilon$ with $\\mathrm{poly}(n,(\\xi/\\varepsilon)^{\\log(\\xi/\\varepsilon)},\\log(1/\\delta))$ queries and time, even when they are exponentially dense in the Pauli basis.","Hamiltonians with Clifford extent at most $\\xi$ and $\\mathrm{Tr}(H)=0$ can be learned from short-time evolution $\\exp(-iHt)$ with the same quasipolynomial scaling, extending Hamiltonian learning beyond Pauli-sparse classes to Hamiltonians dense in the Pauli basis.","Every unitary's Choi state admits a structured decomposition into $O(1/\\varepsilon^2)$ Clifford Choi states plus a residual of low Clifford fidelity, providing a classically simulable surrogate that can be compiled and used for circuit verification and error mitigation.","The learned Clifford is a genuine Clifford circuit, so the output can be directly simulated, compared with an intended circuit, and used as a surrogate in error-mitigation schemes."],"supporting_citations":[{"why":"Black box for the whole construction: its stabilizer-bootstrapping algorithm and list-decoding guarantee (Theorems 2.8 and 2.10) are what actually find the γ-approximate local maximizer.","marker":"[CGYZ25]"},{"why":"Provides the normal form of bipartite stabilizer states, used to round a low-entanglement stabilizer state back to a maximally entangled Clifford Choi state and to compute the local Cliffords.","marker":"[FCY+04]"},{"why":"Its decomposition theorem for bounded-extent states (Theorems 2.12 and 2.13) converts the Clifford agnostic learner into the tomography protocols for unitaries and Hamiltonians.","marker":"[AD26]"},{"why":"Defined the open problem of proper agnostic process tomography and supplied the improper baseline that Theorem 1.1 improves upon.","marker":"[WLKD25]"},{"why":"Supplies the bound that a stabilizer state with fidelity at least opt to the Choi state has entanglement entropy at least n − O(log(1/opt)), which anchors the weak protocol in Appendix A.","marker":"[HBvD+26]"},{"why":"Gives the stabilizer-extent bound (Theorem 2.7) used in Corollary 4.5 to turn bounded Clifford rank of H into a bounded-extent input for the Hamiltonian learner.","marker":"[KS26]"},{"why":"Defines Clifford extent, the complexity measure at the center of Theorem 1.2, and motivates the model via classical simulation of low-extent circuits.","marker":"[BG16]"}],"fun_headline_variants":["Learn dense-in-Pauli Cliffords in quasipolynomial time","Path-counting on stabilizer graph learns Clifford-structured Hamiltonians","Agnostic Clifford tomography via stabilizer-neighbor paths","Quasipolynomial learning for dense Pauli operators with Clifford structure","Clifford-structured unitaries learned even when Pauli-dense"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument relies on a black-box promise about the stabilizer-state search subroutine: that it outputs every near-optimal stabilizer state with the promised probability, even when the target fidelity is as low as $\\mathrm{opt} - \\varepsilon$ and the local-improvement parameter is only a hair above $1/2$; if that promise fails at those parameters, Theorem 1.1 has no proof.","fun_headline_variants_meta":{"raw":{"variants":["Learn dense-in-Pauli Cliffords in quasipolynomial time","Path-counting on stabilizer graph learns Clifford-structured Hamiltonians","Agnostic Clifford tomography via stabilizer-neighbor paths","Quasipolynomial learning for dense Pauli operators with Clifford structure","Clifford-structured unitaries learned even when Pauli-dense"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001022,"raw_usage":{"total_tokens":4362,"prompt_tokens":1050,"completion_tokens":3312,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":666,"completion_tokens_details":{"reasoning_tokens":3222}},"tokens_in":666,"tokens_out":3312,"duration_ms":20428,"temperature":1.0,"reasoning_tokens":3222,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:31:16.093596+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the stabilizer-bootstrapping list-decoding routine on a $2n$-qubit state with stabilizer fidelity $\\tau = 0.1$ using $\\gamma = 1/2 + 10^{-3}/(12\\log(10^3))$ and measure how often a known $\\gamma$-approximate local maximizer appears in the output list: a rate below $((\\gamma-1/2)\\tau)^{O(\\log(1/\\tau))}$ would falsify the black-box guarantee on which Theorem 1.1's proof rests.","supporting_citations":[],"review_version":1}