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.

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.

1 aHietala, Kesha1 aRand, Robert1 aHung, Shih-Han1 aLi, Liyi1 aHicks, Michael uhttps://arxiv.org/abs/2010.0124001742nas a2200169 4500008004100000245004400041210004400085260001500129520128400144100001301428700002301441700001901464700001801483700001501501700001901516856003701535 2021 eng d00aVerified Compilation of Quantum Oracles0 aVerified Compilation of Quantum Oracles c12/13/20213 aQuantum 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.

1 aLi, Liyi1 aVoichick, Finnegan1 aHietala, Kesha1 aPeng, Yuxiang1 aWu, Xiaodi1 aHicks, Michael uhttps://arxiv.org/abs/2112.06700