dorsal/arxiv
View SchemaMeasuring 4-local n-qubit observables could probabilistically solve PSPACE
| Authors | Pawel Wocjan, Dominik Janzing, Thomas Decker, Thomas Beth |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0308011 |
| URL | https://arxiv.org/abs/quant-ph/0308011 |
Abstract
We consider a hypothetical apparatus that implements measurements for arbitrary 4-local quantum observables A on n qubits. The apparatus implements the ``measurement algorithm'' after receiving a classical description of A. We show that a few precise measurements, applied to a basis state would provide a probabilistic solution of PSPACE problems. The error probability decreases exponentially with the number of runs if the measurement accuracy is of the order of the spectral gaps of A. Moreover, every decision problem which can be solved on a quantum computer in T time steps can be encoded into a 4-local observable such that the solution requires only measurements of accuracy O(1/T). Provided that BQP<>PSPACE, our result shows that efficient algorithms for precise measurements of general 4-local observables cannot exist. We conjecture that the class of physically existing interactions is large enough to allow the conclusion that precise energy measurements for general many-particle systems require control algorithms with high complexity.
{
"annotation_id": "bc195cac-8c4c-48d7-970f-11c62d307745",
"date_created": "2026-03-02T18:01:59.756000Z",
"date_modified": "2026-03-02T18:01:59.756000Z",
"file_hash": "698b8896bfbde8399ff392b61d58c8cab168bea06484c98347c813680cc8ebc5",
"private": false,
"record": {
"abstract": "We consider a hypothetical apparatus that implements measurements for\narbitrary 4-local quantum observables A on n qubits. The apparatus implements\nthe ``measurement algorithm\u0027\u0027 after receiving a classical description of A. We\nshow that a few precise measurements, applied to a basis state would provide a\nprobabilistic solution of PSPACE problems. The error probability decreases\nexponentially with the number of runs if the measurement accuracy is of the\norder of the spectral gaps of A.\n Moreover, every decision problem which can be solved on a quantum computer in\nT time steps can be encoded into a 4-local observable such that the solution\nrequires only measurements of accuracy O(1/T).\n Provided that BQP\u003c\u003ePSPACE, our result shows that efficient algorithms for\nprecise measurements of general 4-local observables cannot exist. We conjecture\nthat the class of physically existing interactions is large enough to allow the\nconclusion that precise energy measurements for general many-particle systems\nrequire control algorithms with high complexity.",
"arxiv_id": "quant-ph/0308011",
"authors": [
"Pawel Wocjan",
"Dominik Janzing",
"Thomas Decker",
"Thomas Beth"
],
"categories": [
"quant-ph"
],
"title": "Measuring 4-local n-qubit observables could probabilistically solve PSPACE",
"url": "https://arxiv.org/abs/quant-ph/0308011"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f8f90765-5630-4d94-9348-e0ad257a4fc6",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}