Executing quantum algorithms on a quantum computer requires compilation to representations that conform to all restrictions imposed by the device. Due to devices' limited coherence times and gate fidelities, the compilation process has to be optimized as much as possible. To this end, an algorithm's description first has to be synthesized using the device's gate library. In this paper, we consider the optimal synthesis of Clifford circuits---an important subclass of quantum circuits, with various applications. Such techniques are essential to establish lower bounds for (heuristic) synthesis methods and gauging their performance. Due to the huge search space, existing optimal techniques are limited to a maximum of six qubits. The contribution of this work is twofold: First, we propose an optimal synthesis method for Clifford circuits based on encoding the task as a satisfiability (SAT) problem and solving it using a SAT solver in conjunction with a binary search scheme. The resulting tool is demonstrated to synthesize optimal circuits for up to 26 qubits---more than four times as many as the current state of the art. Second, we experimentally show that the overhead introduced by state-of-the-art heuristics exceeds the lower bound by 27 % on average. The resulting tool is publicly available at https://github.com/cda-tum/qmap.
One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states. \nIf the number of non-Clifford gates in the circuit is small, such simulations can be very effective. \nThis thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from
O(elln2) to
O(mn2), where
ell is the total number of gates in the circuit, and
m is the number of non-Clifford gates. \nSince this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever
ellggm. \nOur method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources. \n \nFurthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of
ketpsiotimesm, where
ketpsi is either a magic state or an equatorial state. \nFor any single qubit magic state
ketpsi, we find stabilizer decompositions of
ketpsiotimesm with
2mlog2(3)/4 terms. This improves on the best known bound of
2mlog2(7)/6. \nSimilarly, for any single qubit equatorial state
ketpsi, we give a stabilizer decomposition of
ketpsiotimesm with
2m/2 terms. \nTo our knowledge no such decompositions were previously known. \nThese results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way. \n \nWe also consider certain obstructions to classical simulations. \nIt has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits. \nLinear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits. \n \nWhile binary LCSs have been studied in detail,
d-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo
d>2. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd
d, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even
d case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap.
Optimal circuit synthesis is the problem of finding the shortest-depth circuit representation of a given functionality with respect to a pre-specified elementary gate set. This is a central problem in both quantum and classical hardware design. While the classical version is very well understood -- both in terms of heuristics and rigorous hardness assertions -- much less is known about optimal quantum circuit synthesis.
We focus on optimal Clifford circuit synthesis, for which various heuristics are known, e.g. via reduction to 3-SAT. Our main result supplies a matching hardness result: a variant of optimal Clifford synthesis is NP-hard. The proof proceeds in two parts: (i) reduce 3-edge colorability on 3-regular graphs to a circuit synthesis problem that only involves CZ gates, (ii) prove that the availability of additional elementary Clifford gates -- most notably: Hadamard, phase and CNOT -- cannot lead to further improvements of the optimal circuit depth. Our work sharpens the complexity-theoretic understanding of Clifford circuits: simulation and equivalence checking are in P, whereas deciding whether a Clifford unitary admits an implementation within a prescribed depth is NP-complete.
Simulating quantum circuits classically is an important area of research in quantum information, with applications in computational complexity and validation of quantum devices. One of the state-of-the-art simulators, that of Bravyi et al, utilizes a randomized sparsification technique to approximate the output state of a quantum circuit by a stabilizer sum with a reduced number of terms. In this paper, we describe an improved Monte Carlo algorithm for performing randomized sparsification. This algorithm reduces the runtime of computing the approximate state by the factor ℓ/m , where ℓ and m are respectively the total and non-Clifford gate counts. The main technique is a circuit recompilation routine based on manipulating exponentiated Pauli operators. The recompilation routine also facilitates numerical search for Clifford decompositions of products of non-Clifford gates, which can further reduce the runtime in certain cases by reducing the 1-norm of the vector of expansion, ‖a‖1 . It may additionally lead to a framework for optimizing circuit implementations over a gate-set, reducing the overhead for state-injection in fault-tolerant implementations. We provide a concise exposition of randomized sparsification, and describe how to use it to estimate circuit amplitudes in a way which can be generalized to a broader class of gates and states. This latter method can be used to obtain additive error estimates of circuit probabilities with a faster runtime than the full techniques of Bravyi et al. Such estimates are useful for validating near-term quantum devices provided that the target probability is not exponentially small.
We consider the problem of classical strong (amplitude-wise) simulation of n-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n - 2)(2n-3- 1) lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision 2-n/2 must take at least 2n-o(n)time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+T quantum circuits with t T-gates. Using the sparsification lemma, we identify a time complexity lower bound of 22.2451×10-8tbelow which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.