TY - CONF T1 - Expanding the VOQC Toolkit T2 - The Second International Workshop on Programming Languages for Quantum Computing (PLanQC 2021) Y1 - 2021 A1 - Kesha Hietala A1 - Liyi Li A1 - Akshaj Gaur A1 - Aaron Green A1 - Robert Rand A1 - Xiaodi Wu A1 - Michael Hicks AB -

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.

JA - The Second International Workshop on Programming Languages for Quantum Computing (PLanQC 2021) UR - http://rand.cs.uchicago.edu/files/planqc_2021c.pdf ER - TY - JOUR T1 - Proving Quantum Programs Correct JF - Schloss Dagstuhl Y1 - 2021 A1 - Kesha Hietala A1 - Robert Rand A1 - Shih-Han Hung A1 - Liyi Li A1 - Michael Hicks AB -

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.

UR - https://arxiv.org/abs/2010.01240 U5 - https://doi.org/10.4230/LIPIcs.ITP.2021.21 ER - TY - JOUR T1 - A Verified Optimizer for Quantum Circuits JF - Proceedings of the ACM on Programming Languages Y1 - 2021 A1 - Kesha Hietala A1 - Robert Rand A1 - Shih-Han Hung A1 - Xiaodi Wu A1 - Michael Hicks AB -

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.

VL - 5 UR - https://arxiv.org/abs/1912.02250 CP - POPL U5 - https://doi.org/10.1145/3434318 ER - TY - JOUR T1 - ReQWIRE: Reasoning about Reversible Quantum Circuits JF - EPTCS Y1 - 2019 A1 - Robert Rand A1 - Jennifer Paykin A1 - Dong-Ho Lee A1 - Steve Zdancewic AB -

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.

VL - 287 UR - https://arxiv.org/abs/1901.10118 U5 - https://doi.org/10.4204/EPTCS.287.17 ER - TY - JOUR T1 - Verification Logics for Quantum Programs Y1 - 2019 A1 - Robert Rand AB -

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.

UR - https://arxiv.org/abs/1904.04304 ER - TY - JOUR T1 - Verified Optimization in a Quantum Intermediate Representation Y1 - 2019 A1 - Kesha Hietala A1 - Robert Rand A1 - Shih-Han Hung A1 - Xiaodi Wu A1 - Michael Hicks AB -

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.

UR - https://arxiv.org/abs/1904.06319 ER -