Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup

T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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$.

desk verdict 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. read the letter →

arxiv 2412.19090 v2 pith:XQEXIKF3 submitted 2024-12-26 quant-ph

Zi-Ming Li , Yu-xi Liu This is my paper · ORCID
classification quant-ph MSC 68Q1281P68
keywords quantumalgorithmGram-SchmidtorthogonalizationQRdecompositionphaseestimationqubitizationQRAMquerycomplexitypolynomialspeedup
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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><u_n|. Conditioning on the first-register outcome 0 is claimed to produce a residual state orthogonal to the previously constructed basis states; Algorithm 3 iterates this construction, and Algorithm 4 extends it to QR decomposition using a quantum inner-product estimation subroutine. The authors claim query complexity O(M^2/epsilon log^2(1/epsilon)) for orthogonalization and O(M^2 log M / epsilon log^2(1/epsilon)) for QR decomposition, with an abstract-level claim of O(N^2 poly(log N)) scaling in the system dimension N, and they include classical numerical demonstrations and several application vignettes.

Significance. If the central claims were supported, the results would constitute a substantial polynomial speedup over classical Gram-Schmidt and over the earlier quantum algorithms cited in the paper, and the algorithmic idea of using QPE to extract the orthogonal complement of a growing subspace is natural and worth investigating. The paper is clearly organized, provides explicit pseudocode, and makes an effort to include an error analysis. However, the core iterative loop as written destroys the newly generated state before it is needed for the next Hamiltonian update, no preparation oracle for the intermediate basis states is supplied, and the stated complexity omits the cost of classical readout/tomography. In addition, the proof of Theorem 2 uses an epsilon-dependence for inner-product estimation that contradicts the paper's own Lemma 6. These are load-bearing gaps, not presentation issues, so the significance of the claimed speedup cannot be judged from the manuscript as it stands.

major comments (4)
  1. [§IV.A, Algorithm 3 steps 10-13 and Eqs. (6)-(7)] The updated Hamiltonian H <- H + |psi><psi| cannot be implemented as specified. The qubitization LCU construction in Eqs. (6)-(7) requires a unitary U_n that prepares |u_n> from |0> for each rank-one term |u_n><u_n| = (1/2)(I + U_n Z U_n^dagger). The only preparation oracle introduced is O_{a_m} for the input vectors. For 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.
  2. [§IV.B, Theorem 1 and Algorithm 3 step 11] 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.
  3. [§V.B, proof of Theorem 2, Eqs. (43)-(44) versus Lemma 6] 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.
  4. [Appendix B3 and B4, Eqs. (B13)-(B15) and (B44)] The correctness and success-probability proofs of Lemmas 4 and 5 assume a uniform prior distribution over p = 1 - sum_n |<u_n|a_{k+1}>|^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.
minor comments (5)
  1. [Algorithm 4, line 23 and line 21] 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.
  2. [§VI.C] 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.
  3. [§IV.C and §V.C] 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.
  4. [Appendix B1, Eq. (B1)] 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.
  5. [Throughout] The phrase 'conditional number' should be 'condition number', and 'Hamilonian' appears in the caption of Fig. 2; these should be corrected.

Circularity Check

1 steps flagged · score 7.0 of 10

Algorithm 3's updated Hamiltonian requires oracles for its own output states, so the claimed O(M^2/epsilon) query bound is circular.

  1. self definitional [Algorithm 3, steps 9-13; Sec. IV A, Eqs. (6)-(7), Lemma 1]
    "if x = 0 then measure 2nd register and get |ψ⟩; readout |ψ⟩ in computational basis as ψ; S′ ← S′ ∪ {ψ}; H ← H + |ψ⟩⟨ψ|; break; ... The Hamiltonian H to obtain u_{k+1} can be chosen as H = Pk n=1 |un⟩⟨un|, which can be simulated as shown in Eq. (6) and Eq. (7) by the qubitization."

    By Eqs. (6)-(7), qubitization of H = sum_n |u_n><u_n| requires operators V and G built from unitaries that prepare each |u_n>. The only preparation oracle supplied is O_{a_m} for the input vectors; for n>1 the |u_n> are generated inside Algorithm 3 by measuring the second register and then reading out a collapsed computational-basis state. No unitary preparing the freshly generated |u_{k+1}> is constructed, and no tomography or QRAM-loading cost is counted in Theorem 1. The next QPE round therefore assumes free access to the very states the algorithm is supposed to produce: H is defined using the output state, while the cost of having that output available as an oracle is omitted.

full rationale

The central complexity claim is not self-contained: the updated Hamiltonian in Algorithm 3 step 13 can only be block-encoded via Eq. (7) if the algorithm already possesses coherent preparation unitaries for every generated basis state, yet the paper only supplies oracles for the input vectors a_m. This makes the main-loop analysis circular by construction. No load-bearing self-citation chain is present; the qubitization lemma [34] is an external result and is not itself circular. I also note a non-circular correctness gap that reinforces the unsupported bound: Theorem 2's proof invokes Lemma 6 as O(1/epsilon log(M^2/epsilon)) while Lemma 6 gives O(1/epsilon^2 log(1/delta)), and the computational-basis readout in Algorithm 3 destroys the coherent |psi> needed for the next H update. These issues are correctness risks rather than additional circularity steps, and they do not change the primary finding that the claimed query complexity assumes the algorithm's outputs are already available as oracles.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard quantum subroutines (QPE, qubitization) plus two unstated assumptions: availability of preparation unitaries for intermediate vectors, and a uniform Bayesian prior for the dependence test. The chosen constants t=pi and epsilon_0=epsilon^4 are hand-set but do not constitute data fitting.

free parameters (2)
  • t = pi
    Evolution time in QPE is fixed to pi so that eigenvalue 1 maps to |1> and eigenvalue 0 maps to |0>; this is a chosen algorithmic constant.
  • epsilon_0 = epsilon^4
    Hamiltonian simulation error tolerance is set to epsilon^4 in Algorithm 3 to make the orthogonality bound in Lemma 5 scale as O(epsilon). This is a chosen precision allocation.
assumptions (5)
  • standard math Quantum phase estimation with a single control qubit correctly maps eigenvalue 1 to |1> and eigenvalue 0 to |0> for evolution time pi.
    Used in Section IV A and Appendix A; this is standard QPE.
  • domain assumption Qubitization and LCU can simulate H = sum |u_n><u_n| with query complexity O(k t + log(1/epsilon_0)) given access to state-preparation oracles for each |u_n>.
    Invoked via Lemma 1 from [34]; depends on availability of oracles that the paper does not supply.
  • domain assumption QRAM can prepare amplitude-encoded states |a_m> in O(log N) time.
    Used in Eq. (5) and throughout; a standard but nontrivial hardware assumption.
  • ad hoc to paper Uniform prior over the overlap probability p in the linear dependence test.
    Appendix B3 assumes p is uniform on [0,1] to justify the (1/epsilon) ln(1/epsilon) repetition count; no justification for this prior is given.
  • ad hoc to paper A unitary preparing each newly generated |u_k> is available for subsequent Hamiltonian updates.
    Required by Algorithm 3 step 13 and Eq. (14) but never specified; without it the algorithm is unimplementable.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup." pith.science (2026). https://pith.science/paper/XQEXIKF3

@misc{pith2026241219090,
  author       = {Pith},
  title        = {Pith review of: Quantum Algorithm for Vector Set Orthogonal Normalization and Matrix QR Decomposition with Polynomial Speedup},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XQEXIKF3}},
  note         = {Machine review of arXiv:2412.19090}
}
abstract

Vector set orthogonal normalization and matrix QR decomposition are fundamental problems in matrix analysis with important applications in many fields. We know that Gram-Schmidt process is a widely used method to solve these two problems. However, the existing methods, including Gram-Schmidt process have problems of high complexity, scaling $O(N^3)$ in the system dimension $N$, which leads to difficulties when calculating large-scale or ill-conditioned problems. With the development of quantum information processing, a series of quantum algorithms have been proposed, providing advantages and speedups over classical algorithms in many fields. In this paper, we propose quantum algorithms to solve these two problems based on the idea of Gram-Schmidt process and quantum phase estimation. The complexity of proposed quantum algorithms is also theoretically and numerically analyzed. We find that our algorithms provide polynomial acceleration over the best-known classical and quantum algorithms on these two problems, scaling $O(N^2\mathrm{poly}(\log N))$ in the dimension $N$ of the system.

Figures

Figures reproduced from arXiv: 2412.19090 by the authors.

Figure 1
Figure 1. FIG. 1. Quantum circuit for QPE [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Circuit constructing the ( [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3. (a) Loss of orthogonality for different dimensions [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: FIG. 4. Quantum circuit for estimating Re [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5. Quantum circuit for estimating Im [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6. (a) CGS is for classcial Gram-Schmit process based [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7. Fitting 10 generated data points (the red triangles) with quantum QR decomposition algorithm based least squares [PITH_FULL_IMAGE:figures/full_fig_p013_7.png]
Figure 8
Figure 8. Figure 8: FIG. 8. The logarithmic relative error [PITH_FULL_IMAGE:figures/full_fig_p014_8.png]
Figure 9
Figure 9. Figure 9: FIG. 9. The electric potential is plotted as a two-dimensional heatmap. The black arrows represent the electric field intensity, [PITH_FULL_IMAGE:figures/full_fig_p015_9.png]
Figure 10
Figure 10. Figure 10: FIG. 10. (a) Convergence of few lowest eigenvalues of Ising [PITH_FULL_IMAGE:figures/full_fig_p016_10.png]
Figure 11
Figure 11. Figure 11: FIG. 11. Quantum circuit for quantum phase estimation [PITH_FULL_IMAGE:figures/full_fig_p017_11.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Quantum complexity phase transition in fermionic quantum circuits

    quant-ph 2025-07 conditional novelty 5.0 of 10

    A measure of operator spreading, Krylov complexity, undergoes a phase transition in quantum percolation: at the percolation threshold for free fermions, but at a lower threshold p=1/4 for 1D interacting fermions.

Reference graph

Works this paper leans on

55 extracted references · 54 canonical work pages · cited by 1 Pith paper

  1. [1]

    u† t1 ut2 = δt1t2 , ∀t1, t2 = 1, 2, · · ·, T

    work page

  2. [2]

    Matrix QR Decomposition Let A ∈ CN ×M be an arbitrary matrix with full rank satisfying N ≥ M

    span{a1, a2, · · ·, aM } = span{u1, u2, · · ·, uT } Problem 2. Matrix QR Decomposition Let A ∈ CN ×M be an arbitrary matrix with full rank satisfying N ≥ M . Find an orthogonal matrix Q ∈ CN ×M and an upper triangular matrix R ∈ CM ×M satisfying:

    work page

  3. [3]

    Problem 2 can be regarded as a generalization of Problem 1

    A = QR There are many classical numerical methods for Problems 1 and 2. Problem 2 can be regarded as a generalization of Problem 1. The transformation matrix R is obtained at the same time when the column vectors of given matrix A is orthogonal normalized. One of the most common ways to solve Problems 1 and 2 is the Gram-Schmidt or- thogonalization proces...

    work page 2000

  4. [4]

    Then there exists a quantum algorithm for calculating the QR decomposition of matrix A

    Given a full rank matrix A ∈ CN ×M with N ≥ M . Then there exists a quantum algorithm for calculating the QR decomposition of matrix A. Suppose the unique exact QR decomposition of matrix A is A = QR, then the algorithm generates matrix ˜Q and matrix ˜R, satisfying ∥ ˜qm − qm ∥= O(ϵ), ∀m, Rm1m2 = 0 , ∀m1 > m 2, and | eRm1m2 − Rm1m2 | = O(ϵ ∥ A ∥), succeed...

    work page

  5. [5]

    ∥ A ⊗ B ∥2 2 = q λmax (A ⊗ B)† (A ⊗ B) 2 = λmax (A ⊗ B)† (A ⊗ B) = λmax A†A ⊗ B†B = λmax A†A · λmax A†A =∥ A ∥2 2 · ∥B ∥2 2 (B1) Therefore ∥ A ⊗ B ∥2=∥ A ∥2 · ∥B ∥2

    Proof of Lemma 2 Proof. ∥ A ⊗ B ∥2 2 = q λmax (A ⊗ B)† (A ⊗ B) 2 = λmax (A ⊗ B)† (A ⊗ B) = λmax A†A ⊗ B†B = λmax A†A · λmax A†A =∥ A ∥2 2 · ∥B ∥2 2 (B1) Therefore ∥ A ⊗ B ∥2=∥ A ∥2 · ∥B ∥2

    work page

  6. [6]

    Suppose the qubit number of the first register is

    Proof of Lemma 3 Proof. Suppose the qubit number of the first register is

    work page

  7. [7]

    Define ∆ U = ( C − U ) − (C − exp(−iHt))

    Then the exact and errant QPE unitary is Uexact = QF T† ⊗ I (C − U ) (H ⊗ I) (B2) Ureal = QF T† ⊗ I (C − exp(−iHt)) (H ⊗ I) (B3) with ∥ U − exp(−iHt) ∥< ϵ0. Define ∆ U = ( C − U ) − (C − exp(−iHt)). From Lemma 2, we get the following equation. ∥ ∆U ∥ =∥ (C − U ) − (C − exp(−iHt)) ∥ =∥ |1⟩⟨1| ⊗(U − exp(−iHt)) ∥ =∥ 1⟩⟨1 ∥∥ U − exp(−iHt) ∥ < ϵ0. (B4) Therefo...

    work page

  8. [8]

    Proof of Lemma 4 In Algorithm 3, we generate a series states successively, so we use mathematical induction to prove Lemma 4. Proof. Firstly, as we take |u1⟩ ≡ |a1⟩, So span{a1} = span{u1}. It is clear that |ut⟩ and |am⟩ is the amplitude encoding of N −dimension vector ut and am. |am⟩ = NX n=1 anm ∥ am ∥ |n − 1⟩. (B6) |ut⟩ = NX n=1 unt ∥ ut ∥ |n − 1⟩. (B7...

    work page

Show all 55 references
  1. [9]

    Proof of Lemma 5 In Algorithm 3, we generate a series states successively, so we again use mathematical induction to prove Lemma 5. Proof. Firstly, as we take |u1⟩ ≡ |a1⟩, So u1 itself is a normalized vector. It is clear that |ut⟩ and |am⟩ is the amplitude encoding of N −dimen...

  2. [10]

    Roger A Horn and Charles R Johnson, Matrix analysis (Cambridge university press, 2012)

    2012

  3. [11]

    169 (Springer Science & Business Media, 2013)

    Rajendra Bhatia, Matrix analysis, Vol. 169 (Springer Science & Business Media, 2013)

    2013

  4. [12]

    Linear least squares solutions by householder transformations,

    Peter Businger and Gene H Golub, “Linear least squares solutions by householder transformations,” Numerische Mathematik 7, 269–276 (1965)

    1965

  5. [13]

    Gram-Schmidt orthogonalization: 100 years and more,

    Steven J Leon, ˚Ake Bj¨ orck, and Walter Gander, “Gram-Schmidt orthogonalization: 100 years and more,” Numerical Linear Algebra with Applications 20, 492–532 (2013)

    2013

  6. [14]

    The QR algorithm,

    Beresford N Parlett, “The QR algorithm,” Computing in science & engineering 2, 38–42 (2000)

    2000

  7. [15]

    Real-time face recognition using Gram-Schmidt orthogonalization for LDA,

    Wenming Zheng, Cairong Zou, and Li Zhao, “Real-time face recognition using Gram-Schmidt orthogonalization for LDA,” in Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004., Vol. 2 (IEEE, 2004) pp. 403–406

    2004

  8. [16]

    Unsupervised feature selection through Gram–Schmidt orthogonalization—A word co- occurrence perspective,

    Deqing Wang, Hui Zhang, Rui Liu, Xianglong Liu, and Jing Wang, “Unsupervised feature selection through Gram–Schmidt orthogonalization—A word co- occurrence perspective,” Neurocomputing 173, 845–854 (2016)

    2016

  9. [17]

    A modified learning algorithm for the multilayer neural network with multi-valued neurons based on the complex QR decomposition,

    Igor Aizenberg, Antonio Luchetta, and Stefano Manetti, “A modified learning algorithm for the multilayer neural network with multi-valued neurons based on the complex QR decomposition,” Soft Computing 16, 563–575 (2012)

    2012

  10. [18]

    Equal-diagonal QR decomposition and its application to precoder design for successive-cancellation detection,

    Jian-Kang Zhang, Aleksandar Kavcic, and Kon Max Wong, “Equal-diagonal QR decomposition and its application to precoder design for successive-cancellation detection,” IEEE Transactions on Information Theory 51, 154–172 (2005)

    2005

  11. [19]

    Fast dual- domain reduced-rank algorithm for 3D deblending via randomized QR decomposition,

    Jinkun Cheng and Mauricio D Sacchi, “Fast dual- domain reduced-rank algorithm for 3D deblending via randomized QR decomposition,” Geophysics 81, V89– V101 (2016)

    2016

  12. [20]

    On the use of the upper triangular (or QR) decomposition for developing constitutive equations for green-elastic materials,

    A.R. Srinivasa, “On the use of the upper triangular (or QR) decomposition for developing constitutive equations for green-elastic materials,” International Journal of Engineering Science 60, 1–12 (2012)

    2012

  13. [21]

    Computation using the QR decompo- sition,

    Colin R Goodall, “Computation using the QR decompo- sition,” (1993)

    1993

  14. [22]

    The loss of orthogonality in the Gram-Schmidt orthogonalization process,

    Luc Giraud, Julien Langou, and Miroslav Rozloznik, “The loss of orthogonality in the Gram-Schmidt orthogonalization process,” Computers & Mathematics with Applications 50, 1069–1075 (2005)

    2005

  15. [23]

    Rounding error analysis of the classical Gram-Schmidt orthogonalization process,

    Luc Giraud, Julien Langou, Miroslav Rozloˇ zn ´ ık, and Jasper van den Eshof, “Rounding error analysis of the classical Gram-Schmidt orthogonalization process,” Numerische Mathematik 101, 87–100 (2005)

    2005

  16. [24]

    Error analysis of QR decompo- sitions by Givens transformations,

    W Morven Gentleman, “Error analysis of QR decompo- sitions by Givens transformations,” Linear Algebra and its Applications 10, 189–197 (1975)

    1975

  17. [25]

    Quantum mechanical computers,

    Richard P Feynman, “Quantum mechanical computers,” Optics News 11, 11–20 (1985). 22

    1985

  18. [26]

    Michael A Nielsen and Isaac L Chuang, Quantum computation and quantum information (Cambridge university press, 2010)

    2010

  19. [27]

    Quantum computing in the NISQ era and beyond,

    John Preskill, “Quantum computing in the NISQ era and beyond,” Quantum 2, 79 (2018)

    2018

  20. [28]

    Hello quantum world! Google publishes landmark quantum supremacy claim,

    Elizabeth Gibney, “Hello quantum world! Google publishes landmark quantum supremacy claim,” Nature 574, 461–463 (2019)

    2019

  21. [29]

    Quantum computational advantage using photons,

    Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al., “Quantum computational advantage using photons,” Science 370, 1460–1463 (2020)

    2020

  22. [30]

    Realization of a scalable shor algorithm,

    Thomas Monz, Daniel Nigg, Esteban A Martinez, Matthias F Brandl, Philipp Schindler, Richard Rines, Shannon X Wang, Isaac L Chuang, and Rainer Blatt, “Realization of a scalable shor algorithm,” Science 351, 1068–1070 (2016)

    2016

  23. [31]

    Algorithms for quantum computation: discrete logarithms and factoring,

    Peter W Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th annual symposium on foundations of computer science (IEEE, 1994) pp. 124–134

    1994

  24. [32]

    Anupam Prakash, Quantum algorithms for linear algebra and machine learning(University of California, Berkeley, 2014)

    2014

  25. [33]

    Quantum algorithm for linear systems of equations,

    Aram W Harrow, Avinatan Hassidim, and Seth Lloyd, “Quantum algorithm for linear systems of equations,” Physical Review Letters 103, 150502 (2009)

    2009

  26. [34]

    Quantum algorithm for systems of linear equations with exponentially improved dependence on precision,

    Andrew M Childs, Robin Kothari, and Rolando D Somma, “Quantum algorithm for systems of linear equations with exponentially improved dependence on precision,” SIAM Journal on Computing 46, 1920–1950 (2017)

    2017

  27. [35]

    Quantum support vector machine for big data classification,

    Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd, “Quantum support vector machine for big data classification,” Physical Review Letters 113, 130503 (2014)

    2014

  28. [36]

    Quantum principal component analysis,

    Seth Lloyd, Masoud Mohseni, and Patrick Reben- trost, “Quantum principal component analysis,” Nature Physics 10, 631–633 (2014)

    2014

  29. [37]

    Quantum inference on Bayesian networks,

    Guang Hao Low, Theodore J Yoder, and Isaac L Chuang, “Quantum inference on Bayesian networks,” Physical Review A 89, 062315 (2014)

    2014

  30. [38]

    Quantum boltzmann machine,

    Mohammad H Amin, Evgeny Andriyash, Jason Rolfe, Bohdan Kulchytskyy, and Roger Melko, “Quantum boltzmann machine,” Physical Review X 8, 021050 (2018)

    2018

  31. [39]

    Quantum Gram-Schmidt processes and their application to efficient state readout for quantum algorithms,

    Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao, “Quantum Gram-Schmidt processes and their application to efficient state readout for quantum algorithms,” Physical Review Research 3, 043095 (2021)

    2021

  32. [40]

    Quantum random access memory,

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, “Quantum random access memory,” Physical Review Letters 100, 160501 (2008)

    2008

  33. [41]

    Quantum QR decomposition in the computational basis,

    Guangsheng Ma, Hongbo Li, and Jiman Zhao, “Quantum QR decomposition in the computational basis,” Quantum Information Processing 19, 1–16 (2020)

    2020

  34. [42]

    Architectures for a quantum random access memory,

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone, “Architectures for a quantum random access memory,” Physical Review A 78, 052310 (2008)

    2008

  35. [43]

    Hamiltonian simulation by qubitization,

    Guang Hao Low and Isaac L Chuang, “Hamiltonian simulation by qubitization,” Quantum 3, 163 (2019)

    2019

  36. [44]

    Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,

    Peter W Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM review 41, 303–332 (1999)

    1999

  37. [45]

    An improved quantum Fourier transform algorithm and applications,

    Lisa Hales and Sean Hallgren, “An improved quantum Fourier transform algorithm and applications,” in Proceedings 41st Annual Symposium on Foundations of Computer Science (IEEE, 2000) pp. 515–525

    2000

  38. [46]

    Quantum algorithms for quantum dynamics,

    Alexander Miessen, Pauline J Ollitrault, Francesco Tacchino, and Ivano Tavernelli, “Quantum algorithms for quantum dynamics,” Nature Computational Science 3, 25–37 (2023)

    2023

  39. [47]

    Compiling basic linear algebra subroutines for quantum computers,

    Liming Zhao, Zhikuan Zhao, Patrick Rebentrost, and Joseph Fitzsimons, “Compiling basic linear algebra subroutines for quantum computers,” Quantum Machine Intelligence 3, 21 (2021)

    2021

  40. [48]

    The density-matrix renormalization group,

    Ulrich Schollw¨ ock, “The density-matrix renormalization group,” Reviews of modern physics 77, 259–315 (2005)

    2005

  41. [49]

    The density-matrix renormalization group in the age of matrix product states,

    Ulrich Schollw¨ ock, “The density-matrix renormalization group in the age of matrix product states,” Annals of physics 326, 96–192 (2011)

    2011

  42. [50]

    Infinite time-evolving block decimation algorithm beyond unitary evolution,

    Roman Orus and Guifre Vidal, “Infinite time-evolving block decimation algorithm beyond unitary evolution,” Physical Review B—Condensed Matter and Materials Physics 78, 155117 (2008)

    2008

  43. [51]

    A practical introduction to tensor networks: Matrix product states and projected entangled pair states,

    Rom´ an Or´ us, “A practical introduction to tensor networks: Matrix product states and projected entangled pair states,” Annals of physics 349, 117–158 (2014)

    2014

  44. [52]

    739 (Springer, 2007)

    Holger Fehske, Ralf Schneider, and Alexander Weisse, Computational many-particle physics, Vol. 739 (Springer, 2007)

    2007

  45. [53]

    Quantum amplitude amplification and estimation,

    Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp, “Quantum amplitude amplification and estimation,” Contemporary Mathematics 305, 53–74 (2002)

    2002

  46. [54]

    Low depth algorithms for quantum amplitude estimation,

    Tudor Giurgica-Tiron, Iordanis Kerenidis, Farrokh Labib, Anupam Prakash, and William Zeng, “Low depth algorithms for quantum amplitude estimation,” Quantum 6, 745 (2022)

    2022

  47. [55]

    Iterative quantum amplitude estimation,

    Dmitry Grinko, Julien Gacon, Christa Zoufal, and Ste- fan Woerner, “Iterative quantum amplitude estimation,” npj Quantum Information 7, 52 (2021)

    2021

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.