  We initiate the study of parallel quantum programming by defining the
operational and denotational semantics of parallel quantum programs. The
technical contributions of this paper include: (1) find a series of useful
proof rules for reasoning about correctness of parallel quantum programs; (2)
prove a (relative) completeness of our proof rules for partial correctness of
disjoint parallel quantum programs; and (3) prove a strong soundness theorem of
the proof rules showing that partial correctness is well maintained at each
step of transitions in the operational semantics of a general parallel quantum
program (with shared variables). This is achieved by partially overcoming the
following conceptual challenges that are never present in classical parallel
programming: (i) the intertwining of nondeterminism caused by quantum
measurements and introduced by parallelism; (ii) entanglement between component
quantum programs; and (iii) combining quantum predicates in the overlap of
state Hilbert spaces of component quantum programs with shared variables.
Applications of the techniques developed in this paper are illustrated by a
formal verification of Bravyi-Gosset-K\"onig's parallel quantum algorithm
solving a linear algebra problem, which gives for the first time an
unconditional proof of a computational quantum advantage.
