A common algebraic description for probabilistic and quantum computations

DOI10.1016/J.TCS.2005.07.008MaRDI QIDQ2575744zbMATH OpenOpenAlexFDO

Authors Martin Beaudry, José M. Fernandez, Markus Holzer

Publication date 6 December 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0212096

zbMATH Keywords

quantum gate array

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68)

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 $FdaggF$ 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.

Recommendations

• Mathematical Foundations of Computer Science 2004
• Quantum computing, postselection, and probabilistic polynomial-time
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Quantum computers that can be simulated classically in polynomial time
• Quantum Computability

Cites work

• A complexity theory for feasible closure properties
• Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
• Gap-definable counting classes
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 3783337 (Why is no real title available?)
• scientific article; zbMATH DE number 107979 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1111784 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• scientific article; zbMATH DE number 1834647 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• On the history of the kronecker product
• On the unique satisfiability problem
• One complexity theorist's view of quantum computing
• Promise problems complete for complexity classes
• Quantum Computability
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Realizable Universal Quantum Logic Gates
• Some observations on the connection between counting and recursion
• The complexity of computing the permanent
• The complexity of promise problems with applications to public-key cryptography
• The complexity of tensor calculus
• Time/Space Trade-Offs for Reversible Computation
• VI.—On Singular Pencils of Zehfuss, Compound, and Schläflian Matrices

Cited in

(3)

• Probabilistic process algebra to unifying quantum and classical computing in closed systems
• scientific article; zbMATH DE number 2013801 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004

This page was built for publication: A common algebraic description for probabilistic and quantum computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575744)