Physics – Quantum Physics
Scientific paper
2002-12-16
Physics
Quantum Physics
16 pages, 1 PS figure
Scientific paper
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.
Beaudry Martin
Fernandez José M.
Holzer Markus
No associations
LandOfFree
A common algebraic description for probabilistic and quantum computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A common algebraic description for probabilistic and quantum computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A common algebraic description for probabilistic and quantum computations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-259710