{"id":"074ef557-2894-4232-b275-be88cee16b79","arxiv_id":"2501.15137","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Presents quantum circuits for row addition, row swapping, trace, and transpose of amplitude-encoded matrices, with O(log N) or O(m) gate complexity after state preparation.","lead":"This paper designs quantum circuits that add one matrix row to another, swap two rows, compute the diagonal sum, and transpose a matrix, assuming the matrix entries are already stored as the amplitudes of a quantum state. The work offers building blocks for future quantum linear algebra libraries, with logarithmic gate counts for the internal operations, though state preparation and low success probabilities remain practical barriers.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The trace algorithm (§3.A) does not deliver a trace: the postselected state carries only the unobservable global phase of tr(S), while the measurable quantity is |tr(S)|²/2^{3n}; estimating it needs Ω(2^{3n}/|tr|²) repetitions, so the advertised O(log N) trace complexity is not end-to-end.","rationale":"The reader's nominated weakest assumption is the state-preparation/readout exclusion, which is a scope limitation that the paper explicitly declares; it is not the most load-bearing concern because the internal circuit derivations can be checked on their own terms. The reader's rationale does flag the trace shortcoming, so there is partial agreement. I independently checked the row-addition and row-swapping derivations: the sign factors and orthogonal-row structure yield the stated success probabilities (G²/8 and 1/24), so those parts are credible. The appendix has a normalization error (the row norms sum to 270/256 > 1 in the example), but that is an illustrative slip, not the central proof. The trace issue is sufficient to keep the verdict conditional: the authors must either reframe the trace result as estimation of |tr|² with explicit exponential overhead, or supply a coherent procedure that extracts the complex trace with bounded expected cost. Since the reader's verdict is already CONDITIONAL, no change is needed.","tokens_in":15750,"tokens_out":16374,"duration_ms":150693,"concrete_test":"Symbolically execute §3.A for S=diag(d_0,...,d_{N-1}) with Σ|d_i|²=1: propagate Eqs. (17)–(21) and record the amplitude of the branch |0>_R|0>_C|0>_A|1>_B1|1>_B2; verify it equals 2^{-3n/2} Σ_i d_i. Then compute the number of trials needed to estimate the B2=1 probability to a fixed relative error; it is Θ(2^{3n}/|Σ_i d_i|²) ≥ N², and with amplitude amplification Θ(2^{3n/2}/|Σ_i d_i|) ≥ N. If either count is not polynomial in n, the O(log N) trace claim requires a different extraction procedure, e.g., one that recovers the phase of Σ_i d_i.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.A is the weak point of the central claim. After Step 6, Eq. (22) gives |Φ5> = (Σ_i a_ii / |Σ_i a_ii|) |0>_R|0>_C|0>_A|1>_B1. Any information about the complex number tr(S) is contained only in a global phase multiplier of a fixed basis state; a global phase is not observable, so the final state alone does not encode the trace in a usable way. The only extraction route offered in the paper is the branch probability p = |Σ_i a_ii|²/2^{3n} for B2=1. Since by Cauchy–Schwarz |Σ_i a_ii|² ≤ N, p ≤ 1/N², which is exponentially small in n. Estimating p to constant relative error needs Ω(2^{3n}/|tr|²) ≥ Ω(N²) preparations/measurements; amplitude amplification lowers this to Ω(2^{3n/2}/|tr|) ≥ Ω(N), still exponential. Thus the O(n)=O(log N) complexity is per successful branch, not the cost of actually obtaining the trace, and even the value obtained is |tr|² rather than tr. This is an internal inconsistency with the claim, not a matter of consensus. The row-addition and row-swapping algorithms do not have this defect: their postselected states correctly implement the intended row operations and have dimension-independent success probabilities (G²/8 and 1/24).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents quantum circuits for four matrix operations on amplitude-encoded matrices: adding one row to another (Section 2.A), swapping two rows (Section 2.B), computing the trace (Section 3.A), and transposing (Section 3.B). The circuits use multi-qubit Toffoli-type controlled operations, C-SWAP gates, Hadamard transforms, and postselection on ancilla measurements. The authors report gate complexities of O(log N) for the row operations and trace, O(m) for transpose, with success probabilities G^2/8, 1/24, |sum_i a_ii|^2/2^{3n}, and 1, respectively. The row-operation and transpose derivations are explicit and internally consistent. The trace algorithm, however, does not deliver the trace as claimed.","tokens_in":16037,"tokens_out":7738,"duration_ms":69280,"significance":"The row-addition and row-swapping circuits are concrete, fully specified constructions that correctly implement the intended transformations, with success probabilities independent of matrix dimension; this is a useful incremental contribution in the line of reference [20]. The transpose circuit is correct and deterministic. A notable strength is that the circuits are given explicitly and the amplitude calculations can be checked step by step; there are no fitted parameters. The trace algorithm, however, only places the global phase of sum_i a_ii on a fixed basis state, and the only measurable quantity is the exponentially small probability |sum_i a_ii|^2/2^{3n}; it therefore does not compute the trace, and the claimed O(log N) cost is not the end-to-end cost. This substantially reduces the scope of the paper's claims.","major_comments":[{"comment":"Section 3.A, Eqs. (20)-(22) and the Conclusion: the trace algorithm does not actually compute the trace. After Step 6 the postselected state is |Phi5> = (sum_i a_ii / |sum_i a_ii|) |0>_R|0>_C|0>_A|1>_B1, in which the trace appears only as an unobservable global phase. The paper states that the trace is obtained from the measurement probability |sum_i a_ii|^2 / 2^{3n}, which yields only |tr S|^2 scaled by 2^{3n} and loses the phase of tr S. Since |sum_i a_ii|^2 <= N by Cauchy-Schwarz, this probability is at most 1/N^2, so estimating it to constant relative error requires Omega(N^2) repetitions classically or Omega(N) with amplitude amplification; both are exponential in n = log N. Therefore the advertised O(log N) complexity is not the end-to-end cost of obtaining the trace, contrary to the central claim.","section":"3.A"},{"comment":"The Conclusion claims that in all algorithms the final result is stored in the probability amplitude of certain quantum states. For the trace algorithm this is not the case: the result is encoded as a global phase in Eq. (22), and the only accessible quantity is the exponentially small postselection probability. The authors should either modify the algorithm to recover the phase of the trace (for example by using an interferometric reference) or explicitly restate the contribution as an algorithm for estimating |tr S|^2 with exponential sample complexity; as written, the trace algorithm is not a trace-calculation algorithm.","section":"3.A / Conclusion"}],"minor_comments":[{"comment":"The phrase 'the elements of thek + 1and the l + 1rows' is garbled; it should read 'the elements of the (k+1)-th and (l+1)-th rows of Z'.","section":"2.A, Step 1"},{"comment":"The statement that W^(4)_{B1B2B3} has 'one control qubit' is inaccurate: the projections P^(i) act on the three qubits B1 and B2, so the control register has three qubits; the complexity O(1) is unaffected.","section":"2.B, Step 5"},{"comment":"There are numerous typographical issues: 'SW AP' and 'C-SW AP' have misplaced spaces, 'swaping' and 'swaped' should be 'swapping' and 'swapped', and '2th' in Appendix 1 should be '2nd'.","section":"Throughout"},{"comment":"Several references have formatting errors, e.g., [1] '563591' and [23] 'V .47'; please correct these.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The trace section is the main obstacle; the row operations and transpose sections are sound. If the trace claim is corrected or removed, the paper could be acceptable as a minor contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read of arXiv:2501.15137. The row-addition and row-swapping circuits are the real content. They explicitly implement the intended operations, and the amplitude calculations check out, including the sign cancellation that gives the 1/24 success probability for swapping. That is a genuine, if modest, extension of Zenchuk's ancilla-measurement framework. The transpose is just a SWAP between registers—correct but trivial.\n\nThe trace algorithm does not deliver what it claims. After postselection, the final state carries only a global phase; the only measurable quantity is the branch probability |tr(S)|^2 / 2^{3n}. Since |tr(S)|^2 ≤ N, this probability is exponentially small, and estimating it to constant relative error requires Ω(N^2) shots (or Ω(N) with amplitude amplification). So the advertised O(log N) trace complexity is not an end-to-end cost, and what you get is |tr|^2, not tr. That is a load-bearing flaw, not a cosmetic issue. The appendix also has normalization errors in the worked example: the given matrix amplitudes do not sum to unit norm, so the example as written is inconsistent.\n\nThe citation pattern is fine—[20] is the right starting point, and the new row-operation circuits are explicit and not present in prior work. Overall, this is a paper with one correct, useful piece (the row operations) and one broken headline result. I would send it to a referee because the row operations deserve scrutiny and could be published after revision, but the trace section needs to be rewritten or removed, and the complexity claim corrected. A serious referee should catch the exponential overhead immediately.","headline":"The row-operation circuits are correct and worth knowing, but the trace algorithm only yields |tr|^2 with exponential sampling overhead, so the headline O(log N) trace claim does not hold end-to-end.","tokens_in":16573,"tokens_out":2612,"would_cite":false,"duration_ms":23961,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper constructs quantum circuits that add rows, swap rows, and compute traces of amplitude-encoded matrices in $O(\\log N)$ gates, and transpose in $O(m)$ gates, using Toffoli gates, single-qubit operations, and ancilla measurements.","keywords":["quantum algorithm","matrix operation","row addition","row swapping","matrix trace","matrix transpose","Toffoli gate","ancilla measurement"],"falsifier":"For a known $2\\times 2$ matrix, prepare the input state $|\\Psi_1\\rangle$, run the row-addition circuit, and compare the measured ancilla success probability and the amplitudes of the post-selected state with the formulas $G^2/8$ and $(a_{lj}+a_{kj})/G$; a reproducible mismatch would show the algorithm does not realize the claimed transformation.","tokens_in":15540,"feed_emoji":"⚛️","tokens_out":13493,"duration_ms":118552,"temperature":0.7,"pith_summary":"The paper tries to establish that basic matrix operations—adding one row to another, swapping two rows, computing the trace, and transposing—can be performed directly on a matrix encoded in the amplitudes of a quantum pure state, using only multi-qubit Toffoli gates, single-qubit gates, and measurements of ancilla qubits. If correct, the gate counts for the row operations and the trace grow as $O(\\log N)$ as the number of rows doubles, and transposition costs $O(m)$ swap gates with unit success probability, making these building blocks inexpensive inside larger quantum algorithms. The algorithms work by labeling the useful part of the encoded state with ancillas, swapping row labels where needed, superposing terms with Hadamard gates, and projecting out the unwanted terms. The complexity counts start from an already-prepared normalized input state, so the logarithmic scaling is a claim about the transformation gates themselves, not about state preparation or final readout.","feed_headline":"Row operations and trace run in logarithmic quantum gates","feed_subtitle":"Amplitude-encoded matrices get row operations and traces in O(log N) gates; transpose is certain.","key_machinery":"The carrying object is the pure-state encoding $|\\Psi_1\\rangle=\\sum_{ij}a_{ij}|i\\rangle|j\\rangle$, in which matrix entries are probability amplitudes indexed by row and column registers. The mechanism is a four-part recipe: ancilla qubits with controlled operations label the amplitudes that should survive; controlled-SWAP gates move labels or rows into the right places; Hadamard gates superpose the labels; and a projective measurement on the ancillas discards redundant components. The complexity bound rests on the multi-qubit Toffoli gate, a controlled-NOT with many control qubits, and on the fact that such a gate can be decomposed into $O(n)$ ordinary Toffoli gates when there are $n$ control qubits, which turns the needed $n$-qubit controls into $O(n)$-gate operations.","core_discovery":"On the paper's own terms, the discovery is that unitary control plus ancilla measurement is enough to realize four matrix operations on an amplitude-encoded state. For row addition, an auxiliary register $|\\Psi_2\\rangle=(|k\\rangle+|l\\rangle)/\\sqrt{2}$ labels the source row; controlled operators mark the term where the row register is $|k\\rangle$, a controlled-SWAP exchanges the row register with the source label, a Hadamard superposes the labels, and projecting the ancillas onto $|000\\rangle$ yields an output state whose amplitudes are $(a_{lj}+a_{kj})/G$ on the target row, normalized by $G$. Row swapping uses the same construction with three labeled terms and has success probability $1/24$. Trace is obtained by marking the diagonal terms where the row and column registers agree, applying a Hadamard transform to all registers, and reading the diagonal sum from the amplitude of the projected state. Transpose is a single SWAP between the column register and an ancilla register, so it succeeds with probability 1. The central complexity claim is that the multi-qubit controls involved decompose into $O(n)=O(\\log N)$ Toffoli gates, making the row operations and trace logarithmic in the row count and transpose linear in $m$.","pith_inferences":["Because the paper counts only gates applied after the amplitude-encoded input state exists, an end-to-end logarithmic claim would also require state preparation and readout costs that grow at most polylogarithmically; the paper explicitly leaves those costs out of scope.","The same label, swap, superpose, and project recipe is likely to generalize to other linear operations on amplitude-encoded data, such as linear combinations of rows with coefficients or column versions of the same elementary transformations.","The trace algorithm's success probability $|\\sum_i a_{ii}|^2/2^{3n}$ implies that, without amplitude amplification, estimating the trace to fixed precision would require many repetitions, so the practical cost includes a dimension-dependent factor despite the logarithmic gate count."],"forward_implications":["For an $N\\times M$ matrix with $N=2^n$, the row-addition and row-swapping circuits use $O(\\log N)$ gates after the input state exists, so their gate counts grow logarithmically as the number of rows doubles.","The transpose circuit uses $O(m)$ SWAP gates and succeeds with probability 1, so transposition is deterministic once the amplitude-encoded input state is available.","The row-addition success probability $G^2/8$ and the row-swap success probability $1/24$ do not depend on matrix size, while the trace success probability $|\\sum_i a_{ii}|^2/2^{3n}$ decays with dimension; the paper notes that amplitude amplification can be used to boost these probabilities.","The outputs remain pure states with the desired transformed matrix held in their amplitudes, so they can feed directly into later quantum computations without a classical readout of every entry."],"supporting_citations":[{"why":"Supplies the foundational unitary-transformation-and-ancilla-measurement construction that this paper extends to row operations, trace, and transpose.","marker":"[20]"},{"why":"Gives the decomposition of an operator with n control qubits into O(n) Toffoli gates, which is what produces the O(log N) complexity.","marker":"[23]"},{"why":"Provides prior quantum algorithms for matrix operations and linear systems that frame the problem this paper addresses.","marker":"[19]"},{"why":"Introduces the pure-state row encoding of matrices into independent quantum subsystems that the algorithms assume as input.","marker":"[21]"},{"why":"Extends the encoding method to unnormalized matrices, which is relevant to the amplitude-encoding premise of the algorithms.","marker":"[22]"}],"fun_headline_variants":["Row ops and trace in O(log N) gates via ancilla measurement","Logarithmic quantum gates for matrix row ops and trace","Matrix transpose is certain; row ops and trace are O(log N)","Ancilla measurement enables logarithmic matrix operations","Quantum row ops and trace hit O(log N) gate count"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithms assume the matrix is already available as a normalized pure state with its entries as amplitudes, and the logarithmic gate counts include only the operations applied after that state exists; if preparing or reading out that state costs more than logarithmically in the matrix size, the end-to-end cost is not logarithmic.","fun_headline_variants_meta":{"raw":{"variants":["Row ops and trace in O(log N) gates via ancilla measurement","Logarithmic quantum gates for matrix row ops and trace","Matrix transpose is certain; row ops and trace are O(log N)","Ancilla measurement enables logarithmic matrix operations","Quantum row ops and trace hit O(log N) gate count"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000578,"raw_usage":{"total_tokens":2678,"prompt_tokens":852,"completion_tokens":1826,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":468,"completion_tokens_details":{"reasoning_tokens":1742}},"tokens_in":468,"tokens_out":1826,"duration_ms":11568,"temperature":1.0,"reasoning_tokens":1742,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:36:35.751684+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a known $2\\times 2$ matrix, prepare the input state $|\\Psi_1\\rangle$, run the row-addition circuit, and compare the measured ancilla success probability and the amplitudes of the post-selected state with the formulas $G^2/8$ and $(a_{lj}+a_{kj})/G$; a reproducible mismatch would show the algorithm does not realize the claimed transformation.","supporting_citations":[{"cited_title":"Algorithms for quantum computation: discrete logarithms and factoring","cited_arxiv_id":null,"evidence_quote":"Supplies the foundational unitary-transformation-and-ancilla-measurement construction that this paper extends to row operations, trace, and transpose."},{"cited_title":"Quantum algorithm for linear systems of equations","cited_arxiv_id":null,"evidence_quote":"Gives the decomposition of an operator with n control qubits into O(n) Toffoli gates, which is what produces the O(log N) complexity."},{"cited_title":"Quantum theory, the Church–Turing principle and the universal quantum computer","cited_arxiv_id":null,"evidence_quote":"Provides prior quantum algorithms for matrix operations and linear systems that frame the problem this paper addresses."},{"cited_title":"Polynomialtime algorithms for prime factor- ization and discrete logarithms on a quantum computer","cited_arxiv_id":null,"evidence_quote":"Introduces the pure-state row encoding of matrices into independent quantum subsystems that the algorithms assume as input."},{"cited_title":"A fast quantum mechanical algorithm for database search","cited_arxiv_id":null,"evidence_quote":"Extends the encoding method to unnormalized matrices, which is relevant to the amplitude-encoding premise of the algorithms."}],"review_version":1}