{"id":"15c63555-0fbe-49d4-9b54-414590c27359","arxiv_id":"2412.19090","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A quantum Gram-Schmidt and QR decomposition algorithm is proposed with O(N^2) claimed complexity, but the algorithm as written cannot be implemented because it destroys the state it needs to keep.","lead":"This paper proposes quantum algorithms for Gram-Schmidt orthogonalization and matrix QR decomposition, claiming an O(N^2) query complexity that would beat classical O(N^3) and prior quantum approaches. The algorithms use quantum phase estimation to project out known basis directions, but they contain unresolved implementation gaps, including a destructive readout step and unprovided oracles for intermediate vectors.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing preparation oracles for newly generated basis states make the updated Hamiltonian in Algorithm 3 unimplementable; the claimed O(M^2/epsilon) query bound is unsupported.","rationale":"The reader's weakest assumption identifies exactly the gap I find: the algorithm assumes it can continue updating the Hamiltonian with newly produced basis states without providing or costing the preparation unitaries those states require. My read agrees with that assessment. The central claim would need, for every generated basis state, a coherent unitary preparation oracle with a known implementation cost. The numerical simulations do not settle this issue because they are classical simulations that internally have the vectors psi available; they do not instantiate the oracle model of Lemma 1. This is not a disagreement with consensus; it is an internal gap in the algorithm as written. The LCU subroutine requires explicit V and G operators, and no such operators are specified for the updated term. Because this gap blocks execution of the core loop, the claimed polynomial speedup is not established. The secondary Lemma 6 inconsistency further weakens the epsilon dependence in Theorem 2, but it is not the primary reason for rejecting the paper. I would keep the reader's REJECT verdict unchanged. If the authors can supply an explicit state-preparation method for each |u_{k+1}> within the counted query budget, the verdict could be revisited, but as written the central complexity claim is unsupported.","tokens_in":27957,"tokens_out":7260,"duration_ms":77966,"concrete_test":"Fix k=1 and attempt to construct explicitly the LCU block-encoding oracles (PREPARE and SELECT) for H_2 = |u_1> is the state obtained after the first postselection in Algorithm 3. Enumerate the elementary gates and oracles needed to implement a unitary U_psi with U_psi|0> = |psi>, starting only from O_{a_1}, O_{a_2}, and the QPE circuit. If the only options are full state tomography or a new oracle U_psi, count their cost and re-derive Theorem 1; if the total exceeds O(M^2/epsilon (log 1/epsilon)^2), the central complexity claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single most load-bearing concern is the implementation of the updated Hamiltonian in Algorithm 3, step 13. The central loop requires simulating H_k = sum_{n=1}^k |u_n> from |0>. The only preparation oracles supplied are for the input vectors a_m. When step k produces a new state |u_{k+1}>, Algorithm 3 line 11 reads it out in the computational basis, which collapses it; no oracle or coherent preparation procedure for |u_{k+1}> is given, and no tomography cost is counted in Theorem 1. Consequently, the updated H in step 13 cannot be block-encoded as specified, so the repeated QPE steps cannot be executed and the claimed O(M^2/epsilon (log 1/epsilon)^2) query complexity does not follow. A secondary inconsistency reinforces this: Theorem 2's proof uses the QIPE cost as O((1/epsilon) log(M^2/epsilon)) although Lemma 6 gives O((1/epsilon^2) log(1/delta)), so the stated epsilon scaling is also unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes quantum algorithms for vector-set orthogonal normalization and matrix QR decomposition, built from a one-qubit quantum phase estimation circuit applied to the Hamiltonian H_k = sum_{n<=k} |u_n> from |0> for each rank-one term |u_n>= 2, the states |u_n> are outputs of the algorithm itself: in step 10 the second register is measured, which collapses |psi>, and step 11 reads it out in the computational basis, yielding at most one classical bit string. No coherent preparation procedure or QRAM-loading routine for |psi> is given, and no cost is charged for reconstructing the amplitudes. Consequently, the block-encoding of H_k for k >= 2 is not realized, the repeated QPE steps cannot be executed as written, and the query complexity claimed in Theorem 1 is not supported.","section":"§IV.A, Algorithm 3 steps 10-13 and Eqs. (6)-(7)"},{"comment":"The algorithm's output S' is a set of classical vectors, and step 11 reads out |psi> in the computational basis. A single computational-basis measurement does not determine the amplitudes of |psi>; producing a classical vector psi satisfying u_{t1}^dagger u_{t2} = O(epsilon) requires state tomography or amplitude estimation, whose cost is not included in Eqs. (23)-(26). For an N-dimensional state this cost is at least Omega(N/epsilon^2) per output vector, so the abstract's O(N^2 poly(log N)) scaling is not justified for the problem as stated, where the vectors themselves must be output.","section":"§IV.B, Theorem 1 and Algorithm 3 step 11"},{"comment":"The proof of Theorem 2 states in Eq. (43) that each inner-product estimate costs O((1/epsilon) log(M^2/epsilon)) oracle calls, and Eq. (44) totals this as O((M^2/epsilon) log(M^2/epsilon)). This contradicts Lemma 6, which gives O((1/epsilon^2) log(1/delta)) calls per estimate (Eq. (32)). Substituting delta = epsilon/M^2 gives O((1/epsilon^2) log(M^2/epsilon)) per entry and O((M^2/epsilon^2) log(M^2/epsilon)) total, not the expression in Eq. (44). The epsilon-scaling in the main theorem is therefore inconsistent with the paper's own subroutine analysis, and the query complexity in Eq. (38) is unsupported.","section":"§V.B, proof of Theorem 2, Eqs. (43)-(44) versus Lemma 6"},{"comment":"The correctness and success-probability proofs of Lemmas 4 and 5 assume a uniform prior distribution over p = 1 - sum_n ||^2, the probability of measuring 0. This p is an input-dependent parameter, and the paper provides no worst-case argument. The posterior calculation with a uniform prior only shows that repeated failures are evidence of linear dependence under that Bayesian assumption; it does not establish a worst-case success probability for arbitrary input sets. Since Lemma 4 is the basis for the completeness claim span{a_1,...,a_M} = span{u_1,...,u_T}, this is a load-bearing gap in the correctness proof.","section":"Appendix B3 and B4, Eqs. (B13)-(B15) and (B44)"}],"minor_comments":[{"comment":"Line 23 returns 'Q, R' although the algorithm computes approximations tilde Q and tilde R; the return statement should use the tilde notation consistently. In line 21, the formula for tilde R_{m1 m1} uses the exact vectors q_{m2}, whereas only the approximate vectors tilde q_{m2} are available in the algorithm.","section":"Algorithm 4, line 23 and line 21"},{"comment":"The discussion of QR iteration for eigenvalues claims that replacing the classical QR decomposition by the quantum one reduces the total complexity, but it does not analyze the number of QR iterations, the classical readout of the intermediate matrix between iterations, or the cost of converting the quantum output into the next input. The claim 'the computational complexity of the quantum QR iteration algorithm is also less than the classical one' is therefore not established.","section":"§VI.C"},{"comment":"The numerical validations appear to be classical matrix computations with a small rounding term added, not simulations of the QPE circuit, measurements, or state-readout steps. The text should state explicitly what is simulated; as written, Figures 3 and 6 do not provide evidence that the quantum circuit in Fig. 2 behaves as claimed.","section":"§IV.C and §V.C"},{"comment":"In the proof of Lemma 2, the last displayed equality writes lambda_max(A^dagger A) on both factors; it should be lambda_max(A^dagger A) lambda_max(B^dagger B). This is a typo, but it obscures the argument.","section":"Appendix B1, Eq. (B1)"},{"comment":"The phrase 'conditional number' should be 'condition number', and 'Hamilonian' appears in the caption of Fig. 2; these should be corrected.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"I see the central difficulty as conceptual rather than local. The algorithm produces each new basis state by measurement, but then needs that same state as a coherently preparable object for the next qubitization step; the manuscript supplies no mechanism and charges no cost for this. Combined with the unaccounted tomography cost and the Lemma 6/Theorem 2 inconsistency, the claimed polynomial speedup is not supported by the presented analysis. I do not see a modest revision that would preserve the main claims; a substantially different algorithm or a much more careful resource accounting would be required."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the core idea—use QPE with H = sum |u_n> onto the orthogonal complement—is genuinely a fresh way to think about quantum Gram-Schmidt. The single-ancilla QPE derivation and the Lemma 3 circuit error bound are clean, and the authors are honest about the 1/epsilon^2 inner-product estimation cost.\n\nThe problem is that as written, the algorithm cannot execute its own loop. Algorithm 3 line 10 measures the second register after a successful first-register measurement; line 11 reads out the result in the computational basis. That is a destructive readout. Then line 13 updates H by adding |psi> from |0>. No such oracle is given for any u_k with k>1; the only preparation oracle supplied is for the input vectors a_m. The complexity analysis in Theorem 1 counts calls to the a_m oracle and to the qubitization operators, but the cost of producing or storing coherent copies of the output states is never accounted for. The stress-test note is correct: this is the load-bearing assumption, and it fails.\n\nThe secondary inconsistency is also real. Theorem 2's proof uses O(1/epsilon log(M^2/epsilon)) per inner-product estimate, but Lemma 6 (correctly, for this SWAP-test style scheme) gives O(1/epsilon^2 log(1/delta)). So the claimed epsilon scaling in the QR theorem is off by a power.\n\nThe numerical validation is also weaker than it looks. It appears to be a classical emulation of the idealized Gram-Schmidt process with extra rounding, not an execution of the QPE circuit with measurement collapse and Hamiltonian simulation error. It therefore does not test the parts of the algorithm that are in question.\n\nWhat is good: the projection-filter idea is worth keeping, and for k=1 it actually works. If the authors supplied coherent preparation oracles for the intermediate states, or kept a second copy of each |psi> and counted that cost, the complexity analysis could be redone. As it stands, the central claim is unsupported.\n\nI would not send this version to referees; I would send it back with a request to fix the oracle model and the epsilon scaling. If they do, the idea deserves a serious look.","headline":"The QPE projection filter is a fresh angle on quantum Gram-Schmidt, but the algorithm destroys the states it needs for the next step, so the claimed O(N^2) speedup is unsupported.","tokens_in":28754,"tokens_out":5577,"would_cite":false,"duration_ms":51778,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims quantum Gram-Schmidt and QR-decomposition algorithms with query complexity $O(M^2/\\epsilon\\,(\\log 1/\\epsilon)^2)$ and $O(M^2\\log M/\\epsilon\\,(\\log 1/\\epsilon)^2)$, producing $\\epsilon$-approximate $Q$ and $R$.","keywords":["quantum algorithm","Gram-Schmidt orthogonalization","QR decomposition","quantum phase estimation","qubitization","QRAM","query complexity","polynomial speedup"],"falsifier":"Run Algorithm 3 for a random full-rank 8x8 matrix with $\\epsilon=10^{-4}$ in a state-vector simulator, counting oracle calls only to the input preparation oracle $O_{a_m}$. If implementing the updated Hamiltonian at step 13 requires an explicit circuit that prepares $|u_{k+1}\\rangle$ from $|0\\rangle$, the observed oracle count will exceed $O(M^2/\\epsilon\\,(\\log 1/\\epsilon)^2)$; a complete circuit for that preparation step is the concrete object that would settle the claim.","tokens_in":27764,"feed_emoji":"⚛️","tokens_out":10938,"duration_ms":111773,"temperature":0.7,"pith_summary":"This paper proposes two quantum algorithms: one for turning a set of vectors into an orthonormal basis (Gram-Schmidt orthogonalization) and one for computing matrix QR decompositions. The central claim is that both achieve polynomial acceleration over the best-known classical and quantum algorithms, summarized as $O(N^2\\mathrm{poly}(\\log N))$ scaling in the system dimension, with theorem-level query counts $O(M^2/\\epsilon\\,(\\log 1/\\epsilon)^2)$ for orthogonalization and $O(M^2\\log M/\\epsilon\\,(\\log 1/\\epsilon)^2)$ for QR decomposition. The algorithms run single-qubit quantum phase estimation on a projector Hamiltonian that grows as each new basis vector is found, using qubitization for simulation and QRAM for input preparation. If the claims are right, large-scale orthogonalization, least-squares fitting, linear systems, and eigenvalue problems would all inherit a polynomial speedup.","feed_headline":"Quantum Gram-Schmidt drops to O(N^2 poly(log N))","feed_subtitle":"Phase estimation on a growing projector yields near-quadratic QR decomposition and orthonormal bases.","key_machinery":"The machine is single-qubit quantum phase estimation on the growing projector $H=\\sum_{n=1}^k |u_n\\rangle\\langle u_n|$, simulated through qubitization with the linear-combination-of-unitaries oracle. Because $H$ has eigenvalues 0 and 1, one control qubit and evolution time $t=\\pi$ are enough: the $|1\\rangle$ branch collects the part of the input already in the current span, and the $|0\\rangle$ branch is the orthogonal complement to be read out as the next basis vector. Qubitization supplies $e^{-iHt}$ with $O(\\alpha t+\\log(1/\\epsilon_0))$ queries to the LCU oracles, and QRAM preparation supplies each input state $|a_m\\rangle$ in $O(\\log N)$ time.","core_discovery":"The central discovery is that Gram-Schmidt can be implemented quantumly with a single control qubit and a Hamiltonian that is the projector onto the already-constructed subspace. Running QPE on $H=\\sum_{n=1}^k |u_n\\rangle\\langle u_n|$ with $t=\\pi$ entangles the control qubit so that the component of $|a_{k+1}\\rangle$ inside the current span is flagged by $|1\\rangle$ and the orthogonal complement by $|0\\rangle$. Measuring $|0\\rangle$ on the control collapses the data register to $|u_{k+1}\\rangle \\propto |a_{k+1}\\rangle - \\sum_{n=1}^k \\langle u_n|a_{k+1}\\rangle |u_n\\rangle$, exactly the Gram-Schmidt update. The paper claims that repeating this with the enlarged Hamiltonian $H\\leftarrow H+|u_{k+1}\\rangle\\langle u_{k+1}|$ yields an orthonormal set spanning the input vectors, with $O(M^2/\\epsilon\\,(\\log 1/\\epsilon)^2)$ queries. For QR decomposition it claims the same loop produces an $\\epsilon$-approximation to $Q$, and a two-circuit inner-product estimator fills $R$ entrywise, all within $O(M^2\\log M/\\epsilon\\,(\\log 1/\\epsilon)^2)$ queries.","pith_inferences":["A natural extension the authors do not spell out is to use the same one-control-qubit construction as a rank-revealing subroutine: when repeated runs all yield outcome 1, the posterior calculation in the paper's Appendix B gives a statistical certificate that the next vector lies in the current span, so the algorithm can return the numerical rank along with the basis.","The paper notes that amplitude estimation could replace the inner-product estimator's $O(1/\\epsilon^2)$ sample count by $O(1/\\epsilon)$; a further inference is that the same amplification idea could be applied to the QPE zero-outcome probability in Theorem 1, lowering the query count's dependence on $\\epsilon$ as well.","Since the algorithm reads out each basis vector in the computational basis, a concrete testable extension is to couple it with a classical controller that decides whether to continue the loop based on measured outcomes; the loop structure in Algorithm 3 is already a hybrid quantum-classical procedure."],"forward_implications":["Orthogonalization of $M$ vectors in $N$ dimensions would use $O(M^2/\\epsilon\\,(\\log 1/\\epsilon)^2)$ oracle queries and only $\\lceil\\log_2 M\\rceil+\\lceil\\log_2 N\\rceil+3$ qubits, beating the previous quantum Gram-Schmidt bound for full-rank inputs.","QR decomposition of a full-rank $N\\times M$ matrix would use $O(M^2\\log M/\\epsilon\\,(\\log 1/\\epsilon)^2)$ queries, improving the previous quantum complexity that scaled as $O(N^{2.5}\\mathrm{poly}\\log N/\\epsilon^2)$.","The output is a classical $\\epsilon$-approximation: $\\|\\tilde q_m-q_m\\|=O(\\epsilon)$ and $|\\tilde R_{m_1m_2}-R_{m_1m_2}|=O(\\epsilon\\|A\\|)$, so downstream classical processing can use $\\tilde Q$ and $\\tilde R$ directly.","Linear least-squares fitting, linear-equation solving, and QR-iteration eigenvalue computation would inherit the speedup, since each uses QR decomposition as its expensive subroutine.","The algorithm is rank-revealing in the linearly dependent case: repeated measurements that never give outcome 0 certify, with probability larger than $1-\\epsilon$, that the next input vector lies in the current span."],"supporting_citations":[{"why":"Supplies the previous quantum Gram-Schmidt algorithm whose $O(r^{27}\\kappa^{14}r)$ complexity the new orthogonalization result claims to improve.","marker":"[30]"},{"why":"Supplies the previous quantum QR-decomposition algorithm with $O(N^{2.5}\\mathrm{poly}\\log N/\\epsilon^2)$ complexity, the comparison target for the new QR bound.","marker":"[32]"},{"why":"Supplies the qubitization Hamiltonian-simulation method, stated as Lemma 1, used to implement the controlled $e^{-iHt}$ operations in both algorithms.","marker":"[34]"},{"why":"Supplies the quantum phase estimation framework and circuit notation on which both algorithms are built.","marker":"[17]"},{"why":"Supplies the QRAM model used to prepare amplitude-encoded input states $|a_m\\rangle$ in $O(\\log N)$ time.","marker":"[31]"},{"why":"Supplies the inner-product estimation circuit that the paper adapts and whose query complexity it proves in Lemma 6.","marker":"[38]"}],"fun_headline_variants":["Quantum Gram-Schmidt cuts complexity to O(N^2 poly(log N))","Faster quantum QR and orthonormalization at O(N^2 poly(log N))","Quantum phase estimation yields quadratic speedup for Gram-Schmidt","Near-quadratic speedup for QR decomposition on quantum computers","O(N^2 poly(log N)) quantum Gram-Schmidt and QR"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that after each new vector is found, the algorithm can update its projector $H\\leftarrow H+|u_{k+1}\\rangle\\langle u_{k+1}|$ and continue, without counting any extra work needed to load the freshly found vector into the quantum memory; only the original input vectors have a preparation oracle.","fun_headline_variants_meta":{"raw":{"variants":["Quantum Gram-Schmidt cuts complexity to O(N^2 poly(log N))","Faster quantum QR and orthonormalization at O(N^2 poly(log N))","Quantum phase estimation yields quadratic speedup for Gram-Schmidt","Near-quadratic speedup for QR decomposition on quantum computers","O(N^2 poly(log N)) quantum Gram-Schmidt and QR"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001291,"raw_usage":{"total_tokens":5300,"prompt_tokens":1002,"completion_tokens":4298,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":618,"completion_tokens_details":{"reasoning_tokens":4202}},"tokens_in":618,"tokens_out":4298,"duration_ms":32131,"temperature":1.0,"reasoning_tokens":4202,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:58:28.371261+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 3 for a random full-rank 8x8 matrix with $\\epsilon=10^{-4}$ in a state-vector simulator, counting oracle calls only to the input preparation oracle $O_{a_m}$. If implementing the updated Hamiltonian at step 13 requires an explicit circuit that prepares $|u_{k+1}\\rangle$ from $|0\\rangle$, the observed oracle count will exceed $O(M^2/\\epsilon\\,(\\log 1/\\epsilon)^2)$; a complete circuit for that preparation step is the concrete object that would settle the claim.","supporting_citations":[{"cited_title":"Realization of a scalable shor algorithm,","cited_arxiv_id":null,"evidence_quote":"Supplies the previous quantum Gram-Schmidt algorithm whose $O(r^{27}\\kappa^{14}r)$ complexity the new orthogonalization result claims to improve."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the previous quantum QR-decomposition algorithm with $O(N^{2.5}\\mathrm{poly}\\log N/\\epsilon^2)$ complexity, the comparison target for the new QR bound."},{"cited_title":"Quantum algorithm for systems of linear equations with exponentially improved dependence on precision,","cited_arxiv_id":null,"evidence_quote":"Supplies the qubitization Hamiltonian-simulation method, stated as Lemma 1, used to implement the controlled $e^{-iHt}$ operations in both algorithms."},{"cited_title":"A modified learning algorithm for the multilayer neural network with multi-valued neurons based on the complex QR decomposition,","cited_arxiv_id":null,"evidence_quote":"Supplies the quantum phase estimation framework and circuit notation on which both algorithms are built."},{"cited_title":"Algorithms for quantum computation: discrete logarithms and factoring,","cited_arxiv_id":null,"evidence_quote":"Supplies the QRAM model used to prepare amplitude-encoded input states $|a_m\\rangle$ in $O(\\log N)$ time."},{"cited_title":"Quantum boltzmann machine,","cited_arxiv_id":null,"evidence_quote":"Supplies the inner-product estimation circuit that the paper adapts and whose query complexity it proves in Lemma 6."}],"review_version":1}