Algorithms · PromiseBQP-complete problem
Diagonal entries of powers of a sparse symmetric matrix
Given a real symmetric N × N matrix A whose rows are sparse — the non-zero positions and values of any row returned by an efficiently computable function rather than stored — together with an index j, an integer power m, an a priori bound b on the norm of A, a threshold g and a precision ε, decide whether the diagonal entry (A^m)_jj is at least g + εb^m or at most g − εb^m.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupStated by the primary source: "Our results show that quantum computation outperforms classical computation in estimating the diagonal entries (provided that BQP≠BPP). But one has to be very careful on which scale this result remains true."
- Reported costPolylogarithmic in the matrix dimension. The abstract places the problem in BQP when m and ε are respectively polylogarithmic and inverse polylogarithmic in N, and the proof states that the estimate can be produced with time and space polynomial in n, m and 1/ε, where N = 2^n. Phase estimation is run with p := 2⌈log((48m)/ε)⌉ control qubits.
- Papers1
A part this method uses, worked through
This page says phase estimation
— here is a concrete, runnable instance of it.
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.
Where it ends up
- 1011100%
The counting register reads 011 = 3 with probability 1: angle/(2π) = 3/8, recovered exactly.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open this part in StudioGiven a real symmetric N × N matrix A whose rows are sparse — the non-zero positions and values of any row returned by an efficiently computable function rather than stored — together with an index j, an integer power m, an a priori bound b on the norm of A, a threshold g and a precision ε, decide whether the diagonal entry (A^m)_jj is at least g + εb^m or at most g − εb^m. Janzing and Wocjan read the matrix as a Hamiltonian. Because A is sparse the evolution exp(iA) can be simulated efficiently, so phase estimation applied to the basis state |j⟩ samples the spectral measure of which the diagonal entry is the m-th moment; raising each measured eigenvalue to the m-th power and averaging estimates (A^m)_jj. The hardness direction runs the other way and is what makes the problem interesting: an arbitrary BQP circuit Y is turned into U := Y σ_z Y†, then into a cyclic-shift unitary W built from U's elementary gates, and A := (W + W†)/2 is sparse and self-adjoint, with a diagonal entry of a suitable power of A recovering the circuit's difference between accepting and rejecting probabilities. The paper states the size of the phase-estimation control register explicitly, at p := 2⌈log((48m)/ε)⌉ qubits. Off-diagonal entries are also shown to lie in BQP, but the hardness proof needs only the diagonal ones, so that is where the authors concentrate. A later section strengthens the hardness to matrices whose entries are drawn from {0, ±1}.
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 →
Janzing and Wocjan read the matrix as a Hamiltonian. Because A is sparse the evolution exp(iA) can be simulated efficiently, so phase estimation applied to the basis state |j⟩ samples the spectral measure of which the diagonal entry is the m-th moment; raising each measured eigenvalue to the m-th power and averaging estimates (A^m)_jj. The hardness direction runs the other way and is what makes the problem interesting: an arbitrary BQP circuit Y is turned into U := Y σ_z Y†, then into a cyclic-shift unitary W built from U's elementary gates, and A := (W + W†)/2 is sparse and self-adjoint, with a diagonal entry of a suitable power of A recovering the circuit's difference between accepting and rejecting probabilities. The paper states the size of the phase-estimation control register explicitly, at p := 2⌈log((48m)/ε)⌉ qubits. Off-diagonal entries are also shown to lie in BQP, but the hardness proof needs only the diagonal ones, so that is where the authors concentrate. A later section strengthens the hardness to matrices whose entries are drawn from {0, ±1}. This record's speedup class, "Superpolynomial", is a secondary source's classification of the approximation and simulation algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "Our results show that quantum computation outperforms classical computation in estimating the diagonal entries (provided that BQP≠BPP). But one has to be very careful on which scale this result remains true.". Reported cost: Polylogarithmic in the matrix dimension. The abstract places the problem in BQP when m and ε are respectively polylogarithmic and inverse polylogarithmic in N, and the proof states that the estimate can be produced with time and space polynomial in n, m and 1/ε, where N = 2^n. Phase estimation is run with p := 2⌈log((48m)/ε)⌉ control qubits..
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)
- Superpolynomial
- Primary source on the speedup
- Stated by the primary source: "Our results show that quantum computation outperforms classical computation in estimating the diagonal entries (provided that BQP≠BPP). But one has to be very careful on which scale this result remains true."
- Reported cost
- Polylogarithmic in the matrix dimension. The abstract places the problem in BQP when m and ε are respectively polylogarithmic and inverse polylogarithmic in N, and the proof states that the estimate can be produced with time and space polynomial in n, m and 1/ε, where N = 2^n. Phase estimation is run with p := 2⌈log((48m)/ε)⌉ control qubits.
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which states it)
- Complexity basis
- abstract of arXiv:quant-ph/0606229: "m and ǫ are polylogarithmic and inverse polylogarithmic in N, respectively"; section 3: "Furthermore, this can be achieved by using time and space resources which are polynomial in n, m, and 1/ǫ. This completes the proof that diagonal entry estimation is in BQP."; and, for the control register, section 3 equation (4): "The number of control qubits can be chosen to be p := 2⌈log((48 m)/ǫ)⌉".
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare PromiseBQP-complete problem 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: Diagonal entries of powers of a sparse symmetric matrix
PROBLEM: Given a real symmetric N × N matrix A whose rows are sparse — the non-zero positions and values of any row returned by an efficiently computable function rather than stored — together with an index j, an integer power m, an a priori bound b on the norm of A, a threshold g and a precision ε, decide whether the diagonal entry (A^m)_jj is at least g + εb^m or at most g − εb^m.
IDEA: Janzing and Wocjan read the matrix as a Hamiltonian. Because A is sparse the evolution exp(iA) can be simulated efficiently, so phase estimation applied to the basis state |j⟩ samples the spectral measure of which the diagonal entry is the m-th moment; raising each measured eigenvalue to the m-th power and averaging estimates (A^m)_jj. The hardness direction runs the other way and is what makes the problem interesting: an arbitrary BQP circuit Y is turned into U := Y σ_z Y†, then into a cyclic-shift unitary W built from U's elementary gates, and A := (W + W†)/2 is sparse and self-adjoint, with a diagonal entry of a suitable power of A recovering the circuit's difference between accepting and rejecting probabilities. The paper states the size of the phase-estimation control register explicitly, at p := 2⌈log((48m)/ε)⌉ qubits. Off-diagonal entries are also shown to lie in BQP, but the hardness proof needs only the diagonal ones, so that is where the authors concentrate. A later section strengthens the hardness to matrices whose entries are drawn from {0, ±1}.
REPORTED COST: Polylogarithmic in the matrix dimension. The abstract places the problem in BQP when m and ε are respectively polylogarithmic and inverse polylogarithmic in N, and the proof states that the estimate can be produced with time and space polynomial in n, m and 1/ε, where N = 2^n. Phase estimation is run with p := 2⌈log((48m)/ε)⌉ control qubits.
BASIS: abstract of arXiv:quant-ph/0606229: "m and ǫ are polylogarithmic and inverse polylogarithmic in N, respectively"; section 3: "Furthermore, this can be achieved by using time and space resources which are polynomial in n, m, and 1/ǫ. This completes the proof that diagonal entry estimation is in BQP."; and, for the control register, section 3 equation (4): "The number of control qubits can be chosen to be p := 2⌈log((48 m)/ǫ)⌉".
PRIMARY SOURCE: Dominik Janzing, Pawel Wocjan (2006), Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete — https://arxiv.org/abs/quant-ph/0606229
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.
Where this sits
This record is named by the layer graph at:
- Estimate the eigenphase of a unitary Slot
Takes A circuit for U that can be applied as controlled U^(2^j), a preparation routine for a state whose overlap with the target eigenvector is not negligible, the number of bits of the phase wanted, and the failure probability that may be tolerated. Returns An estimate of the eigenphase to the requested number of bits, with the failure probability it was obtained at, plus the two costs that actually differ between routes: how many ancillas were held at once, and how many sequential rounds were run.
Related entries
References
- Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
Dominik Janzing, Pawel Wocjan · 2006
Primary source, and the source of this record's cost claim. Consult it for the sparse-access model it assumes, for the b^m scale that the accuracy guarantee is stated relative to, and for the reduction from an arbitrary BQP circuit to a diagonal entry of a matrix power. A secondary source cites this work under the title of its Theory of Computing version, "A simple promiseBQP-complete matrix problem"; the arXiv document is the same work by the same two authors under a different title.