Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Theoretical Computer Science

A common algebraic description for probabilistic and quantum computations

Martin Beaudry, José M. Fernandez, Markus Holzer

Published Aug 16, 2005• 4 citations
Publisher
DOI
10.1016/j.tcs.2005.07.008

Related papers

A Common Algebraic Description for Probabilistic and Quantum Computations

Martin Beaudry, José M. Fernandez, Markus Holzer

arXiv:quant-ph/0212096•Lecture notes in computer science•Jan 1, 2004•3 citations

Probabilistic Process Algebra to Unifying Quantum and Classical Computing in Closed Systems

Yong Wang

arXiv:1610.02500•International Journal of Theoretical Physics•Sep 5, 2019•2 citations

A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract)

Martin Beaudry, José M. Fernandez, Markus Holzer

Through the study of gate arrays we develop a unified frame- work to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this ba- sis we show how to encode a probabilistic or quantum gate array into a sum-free tensor formula which satisfies the conditions of the partial trace problem, and vice-versa. In this way complete problems for the classes pr-BPP (promise BPP) and pr-BQP (promise BQP) are given when changing the semiring from (Q + , + , · ) to the field (Q, + , · ). Moreover, by variants of the problem under consideration, classes like ⊕P, NP, C=P, its complement co-C=P, the promise version of Valiant's class UP, its generalization promise SPP, and unique polytime US are captured as problem property and the semiring varies.

Mathematical Foundations of Computer Science•Jan 1, 2004•0 citations

Probabilistic Logics in Quantum Computation

Héctor Freytes, Antonio Ledda, Giuseppe Sergioli +1 more

Springer eBooks•Jan 1, 2013•4 citations

Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations

Masami Amano, Kazuo Iwama, Rudy Raymond Harry Putra

arXiv:quant-ph/0204075•Lecture notes in computer science•Jan 1, 2002•1 citation

A probabilistic branching bisimulation for quantum processes

Marie Lalire

Full formal descriptions of algorithms making use of quantum principles must take into account both quantum and classical computing components and assemble them so that they communicate and cooperate.Moreover, to model concurrent and distributed quantum computations, as well as quantum communication protocols, quantum to quantum communications which move qubits physically from one place to another must also be taken into account. Inspired by classical process algebras, which provide a framework for modeling cooperating computations, a process algebraic notation is defined, which provides a homogeneous style to formal descriptions of concurrent and distributed computations comprising both quantum and classical parts.Based upon an operational semantics which makes sure that quantum objects, operations and communications operate according to the postulates of quantum mechanics, a probabilistic branching bisimulation is defined among processes considered as having the same behavior.

arXiv:quant-ph/0508116•Aug 16, 2005•6 citations
Through the study of gate arrays we develop a unified frame- work to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this ba- sis we show how to encode a probabilistic or quantum gate array into a sum-free tensor formula which satisfies the conditions of the partial trace problem, and vice-versa. In this way complete problems for the classes pr-BPP (promise BPP) and pr-BQP (promise BQP) are given when changing the semiring from (Q + , + , · ) to the field (Q, + , · ). Moreover, by variants of the problem under consideration, classes like ⊕P, NP, C=P, its complement co-C=P, the promise version of Valiant's class UP, its generalization promise SPP, and unique polytime US are captured as problem property and the semiring varies.
Full formal descriptions of algorithms making use of quantum principles must take into account both quantum and classical computing components and assemble them so that they communicate and cooperate.Moreover, to model concurrent and distributed quantum computations, as well as quantum communication protocols, quantum to quantum communications which move qubits physically from one place to another must also be taken into account. Inspired by classical process algebras, which provide a framework for modeling cooperating computations, a process algebraic notation is defined, which provides a homogeneous style to formal descriptions of concurrent and distributed computations comprising both quantum and classical parts.Based upon an operational semantics which makes sure that quantum objects, operations and communications operate according to the postulates of quantum mechanics, a probabilistic branching bisimulation is defined among processes considered as having the same behavior.