Algorithms · Quantum 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.
Attested & literatureUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
Phase estimation of P(3*pi/4)
3 counting qubits estimating the phase of P(3π/4), which is 2π·3/8 exactly: a phase 3-bit QPE can represent exactly.
Step 1 of 4 · X
Probability of each outcome after this step
- 1000100%
Puts the target qubit into |1⟩, which is an eigenstate of P(3*pi/4): applying the gate to it multiplies it by a phase and changes nothing else. That is the whole requirement QPE places on its input.
The whole state moves from 0000 to 1000 — one certain outcome before, one certain outcome after, no superposition either side.
Spreads the 3 counting qubits over all 8 values they can hold at once. Each one will later ask about a different power of the phase.
Probability spreads from 1 outcome to 8. All 8 are equally likely.
Counting qubit k applies P(3*pi/4) to the target 2^k times, controlled on itself. The target never changes — it is an eigenstate — so the phase it would have picked up is kicked back onto the control instead. This is the step that writes the answer into the register.
The outcome probabilities do not move at all. What this step changes is phase — 8 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
The inverse Fourier transform reads that phase pattern back out as a binary number. Phase in, bits out.
Probability gathers from 8 outcomes onto 1. 1011 goes from 12.5% to 100.0%.
Readout The counting register reads 011 = 3 with probability 1: angle/(2π) = 3/8, recovered exactly.
Open in Studio- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costTwo 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.
- Papers1
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.
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 →
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..
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 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- 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.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity 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.
- Circuit
- Not supplied
This record is not a concrete 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.
Nobody has reviewed this record for gaps yet.
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.
Related entries
- Estimating log-determinants and other spectral sums
Algorithms
- Quantum phase estimation
Algorithms
- Quantum singular value transformation
Algorithms
- HHL linear-systems reference
Algorithms
References
- A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
Yanlin Chen, András Gilyén, Ronald de Wolf · 2024
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.