{"id":"282d0382-7b22-4f37-a3c1-36458348f017","arxiv_id":"2607.19874","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Replacing the depth-zero net search with an 'integerized trotterization' over a good exponential basis makes online synthesis poly(d, log 1/ε), moving the exponential net cost into a one-time preprocessing step.","lead":"This paper changes the Solovay–Kitaev algorithm so that the expensive search over an exponentially large precomputed net is done only once, before handling any target unitary. After that, each new unitary can be compiled in time polynomial in the qudit dimension and polylogarithmic in the desired accuracy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"I reviewed the paper in good faith and focused on the reader's identified weakest assumption: the correctness of the balancing routine in Algorithm 3 / Lemma 3.7. The reader's concrete counterexample is flawed: at the step where w = 0.1, the algorithm still has a non-negative eigenvalue (0.9) remaining in P, so it pops from P rather than N. The partial sums generated by the algorithm are 0.9, 1.8, 1.1, 0.1, 1.0, 0.0, all within [0, 2]. More generally, the invariant holds because: if w < ||Z|| and P is nonempty, adding a non-negative eigenvalue keeps w < 2||Z||; if P is empty, all remaining eigenvalues are negative and sum to -w, so each is at least -w; if w >= ||Z||, every negative eigenvalue is at least -||Z|| >= -w. Thus the balancing algorithm is correct. I also checked the other pillars of the central claim: the commutator construction in Lemma 3.6 works with the given v_k scaling; the discrete trotterization analysis in Proposition 4.8 has a slightly terse rounding bound but the conclusion holds; the recursion error analysis is unchanged from standard SK since the base case guarantees error <= ε0. The BCH constant is not proven in the paper but is a known universal constant, and finite-precision issues are explicitly deferred by the real-RAM convention. Therefore I do not identify a load-bearing concern that would invalidate the paper's main theorem or corollary. The reader's conditional verdict seems driven by an invalid counterexample; I would not move the verdict away from the paper's acceptance on those grounds.","tokens_in":24647,"tokens_out":50550,"duration_ms":422804,"concrete_test":"Run Algorithm 3 exactly as written on diag(0.9, 0.9, 0.9, -1.0, -1.0, -0.7) and verify that every partial sum w_k after each pop lies in [0, 2]. Additionally, run randomized invariant checks on random traceless Hermitian matrices for d = 2..20, confirming that the partial sums never leave [0, 2]. If the invariant fails in any run, the reader's concern would be substantiated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's claimed counterexample to Lemma 3.7 does not hold. For Z = diag(0.9, 0.9, 0.9, -1.0, -1.0, -0.7), after popping 0.9, 0.9, -0.7, -1.0 (w = 0.1), the non-negative stack still contains a 0.9 entry. Algorithm 3 line 7-8 therefore pops from P, not N, giving w = 1.0, and the next pop of -1.0 gives w = 0.0. All partial sums lie in [0, 2]. The invariant is preserved. I have not found another load-bearing mathematical flaw: Algorithm 2's commutator construction is correct with the stated v_k scaling; Proposition 4.8's error analysis is consistent; the recursive error analysis of Theorem 3.11 applies unchanged because the new base case still guarantees error at most ε0. The BCH uniform constant is asserted without proof but is a standard result, and finite precision is explicitly out of scope in the real-RAM model. The central claim appears supported.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a modification of the Solovay-Kitaev (SK) algorithm that eliminates the online search over an ε0-net, which is the source of the exponential dependence on the qudit dimension d. It introduces the notion of a good exponential basis and a discrete trotterization base routine (Algorithm 4). Theorem 4.18 states that, given such a basis, Algorithm 5 approximates p target unitaries in time O(d^6 + p d^4 log^{k_t}(1/ε)) with no net search. For arbitrary universal instruction sets, Theorem 4.22 and Corollary 4.29 show that a good basis can be constructed in a one-time standard-SK preprocessing step, making the net-search cost T0 additive rather than multiplicative in p. The paper also discusses the conditioning parameter μ_N, the restrictiveness of h_max, and possible higher-order product-formula extensions.","tokens_in":24908,"tokens_out":41434,"duration_ms":379859,"significance":"If the main theorems are correct, this is a substantial contribution to the variable-dimension gate synthesis problem. It provides the first explicit construction (known to me) realizing the additive-cost form suggested by Kitaev-Shen-Vyalyi, and it does so with a clear separation of online and preprocessing costs. The good-exponential-basis criterion is a concrete, verifiable sufficient condition (Remark 4.19). The use of BCH-based trotterization to replace the depth-zero net is original and likely to stimulate further work. The paper is honest about limitations: the required h_max is very small (~d^-6 to d^-7), and for arbitrary instruction sets the exponential T0 remains, but only in preprocessing.","major_comments":[{"comment":"The proof of Algorithm 3's invariant is not reliable as written. In the case w_{k-1} ≥ ∥Z∥, the text asserts the existence of a negative eigenvalue in (-w_{k-1}, 0); this may fail (e.g., Z=diag(1,1,-2) at w=2, remaining eigenvalue -2). It also does not justify that the eigenvalue actually popped from the N stack satisfies the needed lower bound. The lemma is nevertheless true: every remaining eigenvalue obeys |μ_j| ≤ ∥Z∥ ≤ w_{k-1}, so μ_j ≥ -w_{k-1}, and the invariant follows. The proof must be corrected (e.g., by adding this one-line observation). This is load-bearing because both Algorithm 1 and Algorithm 5 rely on the commutator decomposition.","section":"§3, Lemma 3.7"}],"minor_comments":[{"comment":"The paragraph beginning 'Many of the usual properties...' is duplicated immediately before Lemma 2.5.","section":"§2"},{"comment":"The loop 'for k=1 to d' uses the ket |k+1⟩ at k=d; this should be k=1 to d-1 (the proof in Lemma 3.6 uses k=0 to d-1).","section":"§3, Algorithm 2"},{"comment":"Line 5 writes 'log(U†Un−1)'; this should be 'log(U† U_{t-1})'.","section":"§3, Algorithm 1 and §4, Algorithm 5"},{"comment":"The symbol h*_max is used both as the scalar defining H*_j = h*_max Λ_j and as the maximum norm max_j ||H*_j||. Since ||Λ_j||≤1 these are compatible only as an upper bound; it would be clearer to introduce a scalar h* and define h*_max accordingly.","section":"§4.2, Theorem 4.22"},{"comment":"The statement that the d^6 trotterization preprocessing is 'absorbed into the T0 SK cost' is only true because T0 is exponential in d (T0 = Ω(2^{c d^2}) in the intended regime). Please make this explicit, since for a hypothetical polynomial T0 the stated bound would need an additional d^6 term.","section":"§4.2, Corollary 4.29"},{"comment":"The uniform BCH constant C for M-term products is asserted without proof or reference. A citation for the M-term version (or a short derivation) would help.","section":"§2, Lemma 2.5"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the reader's reported counterexample to Lemma 3.7 does not actually hold (after two 0.9 pops, the nonnegative stack still contains 0.9). The lemma is true, but the proof as written contains a false existence claim. I do not see a fatal flaw; the manuscript is close. I would be willing to accept after the proof of Lemma 3.7 is repaired and the minor points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Readable paper, and the central idea is real: replace the depth-zero net query in Solovay–Kitaev with integerized trotterization over a \"good exponential basis,\" isolating the net cost in preprocessing. That is precisely the tangent-space suggestion from Kitaev–Shen–Vyalyi, and I do not know of an earlier explicit algorithm along those lines. Proposition 4.8 and Theorem 4.18 have the right shape: explicit inequalities, no constants fitted to data, and Corollary 4.29's additive T0 preprocessing follows from a standard SK reduction, not a circular one.\n\nThe reader's main objection is a misreading. For the claimed eigenvalue multiset, Algorithm 3 does not pop -0.7 while w = 0.9; the nonnegative stack still contains a 0.9, so the algorithm pops from P. The prefix sums stay in [0, 2||Z||]. The stress-test is right about that. However, the proof of Lemma 3.7 as written is not correct: the sentence \"there exists -w < mu_j < 0\" when w >= ||Z|| is false. The correct argument is simpler: every negative eigenvalue is at least -||Z||, so adding any of them to w >= ||Z|| keeps the sum nonnegative. The lemma itself is true; the proof needs a rewrite.\n\nThere are also small presentation issues: the off-diagonal index in Algorithm 2 runs to d-2, not d-1, and a C goes missing in a displayed bound in Theorem 4.22's proof. None of these are load-bearing. The BCH constant C and radius delta0 are asserted without proof, which is standard but should be stated more carefully. Finite precision is explicitly deferred to the real-RAM model. The circuit length grows like d^{19/2}, which makes the scheme mostly conceptual; the authors are candid about that.\n\nBottom line: this is a serious paper with a plausible, checkable main argument and a genuine new contribution. It deserves a careful referee, not a desk reject. I would send it out and ask for a corrected Lemma 3.7 proof and a cleanup of the indexing typos.","headline":"The main construction is sound and genuinely new; the reader's counterexample to Lemma 3.7 does not survive contact with the actual algorithm, but the proof of that lemma is sloppy and should be rewritten.","tokens_in":25408,"tokens_out":14199,"would_cite":true,"duration_ms":123158,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68","22E70"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"The paper claims that a net-free Solovay–Kitaev recursion is possible: with a good exponential basis in hand, each target unitary is compiled in time polynomial in the qudit dimension and polylogarithmic in 1/ε, and the formerly exponential","keywords":["Solovay–Kitaev algorithm","gate synthesis","unitary approximation","trotterization","good exponential basis","qudit dimension","Lie group SU(d)","net search"],"falsifier":"Run the balancing routine (Algorithm 3) on the diagonal Hermitian matrix diag(0.9, 0.9, 0.9, -1.0, -1.0, -0.7), whose operator norm is 1. The greedy stack rule pops 0.9, 0.9, -0.7, -1.0, and then -1.0 when the partial sum is 0.1, producing a final partial sum of -0.9 and violating the claimed 0 ≤ partial sum ≤ 2 invariant. A corrected routine that provably maintains the invariant for all inputs would revive the proof; without one, the stated theorems are not established as written.","tokens_in":24532,"feed_emoji":"⚛️","tokens_out":9565,"duration_ms":86315,"temperature":0.7,"pith_summary":"The paper claims that the expensive coarse net search at the base of the Solovay–Kitaev recursion can be removed from the online phase. The replacement is a discrete, integerized trotterization step: the target unitary's logarithm is expanded in a 'good exponential basis' and approximated by integral powers of basis gates. For instruction sets that admit such a basis, each target is then synthesized in time polynomial in the qudit dimension d and polylogarithmic in 1/ε, after a one-time O(d^6) change-of-basis preprocessing. For arbitrary universal instruction sets, the exponential net cost is not eliminated but is moved into a one-time additive preprocessing term. If correct, this makes the algorithm's dimension dependence benign in practical settings where many unitaries are compiled against the same gate set.","feed_headline":"Drops exponential net lookup from Solovay-Kitaev synthesis","feed_subtitle":"No more coarse-net searches during compilation: online qudit synthesis becomes polynomial in dimension after one preprocessing pass.","key_machinery":"The load-bearing objects are the good exponential basis and the integerized trotterization subroutine (Algorithm 4). The basis provides a short, well-conditioned set of Hamiltonian directions; the subroutine expands log(U)/n in that basis and rounds the real coefficients to integers, then builds U as n repetitions of the resulting product. The Lie-algebra product-formula expansion controls the product-formula error, and the minimum-gain parameter µ—the smallest operator norm attainable by a unit-ℓ∞ coefficient vector—controls the conditioning of the basis. The goodness condition makes the drift error and the product-formula error fit within ε0, thereby replacing an exponential-size precomput","core_discovery":"On the paper's own terms, the central discovery is that the depth-zero ε0-net query of the Solovay–Kitaev recursion can be replaced by a constructive local routine: integer trotterization along the geodesic from the identity to U. A 'good exponential basis'—a basis of exponentials exp(iH_j) whose logarithms are short and well-conditioned—guarantees that this routine meets the ε0 accuracy needed to start the recursion. With such a basis, Theorem 4.18 asserts online synthesis in O(d^6 + p d^4 log^{k_t}(1/ε)) with no net search. For arbitrary universal instruction sets, Corollary 4.29 first synthesizes a good basis in a preprocessing phase using the standard Solovay–Kitaev algorithm, absorbing","pith_inferences":["Higher-order splitting formulas should reduce the d^7-driven circuit-length blow-up by lowering the number of Trotter steps at the price of more exponentials per step; the paper's own error analysis suggests h_max ~ d^{-4} may be reachable, shortening circuits by a factor of d^3.","Scheduled integration, where integer coefficients are re-chosen at each step to cancel drift, could relax the restrictive h_max condition; the paper notes this may reduce to an approximate lattice problem at each step.","The net-free method trades online time for longer circuits—an extra d^{19/2} polylog(d) factor for arbitrary instruction sets—so in depth-sensitive applications, the classic Solovay–Kitaev algorithm may still be preferable despite its exponential net."],"forward_implications":["For any instruction set that contains or can efficiently build a good exponential basis, Algorithm 5 compiles a list of p target unitaries to error ε in O(d^6 + p d^4 log^{k_t}(1/ε)) total time, with no ε0-net search during synthesis.","For an arbitrary universal instruction set, the exponential net cost is confined to a one-time additive preprocessing step costing O(d^2(T0+d^3) log^{k_t} d), so compiling many targets amortizes the expensive base preparation.","The good-exponential-basis condition supplies a verifiable, real-RAM sufficient test for whether an instruction set is universal: compute logarithms, check that they form a basis of su(d), estimate the minimum gain µ, and verify the h_max bound.","Because only the depth-zero subroutine changes, established improvements to the Solovay–Kitaev recursion—inverse-free variants and tighter contraction exponents—can be carried over to this net-free version.","The synthesized circuits are represented as straight-line programs, and the working memory stays polynomial in d (plus log log(1/ε)) after preprocessing, rather than exponential."],"fun_headline_variants":["Solovay-Kitaev without exponential net search","Integer trotterization replaces net search in Solovay-Kitaev","Online qudit synthesis polynomial after net-free preprocessing","Exponential net lookup moved to one-time preprocessing in Solovay-Kitaev","Good exponential basis yields net-free qudit synthesis"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the greedy eigenvalue-balancing routine (Algorithm 3, Lemma 3.7) always keeps the running partial sum of eigenvalues inside [0, 2∥Z∥]; that invariant is asserted but is false for, e.g., eigenvalues (0.9, 0.9, 0.9, -1.0, -1.0, -0.7), and both the classic Solovay–Kitaev recursion and the new net-free version depend on it.","fun_headline_variants_meta":{"raw":{"variants":["Solovay-Kitaev without exponential net search","Integer trotterization replaces net search in Solovay-Kitaev","Online qudit synthesis polynomial after net-free preprocessing","Exponential net lookup moved to one-time preprocessing in Solovay-Kitaev","Good exponential basis yields net-free qudit synthesis"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000253,"raw_usage":{"total_tokens":1469,"prompt_tokens":877,"completion_tokens":592,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":508}},"tokens_in":621,"tokens_out":592,"duration_ms":5484,"temperature":1.0,"reasoning_tokens":508,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T11:29:19.176706+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the balancing routine (Algorithm 3) on the diagonal Hermitian matrix diag(0.9, 0.9, 0.9, -1.0, -1.0, -0.7), whose operator norm is 1. The greedy stack rule pops 0.9, 0.9, -0.7, -1.0, and then -1.0 when the partial sum is 0.1, producing a final partial sum of -0.9 and violating the claimed 0 ≤ partial sum ≤ 2 invariant. A corrected routine that provably maintains the invariant for all inputs would revive the proof; without one, the stated theorems are not established as written.","supporting_citations":[],"review_version":1}