dorsal/arxiv
View SchemaSeveral natural BQP-Complete problems
| Authors | Pawel Wocjan, Shengyu Zhang |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0606179 |
| URL | https://arxiv.org/abs/quant-ph/0606179 |
Abstract
A central problem in quantum computing is to identify computational tasks which can be solved substantially faster on a quantum computer than on any classical computer. By studying the hardest such tasks, known as BQP-complete problems, we deepen our understanding of the power and limitations of quantum computers. We present several BQP-complete problems, including Local Hamiltonian Eigenvalue Sampling and Phase Estimation Sampling. Different than the previous known BQP-complete problems (the Quadratically Signed Weight Enumerator problem [KL01] and the Approximation of Jones Polynomials [FKW02, FLW02, AJL06]), our problems are of a basic linear algebra nature and are closely related to the well-known quantum algorithm and quantum complexity theories.
{
"annotation_id": "ad2b3baf-3eed-4da4-a768-2a51e27376c1",
"date_created": "2026-03-02T18:02:27.609000Z",
"date_modified": "2026-03-02T18:02:27.609000Z",
"file_hash": "744095f5da256a8c643548f9daeba784c97292bde87548211408e1f76e8334ed",
"private": false,
"record": {
"abstract": "A central problem in quantum computing is to identify computational tasks\nwhich can be solved substantially faster on a quantum computer than on any\nclassical computer. By studying the hardest such tasks, known as BQP-complete\nproblems, we deepen our understanding of the power and limitations of quantum\ncomputers. We present several BQP-complete problems, including Local\nHamiltonian Eigenvalue Sampling and Phase Estimation Sampling. Different than\nthe previous known BQP-complete problems (the Quadratically Signed Weight\nEnumerator problem [KL01] and the Approximation of Jones Polynomials [FKW02,\nFLW02, AJL06]), our problems are of a basic linear algebra nature and are\nclosely related to the well-known quantum algorithm and quantum complexity\ntheories.",
"arxiv_id": "quant-ph/0606179",
"authors": [
"Pawel Wocjan",
"Shengyu Zhang"
],
"categories": [
"quant-ph"
],
"title": "Several natural BQP-Complete problems",
"url": "https://arxiv.org/abs/quant-ph/0606179"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8d0faf85-7f0f-4c41-a62e-93efa96b8564",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}