This is an artifact for the paper "pfoqcompiler: Efficient Compilation of Quantum Control in Recursive First-Order Quantum Programs". pfoqcompiler is a compiler for First-Order Quantum (FOQ) programs that outputs Qiskit circuits, implementing the 'anchoring and merging' compilation technique and including static analysis tools that ensure complexity bounds on circuit size and depth.
This is an artifact for the paper "pfoqcompiler: Efficient Compilation of Quantum Control in Recursive First-Order Quantum Programs". pfoqcompiler is a compiler for First-Order Quantum (FOQ) programs that outputs Qiskit circuits, implementing the 'anchoring and merging' compilation technique and including static analysis tools that ensure complexity bounds on circuit size and depth.
Recursive quantum control allows for simple and concise descriptions of algorithms. However, a naive circuit compilation sequentializes the different branches of the quantum if-statement and results in an exponential increase in circuit depth. Existing techniques can parallelize these branches, but do so at the cost of an exponential number of ancillary qubits. We present pfoqcompiler, a compiler targeting Qiskit for the first-order quantum programming language FOQ that exploits program structure to merge compatible recursive procedure calls across quantum branches. We introduce weaker syntactically-checkable conditions for well-foundedness, recursive halving, and uniformity, while preserving previously demonstrated complexity characterizations. For weakly well-founded bounded-width programs, the compiler produces polynomial-size circuits; weakly recursively halving programs additionally yield polylogarithmic depth, while weak uniformity removes the asymptotic overhead of branch sequentialization.
As quantum computing emerges as a promising computational paradigm, quantum programming languages provide the tools that bridge the distance between abstract programming and its hardware implementation. In some cases, restricted programming languages may even provide an avenue for more efficient circuit compilation strategies. In this work, we introduce foq , a first-order quantum programming language which allows for quantum control and recursion, and where a syntactically restricted subset of programs ( pfoq ) is shown to be sound and complete for quantum polytime computation. This is achieved by bounding both the recursion depth and the branching width of programs, which we demonstrate to still be compatible with various interesting applications, such as quantum teleportation and the quantum Fourier transform. pfoq constitutes the first programming-language-based characterization of the quantum complexity class fbqp , and we provide a semantics-preserving compilation algorithm such that any pfoq program can be compiled into a quantum circuit that grows polynomially on its number of input qubits, using an anchoring-and-merging technique to solve the problem of branch sequentialization.
Most existing quantum programming languages are based on the quantum circuit model of computation, as higher-level abstractions are particularly challenging to implement—especially ones relating to quantum control flow. The Qunity language, proposed by Voichick et al., offered such an abstraction in the form of a quantum control construct, with great care taken to ensure that the resulting language is still realizable. However, Qunity lacked a working implementation, and the originally proposed compilation procedure was very inefficient, with even simple quantum algorithms compiling to unreasonably large circuits. In this work, we focus on the efficient compilation of high-level quantum control flow constructs, using Qunity as our starting point. We introduce a wider range of abstractions on top of Qunity’s core language that offer compelling trade-offs compared to its existing control construct. We create a complete implementation of a Qunity compiler, which converts high-level Qunity code into the quantum assembly language OpenQASM 3. We develop optimization techniques for multiple stages of the Qunity compilation procedure, including both low-level circuit optimizations as well as methods that consider the high-level structure of a Qunity program, greatly reducing the number of qubits and gates used by the compiler.
Variational quantum compiling (VQC) algorithms aim to approximate deep quantum circuits with shallow parameterized ansatzes, making them more suitable for NISQ hardware. In this article a variant of VQC named the recursive variational quantum compiling (RVQC) algorithm is proposed. Existing VQC algorithms typically require coherently executing the full circuit during compilation. Under the influence of noise, sufficiently deep target circuits make compiling unfeasible using ordinary VQC. Since the compiling is often accomplished using a gradient-based quantum-classical approach, the quantum noise manifest as a noisy gradient during optimization, making convergence hard to obtain. On the other hand, RVQC can compile a circuit by first dividing it into N shorter sub-circuits, then evaluate one sub-circuit at a time. As a result, the circuit depth required to implement RVQC is not dependent on the depth of the target circuit, but on the depth of the sub-circuits. Choosing a high enough N thus ensures sufficiently shallow sub-circuit which can be successfully compiled individually. We show mathematical evidence of this property. RVQC was compared with VQC on a noise model of the IBM Santiago device with the goal of compiling several randomly generated five-qubit circuits of approximately depth 1000. It was shown that VQC was not able to converge within 500 iterations of optimization. On the other hand, RVQC was able to converge to a fidelity of 0.90±0.05 within a total of 500 iterations when splitting the target circuits into N=5 parts. We argue that this comes as a result of the mitigation of noise-induced barren plateaus.
Realizing a conceptual quantum algorithm on an actual physical device necessitates the algorithm's quantum circuit description to undergo certain transformations in order to adhere to all constraints imposed by the hardware. In this regard, the individual high-level circuit components are first synthesized to the supported low-level gate-set of the quantum computer, before being mapped to the target's architecture-utilizing several optimizations in order to improve the compilation result. Specialized tools for this complex task exist, e.g., IBM's Qiskit, Google's Cirq, Microsoft's QDK, or Rigetti's Forest. However, to date, the circuits resulting from these tools are hardly verified, which is mainly due to the immense complexity of checking if two quantum circuits indeed realize the same functionality. In this paper, we propose an efficient scheme for quantum circuit equivalence checking-specialized for verifying results of the IBM Qiskit quantum circuit compilation flow. To this end, we combine characteristics unique to quantum computing, e.g., its inherent reversibility, and certain knowledge about the compilation flow into a dedicated equivalence checking strategy. Experimental evaluations confirm that the proposed scheme allows to verify even large circuit instances with tens of thousands of operations within seconds or even less, whereas state-of-the-art techniques frequently time-out or require substantially more runtime. A corresponding open source implementation of the proposed method is publicly available at https://github.com/iic-jku/qcec.