◐Attested & literatureAlgorithmsQuantum linear algebra
Approximating the top eigenvector of a Hermitian matrix
Given query access to the entries of a d × d Hermitian matrix A, output a classical description of a good approximation of its top eigenvector, the eigenvector belonging to the largest eigenvalue.
principal eigenvectorpower methodblock encodingtomographyquery complexity
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Given query access to the entries of a d × d Hermitian matrix A, output a classical description of a good approximation of its top eigenvector, the eigenvector belonging to the largest eigenvalue. The Zoo separates this from the ground state problem: obtaining the top eigenvector as a quantum state would be equivalent to that problem, whereas what is wanted here is a classical description of the vector. Chen, Gilyén and de Wolf give two quantum algorithms under an assumed constant eigenvalue gap, and the paper describes both as running a version of the classical power method that is robust to certain benign kinds of errors, with each matrix-vector multiplication implemented on a quantum computer with small and well-behaved error. The two differ in how that multiplication is done: the first estimates the matrix-vector product one entry at a time, by a new procedure the paper calls Gaussian phase estimation, while the second uses block-encoding techniques to compute the product as a quantum state and then obtains a classical description from it by a new time-efficient unbiased pure-state tomography procedure. The same paper extends the construction to a classical description of the subspace spanned by the top-q eigenvectors, and proves a nearly-optimal lower bound on the quantum query complexity of approximating the top eigenvector.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
How it works
The Zoo separates this from the ground state problem: obtaining the top eigenvector as a quantum state would be equivalent to that problem, whereas what is wanted here is a classical description of the vector. Chen, Gilyén and de Wolf give two quantum algorithms under an assumed constant eigenvalue gap, and the paper describes both as running a version of the classical power method that is robust to certain benign kinds of errors, with each matrix-vector multiplication implemented on a quantum computer with small and well-behaved error. The two differ in how that multiplication is done: the first estimates the matrix-vector product one entry at a time, by a new procedure the paper calls Gaussian phase estimation, while the second uses block-encoding techniques to compute the product as a quantum state and then obtains a classical description from it by a new time-efficient unbiased pure-state tomography procedure. The same paper extends the construction to a classical description of the subspace spanned by the top-q eigenvectors, and proves a nearly-optimal lower bound on the quantum query complexity of approximating the top eigenvector. This record's speedup class, "Polynomial", is a secondary source's classification of the optimization, numerics, and machine learning it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: Two algorithms for a d × d Hermitian matrix under an assumed constant eigenvalue gap: one of time complexity Õ(d^1.75), one of time complexity d^(1.5+o(1)), against the best-possible classical algorithm, which the abstract states needs Ω(d²) queries to the entries of A and hence Ω(d²) time. The same abstract states time q·d^(1.5+o(1)) for a classical description of the subspace spanned by the top-q eigenvectors, and a nearly-optimal lower bound of Ω̃(d^1.5) on the quantum query complexity of approximating the top eigenvector. The Zoo instead gives a single figure, Õ(d^(3/2)) against a best classical Õ(d²), which matches neither of the abstract's two upper bounds exactly..
Implementation
Unsupported
top-eigenvector-estimation.txt
ALGORITHM: Approximating the top eigenvector of a Hermitian matrix
PROBLEM: Given query access to the entries of a d × d Hermitian matrix A, output a classical description of a good approximation of its top eigenvector, the eigenvector belonging to the largest eigenvalue.
IDEA: The Zoo separates this from the ground state problem: obtaining the top eigenvector as a quantum state would be equivalent to that problem, whereas what is wanted here is a classical description of the vector. Chen, Gilyén and de Wolf give two quantum algorithms under an assumed constant eigenvalue gap, and the paper describes both as running a version of the classical power method that is robust to certain benign kinds of errors, with each matrix-vector multiplication implemented on a quantum computer with small and well-behaved error. The two differ in how that multiplication is done: the first estimates the matrix-vector product one entry at a time, by a new procedure the paper calls Gaussian phase estimation, while the second uses block-encoding techniques to compute the product as a quantum state and then obtains a classical description from it by a new time-efficient unbiased pure-state tomography procedure. The same paper extends the construction to a classical description of the subspace spanned by the top-q eigenvectors, and proves a nearly-optimal lower bound on the quantum query complexity of approximating the top eigenvector.
REPORTED COST: Two algorithms for a d × d Hermitian matrix under an assumed constant eigenvalue gap: one of time complexity Õ(d^1.75), one of time complexity d^(1.5+o(1)), against the best-possible classical algorithm, which the abstract states needs Ω(d²) queries to the entries of A and hence Ω(d²) time. The same abstract states time q·d^(1.5+o(1)) for a classical description of the subspace spanned by the top-q eigenvectors, and a nearly-optimal lower bound of Ω̃(d^1.5) on the quantum query complexity of approximating the top eigenvector. The Zoo instead gives a single figure, Õ(d^(3/2)) against a best classical Õ(d²), which matches neither of the abstract's two upper bounds exactly.
BASIS: abstract of arXiv:2405.14765 (TeX rendered into Unicode: the abstract's tilde-O written Õ, tilde-Omega written Ω̃, math delimiters removed): "We give two different quantum algorithms that, given query access to the entries of a Hermitian matrix A and assuming a constant eigenvalue gap, output a classical description of a good approximation of the top eigenvector: one algorithm with time complexity Õ(d^{1.75}) and one with time complexity d^{1.5+o(1)}", "Both of our quantum algorithms provide a polynomial speed-up over the best-possible classical algorithm, which needs Ω(d^2) queries to entries of A, and hence Ω(d^2) time", "We extend this to a quantum algorithm that outputs a classical description of the subspace spanned by the top-q eigenvectors in time qd^{1.5+o(1)}", and "We also prove a nearly-optimal lower bound of Ω̃(d^{1.5}) on the quantum query complexity of approximating the top eigenvector." The single Zoo figure is from the Quantum Algorithm Zoo entry "Computing the Principal Eigenvector" (widetilde O rendered Õ, math delimiters removed, reference number and its spacing left as written): "The quantum of [ 462 ] runs in time Õ(d^{3/2}) whereas the best classical algorithm runs in time Õ(d^2)." That sentence is quoted as the Zoo has it, missing noun included.
PRIMARY SOURCE: Yanlin Chen, András Gilyén, Ronald de Wolf (2024), A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix — https://arxiv.org/abs/2405.14765
This is a literature reference record, not an executable circuit.
A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Quantum vs classical
Classical baseline
Compare Quantum linear algebra with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix2024 · Yanlin Chen, András Gilyén, Ronald de Wolf
Primary source: it states the query-access input model, the constant eigenvalue gap assumption, the two time complexities Õ(d^1.75) and d^(1.5+o(1)), the classical Ω(d²) it measures them against, the q·d^(1.5+o(1)) extension to the top-q eigenvector subspace and the Ω̃(d^1.5) quantum query lower bound. It also names the two mechanisms, Gaussian phase estimation for the entry-by-entry route and block-encoding plus unbiased pure-state tomography for the state-based route. Consult it for the ℓ₂-error dependence of each algorithm and for what the o(1) in the exponent hides, neither of which the abstract states.