{"id":"8e42ebfe-37a5-40b5-9d6d-cf46ad9a62b2","arxiv_id":"2504.15356","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"An efficient learning algorithm reconstructs fermionic circuits built from Gaussian unitaries plus a constant number of parity-preserving non-Gaussian gates, up to small diamond-norm error.","lead":"This paper presents a polynomial-time algorithm for learning an n-mode fermionic quantum circuit that contains a constant number of non-Gaussian gates, using black-box access to the circuit. The learned description approximates the original unitary in diamond distance, which matters for verifying and benchmarking fermionic quantum devices.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Lemma 2 and the SVD-based decoupling argument withstand scrutiny, and the central claim is coherent.","rationale":"The reader's weakest_assumption identifies Lemma 2 as the load-bearing bridge from the circuit promise to the tomography construction, and I agree that this is the most important place to scrutinize. However, on close inspection the adapted proof in Appendix A is sound: the orthogonal matrix O_aux is explicitly constructed to map the span of the transformed generator vectors into the first M coordinates, the determinant-adjustment step preserves the required orthogonality condition for q > M, and the resulting u_t is generated by even-weight Majorana strings supported only on [M]. The singular-value structure of c^(1) then follows as stated in Lemma 4, and Lemma 5 correctly propagates the tomography error through the SVD. The rest of the chain, including Pauli decoupling and reduced-channel approximation, is internally consistent. I found no internal inconsistency, no unsupported parameter dependence, and no step that requires an unreasonable hidden assumption. The minor indexing artifact in Lemma 6 is not load-bearing and is easy to repair. Since the central claim survives scrutiny, the appropriate verdict remains ACCEPT, matching the reader's ACCEPT with no adjustment.","tokens_in":39421,"tokens_out":52578,"duration_ms":488177,"concrete_test":"Run a numerical check of Lemma 2's consequence: for n = 6, t = 2, kappa = 4 (M = 8), generate random SO(2n) Gaussians G0, G1, G2 and random quartic gates K1, K2, form Ut = G2 K2 G1 K1 G0, compute c^(1)_jk = 2^{-n} tr[Ut^dagger gamma_k Ut gamma_j], and verify that at least 2n - M = 4 singular values are equal to 1 to numerical precision; repeat with O(2n) Gaussians and the m = 4 qubit corrections. If the unit-singular-value count fails, Lemma 2 is the source.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After a careful pass over the main argument, I do not find a load-bearing flaw. The central claim rests on Lemma 2, the Gaussian-dressing decomposition adapted from Ref. [17], and I checked the adapted proof in Appendix A: the construction of O_aux maps the span of the transformed generators {v_j} into the first M coordinates, the SO(2n) modification preserves the condition for q > M, and the resulting u_t is generated by even-weight strings supported on [M]. Consequently c^(1) has at least 2n - M unit singular values (Lemma 4), and Lemma 5's SVD construction robustly yields W_t satisfying the Majorana decoupling condition. The subsequent Pauli-decoupling lemmas for both implementations and the reduced-channel/Choi-state learning steps are internally consistent, with error propagation through Lemmas 9, 20, 22, and 23. The only minor issue I noted is a slightly conservative index (i > m + 1 in Lemma 6 rather than i > m), but the same argument covers i = m + 1 because even-weight strings on [M] commute with the single-qubit Paulis on qubit m + 1; this does not affect the theorem. I therefore cannot identify a concern that would change the reader's ACCEPT verdict.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of learning an n-mode fermionic unitary U_t promised to have the form U_t = G_t K_t ... G_1 K_1 G_0, where each G_i is a fermionic Gaussian unitary, each K_i is a parity-preserving non-Gaussian gate generated by an even-weight Majorana product of constant weight κ, and t is constant. The main result (Theorem 1) is an algorithm that, given black-box access to U_t, outputs a classical description of a quantum channel U_t^(ℓ) such that D⋄(U_t^(ℓ), U_t) ≤ ε, using O(poly(n, ε^{-1}, log δ^{-1})) queries and classical processing time, with probability at least 1−δ. The algorithm first constructs the one-body fermionic correlation matrix c^(1) by shadow tomography, performs a singular-value decomposition to obtain Gaussian unitaries G_a and G_b so that W_t = G_a† U_t G_b† approximately commutes with all but M = κt Majorana operators, and then learns the constant-size reduced quantum channel via Choi-state shadow tomography and Stinespring dilation. The result is established for both the fermionic implementation (Gaussian gates in SO(2n), parity-preserving inputs) and the qubit implementation (Gaussian gates in O(2n)). A side result (Lemma 13) claims that certain unitaries with two non-Gaussian gates lie outside every finite level of the matchgate hierarchy.","tokens_in":39635,"tokens_out":30875,"duration_ms":268018,"significance":"If the claims hold, the paper solves an open problem from Ref. [17], extending efficient learnability of fermionic Gaussian states with a constant number of non-Gaussian gates to learnability of the corresponding unitaries, in both fermionic and qubit implementations. The proof is constructive and unusually detailed: Lemma 2 supplies the Gaussian-dressing decomposition, Lemma 5 provides a singular-value perturbation bound for the decoupling step, Lemmas 6 and 18 give Pauli-decoupling statements, Lemma 9 bounds the reduced-channel approximation, and Lemma 20 gives a CPTP projection guarantee for learned Choi states. The algorithm is explicit (Algorithms 1 and 2), with sample-complexity estimates for the shadow-tomography steps. The matchgate-hierarchy result, if corrected as noted below, is a valuable complementary contribution.","major_comments":[],"minor_comments":[{"comment":"The quantity m = M/2 is not well-defined when M = κt is odd. Since the non-Gaussian gates have even weight, the support can always be placed on an even number of Majorana modes, and the statement should define m = ceil(M/2) or explicitly replace M by an even upper bound such as M' = 2⌊κt/2⌋. The subsequent ancilla counts (2m+1 and 2m) remain constant under this change, so the theorem is unaffected, but the present wording is ill-defined for odd κt.","section":"Theorem 1 and Section III"},{"comment":"Lemma 6 states the Pauli-decoupling bound for i > m+1, but the proof in Appendix D establishes the stronger statement for i > m, which is the condition needed by Lemma 9 and the final guarantees in Lemmas 22 and 23. The statement should be strengthened to i > m, or the proof should be adjusted to the weaker statement and the later arguments should be modified accordingly; as written, the lemma is weaker than the proof.","section":"Lemma 6 and its use in Lemma 9"},{"comment":"The claim that U_t = K G(θ) K with θ = π/p and p an odd integer lies outside every finite level of the matchgate hierarchy is false for p = 1, because then sin(2^j θ) = 0 for all j ≥ 1 and F_j reduces to γ_2, which is Gaussian. The statement should require p odd with p > 1, or the proof should treat p = 1 separately.","section":"Lemma 13"},{"comment":"There is a typo in the matchgate matrix: the (4,4) entry should be A22, not A21. In addition, the stated condition det(A) = det(B) = ±1 should presumably be det(A) = det(B), as is standard for matchgates.","section":"Equation (9)"},{"comment":"The notation \"input parameters (ϵ2, δ/2)\" is easily misread as ε·2 rather than ε^2. Since the final bound goes through only if Algorithm 1 is run with accuracy ε^2 (because Lemma 5 gives ε0 ≤ T1(n)∥E^(1)∥^{1/2}), the text should be clarified, e.g., by writing (ε^2, δ/2) explicitly.","section":"Proofs of Lemmas 22 and 23"}],"recommendation":"minor_revision","confidential_remarks":"The central result is sound and the manuscript is well within the scope of the journal. The issues I identified are local and easily fixed: a well-definedness issue in m = M/2, a statement/proof mismatch in Lemma 6, a small counterexample in Lemma 13, and a few typos. I also note that the \"Note added\" acknowledges a related independent paper [38] that solves the qubit-implementation case; the present paper's fermionic-implementation result and its different technical route still constitute a meaningful contribution. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read on arXiv:2504.15356. It solves a real open problem—turning the state-learning result of Mele and Herasymenko into unitary learning for fermionic circuits with a constant number of non-Gaussian gates—and the main proof survives a careful pass. The only caveat worth flagging is that the qubit-implementation half overlaps with a concurrent paper (Ref [38]), which the authors themselves disclose in a note added.\n\nThe construction is genuinely good. The two-step strategy is to learn approximate Gaussian dressings that confine the circuit to a constant number of Majorana modes, then learn the remaining constant-size channel via shadow tomography of Pauli observables and Choi-state projection. The key lemmas—Lemma 2's decomposition, Lemma 5's singular-value perturbation, the Majorana and Pauli decoupling lemmas (6 and 18), Lemma 9's reduced-channel approximation, and Lemma 20's CPTP projection—are all supplied with proofs, and the error propagation is explicit. I agree with the stress-test note that there is no load-bearing flaw. The matchgate hierarchy separation in Lemma 13 is a nice extra.\n\nSoft spots are minor. The proof leans on external shadow tomography sample-complexity results, so it's long and not machine-checked; that's normal for this subfield but means a careful referee is needed. Lemma 2 is the bridge between the circuit promise and the constant-size structure, and its proof in Appendix A is the right place to focus scrutiny. There's a slightly conservative index in Lemma 6 (i > m+1 rather than i > m), but the same argument covers the omitted case, so it doesn't affect Theorem 1. The significance is moderate: it's a valuable contribution to fermionic quantum information and benchmarking, not a paradigm shift.\n\nThe paper is aimed at quantum learning theorists and people studying fermionic or matchgate circuits. I'd bring it to a reading group and cite it if I worked in that area. It deserves a serious peer review; with minor revisions (tightening the exposition and fixing the small index point) it should be accepted.","headline":"Closes a real open problem with a careful constructive proof; the qubit-case overlap with a concurrent paper is the only caveat.","tokens_in":40166,"tokens_out":3095,"would_cite":true,"duration_ms":28772,"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":"A fermionic circuit built from Gaussian gates plus a constant number of non-Gaussian gates can be learned efficiently from black-box queries, in both fermionic and qubit implementations.","keywords":["fermionic Gaussian unitaries","non-Gaussian gates","quantum circuit learning","shadow tomography","Majorana operators","matchgate hierarchy","diamond distance","Jordan-Wigner transformation"],"falsifier":"Take a parity-preserving n-mode circuit with two non-Gaussian gates each of the promised form (a single even-weight Majorana exponential, weight at most κ) and compute the matrix c^(1) of Eq. (17); if it does not have at least 2n−κt singular values equal to 1 up to the tomography precision, then Lemma 2 fails for a circuit inside the promised class and the algorithm's SVD step cannot succeed.","tokens_in":1769,"feed_emoji":"⚛️","tokens_out":2534,"duration_ms":79976,"temperature":0.7,"pith_summary":"The paper proves that an unknown n-mode fermionic circuit containing t parity-preserving non-Gaussian gates, where t and the gate weight κ are constants, can be learned from finitely many black-box queries in time polynomial in n and 1/ε, producing a channel within ε in diamond distance with high probability. This matters because such circuits are universal building blocks for fermionic quantum computation, and no previous algorithm could learn the unitary itself; only the output states were known to be learnable. The argument works by showing the promised circuit can be rewritten, up to Gaussian transformations, so that all non-Gaussian action is confined to a constant number of Majorana operators, which are then learned by shadow tomography. The same guarantee covers circuits implemented on qubits through the Jordan-Wigner mapping.","feed_headline":"Fermionic circuits with few non-Gaussian gates become learnable","feed_subtitle":"Polynomial-time algorithm learns the whole unitary, not just its output states, to small diamond error.","key_machinery":"The load-bearing object is the decomposition U_t = G_A u_t G_B (Lemma 2): for any circuit of the promised form, Gaussian unitaries G_A and G_B exist so that u_t is generated by even-weight Majorana strings supported only on the first M = κt Majorana operators. The algorithm's first stage learns the matrix c^(1)_{jk} = (1/d) tr[U_t^† γ_k U_t γ_j] by shadow tomography, and its singular-value decomposition gives approximate Gaussian decouplers G_a, G_b such that W_t = G_a^† U_t G_b^† almost commutes with γ_i for i > M. This Majorana decoupling localizes W_t (or its transformed version for qubits) to m = M/2 modes, where it is learned as a reduced quantum channel via Choi-state shadow tomography, projected onto a valid completely positive trace-preserving map, and realized by a Stinespring dilation V_S; the final description is $U_t^{{(ℓ)}}$ = G_a V_S G_b.","core_discovery":"The central discovery is Theorem 1: for a unitary U_t promised to have the form U_t = G_t K_t ... G_1 K_1 G_0, with t constant and each non-Gaussian K_i an exponential of an even-weight Majorana product of constant weight κ, there is a learning algorithm that accesses U_t only O(poly(n, $ε^{{-1}}$, log $δ^{{-1}}$)) times, uses the same order of classical processing time, and outputs a description of a quantum channel $U_t^{{(ℓ)}}$ with D⋄($U_t^{{(ℓ)}}$, U_t) ≤ ε and success probability at least 1−δ. The same result holds when the unitary is implemented on qubits via matchgates plus X_1. The authors also show that a simple two-non-Gaussian-gate example lies outside every finite level of the matchgate hierarchy, so the new algorithm covers a class that previously known hierarchy-based learning methods cannot.","pith_inferences":["The same strategy suggests a template for learning other unitaries with a few non-Gaussian resources: learn the low-weight response matrix, find decouplers via SVD, reduce to a constant-size core, then learn the core by tomography. If this generalizes, constant-non-Gaussian learning is not a fermionic accident.","The singular-value test on c^(1) gives a natural property-testing primitive: an unknown unitary can be certified to be close to this class by checking that 2n−M singular values of the learned matrix are close to 1, without running the full learning algorithm.","Because the output is a channel that must be dilated with 2m+1 ancillary modes or 2m qubits, the current guarantee is sample-efficient but not ancilla-optimal; reducing the dilation overhead is a direct engineering target."],"forward_implications":["Fermionic circuits of the promised form become efficiently benchmarkable and verifiable from black-box queries, even though the gate decomposition is unknown.","The same learning guarantees transfer to qubit implementations, so experiments on qubit chains using the Jordan-Wigner mapping can certify such unitaries.","The class of circuits considered complements known classical simulation algorithms: these circuits are simulable, and now also learnable without knowing their internal structure.","Because a two-non-Gaussian-gate example lies outside every finite matchgate-hierarchy level, the new decoupling approach is not subsumed by previous hierarchy-based learning algorithms.","The learned channel description can be implemented with only a constant number of ancillas: 2m+1 fermionic modes or 2m qubits."],"supporting_citations":[{"why":"Supplies the decomposition lemma (Lemma 2) and the state-learning predecessor; the load-bearing promise that U_t = G_A u_t G_B with u_t supported on the first M Majorana modes.","marker":"[17]"},{"why":"Provides the fermionic Gaussian unitary ensemble shadow tomography used in Algorithm 1 to estimate c^(1) efficiently.","marker":"[26]"},{"why":"Establishes the reduced-channel approximation (Pauli decoupling implies diamond-distance closeness) used to localize W_t to m modes.","marker":"[8]"},{"why":"Gives the pseudo-Choi state construction used to express the coefficients c_{xk} as expectation values of measurable observables.","marker":"[25]"},{"why":"Supplies the local Clifford shadow tomography bound used in Algorithm 2 to estimate the matrix f_{αβ} and reconstruct the Choi state.","marker":"[27]"},{"why":"Supplies the analytical CPTP projection of learned Choi states used to turn J(Ê) into a valid channel.","marker":"[32]"},{"why":"Defines the matchgate hierarchy and its learning algorithm, the comparison class the paper shows its two-non-Gaussian example escapes.","marker":"[33]"},{"why":"Provides Weyl's singular-value perturbation theorem, used to control the error of the learned singular values in Lemma 4.","marker":"[39]"}],"fun_headline_variants":["Constant non-Gaussian gates make fermionic circuits learnable","Learn fermionic unitaries with few non-Gaussian gates in polynomial time","Efficient learning for fermionic circuits with constant non-Gaussian gates","Few non-Gaussian gates? Fermionic circuits become learnable","Polynomial-time learning of fermionic unitaries with few non-Gaussian gates"],"cache_read_input_tokens":42368,"weakest_assumption_plain":"The algorithm's success presupposes that every circuit of the promised form can be rewritten, with Gaussian unitaries on both sides, so that the remaining unitary acts only on the first κt Majorana operators—if any promised circuit escapes this normal form, the learning procedure cannot even start.","fun_headline_variants_meta":{"raw":{"variants":["Constant non-Gaussian gates make fermionic circuits learnable","Learn fermionic unitaries with few non-Gaussian gates in polynomial time","Efficient learning for fermionic circuits with constant non-Gaussian gates","Few non-Gaussian gates? Fermionic circuits become learnable","Polynomial-time learning of fermionic unitaries with few non-Gaussian gates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001002,"raw_usage":{"total_tokens":4201,"prompt_tokens":866,"completion_tokens":3335,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":3244}},"tokens_in":482,"tokens_out":3335,"duration_ms":21941,"temperature":1.0,"reasoning_tokens":3244,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:30:03.460953+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a parity-preserving n-mode circuit with two non-Gaussian gates each of the promised form (a single even-weight Majorana exponential, weight at most κ) and compute the matrix c^(1) of Eq. (17); if it does not have at least 2n−κt singular values equal to 1 up to the tomography precision, then Lemma 2 fails for a circuit inside the promised class and the algorithm's SVD step cannot succeed.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the decomposition lemma (Lemma 2) and the state-learning predecessor; the load-bearing promise that U_t = G_A u_t G_B with u_t supported on the first M Majorana modes."},{"cited_title":"Huang, Y","cited_arxiv_id":null,"evidence_quote":"Establishes the reduced-channel approximation (Pauli decoupling implies diamond-distance closeness) used to localize W_t to m modes."},{"cited_title":"Surawy-Stepney, J","cited_arxiv_id":null,"evidence_quote":"Supplies the analytical CPTP projection of learned Choi states used to turn J(Ê) into a valid channel."},{"cited_title":"Stewart, Linear Algebra and its Applications 28, 213 (1979)","cited_arxiv_id":null,"evidence_quote":"Provides Weyl's singular-value perturbation theorem, used to control the error of the learned singular values in Lemma 4."}],"review_version":1}