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 - Verified Compilation of Quantum Oracles Y1 - 2021 A1 - Liyi Li A1 - Finnegan Voichick A1 - Kesha Hietala A1 - Yuxiang Peng A1 - Xiaodi Wu A1 - Michael Hicks AB -

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.

UR - https://arxiv.org/abs/2112.06700 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 - 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 - TY - JOUR T1 - Quantitative Robustness Analysis of Quantum Programs (Extended Version) JF - Proc. ACM Program. Lang. Y1 - 2018 A1 - Shih-Han Hung A1 - Kesha Hietala A1 - Shaopeng Zhu A1 - Mingsheng Ying A1 - Michael Hicks A1 - Xiaodi Wu AB -

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.

VL - 3 U4 - Article 31 UR - https://arxiv.org/abs/1811.03585 CP - POPL U5 - https://doi.org/10.1145/3290344 ER -