Pith. sign in

REVIEW 4 major objections 4 minor 64 references

Quantum Algorithm for Estimating Intrinsic Geometry

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

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

Pith's one-line read A quantum algorithm estimates local intrinsic dimension and scalar curvature of a point cloud from pairwise distances exponentially faster than the classical $O(N^3)$ pipeline, with a diffusion-map extension that also improves on prior quan

desk verdict Solid quantum translation of a classical geometric estimator, but a load-bearing algebraic error in the fit formula and hidden dataset-dependent spectral gaps make the advertised speedup unsupported. read the letter →

arxiv 2508.06355 v1 pith:ZO3IRIQQ submitted 2025-08-08 quant-ph

Nhat A. Nghiem , Tuan K. Do , Tzu-Chieh Wei , Trung V. Phan This is my paper
classification quant-ph
keywords quantumalgorithmintrinsicdimensionscalarcurvaturemanifoldlearningblockencodingsingularvaluetransformationdiffusionmapspointcloud
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

The paper sets out to show that a quantum computer can read off two basic geometric quantities of a point cloud — the local intrinsic dimension and the local scalar curvature at a chosen point — directly from the pairwise distances between points, and can do so exponentially faster than the standard classical pipeline. The main theorem claims that, given the classical matrix of pairwise distances, estimating these quantities to additive accuracy $\epsilon$ costs $O((1/\epsilon)\log^{N+3}(N/\epsilon))$ when the ambient dimension $m$ is small and $O((1/\epsilon)\log^{d_i+1}m)$ when $m$ is large, against $O(N^3)$ classically. The same circuit construction also yields a quantum diffusion-map embedding with polylogarithmic complexity, improving on an earlier quantum diffusion-map algorithm. If correct, this turns geometric data analysis — not just topological summaries — into a target for quantum advantage on large point clouds.

What carries the argument

The load-bearing tool is the block-encoding/quantum singular value transformation (QSVT) formalism: a unitary whose top-left block is a scaled matrix, together with routines that multiply, add, invert, and apply polynomials to such encoded matrices. The algorithm starts by encoding the Gaussian affinity kernel $K_{ij}=\exp(-d(x_i,x_j)^2/\sigma^2)$ from the classical distances, uses the spectrum of $K^\dagger K$ to build a diagonal operator whose entries are powers of the diffusion-approximated geodesic distances $d_G(x_i,x_j)$, then applies a refined quantum PCA (Lemma E.1) to find the nearest neighbors of a point and the top singular values of the local covariance matrix $C_i$. Density esti

What would settle it

Compute $\Delta$ and $\delta$ for a point cloud in which two points are separated by $2^{-k}$ times the local scale; as $k$ grows, the refined complexity bound (H.12) grows like $1/\Delta^{|N_i|}$ and $1/\delta^{d_i}$, so the empirical query count should diverge from polylog. A targeted test is to run the nearest-neighbor eigenvalue-finding step and observe how the precision needed to resolve the top eigenvalues blows up as the gap shrinks.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that intrinsic geometry estimation for point clouds is quantumly tractable. It constructs a quantum algorithm that takes a point cloud $X=\{x_i\}\subset\mathbb{R}^m$ together with classical values of the pairwise distances $\{d(x_i,x_j)\}$ and returns estimates of the local intrinsic dimension $d_i$ and the local scalar curvature $S(x_i)$ at any queried point, up to additive error $\epsilon$. Theorem III.1 states the cost is $O((1/\epsilon)\log^{N+3}(N/\epsilon))$ for $N\gg m$ and $O((1/\epsilon)\log^{d_i+1}m)$ for $m\gg N$; the appendix's refined complexity (H.12) writes the first exponent as $|N_i|+3$ and makes the dependence on the spectral gaps $\$\Delta$,

Load-bearing premise

The algorithm's polylog cost rests on the spectral gaps $\Delta$ (the minimum separation between sorted geodesic distances from $x_i$) and $\delta$ (the minimum gap among the top singular values of the local covariance matrix) being $O(1)$; if the data are noisy or contain near-duplicate distances, these gaps can be exponentially small and the claimed speedup collapses.

Editorial extensions

If this is right

  • If Theorem III.1 holds, per-point estimates of local dimension and scalar curvature cost $O((1/\epsilon)\log^{O(1)}(N/\epsilon))$ instead of $O(N^3)$, so the geometric preprocessing of huge point clouds is no longer dominated by classical matrix diagonalization.
  • The speedup improves as the local dimension $d_i$ shrinks, so low-dimensional manifold data — the regime where the manifold hypothesis is most plausible — is where the algorithm is fastest.
  • The same pipeline yields a quantum diffusion-map embedding with complexity $O(\log^{n+1}(N)+\log^{2n+6}(1/\epsilon))$ for $n\ll m$ coordinates, improving on the prior quantum diffusion-map cost of $O(N^2\log^3 N)$ and requiring no matrix oracle.
  • Because the output is local, the method can flag regions of high curvature or anomalous sampling density rather than returning only a global dimension estimate; the authors note the curvature estimate remains informative even when the data is a union of manifolds.

Reading between the lines

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

  • Beyond the paper's claims, the dataset-dependent constants $\Delta$ and $\delta$ are the practical pivot: on adversarial data with near-duplicate distances the refined bound grows as $1/\Delta^{|N_i|}$ and $1/\delta^{d_i}$, so the real-world speedup is conditional on well-separated geodesic spectra.
  • The block-encoded geodesic-distance operator built here is a reusable primitive; the same construction could plausibly estimate other local invariants such as tangent-space angles, Ricci curvature, or heat-kernel signatures without re-encoding the data.
  • The theorem's $N+3$ exponent appears inconsistent with the appendix's $|N_i|+3$; if the corrected form is intended, the dominant scaling depends on the neighborhood size $|N_i|$ (typically $O(1)$), not on the total number of points.
  • A direct experimental check would feed synthetic point clouds with controlled singular-value gaps into the quantum PCA subroutine and watch the precision requirement climb as the gaps shrink; the $1/\delta^{d_i}$ factor predicts a sharp cliff once gaps approach machine precision.
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 / 4 minor

Summary. The paper proposes a quantum algorithm that, given pairwise Euclidean distances of a point cloud, estimates the local intrinsic dimension d_i and local scalar curvature S(x_i) at each point. The method uses diffusion geometry to approximate geodesic distances, then applies block-encoding/QSVT-based quantum PCA to find local neighborhoods and dimensions, estimates geodesic-ball volumes by inverse-density weighting, and obtains curvature from a quadratic fit of normalized volume versus squared radius. The authors claim an exponential speedup over the classical O(N^3) estimator and extend the technique to diffusion maps. Theorem III.1 states polylogarithmic complexity in N and m under the stated data-access assumptions, with details deferred to appendices.

Significance. A genuinely efficient quantum algorithm for local intrinsic dimension and curvature would be a meaningful advance in quantum geometric data analysis, complementing recent quantum TDA work. The paper is well structured, makes use of standard block-encoding/QSVT tools, and includes a detailed complexity table, which is a strength. However, the central curvature-estimation step contains an algebraic error, and the claimed polylogarithmic speedup rests on unproven dataset-dependent assumptions about spectral gaps and normalization constants. As written, the main correctness and complexity claims are not supported; the potential significance is therefore contingent on substantial revision.

major comments (4)
  1. [Appendix G / Eq. (III.10)] The quadratic fit is incorrect. The cost in Eq. (G.3) is C(A) = Σ_j (1 + A r_j^2 - Volnor(B_{r_j}(x_i)))^2. Differentiating with respect to A gives 2 Σ_j r_j^2(1 + A r_j^2 - Volnor(B_{r_j}(x_i))) = 0, so A = Σ_j r_j^2(Volnor(B_{r_j}(x_i)) - 1) / Σ_j r_j^4. Eq. (G.4) omits the factor r_j^2, and Eq. (G.5), repeated as Eq. (III.10), is not the minimizer of Eq. (G.3). Since the paper defines S(x_i) = -6(d_i+2)A, the algorithm does not output the best-fit curvature defined by the classical estimator. This breaks the correctness claim of Theorem III.1 independently of spectral-gap assumptions. The authors must replace the formula and supply a quantum procedure for the correct sums, or prove that the formula used approximates the intended minimizer under explicit assumptions.
  2. [Appendix H, Eq. (H.11)-(H.12); Theorems III.1 and IV.1] The polylogarithmic speedup is not established. The detailed complexity in Eq. (H.11) depends on 1/Δ^{|N_i|}, 1/δ^{d_i}, and on norms/condition numbers; Appendix I contains analogous factors 1/(q_min w_min) and related constants. Eq. (H.12) simplifies by asserting that Δ, δ and other quantities 'can be safely considered to be O(1)'. No argument is provided for this assertion, and near-duplicate geodesic distances can make Δ exponentially small. Theorems III.1 and IV.1 as stated omit these conditions, so the main complexity claims are unsupported unless the theorems are restated with explicit dependence on gaps and normalization constants, or the O(1) assumptions are proved.
  3. [Section III, Eq. (III.2)-(III.3); Appendices C-D vs Appendix B] The quantum geodesic-distance construction uses the unnormalized kernel K (Appendix C, Eq. C.14) and forms a block-encoding of ∝ K^†K, which is then used in Eq. (D.5) to obtain d_G. However, the classical geodesic approximation in Appendix B (Eqs. B.2-B.4) uses the row-stochastic diffusion operator P, not K. The eigenvalues and eigenvectors of K are not those of P in general, so the 'geodesic distances' entering the quantum algorithm are not the same as those in the classical estimator being translated. No proof of equivalence under the stated assumptions is given. This affects the input to both the dimension and curvature estimation, so the correctness of the whole pipeline is called into question.
  4. [Theorem III.1, Eq. (III.11)] The first complexity expression in Theorem III.1 has exponent N+3, where N is the total number of data points, whereas Appendix H and Table I consistently use |N_i|+3 with |N_i| the local neighborhood size. Taken literally, the theorem claims a cost exponential in N, which would contradict the claimed polylogarithmic speedup. If this is a typo, it must be corrected in the theorem statement; if not, the theorem is false. The same notational overloading of N appears in the definition of Δ in Table I and should be cleaned up.
minor comments (4)
  1. [Notation throughout] The symbol N is used both for the total dataset size and for the local neighborhood size |N_i| (e.g., Eq. (III.4) and Appendix B). This makes theorem statements and complexity expressions unnecessarily hard to parse; please use distinct notation.
  2. [Appendix H, step 2] There is a typo: 'twe use' should be 'we use'. Also 'logN 1/ϵ' in Table I should have parentheses for clarity.
  3. [Eq. (III.3) / Appendix B] The approximation d_G ≈ D_t with t=1 is used without a quantified error bound for finite N or noisy data. The paper should state this as an explicit assumption or provide a bound, since the downstream accuracy claims depend on the quality of this approximation.
  4. [Figure 2] The box 'Fit the quadratic curve Br(xi) versus r^2' should specify 'normalized volume' and the fit function 1+A r^2, to match Eq. (II.1) and Appendix G.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the curvature and dimension estimates are computed from the input distances by well-specified quantum routines. The self-citation of quantum PCA is a tool dependency, not a definitional loop.

full rationale

Walking the dependency chain: the input classical pairwise distances are used to build the kernel matrix K, from which geodesic distances are approximated; nearest neighbors, the local PCA matrix C_i, the local dimension d_i, sampling densities, and geodesic-ball volumes are then all computed by the stated quantum and classical procedures; finally the fit parameter A is computed from those volumes and radii, and S(x_i) = -6(d_i+2)A. At no point is an input defined in terms of the target output, nor is a fitted parameter renamed as a prediction. The quantum PCA lemma (Lemma E.1) is cited from the first author's prior work and is load-bearing, but it is a general eigen-estimation subroutine whose proof is reviewed in Appendix J; its assumptions (spectral gaps) do not include the curvature or dimension being estimated, so this is not circular self-citation. No uniqueness theorem is imported from the authors' earlier work. Two caveats are worth flagging but are not circularity: Appendix H asserts that the spectral gaps Delta and delta are 'safely considered to be O(1)' without supporting argument, which is an unsupported complexity assumption; and Eqs. G.3-G.5 are algebraically inconsistent—differentiating Eq. G.3 gives sum_j r_j^2(1 + A r_j^2 - Vol_nor(B_rj(x_i))) = 0, not Eq. G.4, so Eq. G.5 is not the least-squares minimizer it claims to be. That is a correctness defect in the curvature estimation, but it does not make the derivation equivalent to its inputs by construction.

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

The central speedup claim rests on hyperparameters inherited from the classical estimator, on the manifold and diffusion approximations, and critically on the unproven assumption that the spectral gaps of the geodesic-distance and local-covariance operators are O(1). The algorithm also assumes a dense state-preparation routine that consumes O(N^2) ancilla qubits, which is not reflected in the advertised polylogarithmic depth.

free parameters (5)
  • affinity kernel scale sigma
    Hyperparameter in K_ij = exp(-d_ij^2/sigma^2); it controls the diffusion operator and hence the geodesic-distance approximation. The paper suggests the median of pairwise squared distances but says the optimal value is problem-dependent (Appendix B).
  • density kernel scale h
    Controls the Gaussian kernel in the density estimator rho(x_i); chosen as the typical geodesic distance between points (Appendix B, Step 3).
  • PCA threshold tau
    Variance-explained threshold in (0.9, 0.99) used to define local intrinsic dimension (Appendix B, Step 2).
  • neighborhood size |N_i|
    Hyperparameter setting the number of nearest neighbors for local PCA and density estimation; must satisfy d < |N_i| << N (Section II).
  • diffusion timestep t = 1
    Set to 1 for the single-timestep diffusion approximation of geodesic distance (Section III, Eq. III.3).
assumptions (7)
  • domain assumption The manifold hypothesis holds: the point cloud is sampled near a smooth d-dimensional Riemannian manifold.
    Invoked in Section II and the conclusion; the algorithm estimates dimension and curvature under this hypothesis.
  • domain assumption The single-timestep diffusion distance (t=1) approximates the true geodesic distance within the target accuracy.
    Eq. III.3 and Appendix B invoke Varadhan's asymptotic formula without quantifying the approximation error for finite N and noise.
  • ad hoc to paper The spectral gaps Delta and delta are O(1).
    Appendix H states the complexity depends on 1/Delta^{|Ni|} and 1/delta^{di} and then asserts these can be safely considered O(1); no argument is given that they are bounded away from zero for the data sets of interest.
  • standard math The block-encoding/QSVT lemmas (K.1-K.6, D.1, I.2) hold as stated.
    The algorithm is built on the cited framework of Gilyen et al. and related works.
  • standard math State preparation of the dense pairwise-distance state costs O(log N) depth with O(N^2) ancilla qubits.
    Lemma C.4 from [32] is used to prepare states from classical distance data; the exponential qubit overhead is not counted in the reported complexity.
  • standard math Quantum principal component analysis (Lemma E.1) has the claimed complexity.
    Taken from the first author's prior work [34]; its correctness is not re-verified here.
  • domain assumption The classical estimator of Hickok and Blumberg correctly estimates dimension and curvature and the volume expansion Eq. II.1 holds.
    The quantum algorithm inherits the classical pipeline; the paper does not re-derive the statistical properties of that estimator.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Algorithm for Estimating Intrinsic Geometry." pith.science (2026). https://pith.science/paper/ZO3IRIQQ

@misc{pith2026250806355,
  author       = {Pith},
  title        = {Pith review of: Quantum Algorithm for Estimating Intrinsic Geometry},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZO3IRIQQ}},
  note         = {Machine review of arXiv:2508.06355}
}
read the original abstract

High-dimensional datasets typically cluster around lower-dimensional manifolds but are also often marred by severe noise, obscuring the intrinsic geometry essential for downstream learning tasks. We present a quantum algorithm for estimating the intrinsic geometry of a point cloud -- specifically its local intrinsic dimension and local scalar curvature. These quantities are crucial for dimensionality reduction, feature extraction, and anomaly detection -- tasks that are central to a wide range of data-driven and data-assisted applications. In this work, we propose a quantum algorithm which takes a dataset with pairwise geometric distance, output the estimation of local dimension and curvature at a given point. We demonstrate that this quantum algorithm achieves an exponential speedup over its classical counterpart, and, as a corollary, further extend our main technique to diffusion maps, yielding exponential improvements even over existing quantum algorithms. Our work marks another step toward efficient quantum applications in geometrical data analysis, moving beyond topological summaries toward precise geometric inference and opening a novel, scalable path to quantum-enhanced manifold learning.

Figures

Figures reproduced from arXiv: 2508.06355 by the authors.

Figure 1
Figure 1. FIG. 1. An illustration of the classical algorithm for estimating intrinsic dimension and scalar [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

64 extracted references · 50 canonical work pages

  1. [1]

    Finding Ni nearest points to x i Our first challenge is to find those Ni nearest points to the point xi. Recall that we have the unitary block-encoding of the following operator: 1 α||D||p||E||4 F N 2 NX j=1 d4 G(xi, xj) |j − 1⟩ ⟨j − 1| (E.3) which essentially contains ∝ d2 G(xi, xj) on the diagonal. First, we use Lemma D.1 with c = 1 /4 to transform the ...

    work page

  2. [2]

    It can be seen that the first column of this unitary is P j,xj ∈Ni |j⟩ xi

    Obtaining the block-encoding of ∝ C † i Ci Our first challenge is to somehow, from the classical knowledge of those points xj obtained above, construct the centroid: exi = 1 |Ni| X j,xj ∈Ni xj (E.8) To proceed, we use Lemma C.4 and the classical knowledge of those points xj ∈ Ni to prepare the following state: |exi⟩ = 1qP j,xj ∈Ni ||xj||2 X j,xj ∈Ni |j − ...

    work page

  3. [3]

    • Perform singular decomposition on Ci and obtain a series of singular values σ1 ≥ σ2 ≥

    Estimating the (local) intrinsic dimension We recall the last part of Step 2 in the previous appendix B, which accounts for the (local) intrinsic dimension estimation: • Define the matrix Ci to be the matrix of size |Ni| ×m, where the rows of Ci is in correspondence with eNi. • Perform singular decomposition on Ci and obtain a series of singular values σ1...

    work page

  4. [4]

    In this step, we first need to use Lemma C.4 to obtain the unitary Uexi , which has complexity O (log |Ni|)

    Obtaining the block-encoding of 1 4 1P j,xj ∈Ni ||xj ||2 C † i Ci . In this step, we first need to use Lemma C.4 to obtain the unitary Uexi , which has complexity O (log |Ni|). Next, we need to use Lemma K.3 (in Eqn. E.16), which has complexity O (log |Ni|) as the gates H ⊗ log |Ni| has depth 1. In the step of Eqn. E.21, we need to SW AP to quantum system...

    work page

  5. [5]

    In this step, we need to perform principal component analysis on∝ C † i Ci to find the local dimension di

    Estimating the local dimension di. In this step, we need to perform principal component analysis on∝ C † i Ci to find the local dimension di. Thus, Lemma E.1 can be applied. Because the local dimension is defined to be the minimum integer k s.t. Pk α=1 σ2 αP|Ni | α=1 σ2α ≥ τ , we need to use Lemma E.1 at least di times to find the largest di eigenvalues. ...

    work page

  6. [6]

    Before fitting the quadratic curve, we need to use classical computer to compute the sampling density ρ(xi), which is efficient

    Fit the quadratic curve to infer the curvature. Before fitting the quadratic curve, we need to use classical computer to compute the sampling density ρ(xi), which is efficient. The value of geodesic ball and its normalization by a unit ball volume can thus be computed accordingly. The final step is to compute the quantitiesP|Ni| j=1 Volnor Brj (xi) /|Ni| ...

    work page

  7. [7]

    From |xk⟩, we use the block encoding of A to apply and obtain the state: |0⟩ A |xk⟩ + |Garbage⟩ (J.4) Taking another copy of |xk⟩ and append another ancilla |0⟩, we then observe that the overlaps: ⟨0| ⟨xk| |0⟩ A |xk⟩ + |Garbage⟩ = ⟨xk| A |xk⟩ (J.5) which is an approximation to the largest eigenvalue of A. According to [51, 52], the value of k needs to be ...

    work page

  8. [19]

    Laplacian eigen- maps for dimensionality reduction and data representa- tion

    Mikhail Belkin and Partha Niyogi. Laplacian eigen- maps for dimensionality reduction and data representa- tion. Neural computation, 15(6):1373–1396, 2003

    work page 2003

Show all 64 references
  1. [20]

    Quantum diffu- sion map for nonlinear dimensionality reduction.Physical Review A, 104(5):052410, 2021

    Apimuk Sornsaeng, Ninnat Dangniam, Pantita Palit- tapongarnpim, and Thiparat Chotibut. Quantum diffu- sion map for nonlinear dimensionality reduction.Physical Review A, 104(5):052410, 2021

    2021

  2. [21]

    Riemannian geometry as determined by the volumes of small geodesic balls

    Alfred Gray and Lieven Vanhecke. Riemannian geometry as determined by the volumes of small geodesic balls. Acta Math, 142, 1979

    1979

  3. [22]

    Quantum singular value transformation and be- yond: exponential improvements for quantum matrix arithmetics

    Andr´ as Gily´ en, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and be- yond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 193–204, 2019

    2019

  4. [23]

    Optimal hamilto- nian simulation by quantum signal processing

    Guang Hao Low and Isaac L Chuang. Optimal hamilto- nian simulation by quantum signal processing. Physical Review Letters, 118(1):010501, 2017

    2017

  5. [24]

    Hamiltonian sim- ulation by qubitization

    Guang Hao Low and Isaac L Chuang. Hamiltonian sim- ulation by qubitization. Quantum, 3:163, 2019

    2019

  6. [25]

    Synthesis of quantum superpositions by quantum computation

    Lov K Grover. Synthesis of quantum superpositions by quantum computation. Physical review letters , 85(6):1334, 2000

    2000

  7. [26]

    Creating superpositions that correspond to efficiently integrable probability dis- tributions

    Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability dis- tributions. arXiv preprint quant-ph/0208112 , 2002

    2002 arXiv

  8. [27]

    Quantum-state preparation with universal gate decompositions

    Martin Plesch and ˇCaslav Brukner. Quantum-state preparation with universal gate decompositions. Phys- ical Review A , 83(3):032302, 2011

    2011

  9. [28]

    Supervised learning with quantum computers , volume 17

    Maria Schuld and Francesco Petruccione. Supervised learning with quantum computers , volume 17. Springer, 2018

    2018

  10. [29]

    Approxi- mate amplitude encoding in shallow parameterized quan- tum circuits and its application to financial market indi- cators

    Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda, and Naoki Yamamoto. Approxi- mate amplitude encoding in shallow parameterized quan- tum circuits and its application to financial market indi- cators. Physi...

    2022

  11. [30]

    Quantum algorithms for approximate func- tion loading

    Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz. Quantum algorithms for approximate func- tion loading. Physical Review Research , 5(3):033114, 2023

    2023

  12. [31]

    Quantum generative adversarial networks for learning and loading random distributions

    Christa Zoufal, Aur´ elien Lucchi, and Stefan Woerner. Quantum generative adversarial networks for learning and loading random distributions. npj Quantum Infor- mation, 5(1):103, 2019

    2019

  13. [32]

    Quan- tum state preparation with optimal circuit depth: Im- plementations and applications

    Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quan- tum state preparation with optimal circuit depth: Im- plementations and applications. Physical Review Letters, 129(23):230504, 2022

    2022

  14. [33]

    Approximate quantum circuit synthesis using block encodings

    Daan Camps and Roel Van Beeumen. Approximate quantum circuit synthesis using block encodings. Physi- cal Review A , 102(5):052411, 2020

    2020

  15. [34]

    Refined quantum algorithms for princi- pal component analysis and solving linear system

    Nhat A Nghiem. Refined quantum algorithms for princi- pal component analysis and solving linear system. arXiv preprint arXiv:2504.00833, 2025

    2025 arXiv

  16. [35]

    Quantum principal component analysis

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature physics, 10(9):631–633, 2014

    2014

  17. [36]

    Geometric analysis of nonlinear manifold clustering

    Nimita Shinde, Tianjiao Ding, Daniel Robinson, and Ren´ e Vidal. Geometric analysis of nonlinear manifold clustering. Advances in Neural Information Processing Systems, 37:128769–128797, 2024

    2024

  18. [37]

    A Comprehensive Introduction to Dif- ferential Geometry, Volume 2

    Michael Spivak. A Comprehensive Introduction to Dif- ferential Geometry, Volume 2 . Publish or Perish, 2nd edition, 1979

    1979

  19. [38]

    Curvature in mathematics and physics

    Shlomo Sternberg. Curvature in mathematics and physics. Courier Corporation, 2013

    2013

  20. [39]

    A note on riemann normal coor- dinates

    Agapitos Hatzinikitas. A note on riemann normal coor- dinates. arXiv preprint hep-th/0001078 , 2000

    2000 arXiv

  21. [40]

    Asymptotic probabilities and differential equations

    SR Srinivasa Varadhan. Asymptotic probabilities and differential equations. Communications on Pure and Ap- plied Mathematics, 19(3):261–286, 1966

    1966

  22. [41]

    Ele- mentary gates for quantum computation

    Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Ty- cho Sleator, John A Smolin, and Harald Weinfurter. Ele- mentary gates for quantum computation. Physical review A, 52(5):3457, 1995

    1995

  23. [42]

    Synthesis of quantum logic circuits

    Vivek V Shende, Stephen S Bullock, and Igor L Markov. Synthesis of quantum logic circuits. In Proceedings of the 2005 Asia and South Pacific Design Automation Confer- ence, pages 272–275, 2005

    2005

  24. [43]

    Approximation theory and approxi- mation practice, extended edition

    Lloyd N Trefethen. Approximation theory and approxi- mation practice, extended edition . SIAM, 2019

    2019

  25. [44]

    The power of block-encoded matrix powers: im- proved regression techniques via faster hamiltonian sim- ulation

    Shantanav Chakraborty, Andr´ as Gily´ en, and Stacey Jef- fery. The power of block-encoded matrix powers: im- proved regression techniques via faster hamiltonian sim- ulation. arXiv preprint arXiv:1804.01973 , 2018

    2018 arXiv

  26. [45]

    Quantum algorithms for estimating physi- cal quantities using block encodings

    Patrick Rall. Quantum algorithms for estimating physi- cal quantities using block encodings. Physical Review A, 102(2):022408, 2020

    2020

  27. [46]

    Non-linear transformations of quantum amplitudes: Exponential improvement, generalization, and applications

    Arthur G Rattew and Patrick Rebentrost. Non-linear transformations of quantum amplitudes: Exponential improvement, generalization, and applications. arXiv preprint arXiv:2309.09839, 2023

    2023 arXiv

  28. [47]

    Nonlin- ear transformation of complex amplitudes via quantum singular value transformation

    Naixu Guo, Kosuke Mitarai, and Keisuke Fujii. Nonlin- ear transformation of complex amplitudes via quantum singular value transformation. Physical Review Research, 6(4):043227, 2024

    2024

  29. [48]

    Improved quantum power method and nu- merical integration using a quantum singular-value trans- formation

    Nhat A Nghiem, Hiroki Sukeno, Shuyu Zhang, and Tzu- Chieh Wei. Improved quantum power method and nu- merical integration using a quantum singular-value trans- formation. Physical Review A , 111(1):012434, 2025

    2025

  30. [49]

    Improved quantum algorithms for eigenvalues finding and gradient descent

    Nhat A Nghiem and Tzu-Chieh Wei. Improved quantum algorithms for eigenvalues finding and gradient descent. arXiv preprint arXiv:2312.14786 , 2023

    2023 arXiv

  31. [50]

    A quantum speed-up for approximating the top eigen- vectors of a matrix

    Yanlin Chen, Andr´ as Gily´ en, and Ronald de Wolf. A quantum speed-up for approximating the top eigen- vectors of a matrix. In Proceedings of the 2025 An- nual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 994–1036. SIAM, 2025

    2025

  32. [51]

    Error bounds on the power method for determining the largest eigenvalue of a symmetric, posi- tive definite matrix

    Joel Friedman. Error bounds on the power method for determining the largest eigenvalue of a symmetric, posi- tive definite matrix. Linear algebra and its applications , 280(2-3):199–216, 1998

    1998

  33. [52]

    Matrix compu- tations

    Gene H Golub and Charles F Van Loan. Matrix compu- tations. JHU press, 2013

    2013

  34. [53]

    Quantum algorithm for systems of linear equa- tions with exponentially improved dependence on pre- cision

    Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equa- tions with exponentially improved dependence on pre- cision. SIAM Journal on Computing , 46(6):1920–1950, 2017. 10

    1920

  35. [54]

    Geometry, topology and physics

    Mikio Nakahara. Geometry, topology and physics . CRC press, 2018

    2018

  36. [55]

    − dG(xi, xj) h 2# (B.11) is exactly the heat kernel (i.e. the fundamental solution of the diffusion equation at “time

    Jeffrey Marc Lee. Manifolds and differential geometry , volume 107. American Mathematical Soc., 2009. Appendix A: A Derivation for the Geodesic-Ball V olume-F ormula At any point p ∈ M, the manifold is locally flat, so one can introduce Riemann normal-coordinates x ∈ Rd center...

    2009

  37. [56]

    In this part, we first need to use Lemma C.4 to prepare a N -dimensional state |ϕ⟩, which incurs complexity O (log N )

    Obtain the block-encoding of K †K from the pairwise distance {d(xi, xj)}N i,j=1. In this part, we first need to use Lemma C.4 to prepare a N -dimensional state |ϕ⟩, which incurs complexity O (log N ). We then use Lemma C.2 and Lemma C.3 to obtain the block-encoding of the vect...

  38. [57]

    First, twe use Lemma D.2 to obtain the block-encoding of the matrix E = PN i=1|i−1⟩⟨i−1|⊗Ei ||E||F

    Obtain the block-encoding of 1 α||D||2p||E||2 F N 2 PN j=1 d4 G(xi, xj) |j − 1⟩ ⟨j − 1|. First, twe use Lemma D.2 to obtain the block-encoding of the matrix E = PN i=1|i−1⟩⟨i−1|⊗Ei ||E||F . This incurs a complexity O log(N ) log2 κE ϵ where κE is the condition number of E. We ...

  39. [58]

    The neighborhood of xi is defined as |Ni| closest points to xi, in terms of geodesic distance

    Finding the neighborhood of x i. The neighborhood of xi is defined as |Ni| closest points to xi, in terms of geodesic distance. As mentioned, we first use Lemma D.1 to obtain the block-encoding of: NX j=1 dG(min) dG(xi, xj) |j − 1⟩ ⟨j − 1| (H.5) where dG(min) = min{dG(xi, xj)}...

  40. [59]

    Algorithm 2 (Diffusion Map)

    Classical algorithm The pipeline of (classical) diffusion map algorithm first proposed in [18] is as follows. Algorithm 2 (Diffusion Map). Let X = {x1, x2, ...,xN } ⊆Rm be the dataset and d(xi, xj) is the pairwise distance (a form of similarity measure) between xi and xj. Step...

  41. [60]

    Quantum algorithm Algorithm. Previously, in section C, we have shown how to obtain the block-encoding of a matrix, denote as MK, having the following vector as the first column: 1 α||D||p NX i,j=1 |i − 1⟩ exp − d2 ij σ2 ! |j − 1⟩ = 1 α||D||p NX i,j=1 |i − 1⟩ Kij |j − 1⟩ (I.5) ...

  42. [61]

    Let |x0⟩ denote some initial state, generated by some known circuit U0 (assuming to have O(1) depth)

    Use Lemma K.1 k times to constrct construct the block encoding of Ak. Let |x0⟩ denote some initial state, generated by some known circuit U0 (assuming to have O(1) depth). Defined xk = Ak |x0⟩ and the normalized state |xk⟩ = xk ||xk||

  43. [62]

    Use the block encoding of Ak to apply it to |x0⟩, we obtain the state: |ϕ1⟩ = |0⟩ Ak |x0⟩ + |Garbage⟩ (J.1)

  44. [63]

    Use Lemma C.5 allows us to construct the block encoding of |ϕ1⟩ ⟨ϕ1|, which is exactly the block encoding of xkx† k = ||xk||2 |xk⟩ ⟨xk|, according to the K.1. 31

  45. [64]

    We use Lemma J.2 and J.1 to transform the block-encoded operator: γ |xk⟩ ⟨xk| − →e−β(1−γ) |xk⟩ ⟨xk| (J.2)

    Define γ ≡ ||xk||2. We use Lemma J.2 and J.1 to transform the block-encoded operator: γ |xk⟩ ⟨xk| − →e−β(1−γ) |xk⟩ ⟨xk| (J.2)

  46. [65]

    Now we take the above block encoding and apply it to |x0⟩, and according to K.1, we obtain the following state: |0⟩ ⟨xk, x0⟩ e−β(1−γ) |xk⟩ + |Garbage⟩ (J.3)

    Recall that we are given U0 that generates the state |x0⟩, C.5 allows us to block-encode the operator |x0⟩ ⟨x0|. Now we take the above block encoding and apply it to |x0⟩, and according to K.1, we obtain the following state: |0⟩ ⟨xk, x0⟩ e−β(1−γ) |xk⟩ + |Garbage⟩ (J.3)

  47. [66]

    The suc- cess probability of this measurement is | ⟨xk, x0⟩ |2e−2β(1−γ), which can be improved quadratically better using amplitude amplification

    Measuring the first register and post-select on |0⟩, yields the state |xk⟩ on the remaining register. The suc- cess probability of this measurement is | ⟨xk, x0⟩ |2e−2β(1−γ), which can be improved quadratically better using amplitude amplification. By choosing β sufficiently s...

  48. [67]

    Tn i=1 Si ∈ Cwhere Si ∈ Cand n ∈ Z≥1

    The intersection of a finite number of elements of C belongs to C, i.e. Tn i=1 Si ∈ Cwhere Si ∈ Cand n ∈ Z≥1

  49. [68]

    S i∈T Si ∈ Cwhere Si ∈ Cand T is any index set (finite or infinite)

    The union of an arbitrary number of elements of C belongs to C, i.e. S i∈T Si ∈ Cwhere Si ∈ Cand T is any index set (finite or infinite). Definition L.2 (Smooth manifold). M is an m-dimensional smooth manifold if:

  50. [69]

    (Some technical conditions allow the space to behave nicely; a first-time reader can ignore those conditions, which we include here for completeness)

    M is a topological space, Hausdorff, second-countable and paracompact. (Some technical conditions allow the space to behave nicely; a first-time reader can ignore those conditions, which we include here for completeness)

  51. [70]

    The pair (Ui, φi) is called a chart

    M is provided with a collection {(Ui, φi)} where Ui form an open cover of M , that is ∪iUi = M, and φi is a homeomorphism from Ui onto an open subset Vi of Rm. The pair (Ui, φi) is called a chart

  52. [71]

    The collection of such charts is called an atlas

    Given that Ui ∩ Uj ̸= ∅, the map ψij = φi ◦ φ−1 j from φj(Ui ∩ Uj) to φi(Ui ∩ Uj) is smooth ( C ∞). The collection of such charts is called an atlas. The homeomorphism φi is represented by m-functions {x1(p), x2(p), ..., xm(p)}, referred to as local coordinates . If the union ...

  53. [72]

    Note that this forces dim M ≤ dim N

    The map f is called an immersion of M into N if: f∗ : TpM → Tf (p)N is an injection (one to one), that is: rank(f∗) = dim M . Note that this forces dim M ≤ dim N

  54. [73]

    The image f (M ) is called a submanifold of N

    The map f is called an embedding if f is an injection and an immersion. The image f (M ) is called a submanifold of N . Thus, f (M ) is diffeomorphic to M . Definition L.5 (Cotangent space). TpM defines a vector space at each point p of M , and hence, there exist a dual space ...

  55. [74]

    Symmetry: gp(U, V) = gp(V, U), for all tangent vectors U, V∈ TpM

  56. [75]

    35 In the local coordinate {xµ}, we can write the inner product between vectors U and V as: U = U µ(x) ∂ ∂xµ , V = V ν(x) ∂ ∂xν =⇒ gp(U, V) = gµν(x)U µ(x)V ν(x)

    Positive-definiteness: gp(U, U) ≥ 0, for all U ∈ TpM , where the equality holds only when U = 0. 35 In the local coordinate {xµ}, we can write the inner product between vectors U and V as: U = U µ(x) ∂ ∂xµ , V = V ν(x) ∂ ∂xν =⇒ gp(U, V) = gµν(x)U µ(x)V ν(x) . (L.5) This makes ...

Pith tools

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