◐Attested & literatureAlgorithmsPromiseBQP-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.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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. 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}.
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 →
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.
How it works
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..
Implementation
Unsupported
sparse-matrix-power-diagonal-entries.txt
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 3equation (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.
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.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete2006 · Dominik Janzing, Pawel Wocjan
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. The Quantum Algorithm Zoo 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.