Automated equivalence checking of concurrent quantum systems

Article


Ardeshir-Larijani, E., Gay, S. and Nagarajan, R. 2018. Automated equivalence checking of concurrent quantum systems. ACM Transactions on Computational Logic (TOCL). 19 (4), pp. 1-32. https://doi.org/10.1145/3231597
TypeArticle
TitleAutomated equivalence checking of concurrent quantum systems
AuthorsArdeshir-Larijani, E., Gay, S. and Nagarajan, R.
Abstract

The novel field of quantum computation and quantum information has gathered significant momentum in the last few years. It has the potential to radically impact the future of information technology and in influence the development of modern society. The construction of practical, general purpose quantum computers has been challenging, but quantum cryptographic and communication devices have been available in the commercial marketplace for several years. Quantum networks have been built in various cities around the world and a dedicated satellite has been launched by China to provide secure quantum communication. Such new technologies demand rigorous analysis and verification before they can be trusted in safety- and security- critical applications. Experience with classical hardware and software systems has shown the difficulty of achieving robust and reliable implementations.
We present CCSq, a concurrent language for describing quantum systems, and develop verification techniques for checking equivalence between CCSq processes. CCSq has well-defined operational and superoperator semantics for protocols that are functional, in the sense of computing a deterministic input-output relation for all interleavings arising from concurrency in the system. We have implemented QEC (Quantum Equivalence Checker), a tool which takes the specification and implementation of quantum protocols, described in CCSq, and automatically checks their equivalence. For efficiency purposes, we restrict ourselves to Clifford operators in the stabilizer formalism, but we are able to verify protocols over all input states. We have specified and verified a collection of interesting and practical quantum protocols ranging from quantum communication and quantum cryptography to quantum error correction.

Research GroupFoundations of Computing group
LanguageEnglish
PublisherAssociation for Computing Machinery (ACM)
JournalACM Transactions on Computational Logic (TOCL)
ISSN1529-3785
Electronic1557-945X
Publication dates
Print20 Nov 2018
Publication process dates
Deposited25 Jun 2018
Accepted05 Jun 2018
Output statusPublished
Accepted author manuscript
Copyright Statement

© 2018 Association for Computing Machinery.
This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computational Logic (Volume 19, Issue 4), https://doi.org/10.1145/3231597.

Digital Object Identifier (DOI)https://doi.org/10.1145/3231597
Permalink -

https://repository.mdx.ac.uk/item/87v02

Download files


Accepted author manuscript
  • 25
    total views
  • 1
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

Describing and simulating concurrent quantum systems
Bornat, R., Boender, J., Kammueller, F., Poly, G. and Nagarajan, R. 2020. Describing and simulating concurrent quantum systems. Biere, A. and Parker, D. (ed.) International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 20). Dublin 27 - 30 Apr 2020 Springer. pp. 271-277 https://doi.org/10.1007/978-3-030-45237-7_16
Quantum error-correcting output codes
Windridge, D., Mengoni, R. and Nagarajan, R. 2018. Quantum error-correcting output codes. International Journal of Quantum Information. 16 (8). https://doi.org/10.1142/S0219749918400038
A proof-theoretic trust and reputation model for VANET
Primiero, G., Raimondi, F., Chen, T. and Nagarajan, R. 2017. A proof-theoretic trust and reputation model for VANET. S4CIP’17: 2nd Workshop on Safety & Security aSSurance for Critical Infrastructures Protection. Paris, France 29 Apr 2017 Institute of Electrical and Electronics Engineers (IEEE). pp. 146-152 https://doi.org/10.1109/EuroSPW.2017.64
Quantum Bootstrap Aggregation
Windridge, D. and Nagarajan, R. 2017. Quantum Bootstrap Aggregation. de Barros, J., Coecke, B. and Pothos, E. (ed.) Quantum Interaction. San Francisco, CA, USA 20 - 22 Jul 2016 Springer. pp. 115-121 https://doi.org/10.1007/978-3-319-52289-0_9
Hamming distance kernelisation via topological quantum computation
Di Pierro, A., Mengoni, R., Nagarajan, R. and Windridge, D. 2017. Hamming distance kernelisation via topological quantum computation. Martín-Vide C., Neruda R. and Vega-Rodríguez M. (ed.) 6th International Conference on the Theory and Practice of Natural Computing. Prague, Czech Republic 18 - 20 Dec 2017 Springer. pp. 269-280 https://doi.org/10.1007/978-3-319-71069-3_21
Techniques for formal modelling and analysis of quantum systems
Gay, S. and Nagarajan, R. 2013. Techniques for formal modelling and analysis of quantum systems. in: Computation, logic, games, and quantum foundations. The many facets of Samson Abramsky Springer Verlag.
Formalization of quantum protocols using Coq
Boender, J., Kammueller, F. and Nagarajan, R. 2015. Formalization of quantum protocols using Coq. The 12th International Workshop on Quantum Physics and Logic (QPL 2015). Oxford, United Kingdom 15 - 17 Jul 2015 pp. 71-83
Verification of quantum protocols using Coq
Boender, J., Kammueller, F. and Nagarajan, R. 2014. Verification of quantum protocols using Coq. 17th Conference on Quantum Information Processing (QIP). Barcelona, Spain 03 - 07 Feb 2014
Verification of concurrent quantum protocols by equivalence checking
Ardeshir-Larijani, E., Gay, S. and Nagarajan, R. 2014. Verification of concurrent quantum protocols by equivalence checking. TACAS 2014: 20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Grenoble, France 05 - 13 Apr 2014 Springer. https://doi.org/10.1007/978-3-642-54862-8_42
Model checking for communicating quantum processes
Davidson, T., Gay, S., Mlnařík, H., Nagarajan, R. and Papanikolaou, N. 2012. Model checking for communicating quantum processes. International Journal of Unconventional Computing. 8 (1), pp. 73-98.
Lossless quantum prefix compression for communication channels that are always open
Müller, M., Rogers, C. and Nagarajan, R. 2009. Lossless quantum prefix compression for communication channels that are always open. Physical Review A. 79 (1). https://doi.org/10.1103/PhysRevA.79.012302
Equivalence checking of quantum protocols
Ardeshir-Larijani, E., Gay, S. and Nagarajan, R. 2013. Equivalence checking of quantum protocols. in: Piterman, N. and Smolka, S. (ed.) Tools and Algorithms for the Construction and Analysis of Systems : 19th International Conference Proceedings (TACAS 2013). Berlin Springer.
QMC: a model checker for quantum systems
Gay, S., Nagarajan, R. and Papanikolaou, N. 2008. QMC: a model checker for quantum systems. in: Gupta, A. and Malik, S. (ed.) Computer Aided Verification : 20th International Conference, (CAV 2008) Proceedings Berlin Springer.