dorsal/arxiv
View SchemaA common algebraic description for probabilistic and quantum computations
| Authors | Martin Beaudry, Jose M. Fernandez, Markus Holzer |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0212096 |
| URL | https://arxiv.org/abs/quant-ph/0212096 |
Abstract
We study the computational complexity of the problem SFT (Sum-free Formula partial Trace): given a tensor formula F over a subsemiring of the complex field (C,+,.) plus a positive integer k, under the restrictions that all inputs are column vectors of L2-norm 1 and norm-preserving square matrices, and that the output matrix is a column vector, decide whether the k-partial trace of $F\dagg{F}$ is superior to 1/2. The k-partial trace of a matrix is the sum of its lowermost k diagonal elements. We also consider the promise version of this problem, where the 1/2 threshold is an isolated cutpoint. We show how to encode a quantum or reversible gate array into a tensor formula which satisfies the above conditions, and vice-versa; we use this to show that the promise version of SFT is complete for the class BPP for formulas over the semiring (Q^+,+,.) of the positive rational numbers, for BQP in the case of formulas defined over the field (Q,+,.), and for P in the case of formulas defined over the Boolean semiring, all under logspace-uniform reducibility. This suggests that the difference between probabilistic and quantum polynomial-time computers may ultimately lie in the possibility, in the latter case, of having destructive interference between computations occuring in parallel.
{
"annotation_id": "2ea956e9-9946-4107-9b70-34308317c8a3",
"date_created": "2026-03-02T18:01:56.339000Z",
"date_modified": "2026-03-02T18:01:56.339000Z",
"file_hash": "2fd037567dd99e68c1e01f9f16e8edc538ae7287b147f0fea7a958d746028148",
"private": false,
"record": {
"abstract": "We study the computational complexity of the problem SFT (Sum-free Formula\npartial Trace): given a tensor formula F over a subsemiring of the complex\nfield (C,+,.) plus a positive integer k, under the restrictions that all inputs\nare column vectors of L2-norm 1 and norm-preserving square matrices, and that\nthe output matrix is a column vector, decide whether the k-partial trace of\n$F\\dagg{F}$ is superior to 1/2. The k-partial trace of a matrix is the sum of\nits lowermost k diagonal elements. We also consider the promise version of this\nproblem, where the 1/2 threshold is an isolated cutpoint. We show how to encode\na quantum or reversible gate array into a tensor formula which satisfies the\nabove conditions, and vice-versa; we use this to show that the promise version\nof SFT is complete for the class BPP for formulas over the semiring (Q^+,+,.)\nof the positive rational numbers, for BQP in the case of formulas defined over\nthe field (Q,+,.), and for P in the case of formulas defined over the Boolean\nsemiring, all under logspace-uniform reducibility. This suggests that the\ndifference between probabilistic and quantum polynomial-time computers may\nultimately lie in the possibility, in the latter case, of having destructive\ninterference between computations occuring in parallel.",
"arxiv_id": "quant-ph/0212096",
"authors": [
"Martin Beaudry",
"Jose M. Fernandez",
"Markus Holzer"
],
"categories": [
"quant-ph"
],
"title": "A common algebraic description for probabilistic and quantum computations",
"url": "https://arxiv.org/abs/quant-ph/0212096"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "fabe1f91-df2a-4240-932f-08277618b54a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}