Abstract: In this paper, we propose Proq, a runtime assertion scheme for testing and debugging quantum programs on a quantum computer. The predicates in Proq are represented by projections (or equivalently, closed subspaces of the state space), following Birkhoff-von Neumann quantum logic. The satisfaction of a projection by a quantum state can be directly checked upon a small number of projective measurements rather than a large number of repeated executions. On the theory side, we rigorously prove that checking projection-based assertions can help locate bugs or statistically assure that the semantic function of the tested program is close to what we expect, for both exact and approximate quantum programs. On the practice side, we consider hardware constraints and introduce several techniques to transform the assertions, making them directly executable on the measurement-restricted quantum computers. We also propose to achieve simplified assertion implementation using local projection technique with soundness guaranteed. We compare Proq with existing quantum program assertions and demonstrate the effectiveness and efficiency of Proq by its applications to assert two ingenious quantum algorithms, the Harrow-Hassidim-Lloyd algorithm and Shor’s algorithm.
<< IWQC20 |  Schedule >>

Abstract: We give a finite presentation by generators and relations for the group On(Z[1/2]) of n-dimensional orthogonal matrices with entries in Z[1/2]. We then obtain a similar presentation for the group of n-dimensional orthogonal matrices of the form (1/\sqrt{2})^k M, where k is a nonnegative integer and M is an integer matrix. Both groups arise in the study of quantum circuits. In particular, when the dimension is a power of 2 the elements of the latter group are precisely the matrices that can be represented by a quantum circuit over the universal gate set consisting of the Toffoli gate, the Hadamard gate, and the computational ancilla.
<< IWQC20 |  Schedule >>

Abstract: Here we explore which heuristic quantum algorithms for combinatorial optimization might be most practical to try out on a small fault-tolerant quantum computer. We compile circuits for several variants of quantum accelerated simulated annealing including those using qubitization or Szegedy walks to quantize classical Markov chains and those simulating spectral gap amplified Hamiltonians encoding a Gibbs state. We also optimize fault-tolerant realizations of the adiabatic algorithm, quantum enhanced population transfer, the quantum approximate optimization algorithm, and other approaches. Many of these methods are bottlenecked by calls to the same subroutines; thus, optimized circuits for those primitives should be of interest regardless of which heuristic is most effective in practice. We compile these bottlenecks for several families of optimization problems and report for how long and for what size systems one can perform these heuristics in the surface code given a range of resource budgets. Our results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup will achieve an advantage over classical algorithms on modest superconducting qubit surface code processors without significant improvements in the implementation of the surface code. For instance, under quantum-favorable assumptions (e.g., that the quantum algorithm requires exactly quadratically fewer steps), our analysis suggests that quantum accelerated simulated annealing would require roughly a day and a million physical qubits to optimize spin glasses that could be solved by classical simulated annealing in about four CPU-minutes.
<< IWQC20| Schedule >>

Abstract: Several sophisticated design tools for the compilation of quantum circuits emerged in the recent past. Such tools are necessary for realizing a conceptual quantum algorithm on an actual physical device. In order to adhere to all constraints imposed by the hardware, individual high-level circuit components are typically 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. 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.

We present an equivalence checking methodology for quantum circuits which can be used to efficiently verify the results of compilation flows. To this end, we combine characteristics unique to quantum computing, e.g., its inherent reversibility, and certain knowledge about the considered compilation flow into a dedicated equivalence checking strategy. Evaluations show that the resulting method is capable of verifying circuits composed of tens of thousands of gates within seconds or even less. The applicability of the proposed methods has been shown using the compilation flow of IBM's Qiskit as a representative. The tool is publicly available at https://github.com/iic-jku/qcec and can easily be adapted for other compilation flows as well.
<< IWQC20 |  Schedule >>

Abstract: Quantum algorithms need to be compiled to respect the constraints imposed by quantum processors, which is known as the mapping problem. The mapping procedure will result in an increase of the number of gates and of the circuit latency, decreasing the algorithm's success rate. It is crucial to minimize mapping overhead, especially for Noisy Intermediate-Scale Quantum (NISQ) processors that have relatively short qubit coherence times and high gate error rates. Most of prior mapping algorithms have only considered constraints such as the primitive gate set and qubit connectivity, but the actual gate duration and the restrictions imposed by the use of shared classical control electronics have not been taken into account. In this paper, we present a timing and resource-aware mapper called Qmap to make quantum circuits executable on a scalable superconducting processor named Surface-17 with the objective of achieving the shortest circuit latency. In particular, we propose an approach to formulate the classical control restrictions as resource constraints in a conventional list scheduler with polynomial complexity. Furthermore, we implement a routing heuristic to cope with the connectivity limitation. This router nds a set of movement operations that minimally extends circuit latency. To analyze the mapping overhead and evaluate the performance of different mappers, we map 56 quantum benchmarks onto Surface-17. Compared to a prior mapping strategy that minimizes the number of operations, Qmap can reduce the latency overhead up to 47:3% and operation overhead up to 28:6%, respectively.
<< IWQC20 |  Schedule >>

Abstract: We recently prensented Qbricks: an environment for formally verified quantum programs. The goal of this development is to provide a versatile tool for certified implementation of quantum algorithms. Thanks to Qbricks, we could develop certified implementations for various emblematic quantum algorithms, among which are Grover search algorithm and the quantum part of Shor algorithm. In this abstract we introduce Qbricks and its illustration through these certified implementations. We make a particular focus on Shor circuit implementation, presenting its proved specifications.
<< IWQC20 |  Schedule >>

Abstract: An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum (NISQ) devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the $\T$ gate consumes vastly more resources than the other gates in the gate set.

More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford+T gate set. The Clifford+T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given $n$-qubit unitary $U$, using the minimum possible number of T gates (called the T-count of $U$). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of $U$. In its decision version the goal is to decide if the T-count is at most some positive integer $m$. Given an oracle for COUNT-T, we can compute a T-optimal circuit in time polynomial in the T-count and dimension of $U$. We give a provable classical algorithm that solves COUNT-T (decision) in time $O\left(N^{2(c-1)\lceil\frac{m}{c}\rceil}\poly(m,N)\right)$ and space $O\left(N^{2\lceil\frac{m}{c}\rceil}\poly(m,N)\right)$, where $N=2^n$ and $c\geq 2$. We also introduce an asymptotically faster multiplication method that shaves a factor of $N^{0.7457}$ off of the overall complexity.

Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that solves COUNT-T (optimization) with both space and time $\poly(m,N)$.
While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent) , there is a large improvement by going from exponential to polynomial scaling with m. We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time as well as T-count.
<< IWQC20 |  Schedule >>

Abstract: Translations between the quantum circuit model and the measurement-based one-way model are useful for verification and optimisation of quantum computations. By expressing both one-way computations and circuits in the common language of the ZX-calculus, we give the first algorithm that can translate any one-way computation with extended gflow, i.e. allowing measurements in the XY, XZ, and YZ-planes of the Bloch sphere, into an ancilla-free circuit. Circuits can be optimised by translating them into a one-way computation, optimising this, and translating back.
<< IWQC20 |  Schedule >>

Abstract: We describe a compilation strategy for Variational Quantum Eigensolver (VQE) algorithms which use the Unitary Coupled Cluster (UCC) ansatz, designed to reduce circuit depth and gate count. This is achieved by partitioning Pauli exponential terms into mutually commuting sets. These sets are then diagonalised using Clifford circuits and synthesised using the phase polynomial formalism. This strategy reduces cx depth by 75.4% on average, and by up to 89.9%, compared to naive synthesis for a variety of molecules, qubit encodings and basis sets.
<< IWQC20 |  Schedule >>

Abstract: We consider the task of breaking down a quantum computation given as an isometry into C-NOTs and single-qubit gates, while keeping the number of C-NOT gates small. Although several decompositions are known for general isometries, here we focus on a method based on Householder reflections that adapts well in the case of sparse isometries. We show how to use this method to decompose an arbitrary isometry before illustrating that the method can lead to significant improvements in the case of sparse isometries. We also discuss the classical complexity of this method and illustrate its effectiveness in the case of sparse state preparation by applying it to randomly chosen sparse states.
<< IWQC20 |  Schedule >>

Abstract: We present QFAST, a quantum synthesis tool designed to produce short circuits and to scale well in practice. Our contributions are: 1) a novel representation of circuits able to encode placement and topology; 2) a hierarchical approach with an iterative refinement formulation that combines “coarse-grained” fast optimization during circuit structure search with a good, but slower, optimization stage only in the final circuit instantiation stage. When compared against state-of-the-art techniques, although not optimal, QFAST can generate much shorter circuits for “time-dependent evolution” algorithms used by domain scientists. We also show the composability and tunability of our formulation in terms of circuit depth and running time. For example, we show how to generate shorter circuits by plugging in the best available third party synthesis algorithm at a given hierarchy level. Composability enables portability across chip architectures, which is missing from the available approaches.
<< IWQC20 |  Schedule >>

Abstract: Layout synthesis for quantum computing (LSQC) involves mapping the qubits in quantum programs to physical qubits, scheduling the quantum gates, and inserting some gates, usually SWAP gates, to resolve the hardware connectivity issues. We approach this problem with the ‘measure, then improve’ methodology. Before attempts to solve the problem directly, we first conduct some evaluations on the existing tools. Previously, benchmarks for LSQC are usually circuits of some reversible functions. However, due to the complexity of this problem, it is very hard to find the optimal solution for an arbitrary instance. Thus, we can compare the LSQC tools with each other without knowing how far they are from the optimum. To this end, we construct a family of quantum mapping examples with known optimal, QUEKO, which have known optimal depths and gate counts on given coupling graphs. With QUEKO, we evaluate several leading industry and academic LSQC tools, including Qiskit, Cirq, and t|ket>, and find rather large optimality gaps, up to 45x on some near-term feasible circuits. Now that large optimality gaps are measured, we go on to the ‘improve’ stage. We develop a tool for optimal layout synthesis for quantum computing, OLSQ, which formulates LSQC as a mathematical optimization problem. OLSQ makes use of a more compact representation of the solution space, achieving orders-of-magnitude reductions in runtime and memory than previous optimal solutions. Furthermore, by removing some redundant mapping variables between mapping transformations, we arrive at a more scalable, approximate synthesizer, transition-based (TB-) OLSQ. Compared to t|ket>, TB-OLSQ can reduce 70% SWAP cost in geomean on a set of arithmetic quantum circuits. TB-OLSQ can increase fidelity by 1.3x in geomean compared to TriQ, a leading academic work on fidelity optimization. We also apply some domain-specific knowledge to adjust TB-OLSQ in the LSQC of QAOA circuits, resulting in further reductions in depth and SWAP cost.
<< IWQC20 |  Schedule >>

Abstract: “Qubit routing” refers to the task of modifying quantum circuits so that they satisfy the connectivity constraints of a target quantum computer. This involves inserting SWAP gates into the circuit so that the logical gates only ever occur between adjacent physical qubits. The goal is to minimise the circuit depth added by the SWAP gates.
In this paper, we propose a qubit routing procedure that uses a modified version of the deep Q-learning paradigm. The system is able to outperform the qubit routing procedures from two of the most advanced quantum compilers currently available, on both random and realistic circuits, across near-term architecture sizes.
<< IWQC20 |  Schedule >>

Abstract: A highly anticipated use of quantum computers is the simulation of complex quantum systems including molecules and other many-body systems. One promising method involves directly applying a linear combination of unitaries (LCU) to approximate a Taylor series by truncating after some order. Here we present an adaptation of that method, optimized for Hamiltonians with terms of widely varying magnitude, as is commonly the case in electronic structure calculations. We show that it is more efficient to apply LCU using a truncation that retains larger magnitude terms as determined by an iterative procedure. We obtain bounds on the simulation error for this generalized truncated Taylor method, and for a range of molecular simulations we report these bounds as well as direct numerical emulation results. We find that our adaptive method can typically improve the simulation accuracy by an order of magnitude, for a given circuit depth.
<< IWQC20 |  Schedule >>

Abstract: Many quantum algorithms depend upon a specific initial quantum state that needs to be prepared before the algorithm can perform its computation.
Preparing the state corresponding to the initial data is in general an exponential problem that is often omitted from application performance analysis. However, if initialization be difficult, quantum advantages may not be viable. To avoid this complexity, we have developed two techniques for generating quantum circuits that can prepare certain families of quantum states efficiently.
<< IWQC20 |  Schedule >>

Abstract: Given a unitary matrix, how to decompose it into quantum gates of a universal set is the so-called synthesis problem. In this talk, we focus on the exact synthesis problem, i.e., the unitary is exactly decomposed.

The most frequently used universal set is the Clfford+T gate set. The first algorithm for exact synthesis of single qubit unitaries in terms of the Clfford+T gate set was given by Kliuchnikov et al. in [arXiv:1206.5236]. Later, Giles and Selinger proposed another proof for this synthesis method [arXiv:1312.6584]. Furthermore, they generalised the method of exact synthesis of single qubit Clifford+T unitaries to the multi-qubit cases [arXiv:1212.0506]. All of these results were based on techniques from algebraic number theory.

In this talk, we show a different method on exact synthesis of single qubit Clifford+T unitaries purely in algebraic ZX-calculus [arXiv:1911.06752, 2007.13739]. We demonstrate this method by several concrete examples. We would expect that this result could pave the way for exact synthesis of multi-qubit Clifford+T unitaries in algebraic ZX-calculus.
<< IWQC20 |  Schedule >>

Abstract: We review some modern techniques for implementing reversible functions over the Clifford+T gate set. We give general constructors for implementing classical functions up to phase and for measurement-assisted destruction of temporary values. We then apply these to find T-count efficient constructions of some classical functions including temporary products of k bits in space-constrained regimes.
<< IWQC20 |  Schedule >>

Abstract: We present Tweedledum, an open-source library for synthesizing, manipulating, and optimizing quantum circuits. Written in C++17, the library is header-only, which allows straightforward integration into existing compilation systems. A python interface provides means for integration on pythonic frameworks such as IBM's Qiskit, ProjectQ, etc. The new beta version, which still under development, features a complete redesign of the internal intermediate representation. The new IR is multilevel, i.e., quantum operations of various levels of abstractions can be part of the same circuit. The focus of this new version is to make Tweedledum easily extensible and allow users to combine different algorithms in non-trivial ways, thus enabling and facilitating research.
<< IWQC20 |  Schedule >>

Abstract: We introduce an open-source package for error mitigation in quantum computation using zero-noise extrapolation. Error-mitigation techniques improve computational performance (with respect to noise) using minimal overhead in quantum resources by relying on a mixture of quantum sampling and classical post-processing techniques. Our error mitigation package interfaces with multiple quantum computing software stacks, and we demonstrate improved performance on a variety of benchmarks performed on IBM quantum processors and noisy simulators. We describe the library using code snippets to demonstrate usage and discuss features, support, and contribution guidelines.
<< IWQC20 |  Schedule >>

Abstract: Quantum algorithms are normally represented as circuits containing both quantum and classical wires. While common optimization techniques focus on rewriting solely the quantum subcircuits, some types of algorithms such as error correction may benefit from a global optimization process.

In this work we extend the pure-quantum circuit optimization procedure by Duncan et al. to support hybrid quantum-classical circuits using a variant of the graphical ZX-calculus called ZX-ground. We introduce a new simplification strategy for ZX-ground diagrams and detail an algorithm for extracting the hybrid quantum-classical circuits after the optimization.
<< IWQC20 |  Schedule >>

Abstract: Simulators are a particularly versatile feature of the Microsoft Quantum Development Kit (QDK). They allow you to perform different tasks on a Q# program without the need to change its source code. Such tasks include full state simulation, resource estimation, trace simulation, or circuit generation. In our talk, we explain the simulator architecture in the QDK and illustrate how to write custom simulators using reversible simulation and quantum circuit diagram generation as two examples. The talk is based on blog posts in the Q# blog.
<< IWQC20 |  Schedule >>

Abstract: In this work, we investigate exact and heuristic approaches for executing quantum circuits on trapped-ion quantum computers. We consider the quantum charge-coupled device (QCCD) architecture, which consists of qubits in a linear array divided into gate zones, where gates can be applied, and storage zones. We develop an abstract model of the qubit routing problem on this architecture, identifying constraints unique to its design. We propose exact approaches for qubit routing on the QCCD architecture using integer programming (IP) and constraint programming (CP). While these approaches offer attractive bounds on the quality of the produced qubit routing, our preliminary findings indicate that they suffer from scalability issues. We therefore also develop a heuristic approach that increases the size of qubit routing problems that we can solve. To the best of our knowledge, this work is the first to explore exact techniques for the qubit routing problem on the architecture considered.
<< IWQC20 |  Schedule >>

Abstract: To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities. In this work we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. In general the qubit allocation problem is NP-complete, thus an approach using heuristic techniques may be valuable for the next generations of quantum devices with larger hardware graphs.
<< IWQC20 |  Schedule >>

Abstract: Given the rising popularity of quantum machine learning (QML), it is important to develop techniques that effectively simplify commonly adopted families of parametrized quantum circuits (commonly known as ansätze). In this work, specifically, we describe a simplification algorithm for ansätze constructed from repeating layers of mixed Z and X phase gadgets. Our approach leverages a combinatorial description (in terms of GL(n, 2) matrices) of the effect of composing such ansätze with CNOT circuits, and uses simulated annealing to obtain approximate solutions to a corresponding optimization problem.
<< IWQC20 |  Schedule >>

Abstract: We introduce a correlated measurement noise model that can be efficiently described and characterized, and which admits noise-mitigation on the level of marginal probability distributions. Noise mitigation can be performed up to some error for which we give upper bounds. Characterization of the model is done efficiently using Quantum Overlapping Tomography. We perform experiments on up to 11 qubits on IBM's quantum device and conclude a good agreement with our noise model. Furthermore, we study the effects of the readout noise on the performance of the Quantum Approximate Optimization Algorithm (QAOA). We observe numerically that for numerous objective Hamiltonians, including random MAX 2SAT instances, the noise-mitigation improves the quality of optimization and final estimation in QAOA. Finally, we show that in the task of simultaneous estimation of few-body operators that typically appear in QAOA, the covariances between them vanish for a broad class of states, significantly lowering the sampling complexity.
<< IWQC20 |  Schedule >>