%0 Conference Paper %B The Second International Workshop on Programming Languages for Quantum Computing (PLanQC 2021) %D 2021 %T Expanding the VOQC Toolkit %A Kesha Hietala %A Liyi Li %A Akshaj Gaur %A Aaron Green %A Robert Rand %A Xiaodi Wu %A Michael Hicks %X

voqc [Hietala et al. 2021b] (pronounced “vox”) is a compiler for quantum circuits, in the style of
tools like Qiskit [Aleksandrowicz et al. 2019], tket [Cambridge Quantum Computing Ltd 2019],
Quilc [Rigetti Computing 2019], and Cirq [Developers 2021]. What makes voqc different from these
tools is that it has been formally verified in the Coq proof assistant [Coq Development Team 2019].
voqc source programs are expressed in sqir, a simple quantum intermediate representation, which
has a precise mathematical semantics. We use Gallina, Coq’s programming language, to implement
voqc transformations over sqir programs, and use Coq to prove the source program’s semantics
are preserved. We then extract these Gallina definitions to OCaml, and compile the OCaml code to
a library that can operate on standard-formatted circuits.
voqc, and sqir, were built to be general-purpose. For example, while we originally designed sqir
for use in verified optimizations, we subsequently found sqir could also be suitable for writing, and
proving correct, source programs [Hietala et al. 2021a]. We have continued to develop the voqc
codebase to expand its reach and utility.
In this abstract, we present new extensions to voqc as an illustration of its flexibility. These
include support for calling voqc transformations from Python, added support for new gate sets
and optimizations, and the extension of our notion of correctness to include mapping-preservation,
which allows us to apply optimizations after mapping, reducing the cost introduced by making a
program conform to hardware constraints.

%B The Second International Workshop on Programming Languages for Quantum Computing (PLanQC 2021) %8 06/2021 %G eng %U http://rand.cs.uchicago.edu/files/planqc_2021c.pdf %0 Journal Article %J Schloss Dagstuhl %D 2021 %T Proving Quantum Programs Correct %A Kesha Hietala %A Robert Rand %A Shih-Han Hung %A Liyi Li %A Michael Hicks %X

As quantum computing steadily progresses from theory to practice, programmers are faced with a common problem: How can they be sure that their code does what they intend it to do? This paper presents encouraging results in the application of mechanized proof to the domain of quantum programming in the context of the SQIR development. It verifies the correctness of a range of a quantum algorithms including Simon's algorithm, Grover's algorithm, and quantum phase estimation, a key component of Shor's algorithm. In doing so, it aims to highlight both the successes and challenges of formal verification in the quantum context and motivate the theorem proving community to target quantum computing as an application domain.

%B Schloss Dagstuhl %8 7/13/2021 %G eng %U https://arxiv.org/abs/2010.01240 %R https://doi.org/10.4230/LIPIcs.ITP.2021.21 %0 Journal Article %J Proceedings of the ACM on Programming Languages %D 2021 %T A Verified Optimizer for Quantum Circuits %A Kesha Hietala %A Robert Rand %A Shih-Han Hung %A Xiaodi Wu %A Michael Hicks %X

We present VOQC, the first fully verified compiler for quantum circuits, written using the Coq proof assistant. Quantum circuits are expressed as programs in a simple, low-level language called SQIR, which is deeply embedded in Coq. Optimizations and other transformations are expressed as Coq functions, which are proved correct with respect to a semantics of SQIR programs. We evaluate VOQC's verified optimizations on a series of benchmarks, and it performs comparably to industrial-strength compilers. VOQC's optimizations reduce total gate counts on average by 17.7% on a benchmark of 29 circuit programs compared to a 10.7% reduction when using IBM's Qiskit compiler.

%B Proceedings of the ACM on Programming Languages %V 5 %8 11/12/2020 %G eng %U https://arxiv.org/abs/1912.02250 %N POPL %R https://doi.org/10.1145/3434318 %0 Journal Article %J EPTCS %D 2019 %T ReQWIRE: Reasoning about Reversible Quantum Circuits %A Robert Rand %A Jennifer Paykin %A Dong-Ho Lee %A Steve Zdancewic %X

Common quantum algorithms make heavy use of ancillae: scratch qubits that are initialized at some state and later returned to that state and discarded. Existing quantum circuit languages let programmers assert that a qubit has been returned to the |0> state before it is discarded, allowing for a range of optimizations. However, existing languages do not provide the tools to verify these assertions, introducing a potential source of errors. In this paper we present methods for verifying that ancillae are discarded in the desired state, and use these methods to implement a verified compiler from classical functions to quantum oracles.

%B EPTCS %V 287 %G eng %U https://arxiv.org/abs/1901.10118 %9 In Proceedings QPL 2018, arXiv:1901.09476 %& 299-312 %R https://doi.org/10.4204/EPTCS.287.17 %0 Journal Article %D 2019 %T Verification Logics for Quantum Programs %A Robert Rand %X

We survey the landscape of Hoare logics for quantum programs. We review three papers: "Reasoning about imperative quantum programs" by Chadha, Mateus and Sernadas; "A logic for formal verification of quantum programs" by Yoshihiko Kakutani; and "Floyd-hoare logic for quantum programs" by Mingsheng Ying. We compare the mathematical foundations of the logics, their underlying languages, and the expressivity of their assertions. We also use the languages to verify the Deutsch-Jozsa Algorithm, and discuss their relative usability in practice.

%G eng %U https://arxiv.org/abs/1904.04304 %9 Originally submitted in March 2016 as a qualifying examination (WPE-II) for the PhD program at the University of Pennsylvania %0 Journal Article %D 2019 %T Verified Optimization in a Quantum Intermediate Representation %A Kesha Hietala %A Robert Rand %A Shih-Han Hung %A Xiaodi Wu %A Michael Hicks %X

We present sqire, a low-level language for quantum computing and verification. sqire uses a global register of quantum bits, allowing easy compilation to and from existing `quantum assembly' languages and simplifying the verification process. We demonstrate the power of sqire as an intermediate representation of quantum programs by verifying a number of useful optimizations, and we demonstrate sqire's use as a tool for general verification by proving several quantum programs correct.

%8 04/12/2019 %G eng %U https://arxiv.org/abs/1904.06319