%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 %D 2021 %T Verified Compilation of Quantum Oracles %A Liyi Li %A Finnegan Voichick %A Kesha Hietala %A Yuxiang Peng %A Xiaodi Wu %A Michael Hicks %X

Quantum algorithms often apply classical operations, such as arithmetic or predicate checks, over a quantum superposition of classical data; these so-called oracles are often the largest components of a quantum algorithm. To ease the construction of efficient, correct oracle functions, this paper presents VQO, a high-assurance framework implemented with the Coq proof assistant. The core of VQO is OQASM, the oracle quantum assembly language. OQASM operations move qubits among three different bases via the Quantum Fourier Transform and Hadamard operations, thus admitting important optimizations, but without inducing entanglement and the exponential blowup that comes with it. OQASM's design enabled us to prove correct VQO's compilers -- from a simple imperative language called OQIMP to OQASM, and from OQASM to SQIR, a general-purpose quantum assembly language -- and allowed us to efficiently test properties of OQASM programs using the QuickChick property-based testing framework. We have used VQO to implement oracles used in Shor's and Grover's algorithms, as well as several common arithmetic operators. VQO's oracles have performance comparable to those produced by Quipper, a state-of-the-art but unverified quantum programming platform.

%8 12/13/2021 %G eng %U https://arxiv.org/abs/2112.06700 %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 %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 %0 Journal Article %J Proc. ACM Program. Lang. %D 2018 %T Quantitative Robustness Analysis of Quantum Programs (Extended Version) %A Shih-Han Hung %A Kesha Hietala %A Shaopeng Zhu %A Mingsheng Ying %A Michael Hicks %A Xiaodi Wu %X

Quantum computation is a topic of significant recent interest, with practical advances coming from both research and industry. A major challenge in quantum programming is dealing with errors (quantum noise) during execution. Because quantum resources (e.g., qubits) are scarce, classical error correction techniques applied at the level of the architecture are currently cost-prohibitive. But while this reality means that quantum programs are almost certain to have errors, there as yet exists no principled means to reason about erroneous behavior. This paper attempts to fill this gap by developing a semantics for erroneous quantum while-programs, as well as a logic for reasoning about them. This logic permits proving a property we have identified, called ε-robustness, which characterizes possible "distance" between an ideal program and an erroneous one. We have proved the logic sound, and showed its utility on several case studies, notably: (1) analyzing the robustness of noisy versions of the quantum Bernoulli factory (QBF) and quantum walk (QW); (2) demonstrating the (in)effectiveness of different error correction schemes on single-qubit errors; and (3) analyzing the robustness of a fault-tolerant version of QBF.

%B Proc. ACM Program. Lang. %V 3 %P Article 31 %8 2018/12/1 %G eng %U https://arxiv.org/abs/1811.03585 %N POPL %R https://doi.org/10.1145/3290344