{"id":"d7006493-61ea-4fc2-8855-6ee0eee58513","arxiv_id":"2506.01559","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A hybrid quantum-classical algorithm encodes multiple sequence alignment into a binary optimization with O(NL) qubits and reports optimal alignments for tiny examples on a 16-qubit ion-trap device.","lead":"The paper maps multiple sequence alignment into a binary optimization model called hqQUBO and runs it on a 16-qubit trapped-ion quantum computer. It claims a hybrid query encoding cuts quantum resource needs to O(NL) qubits, a step toward applying NISQ devices to bioinformatics.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (6)-(7) replace per-sequence letter conservation by a single total-count penalty, so compensating over/under-counts are unpenalized; the printed hqQUBO does not provably encode MSA.","rationale":"The reader's weakest_assumption is in the right neighborhood, but I sharpen it to a concrete algebraic error: Eq. (6) is not an equivalence, and Eq. (7) is missing the per-sequence sum inside the square. This is an internal inconsistency, not a disagreement with external consensus. It is load-bearing because the central claim is that the optimized bitstrings are optimal MSA solutions; if the objective as printed does not enforce per-sequence letter conservation, the model does not provably encode MSA. I credit the explicit feasible 20-qubit optimum in Fig. 3(B) and the claim that the 8/12/16-qubit top states are feasible, so the empirical demonstrations may survive. The proposed exhaustive enumeration settles whether the invalid states are actually unpenalized minimizers for the reported instances. I would keep the reader's CONDITIONAL verdict: the formal error must be fixed and verified, and the missing code/data and placeholder GitHub links make independent verification impossible, but the concern does not by itself overturn the reported states unless the check shows otherwise.","tokens_in":12667,"tokens_out":15171,"duration_ms":175351,"concrete_test":"For each of the paper's instances (8, 12, and 16 qubits), exhaustively enumerate all 2^n bitstrings, compute Eq. (8) exactly with p=1.5, and record the per-sequence counts C_i = Σ_k x_i,k. If any minimum-energy bitstring has C_i ≠ l_i for some sequence, the printed hqQUBO admits invalid MSAs and the central optimal-alignment claim fails. If all minimizers happen to be feasible, repeat the enumeration with the corrected per-sequence penalty pΣ_i(C_i−l_i)^2 and compare the two minimizer sets; any difference shows Eq. (7) is not the constraint supporting the reported results.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The formal core of the paper is the hqQUBO score in Eq. (8). Before that, the hard constraint (5) requires each sequence to use exactly l_i ones: ∀i, Σ_k x_i,k = l_i. The text replaces this with Σ_i(Σ_k x_i,k − l_i) = 0, which is not equivalent, and then with the soft penalty p(Σ_i(Σ_k x_i,k − l_i))^2 in Eq. (7). The correct per-sequence penalty is pΣ_i(Σ_k x_i,k − l_i)^2. As printed, a bitstring with sequence 1 carrying one extra 1 and sequence 2 carrying one fewer 1 has zero penalty even though neither sequence conserves its letter count. Eq. (4) maps the first l_i ones to letters and sends later ones to the dummy index −1, so extra 1s are score-neutral; a missing trailing letter can also be score-neutral because an all-gap column contributes zero pair score. Thus the ground states of Eq. (8) can include invalid 'alignments' with the same or lower energy as true MSAs. The reported 20-qubit state in Fig. 3(B) is feasible, and the 8/12/16-qubit experiments may have hit feasible states, but the printed objective does not enforce the constraint the paper claims is central. Because no code or data are provided, one cannot tell whether the implementation used the printed penalty or the intended per-sequence version.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes hqQUBO, a hybrid query-based QUBO formulation of multiple sequence alignment (MSA), in which N sequences of maximum length L are encoded as N*L binary variables and the SP score is evaluated classically through a query function f_i(k). The objective is optimized with a hardware-efficient ansatz and a two-stage CVaR loss, first on CPU/GPU simulators and then on the 37-qubit ion-trap device HYQ-A37 for 8, 12, and 16 qubits. The authors report that the 20-qubit simulated instance reaches the known optimal alignment, that the hardware runs produce feasible optimal states with high probability in 2000 shots, and that per-iteration time on the quantum device grows polynomially while their noisy classical simulation grows exponentially, yielding an estimated crossover near 22 qubits.","tokens_in":12978,"tokens_out":5429,"duration_ms":58151,"significance":"If the constraint formulation is corrected and the reported optima are re-verified, this is a useful proof of principle: it demonstrates a query-based binary encoding for small MSA instances, studies the role of entanglement layers and a two-stage CVaR scheme, and validates the approach on a real trapped-ion device up to 16 qubits without error mitigation. The experimental comparison among noiseless simulation, noisy simulation, and hardware is valuable and the authors are appropriately cautious about the qualitative nature of the time-crossover estimate. The main technical contribution is the encoding itself, but the paper currently overstates what is established: there is no comparison with classical MSA solvers, no benchmark of 'state of the art' performance, and no public code or data, so the central claims are not yet reproducible.","major_comments":[{"comment":"The passage from Eq. (5) to Eq. (6) is not an equivalence: the single equation sum_i(sum_k x_i,k - l_i) = 0 allows compensating deviations, e.g., for N=2 with l1=l2=2, a bitstring with three 1s in sequence 1 and one 1 in sequence 2 satisfies the summed equation while violating both per-sequence constraints. Because Eq. (4) maps a third (or later) 1 in a sequence to the dummy index -1, and because a missing trailing letter can be score-neutral when an all-gap column pairs with score 0, such invalid bitstrings are not penalized by the quadratic term in Eq. (8). The ground state of L(x;p) can therefore be an invalid 'alignment' with energy no higher than a true MSA. This is load-bearing: the central claim that hqQUBO encodes MSA requires the per-sequence penalty p * sum_i (sum_k x_i,k - l_i)^2, not p * (sum_i(sumi x_i,k - l_i))^2. The paper reports feasible states in the 20-qubit example and in the hardware runs, but since no code is supplied it is impossible to tell whether the implementation used the printed or the corrected penalty. The authors should fix the objective and rerun or re-verify all reported optima with the corrected constraint.","section":"hqQUBO Formalism, Eqs. (5)-(8)"},{"comment":"The time-efficiency comparison in Fig. 5 compares per-iteration wall-clock time of the variational algorithm on HYQ-A37 with per-iteration time of a classical simulation of the same quantum algorithm. It does not compare against any classical MSA solver (e.g., Clustal Omega, MAFFT, T-Coffee, or exact dynamic programming), so the abstract's 'state of the art performance' and the crossover estimate 'around 22 qubits' are not supported. Moreover, the crossover extrapolation uses only four points (4, 8, 12, 16 qubits), omits the number of iterations needed for convergence, and the text itself concedes that it is 'purely qualitative'. These claims should be removed or replaced by a benchmark against established classical MSA methods with fixed problem instances and time-to-solution.","section":"Results, 'Experimental Results on HYQ-A37' and Fig. 5"},{"comment":"The stated scaling n = O(NL) is a property of the chosen presence/absence binary encoding, not a result about the computational complexity of solving the MSA. The classical complexity quoted in the Introduction, O(L^N) (the text appears to print 'O(L N )'), refers to the size of the search space for exact SP-score alignment; the per-iteration cost of a variational loop and the number of iterations to convergence are not accounted for. The paper should distinguish encoding width from time-to-solution complexity, and the phrase 'quantum resources significantly reduced to O(NL)' should be rephrased accordingly.","section":"Methods, 'Hybrid Query Encoding'"}],"minor_comments":[{"comment":"The spelling of the method name is inconsistent: 'hyQUBO' appears in the abstract and 'hqQUBO' elsewhere; please unify.","section":"Abstract and main text"},{"comment":"The complexity expression for classical MSA is ambiguous as printed ('O(L N )'); it should be typeset unambiguously as O(L^N) or O(NL^N) depending on the intended reference.","section":"Introduction and Methods"},{"comment":"The Code Availability section gives a placeholder URL ('https://github.com') and reference [29] points to 'www.GitHub.xxx.com'; without an actual repository and data, the experiments in Figs. 3-5 cannot be reproduced.","section":"Code and data availability"},{"comment":"There are several typos and grammatical slips, including 'minimas' for 'minima', 'sing-qubit' for 'single-qubit', 'Acccording' for 'According', and 'advantage' for 'advantages'; these should be corrected in a final pass.","section":"Throughout"},{"comment":"The statement that QAOA reaches a depth of 4486 layers in the 12-qubit example is not derived in the text; please explain how this number is obtained or remove it.","section":"Fig. 2 caption"},{"comment":"The claim that this is 'the largest-scale implementation of digital simulation using up to 16 qubits on a trapped-ion quantum computer for life science problem' is presented without a citation or a documented survey; it should be substantiated with a comparison list or removed.","section":"Abstract and Discussion"}],"recommendation":"major_revision","confidential_remarks":"The central constraint error in Eqs. (6)-(7) is the key technical issue; the acceptance decision should hinge on whether the authors correct the objective and re-verify the reported optima. I also recommend pushing back on the unsubstantiated 'state of the art' and 'largest-scale' priority claims, which are likely to attract criticism and are not essential to the paper's contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nThe thing to know: the hybrid query encoding is a real idea, and the 16-qubit trapped-ion experiment is a legitimate engineering milestone. But the QUBO as printed does not enforce the constraint that each sequence keeps exactly l_i letters, so the paper's central claim — that the ground state of Eq. (8) is the optimal MSA — does not follow from the formalism.\n\nWhat's new: Eqs. (3)-(4) map each sequence to a binary string of length L, with letters read off by counting preceding 1s. That reduces qubit count from O(N^2 L) in ref. [21] to O(NL). That's a legitimate improvement. The HEA+CVaR combination is standard, but the two-stage warm-up variant is sensible, and the comparison on 12 qubits showing HEA beating QAOA is evidence that the shallow ansatz helps on this problem. The 8/12/16-qubit runs on HYQ-A37 are real experiments, and the reported 16-qubit state is the known optimal alignment. Good.\n\nThe soft spot is not minor. Eq. (5) requires ∀i, Σ_k x_i,k = l_i. Eq. (6) claims this is equivalent to Σ_i(Σ_k x_i,k − l_i)=0, which is false. The soft penalty in Eq. (7) then penalizes only the total deviation. A bitstring with one extra 1 in sequence 1 and one fewer in sequence 2 has zero penalty. Eq. (4) maps surplus 1s to the dummy −1, which scores 0 against gaps, and a missing trailing letter also scores 0 in an all-gap column. So the ground state of Eq. (8) can be an invalid alignment with energy equal to or lower than the true MSA. The experiments may have hit feasible states, but the printed objective doesn't guarantee it. No code or data are provided, so we can't tell whether the implementation used the intended per-sequence penalty. This needs to be fixed and the experiments re-verified.\n\nOther issues: no classical MSA baselines (e.g., Clustal, MAFFT), so 'state of the art' is unsupported. The time comparison in Fig. 5 compares per-iteration quantum hardware time to classical simulation of the same circuit, not to an actual MSA solver; the 22-qubit crossover is a fitted extrapolation and the authors admit it's qualitative. Appendices A-C and the GitHub link are missing.\n\nBottom line: the encoding is worth publishing, and the experiment is real, but the formal core has a load-bearing error. A serious referee should engage with it and require a corrected penalty, proper baselines, and code/data. I'd accept it for peer review but expect major revision.\n\nBest, [Your name]","headline":"A promising encoding and a genuine 16-qubit demo, but the printed QUBO constraint is mathematically wrong as written, so the central MSA claim is not yet supported.","tokens_in":13554,"tokens_out":4869,"would_cite":false,"duration_ms":44977,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","90C27","92D20"],"pacs":["03.67.-a","03.67.Lx"],"model":"deepseek-v4-flash","headline":"A hybrid query encoding reduces multiple sequence alignment to a QUBO that needs only $O(NL)$ qubits, and a 16-qubit ion-trap experiment returns optimal alignments.","keywords":["multiple sequence alignment","QUBO","variational quantum eigensolver","hardware-efficient ansatz","CVaR","ion-trap quantum computer","protein structure prediction","hybrid quantum-classical"],"falsifier":"Run a small alignment (such as the 16-qubit instance) on a simulator, enumerate all bitstrings that satisfy the letter-count constraint, and compute the ground state of Eq. (8) exactly; then verify that it equals the known optimal alignment and that the variational histogram's top state matches it. Also record on the ion-trap device the fraction of the 2000 shots that satisfy the letter-count constraint; a non-negligible infeasible fraction would falsify the penalty's adequacy.","tokens_in":12449,"feed_emoji":"🧬","tokens_out":7788,"duration_ms":74451,"temperature":0.7,"pith_summary":"The paper claims that multiple sequence alignment (MSA), a computationally hard step behind protein-structure prediction, can be encoded as a quadratic binary optimization whose quantum resources grow only as $O(NL)$ — linear in the number of sequences $N$ times their maximal length $L$ — rather than the $O(N^2 L)$ required by earlier QAOA encodings. The reduction comes from a hybrid query encoding: qubits only mark where letters appear, and a classical computer recovers each letter's identity by counting preceding 1s, so the quantum circuit samples alignments while the classical side does the scoring. Using a hardware-efficient ansatz with a two-stage CVaR loss, the model finds optimal or near-optimal alignments in noiseless simulation and on a 16-qubit ion-trap device, with per-iteration time growing polynomially on the device and a projected crossover with classical simulation near 22 qubits. A sympathetic reader would care because this is one of the first demonstrations of a real life-science optimization problem running at 16 qubits on a trapped-ion processor without error mitigation.","feed_headline":"16-qubit ion trap finds optimal sequence alignments","feed_subtitle":"Hybrid quantum-classical encoding cuts qubit count and points to faster protein-structure inputs.","key_machinery":"The load-bearing object is the Hybrid Query Encoding (HQE) together with the score function of Eq. (8). In HQE, each sequence of maximal length $L$ is represented by $L$ qubits, with $|1\\rangle$ marking an occupied column and $|0\\rangle$ a gap; the query function $f_i(k)$ converts the count of preceding 1s into the letter index of the original sequence, which allows the classical computer to evaluate the pair-similarity weights $w^{(i,j)}_{f_i(k),f_j(k)}$ for any sampled bitstring. The quadratic penalty with $p=1.5$ enforces letter-count conservation. Around this core sit two numerical devices: a hardware-efficient ansatz (HEA) with modest entanglement layers, chosen over deeper QAOA circuits, and a two-stage CVaR loss that first optimizes a tail ratio $r<1$ and then switches to $r=1$, reducing iterations and local-minima trapping. The machinery converts MSA into a variational quantum eigensolver problem whose Hamiltonian is diagonal in the computational basis, with eigenvalues given by $L(x;p)$.","core_discovery":"The paper's central discovery is that the sum-of-pairs score of an alignment can be evaluated exactly through a classical query function $f_i(k)$ defined on the qubit bitstring, which maps each 1 to the index of the corresponding letter in the original sequence by counting preceding 1s, and maps 0s and excess 1s to a dummy index. Substituting this query into the SP-score yields the hybrid loss $L(x;p)$ of Eq. (8), whose ground state corresponds to the optimal alignment. Because the encoding is positional rather than one-hot, the required qubits fall to $O(NL)$. On a 37-qubit ion-trap quantum computer, 2000-shot measurements of the variational state reproduce the optimal alignment with significant probability at 8, 12, and 16 qubits, and the experimental time per iteration grows polynomially, while a noisy classical simulation grows exponentially, placing a crossover around 22 qubits. The authors state that this is the largest digital simulation on a trapped-ion quantum computer for a life-science problem at the time of writing.","pith_inferences":["A natural next test, not performed in the paper, is to scale the same encoding to longer sequences and measure the fraction of sampled bitstrings that satisfy the letter-count constraint; if the penalty does not fully suppress infeasible strings, the optimal-state peaks could be contaminated by invalid alignments.","The crossover estimate is a rough extrapolation that excludes the number of iterations needed for convergence; a fair practical benchmark would compare total time-to-solution against classical progressive aligners rather than noisy GPU simulations.","The HQE trick may carry over to profile or structural alignment, where any scoring function computable from positions can be queried classically; this suggests a wider family of hybrid-query QUBO encodings for bioinformatics problems."],"forward_implications":["If the encoding is sound, the qubit footprint for aligning $N$ sequences of maximal length $L$ drops from $O(N^2 L)$ to $O(NL)$, making NISQ-era devices viable for small-to-medium MSA instances.","The projected cost crossover near 22 qubits implies that for alignment problems requiring more than that many qubits, the ion-trap variational routine could beat noisy classical simulation in wall-clock time per iteration, though total iteration counts must still be included.","The pattern of offloading a reversible classical query (letter identity from run-length counts) to the classical processor generalizes to other combinatorial costs defined on bitstrings, such as assembly or folding constraints that can be written as functions of cumulative counts.","The two-stage CVaR schedule—warm-up with a tail loss, then full loss—offers a concrete way to stabilize VQE convergence in noisy settings, applicable beyond MSA."],"supporting_citations":[{"why":"Establishes the use of MSA in high-accuracy protein-structure prediction and motivates the need for faster alignment.","marker":"[1]"},{"why":"Proves that SP-score MSA is NP-hard, which motivates a quantum optimization approach.","marker":"[4]"},{"why":"Derives QAOA from Trotterized adiabatic evolution, used to explain why QAOA circuit depth scales poorly compared to HEA.","marker":"[20]"},{"why":"Provides the QAOA formulation of MSA that the hqQUBO model is compared against, with a one-hot column encoding requiring more qubits.","marker":"[21]"},{"why":"Introduces the CVaR loss function on which the two-stage optimization scheme is based.","marker":"[22]"}],"fun_headline_variants":["Hybrid query encoding cuts qubits for MSA on ion trap","16-qubit ion trap finds alignments via hybrid quantum query","Quantum MSA: O(NL) qubits with hybrid encoding on 16 qubits","Ion-trap quantum computer optimizes sequence alignment with 16 qubits","Hybrid querying quantum model solves MSA on trapped-ion system"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire model assumes that the query mapping $f_i(k)$ together with the penalty term $p=1.5$ computes the exact SP-score and keeps every sampled bitstring feasible; if that mapping is wrong for longer sequences or the penalty fails to exclude letter-count violations, the reported optimal states may not be valid alignments.","fun_headline_variants_meta":{"raw":{"variants":["Hybrid query encoding cuts qubits for MSA on ion trap","16-qubit ion trap finds alignments via hybrid quantum query","Quantum MSA: O(NL) qubits with hybrid encoding on 16 qubits","Ion-trap quantum computer optimizes sequence alignment with 16 qubits","Hybrid querying quantum model solves MSA on trapped-ion system"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000258,"raw_usage":{"total_tokens":1628,"prompt_tokens":1035,"completion_tokens":593,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":651,"completion_tokens_details":{"reasoning_tokens":496}},"tokens_in":651,"tokens_out":593,"duration_ms":6634,"temperature":1.0,"reasoning_tokens":496,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:38:04.426408+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a small alignment (such as the 16-qubit instance) on a simulator, enumerate all bitstrings that satisfy the letter-count constraint, and compute the ground state of Eq. (8) exactly; then verify that it equals the known optimal alignment and that the variational histogram's top state matches it. Also record on the ion-trap device the fraction of the 2000 shots that satisfy the letter-count constraint; a non-negligible infeasible fraction would falsify the penalty's adequacy.","supporting_citations":[{"cited_title":"Highly accurate protein structure prediction with alphafold.nature, 596(7873):583–589, 2021","cited_arxiv_id":null,"evidence_quote":"Establishes the use of MSA in high-accuracy protein-structure prediction and motivates the need for faster alignment."},{"cited_title":"On the complexity of 12 multiple sequence alignment.Journal of computational biology, 1(4):337–348, 1994","cited_arxiv_id":null,"evidence_quote":"Proves that SP-score MSA is NP-hard, which motivates a quantum optimization approach."},{"cited_title":"Quaser: Quantum accelerated de novo dna sequence reconstruc- tion.Plos one, 16(4):e0249850, 2021","cited_arxiv_id":null,"evidence_quote":"Derives QAOA from Trotterized adiabatic evolution, used to explain why QAOA circuit depth scales poorly compared to HEA."},{"cited_title":"Multi-sequence alignment using the Quantum Approximate Optimization Algorithm","cited_arxiv_id":"2308.12103","evidence_quote":"Provides the QAOA formulation of MSA that the hqQUBO model is compared against, with a one-hot column encoding requiring more qubits."},{"cited_title":"Improv- ing variational quantum optimization using cvar.Quan- tum, 4:256, 2020","cited_arxiv_id":null,"evidence_quote":"Introduces the CVaR loss function on which the two-stage optimization scheme is based."}],"review_version":1}