Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> We establish fundamental and general techniques for formal verification of quantum protocols. Quantum protocols are novel communication schemes involving the use of quantum-mechanical phenomena for representation, storage and transmission of data. As opposed to quantum computers, quantum communication systems can and have been implemented using present-day technology; therefore, the ability to model and analyse such systems rigorously is of primary importance. ::: While current analyses of quantum protocols use a traditional mathematical approach and require considerable understanding of the underlying physics, we argue that automated verification techniques provide an elegant alternative. We demonstrate these techniques through the use of PRISM, a probabilistic model-checking tool. Our approach is conceptually simpler than existing proofs, and allows us to disambiguate protocol definitions and assess their properties. It also facilitates detailed analyses of actual implemented systems. We illustrate our techniques by modelling a selection of quantum protocols (namely superdense coding, quantum teleportation, and quantum error correction) and verifying their basic correctness properties. Our results provide a foundation for further work on modelling and analysing larger systems such as those used for quantum cryptography, in which basic protocols are used as components. <s> BIB001 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> Logics for reasoning about quantum states have been given in the literature. In this paper, we extend one such logic with temporal constructs mimicking the standard computational tree logic used to reason about classical transition systems. We investigate the model-checking problem for this temporal quantum logic and illustrate its use by reasoning about the BB84 key distribution protocol. <s> BIB002 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> The novel field of quantum computation and quantum information has been growing at a rapid rate; the study of quantum information in particular has led to the emergence of communication and cryptographic protocols with no classical analogues. Quantum information protocols have interesting properties which are not exhibited by their classical counterparts, but they are most distinguished for their applications in cryptography. Notable results include the unconditional security proof [1] of quantum key distribution. This result, in particular, is one of the reasons for the widespread interest in this field. Furthermore, the implementation of quantum cryptography has been demonstrated in non-laboratory settings and is already an important practical technology. Implementations of quantum cryptography have already been commercially launched and tested by a number of companies including MagiQ, Id Quantique, Toshiba, and NEC. The unconditional security of quantum key distribution protocols does not automatically imply the same degree of security for actual systems, of course; this justifies the need for systems modelling and verification in this setting. <s> BIB003 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> Logics for reasoning about quantum states and their evolution have been given in the literature. In this paper, we consider quantum computation tree logic (QCTL), which adds temporal modalities to exogenous quantum propositional logic. We give a sound and complete axiomatization of QCTL and combine the standard CTL model-checking algorithm with the dEQPL model-checking algorithm to obtain a model-checking algorithm for QCTL. Finally, we illustrate the use of the logic by reasoning about the BB84 key distribution protocol. <s> BIB004 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> We describe model-checking techniques for protocols arising in quantum information theory and quantum cryptography. We discuss the theory and implementation of practical model checker, QMC, for quantum protocols. In our framework, we assume that the quantum operations performed in a protocol are restricted to those within stabilizer formalism; while this particular set of operations is not universal for quantum computation, it allows us to develop models of several useful protocols as well as of systems involving both classical and quantum information processing. We discuss the modeling language of QMC, the logic used for verification, the verification algorithms that have been implemented in the tool. We demonstrate our techniques with applications to number of case studies, including quantum teleportation and BB84 quantum coin-flipping protocol <s> BIB005 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> Quantum communication is a rapidly growing area of research and development. While the successful construction of a large-scale quantum computer may be some years away, there are already commercial implementations of secure communication using quantum cryptography. The application of formal methods to classical communication and cryptographic systems has been very successful, and is now widely used in industry by organisations such as Intel, Microsoft and NASA. There is reason to believe that similar benefits can be expected for the verification of quantum systems. ::: ::: In this thesis, we focus on the use of process calculus, specifically Communicating Quantum Processes (CQP), for the analysis of quantum protocols. Congruence relations are an important aspect of process calculus, since they provide the foundation for equational reasoning. Previous work on congruence relations for quantum processes excluded the classical information arising from measurements, and was therefore unable to analyse many of the interesting known quantum communication protocols. Developing a congruence relation for general quantum processes is difficult because of the interaction between measurement, entanglement and parallel composition. ::: ::: We define a labelled transition relation for CQP in order to describe external interactions. Based on this semantics, we define a notion of observational equivalence for CQP processes, namely probabilistic branching bisimilarity. We find that this relation is not preserved by parallel composition, however we are able to gain a deeper understanding of the link between probabilistic branching and measurement. Based on this newfound understanding, we present a novel semantics for quantum processes, combining mixed quantum states with probabilistic branching. With respect to this new semantic model, we define full probabilistic branching bisimilarity and prove that it is a congruence. We use this congruence relation to discuss an axiomatic approach to the verification of quantum processes. The quantum teleportation protocol is used as a primary example throughout, and we prove that it is congruent to a quantum channel. ::: ::: We define a translation from CQP to the Quantum Model Checker (QMC) in order to provide automated verification techniques using CQP specifications. We prove that this translation preserves the semantics of CQP processes, thereby enabling a multifaceted approach to formal verification by enhancing the manual techniques of process calculus with the benefits of model checking. <s> BIB006 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> Quantum communication is a rapidly growing area of research and development. Quantum cryptography has already been implemented for secure communication, and commercial solutions are available. The application of formal methods to classical computing and communication systems has been very successful, and is widely used by industry. We expect similar benefits for the verification of quantum systems. Communicating Quantum Processes (CQP) is a process calculus based on the π-calculus with the inclusion of primitives for quantum information. Process calculi provide an algebraic approach to system specification and behavioural analysis. The Quantum Model Checker (QMC) is a tool for the automated verification of system correctness. Through an exhaustive search of the possible executions, QMC can check that correctness properties expressed using temporal logic formulae are satisfied. In this paper we describe our approach to the verification of quantum systems using a combination of process calculus and model checking. We also define a formal translation from CQP to the modelling language used by QMC and prove that this preserves the semantics of all supported CQP processes. © 2012 Old City Publishing, Inc. <s> BIB007 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> Quantum Information Processing (QIP) is an emerging area at the intersection of physics and computer science. It aims to establish the principles of communication and computation for systems based on the theory of quantum mechanics. Interesting QIP protocols such as quantum key distribution, teleportation, and blind quantum computation have already been realised in the laboratory and are now in the realm of mainstream industrial applications. The complexity of these protocols, along with possible inaccuracies in implementation, demands systematic and formal analysis. In this paper, we present a new technique and a tool, with a high-level interface, for verification of quantum protocols using equivalence checking. Previous work by Gay, Nagarajan and Papanikolaou used model-checking to verify quantum protocols represented in the stabilizer formalism, a restricted model which can be simulated efficiently on classical computers. Here, we are able to go beyond stabilizer states and verify protocols efficiently on all input states. <s> BIB008 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> We present a tool which uses a concurrent language for describing quantum systems, and performs verification by checking equivalence between specification and implementation. In general, simulation of quantum systems using current computing technology is infeasible. We restrict ourselves to the stabilizer formalism, in which there are efficient simulation algorithms. In particular, we consider concurrent quantum protocols that behave functionally in the sense of computing a deterministic input-output relation for all interleavings of the concurrent system. Crucially, these input-output relations can be abstracted by superoperators, enabling us to take advantage of linearity. This allows us to analyse the behaviour of protocols with arbitrary input, by simulating their operation on a finite basis set consisting of stabilizer states. Despite the limitations of the stabilizer formalism and also the range of protocols that can be analysed using this approach, we have applied our equivalence checking tool to specify and verify interesting and practical quantum protocols from teleportation to secret sharing. <s> BIB009 </s> Model Checking Quantum Systems --- A Survey <s> II. EARLY RESEARCH ON MODEL CHECKING OF QUANTUM SYSTEMS <s> When elementary quantum systems, such as polarized photons, are used to transmit digital information, the uncertainty principle gives rise to novel cryptographic phenomena unachievable with traditional transmission media, e.g. a communications channel on which it is impossible in principle to eavesdrop without a high probability of disturbing the transmission in such a way as to be detected. Such a quantum channel can be used in conjunction with ordinary insecure classical channels to distribute random key information between two users with the assurance that it remains unknown to anyone else, even when the users share no secret information initially. We also present a protocol for coin-tossing by exchange of quantum messages, which is secure against traditional kinds of cheating, even by an opponent with unlimited computing power, but ironically can be subverted by use of a still subtler quantum phenomenon, the Einstein-Podolsky-Rosen paradox. <s> BIB010
Despite the difficulties discussed in the previous section, quite a few model-checking techniques for quantum systems have been developed in the last 10 years. The earliest work mainly targeted checking quantum communication protocols: • Taking the probabilism arising from quantum measurements into account, BIB001 used the probabilistic modelchecker PRISM  to verify the correctness of quantum protocols, including superdense coding, quantum teleportation and quantum error correction. • A branching-time temporal extension (called quantum computation tree logic or QCTL for short) of exogenous quantum propositional logic  was introduced and then the model-checking problem for this logic was studied in BIB002 , BIB004 , with verification of the correctness of quantum key distribution BB84 BIB010 as an application. • A linear temporal extension QLTL of exogenous quantum propositional logic  was then defined and the corresponding model-checking problem was investigated in  . • Model-checking techniques were developed in BIB006 , BIB007 for quantum communication protocols modelled in process algebra CQP (Communicating Quantum Processes)  . The checked properties are specified by the quantum computation tree logic QCTL defined in BIB004 . • A model-checker for quantum communication protocols was also developed in BIB003 ,  , BIB005 , where the checked properties are specified by QCTL BIB004 too, but only the protocols that can be modelled as quantum circuits expressible in the stabiliser formalism  were considered. In BIB008 , BIB009 , this technique was extended beyond stabiliser states and used to check equivalence of quantum protocols.