dorsal/arxiv
View SchemaEstimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
| Authors | Dominik Janzing, Pawel Wocjan |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0606229 |
| URL | https://arxiv.org/abs/quant-ph/0606229 |
Abstract
Let A be a real symmetric matrix of size N such that the number of the non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are specified by an efficiently computable function. We consider the problem of estimating an arbitrary diagonal entry (A^m)_jj of the matrix A^m up to an error of \epsilon b^m, where b is an a priori given upper bound on the norm of A, m and \epsilon are polylogarithmic and inverse polylogarithmic in N, respectively. We show that this problem is BQP-complete. It can be solved efficiently on a quantum computer by repeatedly applying measurements of A to the jth basis vector and raising the outcome to the mth power. Conversely, every quantum circuit that solves a problem in BQP can be encoded into a sparse matrix such that some basis vector |j> corresponding to the input induces two different spectral measures depending on whether the input is accepted or not. These measures can be distinguished by estimating the mth statistical moment for some appropriately chosen m, i.e., by the jth diagonal entry of A^m. The problem is still in BQP when generalized to off-diagonal entries and it remains BQP-hard if A has only -1, 0, and 1 as entries.
{
"annotation_id": "f03d7211-dd08-4751-97f3-3a1429f9b791",
"date_created": "2026-03-02T18:02:26.741000Z",
"date_modified": "2026-03-02T18:02:26.741000Z",
"file_hash": "5e3b3aa5a242db21a05c2243081721c7d8467a56cb1a014faadefa6faa505854",
"private": false,
"record": {
"abstract": "Let A be a real symmetric matrix of size N such that the number of the\nnon-zero entries in each row is polylogarithmic in N and the positions and the\nvalues of these entries are specified by an efficiently computable function. We\nconsider the problem of estimating an arbitrary diagonal entry (A^m)_jj of the\nmatrix A^m up to an error of \\epsilon b^m, where b is an a priori given upper\nbound on the norm of A, m and \\epsilon are polylogarithmic and inverse\npolylogarithmic in N, respectively.\n We show that this problem is BQP-complete. It can be solved efficiently on a\nquantum computer by repeatedly applying measurements of A to the jth basis\nvector and raising the outcome to the mth power. Conversely, every quantum\ncircuit that solves a problem in BQP can be encoded into a sparse matrix such\nthat some basis vector |j\u003e corresponding to the input induces two different\nspectral measures depending on whether the input is accepted or not. These\nmeasures can be distinguished by estimating the mth statistical moment for some\nappropriately chosen m, i.e., by the jth diagonal entry of A^m. The problem is\nstill in BQP when generalized to off-diagonal entries and it remains BQP-hard\nif A has only -1, 0, and 1 as entries.",
"arxiv_id": "quant-ph/0606229",
"authors": [
"Dominik Janzing",
"Pawel Wocjan"
],
"categories": [
"quant-ph"
],
"title": "Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete",
"url": "https://arxiv.org/abs/quant-ph/0606229"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9db49b42-f09f-49a1-9b7e-5ebec27fd12a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}