Certified Quantum Computation in Isabelle/HOL

Anthony Bordg; Hanna Lachnitt; Yijun He

doi:10.1007/s10817-020-09584-7

Certified Quantum Computation in Isabelle/HOL

J Autom Reason. 2021;65(5):691-709. doi: 10.1007/s10817-020-09584-7. Epub 2020 Dec 24.

Authors

Anthony Bordg¹, Hanna Lachnitt², Yijun He³

Affiliations

¹ Department of Computer Science and Technology, University of Cambridge, Cambridge, UK.
² Computer Science Department, Stanford University, Stanford, USA.
³ University of Cambridge, Cambridge, UK.

Abstract

In this article we present an ongoing effort to formalise quantum algorithms and results in quantum information theory using the proof assistant Isabelle/HOL. Formal methods being critical for the safety and security of algorithms and protocols, we foresee their widespread use for quantum computing in the future. We have developed a large library for quantum computing in Isabelle based on a matrix representation for quantum circuits, successfully formalising the no-cloning theorem, quantum teleportation, Deutsch's algorithm, the Deutsch-Jozsa algorithm and the quantum Prisoner's Dilemma. We discuss the design choices made and report on an outcome of our work in the field of quantum game theory.

Keywords: Certification; Deutsch–Jozsa algorithm; Deutsch’s algorithm; Isabelle/HOL; No-cloning; Quantum computing; Quantum prisoner’s dilemma; Quantum teleportation.