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, named QPAlg for Quantum Process Algebra, which provides a homogeneous style to formal descriptions of concurrent and distributed computations comprising both quantum and classical parts. On the quantum side, QPAlg provides quantum variables, operations on quantum variables (unitary operators and measurement observables), as well as new forms of communications involving the quantum world. The operational semantics makes sure that these quantum objects, operations and communications operate according to the postulates of quantum mechanics.

Past years have seen the development of a few proposals for quantum extensions of process calculi. The rationale is clear: with the development of quantum communication protocols, there is a need to abstract and focus on the basic features of quantum concurrent systems, like CCS and CSP have done for their classical counterparts. So far, though, no accepted standard has emerged, neither for the syntax nor for the behavioural semantics. Indeed, the various proposals do not agree on what should be the observational properties of quantum values, and as a matter of fact, the soundness of such properties has never been validated against the prescriptions of quantum theory. To this aim, we introduce a new calculus, Linear Quantum CCS (lqCCS), and investigate the features of behavioural equivalences based on barbs and contexts. Our calculus can be thought of as an asynchronous, linear version of qCCS, which is in turn based on value-passing CCS. The combination of linearity and asynchronous communication fits well with the properties of quantum systems (e.g. the no-cloning theorem), since it ensures that each qubit is sent exactly once, precisely specifying which qubits of a process interact with the context. We exploit contexts to examine how bisimilarities relate to quantum theory. We show that the observational power of general contexts is incompatible with quantum theory: roughly, they can perform non-deterministic moves depending on quantum values without measuring (hence perturbing) them. Therefore, we refine the operational semantics in order to prevent contexts from performing unfeasible non-deterministic choices. This induces a coarser bisimilarity that better fits the quantum setting: ( i ) it lifts the indistinguishability of quantum states to the distributions of processes and, despite the additional constraints, ( i i ) it preserves the expressiveness of non-deterministic choices based on classical information. To the best of our knowledge, our semantics is the first one that satisfies the two properties above.