|
| related topics |
| {let, theorem, proof} |
| {algorithm, log, probability} |
| {qubit, qubits, gate} |
| {time, systems, information} |
| {level, atom, field} |
| {group, space, representation} |
|
A common algebraic description for probabilistic and quantum computations
Martin Beaudry, Jose M. Fernandez, Markus Holzer
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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0212096
- categories:
- quant-ph
- comments:
- 16 pages, 1 PS figure
- arxiv_id:
- quant-ph/0212096
- created:
- 2002-12-16
Full article ▸
|
|
| related documents |
| 0405081v1 |
| 0610235v2 |
| 0401053v1 |
| 0503159v2 |
| 0410229v1 |
| 0605239v4 |
| 0605090v1 |
| 9704044v1 |
| 0308151v2 |
| 0307139v1 |
| 0410120v1 |
| 0702212v1 |
| 0701143v2 |
| 0302022v1 |
| 0305031v1 |
| 0309057v1 |
| 0701037v2 |
| 0603206v1 |
| 0607148v3 |
| 0304145v2 |
| 0506062v2 |
| 9503013v1 |
| 0312164v1 |
| 0502040v2 |
| 0305005v1 |
|