Abstract Treating stabilizer operations as free, we establish lower bounds on the number of resource states, also known as magic states, needed to perform various quantum computing tasks. Our bounds apply to adaptive computations using measurements with an arbitrary number of stabilizer ancillas. We consider (1) resource state conversion, (2) single-qubit unitary synthesis, and (3) computational subroutines including the quantum adder and the multiply-controlled Z gate. To prove our resource conversion bounds we introduce two new monotones, the stabilizer nullity and the dyadic monotone, and make use of the already-known stabilizer extent. We consider conversions that borrow resource states, known as catalyst states, and return them at the end of the algorithm. We show that catalysis is necessary for many conversions and introduce new catalytic conversions, some of which are optimal. By finding a canonical form for post-selected stabilizer computations, we show that approximating a single-qubit unitary to within diamond-norm precision ɛ requires at least 1/7 ⋅ log 2 (1/ ɛ ) − 4/3 T -states on average. This is the first lower bound that applies to synthesis protocols using fall-back, mixing techniques, and where the number of ancillas used can depend on ɛ . Up to multiplicative factors, we optimally lower bound the number of T or CCZ states needed to implement the ubiquitous modular adder and multiply-controlled- Z operations. When the probability of Pauli measurement outcomes is 1/2, some of our bounds become tight to within a small additive constant.
We introduce magic measures to quantify the nonstabilizerness of multiqubit quantum gates and establish lower bounds on the
T count for fault-tolerant quantum computation. First, we introduce the stabilizer nullity of multiqubit unitary, which is based on the subgroup of the quotient Pauli group associated with the unitary. This unitary stabilizer nullity extends the state-stabilizer nullity by Beverland et al. [Quantum Sci. Technol. 5, 035009 (2020)] to a dynamic version. In particular, we show this nonstabilizerness measure has desirable properties, such as subadditivity under composition and additivity under tensor product. Second, we prove that a given unitary's stabilizer nullity is a lower bound for the
T count, utilizing the above properties in gate synthesis. Third, we compare the state and the unitary stabilizer nullity, proving that the lower bounds for the
T count obtained by the unitary stabilizer nullity are never less than the state-stabilizer nullity. Moreover, we show an explicit
n-qubit unitary family of unitary stabilizer nullity
2n, which implies that its
T count is at least
2n. This gives an example where the bounds derived by the unitary stabilizer nullity strictly outperform the state-stabilizer nullity by a factor of 2. We finally showcase the advantages of unitary stabilizer nullity in estimating the
T count of quantum gates with interests.
Decomposing unitary operators into Clifford gates and non-Clifford gates is an extremely important problem in quantum computing, as each extra quantum gate in a quantum circuit makes it more prone to errors. The first objective in this problem is usually to minimize the number of non-Clifford gates. The second objective, and the objective of this thesis, is to minimize the number of 2-qubit gates in the Clifford operators that are left. Most algorithms from the literature for decomposing Clifford operators into Clifford gates involve using a decomposition such as the Bruhat decomposition to first split the input operator into multiple separate operators. These operators are then individually decomposed into Clifford gates. A problem with this approach is that the minimum number of 2-qubit gates needed to implement all the separate operators can be greater than what is needed to implement the input Clifford operator in the first place. This thesis tackles this problem by developing an algorithm for decomposing Clifford operators into Clifford gates without splitting the input operator into multiple smaller operators first. To help with the decomposition steps, this thesis defines a set of operators called 2-qubit symplectic transvections. This results in an algorithm that performs well for small to medium sized Clifford operators. This thesis assumes that the order of the qubits does not affect the implementation cost for quantum gates. This means that swap gates can be implemented for free by relabeling the qubits. It is also assumed that 1-qubit gates have negligible implementation cost compared to 2-qubit gates.
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.
A decision diagram (DD) is a graph-like data structure for homomorphic compression of Boolean and pseudo-Boolean functions. Over the past decades, decision diagrams have been successfully applied to verification, linear algebra, stochastic reasoning, and quantum circuit analysis. Floating-point errors have, however, significantly slowed down practical implementations of real- and complex-valued decision diagrams. In the context of quantum computing, attempts to mitigate this numerical instability have thus far lacked theoretical scaling guarantees and have had only limited success in practice. Here, we focus on the analysis of quantum circuits consisting of Clifford gates and
T gates (a common universal gate set). We first hand-craft an algebraic representation for complex numbers, which replace the floating point coefficients in a decision diagram. Then, we prove that the sizes of these algebraic representations are linearly bounded in the number of
T gates and qubits, and constant in the number of Clifford gates. Furthermore, we prove that both the runtime and the number of nodes of decision diagrams are upper bounded as
2t⋅poly(g,n), where
t (
g) is the number of
t gates (Clifford gates) and
n the number of qubits. Our proofs are based on a
T-count dependent characterization of the density matrix entries of quantum states produced by circuits with Clifford+
T gates, and uncover a connection between a quantum state's stabilizer nullity and its decision diagram width. With an open source implementation, we demonstrate that our exact method resolves the inaccuracies occurring in floating-point-based counterparts and can outperform them due to lower node counts. Our contributions are, to the best of our knowledge, the first scaling guarantees on the runtime of (exact) quantum decision diagram simulation for a universal gate set.
We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.