Lower bound for the $T$ count via unitary stabilizer nullity

Jiaqing Jiang [email protected] Institute for Quantum Computing, Baidu Research, Beijing 100193, China Computing and Mathematical Sciences, California Institute of Technology, Pasadena, California, USA Xin Wang [email protected] Institute for Quantum Computing, Baidu Research, Beijing 100193, China

Abstract

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 multi-qubit 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. 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.

I Introduction

A quantum circuit comprised of only Clifford gates confers no computational advantage since it can be efficiently simulated on a classical computer [1, 2]. However, the addition of $T$ gates into Clifford circuits [3, 4] can achieve universal quantum computation. The minimum number of $T$ gates used, or the $T$ count, plays a role in quantum computation. The study of $T$ count has applications in quantum simulation, quantum error correction, and quantum circuit synthesis. Specifically, in the theoretical study of classically simulating quantum computation, $T$ count serves as a quantifier of difficulty for such simulation in many algorithms [5, 6, 7]. It is shown that quantum circuits composed of Clifford gates and $t$ $T$ gates can be simulated on a classical computer in time, which is exponential in $t$ [5, 7, 8, 9]. Better estimation of the $T$ -count gives better analysis of the performance for those algorithms. On the other hand, in the framework of fault-tolerant quantum computation [10, 11], $T$ count dominates the cost of computation. This is because in many promising fault-tolerant architectures, the Clifford gates can be implemented transversally [12] and the required $T$ gate for universality can be performed via state injection [13, 10]. The key of this resolution is to perform magic state distillation [11, 14], which is a resource-intensive subroutine with a costly overhead [14, 15] (see Refs.[16, 17, 18, 19, 20, 21, 22, 23] for recent progress).

Quantum resource theories [24] offer a powerful framework for studying quantum resources for information processing. The resource theory of $T$ count has found applications in magic state distillation and non-Clifford gate synthesis [25]. To better realize quantum computation, there are many circuit synthesis algorithms that aim to reduce the number of $T$ gates in the implementation of a given unitary operator [26, 27, 28, 29, 30], providing a better upper bound for its $T$ count.

This work aims to study lower bounds for the $T$ count. A lower bound for the $T$ count estimates the minimum magic resources [25] required for quantum computation, and gives a lower bound for the runtime of the classical simulation algorithms [8, 5, 6] based on Clifford+ $T$ gate sets. Specifically, for a given $n$ -qubit unitary $U$ , write $t(U)$ as the minimum number of $T$ gates among all implementations of $U$ over the Clifford+ $T$ gate set, i.e., the $T$ count equals $t(U)$ . The task is to calculate a quantity $v(U)$ such that $v(U)\leq t(U)$ . A good lower bound is a $v(U)$ which is as large as possible, and the time complexity for computing $v(U)$ is as small as possible. From the theoretical perspective, the explicit expressions of $v(U)$ for some $n$ -qubit unitary families are useful and desirable. For the decision version of the lower-bound task, Gosset et al. [29] gives an algorithm which for any integer $m$ and $n$ -qubit unitary $U$ , it decides whether the $T$ count for $U$ is less than $m$ , with both time and space complexity of $O(2^{nm}poly(m,2^{n}))$ . Although this algorithm can be used to calculate the exact value of the $T$ count, the time complexity is quite high. Even for small $m$ such as $m=n$ , the complexity will scale as $O(2^{cn^{2}})$ for some constant $c$ . Other methods for deriving lower bounds for the $T$ count are mostly based on magic monotones. Those magic monotones are primarily designed for quantifying the non-Clifford resources for constructing quantum states, such as quantifying the number of the magic state $|T\rangle$ needed for constructing a given state $|\psi\rangle$ . Those magic monotones could also naturally induce a lower bound for the $T$ count for a given unitary. Note that due to the adaptive operations allowed in the model of computation with magic states, which are not allowed in the model of computation with unitary, the lower bound of the $T$ count for $U$ induced by those magic monotones can be strictly smaller than the $T$ count for $U$ [31, 32, 29]. This subtle distinction is clarified in Appendix B.

The relevant magic monotones can be summarized as follows. For a pure state $|\psi\rangle$ , the stabilizer rank [7] is defined as the minimum number of nonzero coefficients when decomposing $|\psi\rangle$ onto a linear combination of stabilizer states. The stabilizer extent [7, 33] is defined as the square of the minimum $l_{1}$ norm of the above coefficients. It relates to the approximate stabilizer rank, that is the stabilizer rank of states, which approximate $|\psi\rangle$ within given precision. The robustness of nonstabilizerness [31] is also related to the minimum $l_{1}$ norm but defined for mixed states. The stabilizer rank can also be generalized to mixed states in multiple ways [8]. The channel robustness and magic capacity [34] are closely related to the robustness of magic. They can be used for quantifying the non-Clifford resources for multiqubit operations. All of the above magic monotones are more or less involving optimization over the set of stabilizer states, and thus are costly to compute since the cardinality of stabilizer states increases as $2^{\Omega(n^{2})}$ [35]. Moreover, since they involve optimization, it is hard to derive explicit expressions for those magic monotones for $n$ -qubit unitaries or quantum states. Beyond the magic monotones based on optimization, Beverland et al. [25] proposed the state-stabilizer nullity based on quantities related to the Pauli group. More specifically, let $s(|\psi\rangle)$ be the size of the stabilizer of $|\psi\rangle$ , where the stabilizer is the subgroup of the Pauli group for which $|\psi\rangle$ is a $+1$ eigenvector, the state-stabilizer nullity of $|\psi\rangle$ is defined as $v_{s}(|\psi\rangle)=n-\log_{2}s(|\psi\rangle)$ . In general, the state-stabilizer nullity can be computed in time $O(2^{4n})$ . Moreover, for some useful unitary families $\{U_{n}\}_{n}$ , the explicit expressions of the state-stabilizer nullity of $U_{n}|+\rangle^{\otimes n}$ can be easily computed. And this quantity can be used to lower bound the $T$ count for $U_{n}$ . An example is showing that the $n$ -qubit Toffoli gate has $T$ count $n$ , implying that implementing such a gate needs at least $n$ $|T\rangle$ states or $T$ gates. The state-stabilizer nullity is designed for quantifying non-Clifford resources for constructing states, although it can be used to derive lower bounds for the $T$ count for unitaries, a “unitary-stabilizer nullity” is desirable for better quantifying the nonstabilizerness and estimate the $T$ count of multiqubit gates. It is unclear and nontrivial to generalize the definition from states to unitaries. Beyond all the above, there are also magic monotones defined for qudit systems of odd prime dimension, which cannot be directly used for qubit systems [36, 23].

In this work, we define the unitary-stabilizer nullity. Instead of counting the operators in the Pauli group, which stabilize $|\psi\rangle$ , for a target $U$ we count the $\pm 1$ s in the Pauli transfer matrix. In other words, we calculate the size of the intersection between $U{\cal P}_{n}U^{\dagger}$ and ${\cal P}_{n}$ , where ${\cal P}_{n}$ is the quotient Pauli group, that is the Pauli-group modulo phases. Denoting the size as $s(U)$ , the unitary-stabilizer nullity is defined as $v(U)=2n-\log_{2}s(U)$ . Intuitively, $s(U)$ quantifies the similarity between $U$ and Clifford unitaries, where for Clifford unitary $U$ , $s(U)=4^{n}$ . To use $v(\cdot)$ to derive a lower bound for the $T$ count, we prove two key properties: $v(\cdot)$ satisfies faithfullness, i.e. $v(U)\geq 0$ for any $U$ , $v(U)=0$ if and only if $U$ is Clifford, and subadditivity under composition, i.e. $v(U\cdot V)\leq v(U)+v(V)$ or equivalently, $s(U)s(V)\leq 4^{n}s(UV)$ . We further apply these properties to establish the lower bound for the $T$ count.

We then compare the lower bounds of the $T$ count obtained by the state-stabilizer nullity and the unitary-stabilizer nullity. We show that the bound given by the unitary-stabilizer nullity will never be smaller than the bound given by the state-stabilizer nullity, that is $v(U)\geq v_{s}(U|\phi\rangle),$ for any stabilizer state $|\phi\rangle$ . We also prove that for any diagonal $U$ , $v(U)=v_{s}(U|+\rangle^{\otimes n})$ , which in turn shows that for any diagonal $U$ , the maximum lower bound obtained by the state-stabilizer nullity, i.e., $v_{s}(U|\phi\rangle)$ for some stabilizer state $|\phi\rangle$ , is achieved by $|\phi\rangle=|+\rangle^{\otimes n}$ . Moreover, we give an explicit $n$ -qubit unitary family, which has unitary-stabilizer nullity $2n$ . Since the state-stabilizer nullity is always less than $n$ , such a unitary family illustrates that the lower bound of the $T$ count given by the unitary-stabilizer nullity can be strictly better than the bound given by the state-stabilizer nullity by a factor of $2$ .

In general, the unitary-stabilizer nullity can be computed in time $O(2^{7n})$ , which is less than $O(2^{(1/2+o(1))n^{2}})$ but still costly. However, as mentioned above, for certain $n$ -qubit unitary families the explicit expressions of the unitary-stabilizer nullity can be easily computed. We believe this property will make it useful in the theoretical study. At the technical level, most of the proofs are based on connecting $s(U)$ to certain subgroups and applying the Lagrangian theorem [37] and its variants, deriving relationships between the sizes of subgroups. Based on the group theory, an interesting fact is that unlike other magic monotones, both the state- and the unitary-stabilizer nullity are always integers. Note that since the unitary-stabilizer nullity is bounded by $2n$ , the lower bound for $T$ count it gives is up to $2n$ .

Finally, we connect the unitary-stabilizer nullity and the state-stabilizer nullity with auxiliary systems. Specifically, we prove that $v(U)$ equals the best bound one can obtain by the state-stabilizer nullity with auxiliary systems. That is for any $d$ -qubit auxiliary system, for any $(d+n)$ -qubit stabilizer state $|\psi\rangle$ , we have $v(U)\geq v_{s}((I_{2^{d}}\otimes U|\psi\rangle)$ . In particular, we show that $v(U)=v_{s}((I_{2^{n}}\otimes U)|\phi\rangle)$ where $|\phi\rangle$ is the $2n$ -qubit maximally entangled state. We also give numerical results that compare the $T$ count lower bound obtained by the state-stabilizer nullity, the unitary-stabilizer nullity, and the stabilizer extent. The results show that for several gates of practical interest, the unitary-stabilizer unitary can derive a better $T$ count lower bound.

Outline and main contributions

The outline and main contribution of this paper can be summarized as follows:

•

In section II, we set the notations and introduce the unitary-stabilizer nullity.
•

In section III, we prove basic properties of the unitary-stabilizer nullity, that is faithfulness, invariance under Clifford operations, and additivity under tensor product. Moreover, we show that the unitary-stabilizer nullity satisfies the subadditivity under composition.
•

In section IV, we show that the unitary-stabilizer nullity can derive a lower bound of the $T$ count for a given unitary $U$ . The method can be generalized to give lower bounds for arbitrary non-Clifford gates beyond the $T$ gate. We also compare the lower bound obtained by the unitary- and the state-stabilizer nullity. We prove that the bound by the unitary-stabilizer nullity will never perform worse than the state-stabilizer nullity. Moreover, we show that there is an explicit $n$ -qubit unitary family of unitary-stabilizer nullity $2n$ , illustrating our bounds can strictly outperform the state-stabilizer nullity. Besides, for diagonal unitaries, we prove our bounds coincide with the state-stabilizer nullity. Then connect the unitary-stabilizer nullity with the state-stabilizer nullity with auxiliary systems.
•

In section IV.5, we investigate the $T$ counts of a plethora of quantum gates of practical interest and the improvements are evident for many cases.
•

Finally in Section V, we conclude and discuss open problems.

II Preliminaries

II.1 Notations

In this part, we set the notations. We use $i$ as the imaginary number. We use $\mathbb{C}$ as the complex field, $\mathbb{N}^{+}$ as the positive integers. For a complex number $\lambda$ , we use $\lambda^{\dagger}$ as its conjugate, $|\lambda|$ as its norm. Let $A,B$ be two subgroups of a group $G$ , we use $A\times B$ as the set $A\times B\mathrel{\mathop{\mathchar 58\relax}}=\{ab|a\in A,b\in B\}$ . Note that when $G$ is Abelian, $A\times B$ is a subgroup of $G$ . For any $n$ -bit string ${{\textbf{x}}}\in\{0,1\}^{n}$ , we use $\odot({{\textbf{x}}})$ as the product $x_{1}x_{2}...x_{n}$ . We use $1^{n}$ as the $n$ -bit string of all ones. Given two strings ${{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n},$ we use ${{\textbf{x}}}\cdot{{\textbf{y}}}$ as their inner product, ${{\textbf{x}}}\oplus{{\textbf{y}}}$ as their bitwise XOR operation. We abbreviate $x\in\{-1,+1\}$ as $x=\pm 1$ . We use $I_{d}$ as the $d$ -dimensional identity matrix. We abbreviate $I_{d}$ as $I$ when $d$ is clear in the context. We write the state $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ as $|+\rangle$ . For a matrix $U$ , we use $U^{T}$ as its transpose, $U^{\dagger}$ as its transpose conjugate. For integers $d$ and $k$ , we use $d|k$ to denote $d$ is a factor of $k$ . We use the $\delta_{{{\textbf{u}}}{{\textbf{v}}}}$ to denote the function that equals $1$ if and only if ${{\textbf{u}}}={{\textbf{v}}}$ and $0$ otherwise.

We use $[n]$ as the set $\{0,1,...,n-1\}.$ We use $4^{[n]}$ as the set of length- $n$ vectors with alphabet $[4]$ , i.e. $4^{[n]}\mathrel{\mathop{\mathchar 58\relax}}=\{0,1,2,3\}^{n}$ . We use the lowercase character to denote a number, and the bold lowercase character to denote a vector, that is $u\in[4]$ and ${{\textbf{u}}}\in[4]^{n}$ respectively. We represent Pauli operators as

	$\displaystyle\sigma_{0}=I_{2}=\begin{bmatrix}1&0\\ 0&1\end{bmatrix},\sigma_{1}=X=\begin{bmatrix}0&1\\ 1&0\end{bmatrix},$		(1)
	$\displaystyle\sigma_{2}=Y=\begin{bmatrix}0&-i\\ i&0\end{bmatrix},\sigma_{3}=Z=\begin{bmatrix}1&0\\ 0&-1\end{bmatrix}.$		(2)

We write phase gate (S), $T$ gate (T) and Hadamard gate (H) as

\displaystyle S=\begin{bmatrix}1&0\\ 0&i\end{bmatrix},T=\begin{bmatrix}1&0\\ 0&e^{\frac{\pi i}{4}}\end{bmatrix},H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\ 1&-1\end{bmatrix}.

(3)

The CNOT gate is the two-qubit control NOT gate, i.e. $CNOT|x_{1}\rangle|x_{2}\rangle=|x_{1}\rangle|x_{1}\oplus x_{2}\rangle$ . The $C^{n-1}Z$ is the multicontrolled Z gate, i.e. $C^{n-1}Z|x_{1}...x_{n}\rangle=(-1)^{x_{1}x_{2}\cdots x_{n}}|x_{1}...x_{n}\rangle$ .

The one-qubit Pauli group is the group generated by the Pauli operators, i.e. $\hat{{\cal P}}_{1}=\{i^{k}\sigma_{h}|k,h\in[4]\}$ . The $n$ -qubit Pauli group is defined to be the $n$ -fold tensor product of the one-qubit Pauli-group, i.e. $\hat{{\cal P}}_{n}\mathrel{\mathop{\mathchar 58\relax}}=\hat{{\cal P}}_{1}^{\otimes n}$ . In the following, we are uninterested in the overall phases. We define the one-qubit Pauli-group modulo phases to be ${\cal P}_{1}=\hat{{\cal P}}_{1}/\{i^{k}I_{2}|k\in[4]\}=\{\sigma_{h}|h\in[4]\}$ , where the last equality means we use $\sigma_{h}$ as a representative of elements in $\{i^{k}\sigma_{h}|k\in[4]\}$ . Similarly, we define the $n$ -qubit Pauli group modulo phases, or the $n$ -qubit quotient Pauli group, to be ${\cal P}_{n}\mathrel{\mathop{\mathchar 58\relax}}={\cal P}_{1}^{\otimes n}=\{\sigma_{h}|h\in[4]\}^{\otimes n}$ . Notice that ${\cal P}_{n}$ is an Abelian group with respect to matrix-product modulo phases. We have $|{\cal P}_{1}|=4$ and $|{\cal P}_{n}|=4^{n}$ where $|\cdot|$ is the size of the group. Elements in ${\cal P}_{n}$ can be represented by a string ${{\textbf{u}}}\in 4^{[n]}$ , that is $\sigma_{{\textbf{u}}}=\otimes_{k=1}^{n}\sigma_{{{\textbf{u}}}_{k}}$ .

The $n$ -qubit Clifford group ${\cal C}_{n}$ is the set of $n$ -qubit unitary $U$ which maps Pauli group to Pauli group, i.e. $U\hat{{\cal P}}_{n}U^{\dagger}=\hat{{\cal P}}_{n}$ . An $n$ -qubit state $|\psi\rangle$ is called a stabilizer state if $|\psi\rangle=U|0\rangle^{\otimes n}$ for some $U\in{\cal C}_{n}$ . One can verify that $U{\cal P}_{n}U^{\dagger}={\cal P}_{n}$ , with respect to matrix-product modulo phases. In the following context, when involving the quotient group ${\cal P}_{n}$ , we always assume the operation is matrix product modulo phases.

For a given unitary $U$ , we define its $T$ count $t(U)$ as the minimum number of $T$ gates required when decomposing $U$ into a sequence of gates over Clifford plus $T$ gate set, without auxiliary qubits and measurement. Here we view Clifford gates, or Clifford unitaries, as free resources. More clarifications can be seen in the quantum computation with unitary part in Appendix B. If $U$ cannot be exactly synthesized by Clifford plus $T$ gate set, we denote its $T$ count as $+\infty$ .

II.2 Pauli function

In this part, we introduce the state Pauli function and the unitary Pauli function, which are the basic elements for defining the state- and the unitary-stabilizer nullity. Those functions are related to the values of the matrix representation of a linear map in the Pauli basis. We adopt the terminology from Ref. [25].

We name them the Pauli functions in order to unify the framework of the state- and the unitary-stabilizer nullity, and to better analyze their properties.

Definition 1 (State Pauli function)

For ${{\textbf{u}}}\in 4^{[n]}$ , the Pauli function of an $n$ -qubit pure state $|\psi\rangle$ is defined as $P_{|\psi\rangle}({{\textbf{u}}})\mathrel{\mathop{\mathchar 58\relax}}=\operatorname{Tr}|\psi\rangle\!\langle\psi|\sigma_{{{\textbf{u}}}}$ .

Definition 2 (Unitary Pauli function)

For ${{\textbf{u}}},{{\textbf{v}}}\in 4^{[n]}$ , the Pauli function of an $n$ -qubit unitary $U$ is defined as $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\operatorname{Tr}(\sigma_{{{\textbf{u}}}}U\sigma_{{{\textbf{v}}}}U^{\dagger})/2^{n}$ .

The matrix whose $({{\textbf{u}}},{{\textbf{v}}})$ th element is $P_{U}({{\textbf{u}}}|{{\textbf{v}}})$ is known to be the Pauli transfer matrix of $U$ . The Pauli transfer matrix is the matrix representation of the linear map $U(\cdot)U^{\dagger}$ in the Pauli basis. Equivalently, one can show that $U\sigma_{{\textbf{v}}}U^{\dagger}=\sum_{{\textbf{u}}}P_{U}({{\textbf{u}}}|{{\textbf{v}}})\sigma_{{\textbf{u}}}.$ A useful fact is that the Pauli transfer matrix of unitary is orthogonal. That is for unitary $U$ ,

\displaystyle\!\!\!\sum_{{{\textbf{u}}}}P_{U}({{\textbf{u}}}|{{\textbf{v}}})P_{U}({{\textbf{u}}}|{{\textbf{v}}}^{\prime})=\operatorname{Tr}(U\sigma_{{{\textbf{v}}}}U^{\dagger}U\sigma_{{{\textbf{v}}}^{\prime}}U^{\dagger})/2^{n}=\delta_{{{\textbf{v}}}{{\textbf{v}}}^{\prime}}.

(4)

Both the state and the unitary Pauli functions take values in $[-1,1]$ . To analyze the properties of the unitary Pauli function, we connect $U$ to a subgroup of the quotient Pauli group.

Definition 3 (Pauli subgroup associated with $U$ )

Given an $n$ -qubit unitary $U$ , we define the Pauli subgroup associated with $U$ to be ${\cal P}_{U}\mathrel{\mathop{\mathchar 58\relax}}=U{\cal P}_{n}U^{\dagger}\cap{\cal P}_{n}$ .

One can verify that ${\cal P}_{U}$ is a subgroup of ${\cal P}_{n}$ . It is worth noting that $U{\cal P}_{U}U^{\dagger}$ may not be equal to ${\cal P}_{U}$ , and ${\cal P}_{U}$ is not $U{\cal P}_{n}U^{\dagger}$ .

II.3 Stabilizer nullity

In this part, we give the definitions of the state- and the unitary-stabilizer nullity.

Definition 4 (state-stabilizer nullity [25])

For an $n$ -qubit state $|\psi\rangle$ , the stabilizer nullity of $|\psi\rangle$ is defined as $v_{s}(|\psi\rangle)\mathrel{\mathop{\mathchar 58\relax}}=n-\log_{2}s(|\psi\rangle)$ , where $s(|\psi\rangle)$ is equal to the number of $\pm$ 1s in the Pauli function of $|\psi\rangle$ when varying ${{\textbf{u}}}\in 4^{[n]}$ .

To better explore the power of stabilizer nullity in quantifying the $T$ count (or nonstabilizerness) of quantum dynamics, we introduce the unitary-stabilizer nullity as follows.

Definition 5 (unitary-stabilizer nullity)

For an $n$ -qubit unitary $U$ , the stabilizer nullity of $U$ is defined as

\displaystyle v(U)\mathrel{\mathop{\mathchar 58\relax}}=2n-\log_{2}s(U).

(5)

where $s(U)$ is equal to the number of $\pm 1$ s in the Pauli function of $U$ when varying ${{\textbf{u}}},{{\textbf{v}}}\in 4^{[n]}$ .

Note that Beverland et al [25] originally define the state-stabilizer nullity as $\nu(|\psi\rangle)=n-\log_{2}{|\mathrm{Stab}\,|\psi\rangle}|$ , where $\mathrm{Stab}\,|\psi\rangle=\{P\in\hat{{\cal P}}_{n}\mathrel{\mathop{\mathchar 58\relax}}P|\psi\rangle=|\psi\rangle\}$ , that is $\mathrm{Stab}\,|\psi\rangle$ is the subgroup of the Pauli group $\hat{{\cal P}}_{n}$ for which $|\psi\rangle$ is a $+1$ eigenvector. Definition 4 is equivalent to Beverland’s definition, that is $v_{s}(|\psi\rangle)=\nu(|\psi\rangle)$ , as illustrated in Appendix A.

For any stabilizer state $|\psi\rangle$ , Beverland et al [25] show that $v_{s}(|\psi\rangle)=0$ . For any Clifford unitary $U$ , one can verify that $v(U)=0$ by Lemma 1.

III Basic properties of unitary-stabilizer nullity

III.1 Basic properties of the unitary Pauli function

We firstly analyze the basic properties of the unitary Pauli function. Roughly speaking, the unitary Pauli function measures the similarity between $U$ and the Clifford operators, where the similarity is quantified by how well the map $U(\cdot)U^{\dagger}$ keeps the Pauli group invariant. To see this intuition, we prove some basic properties of the unitary Pauli function.

We give short proofs to Lemma 1, Lemma 2 and Lemma 3 assuming the familiarity of quantum information. The more detailed proofs are put into Appendix C.4.

Lemma 1

If $U$ is an $n$ -qubit Clifford unitary, for ${{\textbf{u}}},{{\textbf{v}}}\in 4^{[n]}$ ,

•

for every u, there is only one v such that $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ , and for all ${{\textbf{v}}}^{\prime}\neq{{\textbf{v}}}$ , $P_{U}({{\textbf{u}}}|{{\textbf{v}}}^{\prime})=0$ .
•

for every v, there is only one u such that $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ , and for all ${{\textbf{u}}}^{\prime}\neq{{\textbf{u}}}$ , $P_{U}({{\textbf{u}}}^{\prime}|{{\textbf{v}}})=0$ .

Proof. We give only proof to the first statement, the second is similar. Recall that

	$\displaystyle P_{U}({{\textbf{u}}}\|{{\textbf{v}}})$	$\displaystyle=\operatorname{Tr}(\sigma_{{\textbf{u}}}U\sigma_{{\textbf{v}}}U^{\dagger})/2^{n},$		(6)
	$\displaystyle\operatorname{Tr}(\sigma_{{\textbf{u}}}\sigma_{{\textbf{v}}})$	$\displaystyle=\left\{\begin{aligned} &2^{n},&\text{ if ${{\textbf{u}}}={{\textbf{v}}}$}\\ &0,&\text{ else.}\end{aligned}\right.$		(7)

Since $U$ is Clifford, $U(\cdot)U^{\dagger}$ is an isomorphism of $\hat{{\cal P}}_{n}$ , i.e. $U\hat{{\cal P}}_{n}U^{\dagger}=\hat{{\cal P}}_{n}$ . In other words, $U(\cdot)U^{\dagger}$ is a permutation over the Pauli operators $\{\sigma_{{\textbf{u}}}\}_{{{\textbf{u}}}\in 4^{[n]}}$ , up to a $\pm 1$ sign. Thus by Eq. (6) and Eq. (LABEL:eq:c01), we know $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ if and only if $U\sigma_{{{\textbf{v}}}}U^{\dagger}=\pm\sigma_{{\textbf{u}}}$ . Thus the lemma holds. $\blacksquare$

Similar results also hold for general unitary $U$ beyond Clifford operators, which is proved in the following lemma.

Lemma 2

For any $n$ -qubit unitary $U$ , if there exist ${{\textbf{u}}},{{\textbf{v}}}\in 4^{[n]}$ such that $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ . Then

	$\displaystyle U\sigma_{{\textbf{v}}}U^{\dagger}=\pm\sigma_{{\textbf{u}}},$		(8)
	$\displaystyle\forall{{\textbf{u}}}^{\prime}\neq{{\textbf{u}}},P_{U}({{\textbf{u}}}^{\prime}\|{{\textbf{v}}})=0.$		(9)

Proof. Recall that from equation (4) we know the Pauli transfer matrix of $U$ , whose $({{\textbf{u}}},{{\textbf{v}}})$ -th element is $P_{U}({{\textbf{u}}},{{\textbf{v}}})$ , is orthogonal. Specially, choosing ${{\textbf{v}}}^{\prime}={{\textbf{v}}}$ in Eq. (4) we know

\displaystyle\sum_{{{\textbf{u}}}}|P_{U}({{\textbf{u}}}|{{\textbf{v}}})|^{2}=1.

(10)

Thus if $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ , we have $\forall{{\textbf{u}}}^{\prime}\neq{{\textbf{u}}},P_{U}({{\textbf{u}}}^{\prime}|{{\textbf{v}}})=0.$ Since $U\sigma_{{\textbf{v}}}U^{\dagger}=\sum_{{\textbf{u}}}P_{U}({{\textbf{u}}}|{{\textbf{v}}})\sigma_{{\textbf{u}}},$ thus we complete the proof.

$\blacksquare$

In the following, we give a simple but useful connection between the unitary-stabilizer nullity and the subgroup associated with $U$ . Recall that $s(U)$ is the number of $\pm 1$ s in the unitary Pauli function, as in Definition 5. In the following lemma, we prove that $s(U)$ equals to the size of ${\cal P}_{U}$ , that is the intersection of $U{\cal P}_{n}U^{\dagger}$ and ${\cal P}_{n}$ . Note that ${\cal P}_{n}$ is the quotient Pauli group rather than the Pauli group $\hat{{\cal P}_{n}}$ .

Lemma 3

For any $n$ -qubit unitary $U$ , ${\cal P}_{U}$ is a subgroup of ${\cal P}_{n}$ . What is more,

\displaystyle|{\cal P}_{U}|=|{\cal P}_{U^{\dagger}}|=s(U).

(11)

Proof. By Lemma 2, we know every $\pm 1$ in the Pauli transfer matrix will imply a distinct element in ${\cal P}_{U}$ . That is if $P_{U}({{\textbf{u}}}_{{{\textbf{v}}}}|{{\textbf{v}}})=\pm 1$ , then $\sigma_{{{\textbf{u}}}_{{{\textbf{v}}}}}\in{\cal P}_{U}$ . Besides, for different v, such ${{\textbf{u}}}_{{{\textbf{v}}}}$ are different, this comes from the fact that the Pauli transfer matrix is orthogonal, thus any row cannot have two $\pm 1$ s. Thus $|{\cal P}_{U}|\geq|s(U)|$ . On the other hand, for every element in ${\cal P}_{U}$ , that is a $\sigma_{{\textbf{u}}}$ such that $U\sigma_{{\textbf{v}}}U^{\dagger}=\pm\sigma_{{\textbf{u}}}$ for some v, we would have $|P_{U}({{\textbf{u}}}|{{\textbf{v}}})|=1$ , thus $|{\cal P}_{U}|\leq|s(U)|$ . Thus $|P_{U}|=s(U)$ . Besides, we have $\operatorname{Tr}(\sigma_{{\textbf{u}}}U\sigma_{{\textbf{v}}}U^{\dagger})=\operatorname{Tr}(\sigma_{{\textbf{v}}}U^{\dagger}\sigma_{{\textbf{u}}}U)$ , thus the Pauli transfer matrix of $U^{\dagger}$ is the transpose of the Pauli transfer matrix of $U$ . Thus $|{\cal P}_{U^{\dagger}}|=|s(U)|=|{\cal P}_{U}|$ . $\blacksquare$

An interesting corollary is that the unitary-stabilizer nullity is always an integer, although we do not utilize this property in the following sections.

Corollary 4

For any $n$ -qubit unitary $U$ , $v(U)$ must be an integer, or equivalently, $s(U)=2^{k}$ for some non-negative integer $k$ .

By Lemma 3, we know $s(U)=|{\cal P}_{U}|$ . Since ${\cal P}_{U}$ is a subgroup of ${\cal P}_{n}$ , where $|{\cal P}_{n}|=4^{n}$ , by group theory, we know that $s(U)|4^{n}$ . Thus $v(U)=2n-\log_{2}s(U)$ is always an integer.

III.2 Basic properties of the unitary-stabilizer nullity

In this section, we prove the basic properties of the unitary-stabilizer nullity, that is the faithfulness, invariance under Clifford operations, additivity under tensor product and subadditivity under composition.

Theorem 5 (Faithfulness)

Let $U$ be an $n$ -qubit unitary. Then $v(U)\geq 0$ . Furthermore, $v(U)=0$ if and only if $U$ is a Clifford unitary. Or equivalently, $s(U)\leq 4^{n}$ and $s(U)=4^{n}$ if and only if $U$ is a Clifford unitary.

Proof. For any $n$ -qubit unitary $U$ , we firstly prove $v(U)\geq 0$ , or equivalently, $s(U)\leq 4^{n}$ . By Lemma 2, if there exist ${{\textbf{u}}},{{\textbf{v}}}$ such that $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=1$ then for any ${{\textbf{u}}}^{\prime}\neq{{\textbf{u}}},{\cal P}_{U}({{\textbf{u}}}^{\prime}|{{\textbf{v}}})=0$ . Thus every $\pm 1$ in the Pauli function must come together with $4^{n}-1$ number of $0s$ . Thus $s(U)\leq 4^{n}$ .

If $s(U)=4^{n}$ , by Lemma 2, for every Pauli operator $\sigma_{{\textbf{v}}}$ , $U\sigma_{{\textbf{v}}}U^{\dagger}$ is a Pauli operator, thus $U$ is a Clifford unitary. On the other hand, if $U$ is a Clifford operator, by Lemma 1, it is easy to verify $s(U)=4^{n}.$ $\blacksquare$

Theorem 6 (Invariant under Clifford operation)

For an $n$ -qubit unitary $U$ and an $n$ -qubit Clifford unitary $V$ ,

\displaystyle v(VU)=v(U),\quad s(VU)=s(U).

(12)

Similarly, it also holds that $v(UV)=v(U),s(UV)=s(U)$ .

Proof. Recall that the unitary Pauli function

	$\displaystyle P_{VU}({{\textbf{u}}}\|{{\textbf{v}}})$	$\displaystyle=\operatorname{Tr}\sigma_{{\textbf{u}}}VU\sigma_{{\textbf{v}}}U^{\dagger}V^{\dagger}/2^{n}$
		$\displaystyle=\operatorname{Tr}V^{\dagger}\sigma_{{\textbf{u}}}VU\sigma_{{\textbf{v}}}U^{\dagger}/2^{n}.$		(13)

Since $V$ is Clifford, then $V^{\dagger}(\cdot)V$ is an isomorphism over the Pauli group, i.e. $V^{\dagger}\hat{{\cal P}}_{n}V=\hat{{\cal P}}_{n}$ . Further, since $V^{\dagger}\sigma_{{\textbf{u}}}V$ does not change the eigenvalue of $\sigma_{{\textbf{u}}}$ , where is $\pm 1$ . Thus

\displaystyle V^{\dagger}\{\sigma_{{\textbf{u}}}|{{\textbf{u}}}\in 4^{[n]}\}V=\{p_{{\textbf{u}}}\sigma_{{\textbf{u}}}|{{\textbf{u}}}\in 4^{[n]},p_{{\textbf{u}}}=\pm 1\}.

(14)

In other words, the set of unitary Pauli functions satisfies

\displaystyle\{P_{VU}({{\textbf{u}}}|{{\textbf{v}}})\}=\{p_{{\textbf{u}}}P_{U}({{\textbf{u}}}|{{\textbf{v}}})\,|\,p_{{\textbf{u}}}=\pm 1\}.

(15)

Thus $s(VU)=s(U)$ , thus $v(VU)=s(U)$ . Similarly, it holds that $v(VU)=v(U),s(VU)=s(U)$ . $\blacksquare$

Theorem 7 (Additivity under tensor product)

Given $n$ -qubit unitary $U$ and $m$ -qubit unitary $V$ , the following holds

\displaystyle v(U\otimes V)=v(U)+v(V).

(16)

Proof. For simplicity, given ${{\textbf{u}}}\in 4^{[n+m]}$ , we write ${{\textbf{u}}}^{(1)}$ as the first $n$ bits of u, i.e. ${{\textbf{u}}}^{(1)}={{\textbf{u}}}_{1}{{\textbf{u}}}_{2}...{{\textbf{u}}}_{n}$ . We write ${{\textbf{u}}}^{(2)}$ as the last $m$ bits of u, i.e. ${{\textbf{u}}}^{(2)}={{\textbf{u}}}_{n+1}{{\textbf{u}}}_{n+2}...{{\textbf{u}}}_{n+m}$ . It suffices to notice that

	$\displaystyle P_{U\otimes V}({{\textbf{u}}}\|{{\textbf{v}}})$
	$\displaystyle=\operatorname{Tr}\sigma_{{{\textbf{u}}}^{(1)}}\otimes\sigma_{{{\textbf{u}}}^{(2)}}\left(U\otimes V\right)\sigma_{{{\textbf{v}}}^{(1)}}\otimes\sigma_{{{\textbf{v}}}^{(2)}}\left(U^{\dagger}\otimes V^{\dagger}\right)/2^{(n+m)}$
	$\displaystyle=\operatorname{Tr}\sigma_{{{\textbf{u}}}^{(1)}}U\sigma_{{{\textbf{v}}}^{(1)}}U^{\dagger}/2^{n}\cdot\operatorname{Tr}\sigma_{{{\textbf{u}}}^{(2)}}V\sigma_{{{\textbf{v}}}^{(2)}}V^{\dagger}/2^{m}$
	$\displaystyle=P_{U}({{\textbf{u}}}^{(1)}\|{{\textbf{v}}}^{(1)})\cdot P_{V}({{\textbf{u}}}^{(2)}\|{{\textbf{v}}}^{(2)}).$		(17)

Thus we have $s(U\otimes V)=s(U)s(V)$ , $2(n+m)-\log_{2}s(U\otimes V)=(2n-\log_{2}s(U))+(2m-\log_{2}s(V))$ , and then $v(U\otimes V)=v(U)+v(V)$ . $\blacksquare$

Lemma 8

For any $n$ -qubit unitary $U$ and $V$ ,

\displaystyle|{\cal P}_{U^{\dagger}}\cap{\cal P}_{V}|\leq s(UV).

(18)

Recall that

	$\displaystyle{\cal P}_{UV}$	$\displaystyle=UV{\cal P}_{n}V^{\dagger}U^{\dagger}\cap{\cal P}_{n}$
		$\displaystyle=U\left(V{\cal P}_{n}V^{\dagger}\cap U^{\dagger}{\cal P}_{n}U\right)U^{\dagger}.$		(19)

Noting that $U(\cdot)U^{\dagger}$ is an injection, we have

$\displaystyle\|{\cal P}_{UV}\|$	$\displaystyle=\|V{\cal P}_{n}V^{\dagger}\cap U^{\dagger}{\cal P}_{n}U\|$
	$\displaystyle\geq\|V{\cal P}_{n}V^{\dagger}\cap U^{\dagger}{\cal P}_{n}U\cap{\cal P}_{n}\|$
	$\displaystyle\geq\|{\cal P}_{V}\cap{\cal P}_{U^{\dagger}}\|.$	(20)

By Lemma 3 we know $|{\cal P}_{UV}|=s(UV)$ , we conclude $|{\cal P}_{U^{\dagger}}\cap{\cal P}_{V}|\leq s(UV)$ .

The following lemma is a variation of Lagrange’s theorem in group theory. It connects the sizes between subgroups and their intersections. A detailed proof is provided in Appendix. C.4.

Lemma 9

Suppose $A,B$ are subgroups of $H$ , then $|A\times B|=\frac{|A|\cdot|B|}{|A\cap B|}$ . Since $A\times B\subseteq H$ we have $|A|\cdot|B|\leq|H|\cdot|A\cap B|$ .

Utilizing Lemma 9, we finally arrive at the statement that the unitary-stabilizer nullity satisfies the subadditivity under composition.

Theorem 10 (Subadditivity under composition)

Given $n$ -qubit unitary $U$ and $V$ , the following holds

\displaystyle v(UV)\leq v(U)+v(V).

(21)

Or equivalently $s(U)s(V)\leq 4^{n}s(UV)$ .

Proof. Let $H={\cal P}_{n},A={\cal P}_{U^{\dagger}},B={\cal P}_{V}$ , we know $A,B$ are subgroups of $H$ . By Lemma 9 we have

\displaystyle|{\cal P}_{U^{\dagger}}|\cdot|{\cal P}_{V}|\leq|{\cal P}_{U^{\dagger}}\cap{\cal P}_{V}|\cdot 4^{n}.

(22)

Combine with Lemma 8, we have

\displaystyle|{\cal P}_{U^{\dagger}}|\cdot|{\cal P}_{V}|\leq|s(UV)|\cdot 4^{n}.

(23)

Further by Lemma 3, we know

\displaystyle|{\cal P}_{V}|=s(V),|{\cal P}_{U^{\dagger}}|=|{\cal P}_{U}|=s(U).

(24)

thus finally we get

\displaystyle s(U)s(V)\leq 4^{n}s(UV).

(25)

$\blacksquare$

IV Applications

Interestingly, by the properties in section III, especially the subadditivity under composition, we can use $v(\cdot)$ to give a lower bound for the $T$ count. In section IV.1, we prove this connection. In section IV.2 we compare the lower bound for $T$ count obtained by the state- and the unitary-stabilizer nullity, and prove that the unitary-stabilizer nullity never performs worse than the state-stabilizer nullity. We also prove that for diagonal unitary, the two lower bounds coincide. Finally, in section IV.3, we give an $n$ -qubit unitary family which has unitary-stabilizer nullity $2n$ . This circuit family gives an example where the lower bound obtained by the unitary-stabilizer nullity strictly outperforms the state-stabilizer nullity by a factor of $2$ . Furthermore, in section IV.4, we connect the unitary-stabilizer nullity and the state-stabilizer nullity with auxiliary systems, showing that adding auxiliary systems and choosing proper stabilizer states can strictly improve the lower bound obtained by the state-stabilizer nullity.

IV.1 Lower bounds for the $T$ count

Recall that for a given unitary $U$ , its $T$ count $t(U)$ is the minimum number of $T$ gates used among any implementation of $U$ that decomposes $U$ into a sequence of gates from Clifford plus $T$ -gate set, without ancillary qubits and measurement. In this section, we would use the unitary-stabilizer nullity to lower bound the $T$ count. The main idea is to use the fact that $v(\cdot)$ satisfies the subadditivity under composition.

Theorem 11 (Lower bound for the $T$ count)

For any $n$ -qubit unitary $U$ , its $T$ count is lower bounded by its unitary-stabilizer nullity, that is

\displaystyle t(U)\geq v(U).

(26)

Proof. Notice that $v(T)=1$ by verifying the unitary Pauli function of $T$

\displaystyle\{P_{T}({{\textbf{u}}}|{{\textbf{v}}})\}=\begin{bmatrix}1&0&0&0\\ 0&\frac{\sqrt{2}}{2}&-\frac{\sqrt{2}}{2}&0\\ 0&\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}&0\\ 0&0&0&1\end{bmatrix}.

(27)

Thus, we have $v(T)=2-\log_{2}2=1$ .

Besides, since $I_{2}$ is a Clifford operator, by the faithfulness, i.e. Theorem 5, we have

\displaystyle v(I_{2})=0.

(28)

By the additivity under tensor product, i.e. Theorem 7, we have

\displaystyle v(T\otimes I_{2}\otimes I_{2}...\otimes I_{2})=v(T)+0=1.

(29)

From Theorem 5 we know that all the Clifford unitaries have unitary-stabilizer nullity $0$ . Suppose $U$ is decomposed into sequence of Clifford gates and $t(U)$ $T$ gates, using the subadditivity of composition sequentially, that is Theorem 10, we have

	$\displaystyle v(U)$	$\displaystyle\leq 0+t(U)\cdot v(T)$		(30)
		$\displaystyle=t(U).$

This concludes the theorem. $\blacksquare$

To compare the lower bound got by the unitary-stabilizer nullity and the lower bound by the state-stabilizer nullity, we would use the following theorem from [25].

Theorem 12

[25] For any $n$ -qubit unitary $U$ , for any $(n+t)$ -qubit stabilizer state $|\phi\rangle$ , the $T$ count of $U$ is lower bounded by

\displaystyle t(U)\geq v_{s}\left((I_{2^{t}}\otimes U)|\phi\rangle\right).

(31)

To generalize our result a little bit, consider the task that decomposing $U$ into sequence of Clifford gates and $W$ gates, where $W$ gate is a gate beyond Clifford. Using similar proofs as in the Theorem 11, we can also use the unitary-stabilizer nullity to lower bound the number of $W$ gates.

Theorem 13 (Lower bound for gate synthesis)

For any $n$ -qubit unitary $U$ , the number of gates $W$ required to realize $U$ under Clifford unitaries, denoted as $w(U)$ , satisfies

\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}w(U)}\geq\frac{v(U)}{v(W)}.

(32)

Proof. Note that the subadditivity under composition (Theorem 10) holds for arbitrary two unitaries. Suppose $U$ is decomposed into Clifford and $W$ gates, using Theorem 10 we get similar results as Eq. (29) and Eq. (30), i.e. $v(W\otimes I_{2}\otimes I_{2}...\otimes I_{2})=v(W)$ and $v(U)\leq w(U)v(W)$ . Thus we prove the theorem. $\blacksquare$

IV.2 Comparison between the unitary and state-stabilizer nullity

Beverland et al. [25] showed that for a unitary $U$ , for any stabilizer state $|\psi\rangle$ , the state-stabilizer nullity can derive a lower bound for $T$ count for $U$ as $v_{s}(U|\psi\rangle)$ . We compare this lower bound with the lower bound obtained by the unitary-stabilizer nullity from Theorem 11. We prove in Theorem 14 that our method will never perform worse and provide the detailed proof in Appendix D. We further show that our bound can perform strictly better for a certain unitary family by a factor of 2, as in Corollary 21. We also prove that for diagonal unitary, the lower bounds for $T$ count obtained by the state- and the unitary-stabilizer nullity are the same, as in Theorem 18.

Theorem 14

For any $n$ -qubit unitary $U$ , for any $n$ -qubit stabilizer state $|\psi\rangle$ ,

\displaystyle v(U)\geq v_{s}(U|\psi\rangle).

(33)

That is

\displaystyle v(U)\geq\max_{C\in{\cal C}_{n}}v_{s}(UC|0\rangle^{\otimes n}).

(34)

The equality holds if and only if there exists Clifford $C\in{\cal C}_{n}$ such that

		$\displaystyle\left\{{{\textbf{u}}}\in 4^{[n]}\,\|\,\langle 0^{\otimes n}\|C^{\dagger}U^{\dagger}\sigma_{{\textbf{u}}}UC\|0\rangle^{\otimes n}=\pm 1\right\}$
		$\displaystyle=\left\{{{\textbf{u}}}\in 4^{[n]}\,\|\,C^{\dagger}U^{\dagger}\sigma_{{\textbf{u}}}UC\in\pm\{I,Z\}^{\otimes n}\right\}.$		(35)

and

\displaystyle C\{I,Z\}^{\otimes n}C^{\dagger}\times\left(U^{\dagger}{\cal P}_{n}U\cap{\cal P}_{n}\right)={\cal P}_{n}.

(36)

The equality in equation (36) is with respect to matrix-product modulo phases.

In the following, we prove several lemmas which will be used to show the unitary-stabilizer nullity and the state-stabilizer nullity coincide for the diagonal unitary.

Lemma 15

For any ${{\textbf{u}}}\in 4^{[n]}$ ,

\displaystyle\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}|\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle|\,|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}|\in\{I,X\}^{\otimes n}.

(37)

Here $|\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle|$ is the norm of the complex number $\langle{{\textbf{x}}}|\sigma_{{\textbf{u}}}|{{\textbf{y}}}\rangle$ .

Proof. Firstly we prove this lemma for $n=1$ . We can directly verify that

\displaystyle\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}}|\langle{{\textbf{x}}}\sigma{{\textbf{y}}}\rangle|\,|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}|=\left\{\begin{aligned} &I,\quad\text{If }\sigma\in\{I,Z\}\\ &X,\quad\text{If }\sigma\in\{X,Y\}\\ \end{aligned}\right.

(38)

It is worth noting that $\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}}|\langle{{\textbf{x}}}\sigma{{\textbf{y}}}\rangle|\,|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}|$ records the positions of the nonzero values in $\sigma$ . From this point of view, we can generalize this proof to all $n$ . $\blacksquare$

By Theorem 14 we prove that the lower bound for the $T$ -count obtained by the unitary-stabilizer nullity will never perform worse than the bound obtained by the state-stabilizer nullity. In particular, we prove that for the diagonal unitary, the two bounds coincide.

We would use Eq. (14) and set $C=H^{\otimes n}$ . Before showing the main result of this section, we would like to present the following lemmas with detailed proof in Appendix D.

Lemma 16

For any diagonal $n$ -qubit unitary $U$ ,

	$\displaystyle\{{{\textbf{u}}}\in 4^{[n]}\,\|\,\langle+\|^{\otimes n}U^{\dagger}\sigma_{{\textbf{u}}}U\|+\rangle^{\otimes n}=\pm 1\}$
	$\displaystyle=\{{{\textbf{u}}}\in 4^{[n]}\,\|\,U^{\dagger}\sigma_{{\textbf{u}}}U\in\pm\{I,X\}^{\otimes n}\}.$		(39)

Lemma 17

For any diagonal unitary $U$ ,

\displaystyle\{I,X\}^{\otimes n}\times\left(U^{\dagger}{\cal P}_{n}U\cap{\cal P}_{n}\right)={\cal P}_{n}.

(40)

w.r.t product modulo phases.

Now we are ready to establish the result for diagonal unitary as follows.

Theorem 18

For any diagonal $n$ -qubit unitary $U$ ,

\displaystyle v(U)=\max_{C\in{\cal C}_{n}}v_{s}(UC|0\rangle^{\otimes n}).

(41)

Proof. By setting $C=H^{\otimes n}$ in Theorem 14 and then using Lemma 16, Lemma 17 to show that equations $(\ref{eq:diageqc})(\ref{eq:noless})$ are satisfied. $\blacksquare$

Corollary 19

For any diagonal $n$ -qubit unitary $U$ , the maximum of its corresponding state-stabilizer nullity, i.e. $v_{s}(U|\psi\rangle)$ over all $n$ -qubit stabilizer state $|\psi\rangle$ , is achieved by $|\psi\rangle=|+\rangle^{\otimes n}.$

IV.3 Explicit expressions of the unitary-stabilizer nullity for unitary families

As proved in the previous sections, for the task of lower bounding the $T$ count for a given unitary, the bound obtained by the unitary-stabilizer nullity is always no less than the bound obtained by the state-stabilizer nullity. In this section, we give an example where the unitary-stabilizer nullity performs strictly better.

In Proposition 4.1 of Ref. [25] it showed that for $n\geq 3$ , the state-stabilizer nullity of the states related to the $n$ -bit controlled $Z$ gate is $n$ , i.e. $v_{s}(C^{n-1}Z|+\rangle^{\otimes n})=n$ . This implies the $T$ count for $C^{n-1}Z$ is at least $n$ . One may wonder whether the unitary-stabilizer nullity can improve these bounds. Unfortunately, since $C^{n-1}Z$ is diagonal, by Theorem 18 we know its unitary-stabilizer nullity is also $n$ . To find examples to differentiate the state- and unitary-stabilizer nullity, we should focus on nondiagonal unitaries.

In the following, we give a family of $n$ -qubit unitary, which has unitary-stabilizer nullity $2n$ . This implies constructing such a unitary needs at least $2n$ $T$ gates by Theorem 11. This unitary, or its corresponding quantum circuit, consists of an $n$ -qubit controlled $Z$ gate, a layer of Hadamard gate, and an $n$ -qubit controlled $Z$ gate.

Theorem 20

For $n\geq 3$ ,

\displaystyle v(C^{n-1}Z\,H^{\otimes n}\,C^{n-1}Z)=2n.

(42)

Theorem 20 implies that the lower bound given by the unitary-stabilizer nullity can outperform the bound given by the stabilizer nullity. The detailed proof is provided in Appendix C. We further have the following corollary.

Corollary 21

There exists a family of $n$ -qubit unitary $U_{n}$ such that

\displaystyle v(U_{n})>\max_{C\in{\cal C}_{n}}v_{s}(U_{n}C|0\rangle^{\otimes n})).

(43)

IV.4 Adding auxiliary systems improves the state-stabilizer nullity

In this section, we reconnect the state-stabilizer nullity and the unitary-stabilizer nullity. For any $n$ -qubit unitary $U$ , instead of comparing $v_{s}(U|\psi\rangle)$ and $v(U)$ for some $n$ -qubit stabilizer state $|\psi\rangle$ as in section IV.2, we add auxiliary systems and carefully choose the stabilizer states in the computation of $v_{s}(\cdot)$ , i.e. $v_{s}(I_{2^{d}}\otimes U|\phi\rangle)$ for some $d$ -qubit auxiliary system and $(d+n)$ -qubit stabilizer state $|\phi\rangle$ . By Theorem 22 and Corollary 23, we prove that adding auxiliary systems can strictly increase the value of the state-stabilizer nullity, thus strictly improving the lower bound for the $T$ count through Theorem 12. Furthermore, we prove that the unitary-stabilizer nullity $v(U)$ equals the best lower bound for the $T$ count which one can get through this method, i.e. computing the state-stabilizer nullity with auxiliary systems, as in Theorem 24.

It is worth noting that although the state-stabilizer nullity $v_{s}(\cdot)$ can derive a lower bound for the $T$ count, it is not the $T$ count itself, and it holds different properties to the $T$ count. Thus although the $T$ count for $I_{2^{d}}\otimes U$ is no more than the $T$ count for $U$ , the state-stabilizer nullity for $I_{2^{d}}\otimes U$ (with respect to some stabilizer state) can be strictly larger than the state-stabilizer nullity for $U$ , as in Corollary 23.

Theorem 22

Let $|\Phi\rangle$ be the maximally entangled states on $2n$ -qubit systems, i.e. $|\Phi\rangle=\sum_{{{\textbf{x}}}\in\{0,1\}^{n}}\frac{1}{\sqrt{2^{n}}}|{{\textbf{x}}}\rangle|{{\textbf{x}}}\rangle$ . For any $n$ -qubit unitary $U$ ,

\displaystyle v(U)=v_{s}\left(I_{2^{n}}\otimes U|\Phi\rangle\right).

(44)

Corollary 23

For the $2n$ -qubit maximally entangled states $|\Phi\rangle=\sum_{{{\textbf{x}}}\in\{0,1\}^{n}}\frac{1}{\sqrt{2^{n}}}|{{\textbf{x}}}\rangle|{{\textbf{x}}}\rangle$ , for any $n$ -qubit unitary $U$ ,

\displaystyle v_{s}(I_{2^{n}}\otimes U|\Phi\rangle)\geq\max_{C\in{\cal C}_{n}}v_{s}(UC|0\rangle^{\otimes n}).

(45)

The above inequality can be strict, that is

\displaystyle\exists U\text{ such that }v_{s}(I_{2^{n}}\otimes U|\Phi\rangle)>\max_{C\in{\cal C}_{n}}v_{s}(UC|0\rangle^{\otimes n}).

(46)

Before giving proofs to the theorem and the corollary, we want to make several clarifications:

•

One can easily check the following argument holds as in Appendix C.3

\displaystyle\max_{C^{\prime}\in{\cal C}_{2n}}v_{s}\left(I_{2^{n}}\otimes U\right)C^{\prime}|0^{\otimes 2n}\rangle)\geq\max_{C\in{\cal C}_{n}}v_{s}(UC|0\rangle^{\otimes n}).

(47)

That is when adding the auxiliary systems, the best lower bounds for the $T$ count we can get by the state-stabilizer nullity, is never less than the case when there is no auxiliary system. Compared to this easy argument, Theorem 22 has two key differences. The first one is finding the best bound in the left side of Eq. (47), or equivalent enumerating all possible $2n$ -qubit stabilizer state $C^{\prime}|0^{2n}\rangle$ , need at least $O(2^{\Omega(n^{2})})$ time and thus is hard. In contrast, in Corollary 23 and Theorem 24 we show that to find the best bound, it suffices to set the $2n$ -qubit stabilizer state to be a fixed state, that is the maximally entangled state. The second difference is Eq. (47) shows only $\geq$ , Corollary 23 shows that this inequality can be strict $>$ in some cases. Combined with Theorem 12, this implies analyzing the state-stabilizer nullity with auxiliary systems can strictly improve the lower bound for the $T$ count.

•

One may expect whether using higher-dimensional auxiliary systems or choosing other stabilizer states other than the maximally entangled states can further improve the bound by the state-stabilizer nullity. The answer is no. See as in Theorem 24.
•

Since in general the state-stabilizer nullity does not satisfy the subadditivity under composition (counterexample can be seen as in Appendix C.2), thus using properties of the state-stabilizer nullity and Theorem 22 is not sufficient to imply the subadditivity under composition of the unitary-stabilizer nullity, that is Theorem 10.
•

Corollary 23 and equation (46) do not violate the property that the state-stabilizer nullity is invariant under Clifford unitaries, i.e. for any unitary $V$ , one has $v_{s}(CV|\psi\rangle)=v_{s}(V|\psi\rangle)$ for any Clifford unitary $C$ and stabilizer state $|\psi\rangle$ . More clarifications can be seen at Appendix C.

Proof. [of Theorem 22] By the symmetry of the maximally entangled states, for any $n$ -qubit operator $M\in\mathbb{C}^{2^{n}\otimes 2^{n}}$ , we have $(M\otimes I_{2^{n}})|\Phi\rangle=(I_{2^{n}}\otimes M^{T})|\Phi\rangle$ , which is known as the transpose trick.

For simplicity, in the following we abbreviate $I_{2^{n}}$ as $I$ . Suppose the $2n$ -qubit maximally entangled state $|\Phi\rangle$ is on systems $A\otimes B$ , where both $A,B$ are $n$ -qubit systems. Then for any $2n$ -qubit Pauli operator $\sigma_{{\textbf{u}}}\otimes\sigma_{{\textbf{v}}}$ , where ${{\textbf{u}}},{{\textbf{v}}}\in 4^{[n]}$ , the corresponding state Pauli function satisfies

	$\displaystyle P_{(I\otimes U)\|\Phi\rangle}({{\textbf{u}}}{{\textbf{v}}})$
	$\displaystyle=\operatorname{Tr}_{AB}\left(\sigma_{{\textbf{u}}}\otimes\sigma_{{\textbf{v}}}\,(I\otimes U)\,\|\Phi\rangle\langle\Phi\|\,(I\otimes U^{\dagger})\right)$
	$\displaystyle=\operatorname{Tr}_{AB}\left((I\otimes U^{\dagger})\,\sigma_{{\textbf{u}}}\otimes\sigma_{{\textbf{v}}}\,(I\otimes U)\,\|\Phi\rangle\langle\Phi\|\right)$
	$\displaystyle=\operatorname{Tr}_{AB}\left(\,(I\otimes U^{\dagger}\sigma_{{\textbf{v}}}U)\,(\sigma_{{\textbf{u}}}\otimes I)\,\|\Phi\rangle\langle\Phi\|\right)$
	$\displaystyle=\operatorname{Tr}_{AB}\left(\,(I\otimes U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}}^{T})\|\Phi\rangle\langle\Phi\|\right)$
	$\displaystyle=\gamma\operatorname{Tr}_{AB}\left(\,(I\otimes U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}})\|\Phi\rangle\langle\Phi\|\right).$		(48)

The last two are obtained by the transpose trick and the fact that $\gamma\in\{-1,+1\})$ . Further, notice that

\displaystyle|\Phi\rangle\langle\Phi|

\displaystyle=\frac{1}{2^{n}}\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}|{{\textbf{x}}}\rangle|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}|\langle{{\textbf{y}}}|.

(49)

The above equations can be further simplified by

	$\displaystyle P_{(I\otimes U)\|\Phi\rangle}({{\textbf{u}}}{{\textbf{v}}})$
	$\displaystyle=\gamma\operatorname{Tr}_{AB}\left(\,(I\otimes U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}})\frac{1}{2^{n}}\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}\|{{\textbf{x}}}\rangle\|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}\|\langle{{\textbf{y}}}\|\right)$
	$\displaystyle=\gamma\operatorname{Tr}_{B}\left(\,U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}}\frac{1}{2^{n}}\sum_{{{\textbf{x}}}\in\{0,1\}^{n}}\|{{\textbf{x}}}\rangle\langle{{\textbf{x}}}\|\right)$
	$\displaystyle=\gamma\operatorname{Tr}_{B}\left(\,U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}}\frac{1}{2^{n}}I\right)$
	$\displaystyle=\frac{\gamma}{2^{n}}\operatorname{Tr}_{B}\left(\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}}U^{\dagger}\right)$
	$\displaystyle={\gamma}\,P_{U}({{\textbf{v}}}\|{{\textbf{u}}}).$		(50)

In other words, if we ignore the $\gamma=\pm 1$ factor, then there is a one-to-one correspondence between the values of state Pauli functions and the unitary Pauli function. Thus the two Pauli functions have the same number of $\pm 1$ s, that is $s(U)=s((I\otimes U)|\Phi\rangle)$ . Since $|\Phi\rangle$ is a $2n$ -qubit state, we obtain $2n-s(U)=2n-s((I\otimes U)|\Phi\rangle)$ . Then we have $v(U)=v_{s}\left((I\otimes U)|\Phi\rangle\right)$ . $\blacksquare$

Moreover, the proof of Corollary 23 can be proved by combining Theorem 22, Theorem 14 and Corollary 21.

In the following, we find that $v(U)$ equals the best lower bound for the $T$ count that can be obtained from the state-stabilizer nullity with auxiliary systems. In the following theorem the maximization is over $d$ -qubit auxiliary systems for any positive integer $d$ . The detailed proof is provided in Appendix D.

Theorem 24

For any $n$ -qubit unitary $U$ , we have

\displaystyle v(U)=\max_{d\in\mathbb{N}^{+}}\max_{C\in{\cal C}_{d+n}}v_{s}\left((I_{2^{d}}\otimes U)\,C|0\rangle^{\otimes(d+n)}\right).

(51)

IV.5 Estimating the $T$ count for quantum gates of interests

In this section, we showcase the specific applications of unitary-stabilizer nullity in gate synthesis. We present numerical results of using the state-stabilizer nullity, the unitary-stabilizer nullity, and the stabilizer extent [7] to derive lower bounds for the $T$ count. We compare their performance and summarize the results in Table 1. The definition and properties of stabilizer extent are put in Appendix B.4. The quantum Fourier transform QFT_n is the unitary where QFT ${}_{n}|j\rangle\mathrel{\mathop{\mathchar 58\relax}}=\frac{1}{\sqrt{2^{n}}}\sum_{k=0}^{2^{n}-1}e^{2\pi ijk/2^{n}}|k\rangle$ .

As shown in table 1, when compared with state-stabilizer nullity, the lower bounds obtained by unitary-stabilizer nullity is the same as for diagonal gates, and better in the general case. When compared with stabilizer extent, for small $n$ , the unitary-stabilizer nullity outperforms for some gates. For larger $n$ , the stabilizer extent might perform better, but it is harder to compute since the cardinality of stabilizer states increases as $2^{\Omega(n^{2})}$ [35].

Unitary	Corresponding state	Lower bounds obtained by
		state-stabilizer nullity	unitary-stabilizer nullity	stabilizer extent
$T$	$T\|+\rangle$	1	1	1
$\sqrt{T}$	$\sqrt{T}\|+\rangle$	1	1	0.7549
$CCZ$	$CCZ\|+\rangle^{\otimes 3}$	3	3	3.6349
$C^{3}Z$	$C^{3}Z\|+\rangle^{\otimes 4}$	4	4	5.1226
$\sqrt{T}H\sqrt{T}$	$\sqrt{T}H\sqrt{T}\|+\rangle$	1	2	0.9109
$THT$	$THT\|+\rangle$	1	2	1.4542
QFT₃	QFT ${}_{3}\|x\rangle$
	$x\equiv 0\mod 2$	0	4	0.0000
	$x\equiv 1\mod 2$	1	4	1.0000
QFT₄	QFT ${}_{4}\|x\rangle$
	$x\equiv 1\mod 2$	2	6	1.7555
	$x\equiv 0\mod 4$	0	6	0.0000
	$x\equiv 2\mod 4$	1	6	1.0000

Table 1: Lower bounds for

T

count for the given unitary. The first column is the given unitary

U

. The second column is the corresponding state

|\psi\rangle

. The next three columns are the lower bounds obtained by state-stabilizer nullity

v_{s}

, the unitary-stabilizer nullity

v

, and the stabilizer extent

\xi

. The corresponding value are

v_{s}(|\psi\rangle)

v(U)

and

\frac{\log(\xi(|\psi\rangle)}{\log\xi(|T\rangle)}

, as proved in Theorem 11, Theorem 12. Since QFT

{}_{n}|+\rangle^{\otimes n}=|0\rangle

, similar to Ref. [25] instead we use QFT

{}_{n}|x\rangle

as its corresponding states.

V Conclusion

Resource theory for magic monotones has wide applications in quantum information. In this work, we introduce a magic monotone for unitaries, and use it to lower bound the $T$ count in the circuit synthesis task. This lower bound quantifies the minimum magic resources required for the computation, and lower bounds the runtime of classical simulation algorithms based on the Clifford+ $T$ gate set. We also give numerical results which show that our magic monotone can give better $T$ count lower bounds for some gates when compared with other magic monotones.

Specifically, in this paper, for any $n$ -qubit unitary $U$ , we introduce its unitary-stabilizer nullity as $v(U)=2n-s(U)$ , where $s(U)$ is the number of $\pm 1s$ in the Pauli transfer matrix. We prove that the unitary-stabilizer nullity satisfies several desirable properties, and in particular establish that it is a lower bound for the $T$ count of $U$ . We show that the lower bound obtained by the unitary-stabilizer nullity never performs worse than the state-stabilizer nullity. We also give an $n$ -qubit unitary family of unitary-stabilizer nullity $2n$ , providing examples where the unitary-stabilizer nullity strictly outperforms. For the diagonal unitaries, we prove the lower bounds obtained by the state- and the unitary-stabilizer nullity are the same. Besides, we connect the unitary-stabilizer nullity and the state-stabilizer nullity with auxiliary systems. Moreover, the results in this work may shed lights for the study of resource theories of quantum dynamics (e.g., Refs. [38, 39, 40, 41, 42, 43, 44]).

Meaningful magic monotones with desirable properties are very useful to exploit the power of nonstabilizer resources in quantum computation. Our work has, in particular, shown the applications of unitary-stabilizer nullity in estimating the $T$ count, which is central for resource estimation for fault-tolerant computation [11], performance analysis for classical-simulation algorithms [8, 5, 6], and even for the complexity of the parameterized Quantum Merlin-Arthur problem (QMA problem) [45]. There are many other applications beyond. For one thing, we could apply the unitary-stabilizer nullity to benchmark the gate synthesis task under stabilizer operations [46, 28, 27]. Using the result in Theorem 13, the benchmark method can be generalized for any non-Clifford gates. For another, one might use the unitary-stabilizer nullity to quantify the nonstabilizerness of quantum circuits [47, 48] on near-term quantum devices, as we could extract the unitary Pauli function on the quantum hardware, via firstly measuring the states $U(\sigma_{v}+I)/{2^{n}}U^{\dagger}$ and $U(I-\sigma_{{\textbf{v}}})/{2^{n}}U^{\dagger}$ with measurement operator $\sigma_{{\textbf{u}}}$ , and then obtain the Pauli function. Protocols for evaluating the nonstabilizerness experimentally [47, 48] can be used to analyze the performance of quantum devices.

Beyond this work, there are still various interesting open questions on the quantification of non-Clifford resources:

•

For the task of lower bounding $T$ gates for a given unitary, the unitary-stabilizer nullity gives a bound up to $2n$ . However, in general the $T$ count can be much larger than $2n$ . For example, it is known that only unitaries with elements in certain rings can be exactly synthesized by Clifford and $T$ gates [49]. Is it possible to get a superlinear bound by devising alternative magic monotones?
•

Here we define the $T$ count to be the minimum number of $T$ gates used for exactly synthesizing a given unitary $U$ . Is it possible to lower bound the number of $T$ gates for unitary $V$ which approximates $U$ , i.e. $|V-U|\leq\epsilon$ ? Beverland et al. [25] have considered this setting for single-qubit unitaries.

Acknowledgements. We thank the anonymous reviewers for their valuable suggestions, which help us better present the results and proofs. This work was done when J. J. was a research intern at Baidu Research.

Appendix A Equivalence between the definitions of the state-stabilizer nullity

In this section, we show Definition 4 is equivalent to the definition of the state-stabilizer nullity in the original paper [25]. Recall that for an $n$ -qubit state $|\psi\rangle$ , Beverland et al [25] define the state-stabilizer nullity as

\displaystyle\nu(|\psi\rangle)=n-\log_{2}{|\mathrm{Stab}\,|\psi\rangle}|,

(52)

where $\mathrm{Stab}\,|\psi\rangle$ is the stabilizer of $|\psi\rangle$ , that is

\displaystyle\mathrm{Stab}\,|\psi\rangle=\{P\in\hat{{\cal P}}_{n}\mathrel{\mathop{\mathchar 58\relax}}P|\psi\rangle=|\psi\rangle\}.

(53)

Here we prove our definition $v_{s}(|\psi\rangle)$ is equivalent to $\nu(|\psi\rangle)$ , that is $v_{s}(|\psi\rangle)=\nu(|\psi\rangle)$ , by building a one-to-one correspondence between ${{\textbf{u}}}\in 4^{[n]}$ where $P_{|\psi\rangle}({{\textbf{u}}})=\pm 1$ , and $P\in\hat{{\cal P}}_{n}$ where $P|\psi\rangle=|\psi\rangle$ . The key is noticing that the state Pauli functions are ranging over the quotient group ${\cal P}_{n}$ , while the $\mathrm{Stab}$ is ranging over the Pauli group $\hat{{\cal P}}_{n}$ where

	$\displaystyle{\cal P}_{n}=\{\sigma_{{\textbf{u}}}\|{{\textbf{u}}}\in 4^{[n]}\},$		(54)
	$\displaystyle\hat{{\cal P}}_{n}=\{\pm\sigma_{{\textbf{u}}},\pm i\sigma_{{\textbf{u}}}\|{{\textbf{u}}}\in 4^{[n]}\}.$		(55)

More precisely,

$\rightarrow$ For one direction, if any u satisfies that $P_{|\psi\rangle}({{\textbf{u}}})=\gamma$ where $\gamma=\pm 1$ , since $\sigma_{{\textbf{u}}}$ only has $\pm 1$ eigenvalues and $|\psi\rangle$ is unit, we must have

\displaystyle\sigma_{{\textbf{u}}}|\psi\rangle=\gamma|\psi\rangle.

(56)

Thus we find $P^{({{\textbf{u}}})}\mathrel{\mathop{\mathchar 58\relax}}=\gamma\sigma_{{\textbf{u}}}\in\hat{{\cal P}}_{n}$ such that

\displaystyle P^{({{\textbf{u}}})}\in\mathrm{Stab}\,|\psi\rangle.

(57)

Further notice that for ${{\textbf{u}}}\neq{{\textbf{v}}}$ where $P_{|\psi\rangle}({{\textbf{u}}})=P_{|\psi\rangle}({{\textbf{v}}})=\pm 1$ , we have $P^{({{\textbf{u}}})}\neq P^{({{\textbf{v}}})}$ . Thus the map from u to $P^{({{\textbf{u}}})}$ is a bijection.

$\leftarrow$ For the other direction, notice that since $i\sigma_{{\textbf{u}}}$ has eigenvalues $\pm i$ , we have

\displaystyle i\sigma_{{\textbf{u}}}|\psi\rangle\neq|\psi\rangle,\forall|\psi\rangle.

(58)

Then for any $P\in\mathrm{Stab}\,|\psi\rangle$ , there exists ${{\textbf{u}}}_{P}\in 4^{[n]}$ such that $P=\gamma\sigma_{{{\textbf{u}}}_{P}}$ where $\gamma=\pm 1$ . We can verify that

\displaystyle P_{|\psi\rangle}({{\textbf{u}}}_{p})=\gamma.

(59)

Also notice that by the linearity, if $P\in\mathrm{Stab}\,|\psi\rangle$ , then $-P\not\in\mathrm{Stab}\,|\psi\rangle$ . Thus for any $P\neq P^{\prime}\in\mathrm{Stab}\,|\psi\rangle$ , ${{\textbf{u}}}_{P}\neq{{\textbf{u}}}_{P^{\prime}}$ . Thus the map from $P\in\mathrm{Stab}\,|\psi\rangle$ to ${{\textbf{u}}}_{P}$ is also a bijection.

Combing the above argument that there is a bijection from u where $P_{|\psi\rangle}({{\textbf{u}}})=\pm 1$ to the elements of $\mathrm{Stab}\,|\psi\rangle$ and a bijection vice versa, we conclude that

\displaystyle v_{s}(|\psi\rangle)=\nu(|\psi\rangle).

(60)

Appendix B Non-Clifford resources in two computational models

In this section, we specify two computation models which we mentioned in this manuscript, that is the quantum computation model with magic states, and the quantum computation model with unitary. We would use examples from [31, 32, 29] to clarify the relationship between the number of non-Clifford resources used in the two models, that is Proposition 25 and Proposition 26.

To begin with, we firstly clarify the two computation models. We write $T$ gate as $T=\begin{bmatrix}1&0\\ 0&e^{i\pi/4}\end{bmatrix}$ , T state as $|T\rangle=T|+\rangle.$

B.1 Two computation models

Quantum computation with magic state [11]. In this model, the computational task is to construct a target $n$ -qubit quantum state $\rho$ , either a pure state or a mixed state. The valid operations are as follows.

•

Initiate qubits in state $|0\rangle^{\otimes m}|T\rangle^{\otimes s}$ for some integer $m,s$ .
•

Perform stabilizer operations, including using Clifford unitaries and qubit measurement in the computational basis. Here the Clifford unitary is performed adaptively, that is the Clifford unitary used can depend on previous measurement outcomes.
•

After the computation, use the first $n$ qubits as the output, which should be in state $\rho$ .

There are variants of this model which allow using catalyst states in the initiation, we do not consider those variants here. For readers who are interested, more can be seen in [25].

Quantum computation with unitary. In this model, the computational task is to construct a target $n$ -qubit unitary $U$ using basic gates. More specifically, the task is to decompose $U$ into a sequence of gates from the Clifford+ $T$ gate set, without using ancillary qubits and measurement. Mathematically, we aim to find unitary $U_{1},...,U_{l}$ such that

\displaystyle U=U_{1}U_{2}...U_{l},

(61)

where each $U_{i}$ corresponds to either a Clifford gate, or a $T$ gate. Here $l$ is an integer corresponding to the size of the circuit.

Differences: Note that in the quantum computation with magic state, one can use auxiliary qubits, do measurements and perform Clifford unitary adaptively, while in the quantum computation with unitary, one cannot use auxiliary qubits, cannot do measurements and there are no adaptive operations.

B.2 Non-Clifford resources used in the two models

In the quantum computation with magic state model, the T state $|T\rangle$ is the non-Clifford resource, while the stabilizer operations are viewed as free operations. For an $n$ -qubit state $\rho$ , we use $w_{s}(\rho)$ to denote the minimum $s$ , that is the minimum number of $|T\rangle$ needed to construct $\rho$ . We denote $w_{s}(\rho)=+\infty$ if $\rho$ cannot be exactly constructed through the above process.

In the quantum computation with unitary model, the $T$ gate is the non-Clifford resources, while the Clifford gates, or Clifford unitaries, are viewed as free resources. We use $t(U)$ to denote the minimum number of $T$ gates used in Eq. (61). We denote $t(U)=+\infty$ if $U$ cannot be exactly synthesized with Clifford+ $T$ gate set. We also call $t(U)$ the $T$ count of $U$ .

B.3 Relation between number of non-Clifford resources in two models

As we inexplicitly used in the manuscript, firstly the lower bound of $|T\rangle$ can derive a lower bound of $T$ . This fact is used in [25].

Proposition 25

[25] For an $n$ -qubit unitary $U$ , for any $n$ -qubit stabilizer state $|\phi\rangle$ ,

\displaystyle t(U)\geq w_{s}(U|\phi\rangle).

(62)

Proof. This proof is direct. Suppose we decompose $U$ into sequences of gates in Clifford+ $T$ gate set with in total $t(U)$ $T$ gates. Then use gate injection [10, 50] we can construct state $U|\phi\rangle$ by using $t(U)$ copies of $|T\rangle$ . $\blacksquare$

Furthermore, in the other direction, one may wonder if $t(U)$ can be completely characterized by $w_{s}(\cdot)$ , via enumerating all stabilizer states $|\phi\rangle$ . We emphasize here this is not true.

Proposition 26

[31, 32, 29] There exists $3$ -qubit unitary $U$ such that

\displaystyle t(U)>\max_{|\phi\rangle}w_{s}(U|\phi\rangle),

(63)

where the maximum is over all $3$ -qubit stabilizer states $|\phi\rangle$ .

Proof. This fact is implied by [31, 32, 29]. Here $U$ is set to be the Toffoli gate. Using algorithm which outputs exactly $w(\cdot)$ , Gosset shows $t(U)=7$ [29]. On the other hand, by utilizing the adaptive computation, $w_{s}(U|\phi\rangle)\leq 4$ [32]. $\blacksquare$

B.4 Background of stabilizer extent

For completeness, here we write down the definition and properties of stabilizer extent, which is from [25].

Definition 6 ([25].)

For an arbitrary pure state $|\psi\rangle$ , the stabilizer extent $\xi(|\psi\rangle)$ is defined as

\displaystyle\xi(|\psi\rangle)=\min\|(c_{1},c_{2},...,c_{k})\|_{1}^{2}\text{ s.t }|\psi\rangle=\sum_{\alpha=1}^{k}c_{\alpha}|\phi_{\alpha}\rangle,

(64)

where the minimization is over all complex linear combination of stabilizer states $\{|\phi_{\alpha}\rangle\}$ .

Theorem 27 ([25])

For any $n$ -qubit unitary $U$ , for any single-qubit stabilizer states $|\psi_{1}\rangle,...,|\psi_{n}\rangle$ , we have

\displaystyle t(U)\geq\frac{\log\xi(U|\psi_{1}\rangle...|\psi_{n}\rangle)}{\log\xi(|T\rangle)}.

(65)

Appendix C Clarification on properties of the state-stabilizer nullity

C.1 Corollary 23 does not violate properties of the state-stabilizer nullity

Corollary 23 and equation (46) does not violate the property that the state-stabilizer nullity is invariant under Clifford unitaries, i.e., for any $n$ -qubit unitary $V$ , for any $n$ -qubit Clifford unitary $C\in{\cal C}_{n}$ and any $n$ -qubit stabilizer state $|\psi\rangle$ , one have

\displaystyle v_{s}(CV|\psi\rangle)=v_{s}(V|\psi\rangle).

(66)

What the corollary implies is slightly different. Specifically, what it implies is $\exists V,C$ such that

\displaystyle v_{s}(VC|\psi\rangle)\neq v_{s}(V|\psi\rangle),

(67)

Or equivalently there may exist different $n$ -qubit stabilizer states $|\psi_{1}\rangle$ and $|\psi_{2}\rangle$ such that

\displaystyle v_{s}(V|\psi_{1}\rangle)\neq v_{s}(V|\psi_{2}\rangle).

(68)

Write $|\Phi\rangle$ to be the $2n$ -qubit maximally entangled states, Corollary 23 implies $\exists$ $n$ -qubit unitary $U$ such that setting $V=(I_{2^{n}}\otimes U)$

\displaystyle v_{s}(V|\Phi\rangle)>v_{s}(V(I_{2^{n}}\otimes C^{\prime\prime})|0^{\otimes 2n}\rangle),

(69)

for any $n$ -qubit Clifford $C^{\prime\prime}\in{\cal C}_{n}$ .

C.2 The state-stabilizer nullity does not satisfy the subadditivity under composition

In this section, we show that for any $1$ -qubit stabilizer state $|\psi\rangle$ , there exist single-qubit unitaries $U,V$ such that

\displaystyle v_{s}(UV|\psi\rangle)>v_{s}(U|\psi\rangle)+v_{s}(V|\psi\rangle).

(70)

Thus the state-stabilizer nullity does not satisfy the subadditivity under composition. In particular, suppose

\displaystyle|\psi\rangle=C|0\rangle,C\in{\cal C}_{1}.

(71)

Set

\displaystyle U=e^{iX}HC^{-1},V=CHC^{-1}.

(72)

Since $|+\rangle$ is an eigenstate of $e^{iX}$ , one can verify that

\displaystyle v_{s}(U|\psi\rangle)=v_{s}(e^{iX}|+\rangle)=0.

(73)

Since $CH$ is Clifford, then

\displaystyle v_{s}(V|\psi\rangle)=v_{s}(CH|0\rangle)=0.

(74)

Finally, one can verify by calculating the state Pauli function that

\displaystyle v_{s}(UV|\psi\rangle)=v_{s}(e^{iX}|0\rangle)=1.

(75)

Thus Eq. (70) holds. This counterexample can be generalized to $n$ -qubit case.

C.3 Non-decreasing of state-stabilizer nullity with higher-dimensional systems

Lemma 28

For any $n$ -qubit unitary $U$ , for any $d\geq d^{\prime}$ , we have

\displaystyle\max_{C\in{\cal C}_{d+n}}v_{s}\left((I_{2^{d}}\otimes U)C|0\rangle^{\otimes d+n}\right)\geq\max_{C^{\prime}\in{\cal C}_{d^{\prime}+n}}v_{s}\left((I_{2^{d^{\prime}}}\otimes U)C^{\prime}|0\rangle^{\otimes d^{\prime}+n}\right).

(76)

Proof. It suffices to notice that, for any $C^{\prime}\in{\cal C}_{d^{\prime}+n}$ , let

\displaystyle C\mathrel{\mathop{\mathchar 58\relax}}=I_{2^{d-d^{\prime}}}\otimes C^{\prime}.

(77)

we have

$\displaystyle v_{s}\left((I_{2^{d}}\otimes U)C\|0\rangle^{\otimes d+n}\right)$	$\displaystyle=v_{s}\left((I_{2^{d-d^{\prime}}}\otimes I_{2^{d^{\prime}}}\otimes U)C\|0\rangle^{\otimes d+n}\right)$
	$\displaystyle=v_{s}\left(\|0\rangle^{d-d^{\prime}}\otimes(I_{2^{d^{\prime}}}\otimes U)C^{\prime}\|0\rangle^{\otimes d^{\prime}+n}\right)$
	$\displaystyle=v_{s}\left(\|0\rangle^{d-d^{\prime}}\right)+v_{s}\left((I_{2^{d^{\prime}}}\otimes U)C^{\prime}\|0\rangle^{\otimes d^{\prime}+n}\right)$	(78)
	$\displaystyle=v_{s}\left((I_{2^{d^{\prime}}}\otimes U)C^{\prime}\|0\rangle^{\otimes d^{\prime}+n}\right).$	(79)

The Eq. (78) is obtained by the fact that the state-stabilizer nullity is additive under tensor product. The Eq. (79) is by the fact that $v_{s}(|\phi\rangle)=0$ for stabilizer state $|\phi\rangle$ . The proof of the two facts can be seen in [25]. $\blacksquare$

C.4 Detailed proofs of Lemma 1, Lemma 2, and Lemma 9

Proof. [of Lemma 1] We only give proof to the first statement, the second is similar. Recall that

	$\displaystyle P_{U}({{\textbf{u}}}\|{{\textbf{v}}})$	$\displaystyle=\operatorname{Tr}(\sigma_{{\textbf{u}}}U\sigma_{{\textbf{v}}}U^{\dagger})/2^{n},$		(80)
	$\displaystyle\operatorname{Tr}(\sigma_{{\textbf{u}}}\sigma_{{\textbf{v}}})$	$\displaystyle=\left\{\begin{aligned} &2^{n},&\text{ if ${{\textbf{u}}}={{\textbf{v}}}$}\\ &0,&\text{ else.}\end{aligned}\right.$		(81)

Since $U$ is Clifford, $U(\cdot)U^{\dagger}$ is an isomorphism of $\hat{{\cal P}}_{n}$ , i.e. $U\hat{{\cal P}}_{n}U^{\dagger}=\hat{{\cal P}}_{n}$ . Thus $\forall{{\textbf{u}}}\in 4^{[n]}$ , there exists ${{\textbf{v}}}\in 4^{[n]},k\in[4]$ such that $Ui^{k}\sigma_{{\textbf{v}}}U^{\dagger}=\sigma_{{\textbf{u}}},$ or equivalently $U\sigma_{{\textbf{v}}}U^{\dagger}=(-i)^{k}\sigma_{{\textbf{u}}}$ . Furthermore, since the conjugate operation would not change the eigenvalues of $\sigma_{{\textbf{v}}}$ , which are $\pm 1$ . Thus the global phase $(-i)^{k}$ must be $\pm 1$ . Thus there exists at least one v such that $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ .

On the other hand, by the linearity of $U(\cdot)U^{\dagger}$ , if there exists ${{\textbf{v}}}\neq{{\textbf{v}}}^{\prime}$ such that

	$\displaystyle U\sigma_{{\textbf{v}}}U^{\dagger}$	$\displaystyle=(-i)^{k_{{\textbf{v}}}}\sigma_{{\textbf{u}}},$		(82)
	$\displaystyle U\sigma_{{{\textbf{v}}}^{\prime}}U^{\dagger}$	$\displaystyle=(-i)^{k_{{{\textbf{v}}}^{\prime}}}\sigma_{{\textbf{u}}}.$		(83)

Then we have $U\left((-i)^{k_{{{\textbf{v}}}^{\prime}}}\sigma_{{\textbf{v}}}-(-i)^{k_{{{\textbf{v}}}}}\sigma_{{{\textbf{v}}}^{\prime}}\right)U^{\dagger}=0$ , which leads to a contradiction by the fact that $\sigma_{{\textbf{v}}}$ and $\sigma_{{{\textbf{v}}}^{\prime}}$ are linear independent. Thus we prove that there is only one such v which satisfies $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ . Since $U(\cdot)U^{\dagger}$ is an isomorphism of $\hat{{\cal P}}_{n}$ by Eq. (LABEL:eq:c01) we know for any ${{\textbf{v}}}^{\prime}\neq{{\textbf{v}}}$ , we have $P_{U}({{\textbf{u}}}|{{\textbf{v}}}^{\prime})=0$ . $\blacksquare$

Proof. [of Lemma 2] Since $\sigma_{{\textbf{u}}}$ is a Pauli operator, $2^{n-1}$ number of its eigenvalues are $+1$ , and $2^{n-1}$ eigenvalues are $-1$ . We write

\displaystyle\sigma_{{\textbf{u}}}=\sigma_{{\textbf{u}}}^{+}-\sigma_{{\textbf{u}}}^{-},

(84)

where $\sigma_{{\textbf{u}}}^{\pm}$ are the projections onto the $\pm 1$ eigenspace of $\sigma_{{\textbf{u}}}$ . Similarly, we write

\displaystyle\sigma_{{\textbf{v}}}=\sigma_{{\textbf{v}}}^{+}-\sigma_{{\textbf{v}}}^{-},\quad Q_{{\textbf{v}}}^{+}=U\sigma_{{\textbf{v}}}^{+}U^{\dagger},\quad Q_{{\textbf{v}}}^{-}=U\sigma_{{\textbf{v}}}^{-}U^{\dagger}.

(85)

Then

$\displaystyle P_{U}({{\textbf{u}}}\|{{\textbf{v}}})$	$\displaystyle=\operatorname{Tr}\sigma_{{\textbf{u}}}U\sigma_{{\textbf{v}}}U^{\dagger}/2^{n}$	(86)
	$\displaystyle=\operatorname{Tr}(2\sigma_{{\textbf{u}}}^{+}-I)(2Q_{{\textbf{v}}}^{+}-I)/2^{n}\text{ (Since $\sigma_{{\textbf{u}}}^{+}+\sigma_{{\textbf{u}}}^{-}=I$)}$
	$\displaystyle=(4\operatorname{Tr}\sigma_{{\textbf{u}}}^{+}Q_{{\textbf{v}}}^{+}-2^{n})/2^{n}.$	(87)

Since $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ , we have either

\displaystyle\operatorname{Tr}\sigma_{{\textbf{u}}}^{+}Q_{{\textbf{v}}}^{+}=0.

(88)

\displaystyle\operatorname{Tr}\sigma_{{\textbf{u}}}^{+}Q_{{\textbf{v}}}^{+}=2^{n-1}.

(89)

Note that the eigenvalues of $\sigma_{{\textbf{u}}}^{+}$ (or $Q_{{\textbf{v}}}^{+}$ ) are $2^{n-1}$ $1$ -eigenvalue and $2^{n-1}$ $0$ -eignenvalue.

If equation (88) holds, we must have $Q_{{\textbf{v}}}^{+}=\sigma_{{\textbf{u}}}^{-}$ . To prove this, let ${{\textbf{x}}}_{1},...,{{\textbf{x}}}_{2^{n-1}}$ be an orthogonal basis of the $+1$ -eigenspace of $Q_{{\textbf{v}}}$ . Since $Q_{{\textbf{v}}}^{+}$ and $\sigma_{{\textbf{u}}}^{-}$ are all projections, it suffices to prove vector spaces $\{{{\textbf{x}}}|Q_{{\textbf{v}}}^{+}{{\textbf{x}}}={{\textbf{x}}}\}=\{{{\textbf{x}}}|\sigma_{{\textbf{u}}}^{-}{{\textbf{x}}}={{\textbf{x}}}\}$ . Since the two spaces have the same dimension of $2^{n-1}$ , it suffices to prove

\displaystyle\sigma_{{\textbf{u}}}^{-}{{\textbf{x}}}_{i}={{\textbf{x}}}_{i},\forall i.

(90)

or by the fact $\sigma_{{\textbf{u}}}^{+}+\sigma_{{\textbf{u}}}^{-}=I$ , equivalently to prove

\displaystyle\sigma_{{\textbf{u}}}^{+}{{\textbf{x}}}_{i}=0,\forall i.

(91)

If the above is not true, $\exists i_{0},\sigma_{{\textbf{u}}}^{+}{{\textbf{x}}}_{i_{0}}\neq 0$ . Extend $\{{{\textbf{x}}}_{i}\}_{i=1}^{2^{n-1}}$ to the basis of the whole ( $2^{n}$ -dimensional) space, we have

\displaystyle\operatorname{Tr}\sigma_{{\textbf{u}}}^{+}Q_{{\textbf{v}}}^{+}

\displaystyle=\sum_{i=1}^{2^{n}}\langle{{\textbf{x}}}_{i}|\sigma_{{\textbf{u}}}^{+}Q_{{\textbf{v}}}^{+}|{{\textbf{x}}}_{i}\rangle=\sum_{i=1}^{2^{n-1}}\langle{{\textbf{x}}}_{i}|\sigma_{{\textbf{u}}}^{+}|{{\textbf{x}}}_{i}\rangle\geq\langle{{\textbf{x}}}_{i_{0}}|\sigma_{{\textbf{u}}}^{+}|{{\textbf{x}}}_{i_{0}}\rangle>0,

(92)

which leads to a contradiction. Thus we conclude $Q_{{\textbf{v}}}^{+}=\sigma_{{\textbf{u}}}^{-}$ , that is

\displaystyle U\sigma_{{\textbf{v}}}U^{\dagger}

\displaystyle=2Q_{{\textbf{v}}}^{+}-I=2\sigma_{{\textbf{u}}}^{-}-I=-\sigma_{{\textbf{u}}}.

(93)

Then $\forall{{\textbf{u}}}^{\prime}\neq{{\textbf{u}}}$ , $P_{U}({{\textbf{u}}}^{\prime}|{{\textbf{v}}})=0.$

If equation (89) holds, notice that

\displaystyle\operatorname{Tr}\sigma_{{\textbf{u}}}^{-}Q_{{\textbf{v}}}^{+}

\displaystyle=\operatorname{Tr}(I-\sigma_{{\textbf{u}}}^{+})Q_{{\textbf{v}}}^{+}=2^{n-1}-2^{n-1}=0.

(94)

Similarly, we conclude $Q_{{\textbf{v}}}^{+}=\sigma_{{\textbf{u}}}^{+}$ . $\blacksquare$

Proof. [of Lemma 3] Notice that

	$\displaystyle\|{\cal P}_{U}\|$	$\displaystyle=\|U{\cal P}_{n}U^{\dagger}\cap{\cal P}_{n}\|=\|U({\cal P}_{n}\cap U^{\dagger}{\cal P}_{n}U)U^{\dagger}\|$
		$\displaystyle=\|{\cal P}_{n}\cap U^{\dagger}{\cal P}_{n}U\|=\|{\cal P}_{U^{\dagger}}\|.$		(95)

In the following we show that $|{\cal P}_{U}|=s(U)$ . Since ${\cal P}_{U}$ is an intersection of two groups, thus ${\cal P}_{U}$ is a group. Since ${\cal P}_{U}\subseteq{\cal P}_{n}$ , thus further ${\cal P}_{U}$ is a subgroup of ${\cal P}_{n}$ . To prove $|{\cal P}_{U}|=s(U)$ , it suffices to prove that there is an one-to-one correspondence between $\sigma_{{\textbf{u}}}\in{\cal P}_{U}$ and a pair $({{\textbf{u}}},{{\textbf{v}}})$ such that $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ .

The proof is as follows. On one hand if $\sigma_{{\textbf{u}}}\in{\cal P}_{U}=U{\cal P}_{n}U^{\dagger}\cap{\cal P}_{n}$ , then by definition there exists ${{\textbf{v}}}_{{\textbf{u}}}\in 4^{[n]}$ such that

\displaystyle U\sigma_{{{\textbf{v}}}_{{\textbf{u}}}}U^{\dagger}=\pm\sigma_{{\textbf{u}}}.

(96)

Thus, we have $P_{U}({{\textbf{u}}}|{{\textbf{v}}}_{{\textbf{u}}})=\pm 1$ . Further we know such ${{\textbf{v}}}_{{{\textbf{u}}}}$ is unique since Eq. (96) implies $U^{\dagger}\sigma_{{{\textbf{u}}}}U=\pm\sigma_{{{\textbf{v}}}_{{{\textbf{u}}}}}$ , and for any ${{\textbf{v}}}\neq{{{\textbf{v}}}_{{{\textbf{u}}}}}$ we have $\operatorname{Tr}(\sigma_{{{\textbf{v}}}_{{{\textbf{u}}}}}\sigma_{{\textbf{v}}})=0$ .

One the other hand, for any $({{\textbf{u}}},{{\textbf{v}}})$ such that $P_{U}({{\textbf{u}}}|{{\textbf{v}}})=\pm 1$ , by Lemma 2 we have $U\sigma_{{\textbf{v}}}U^{\dagger}=\pm\sigma_{{\textbf{u}}}$ thus

\displaystyle\sigma_{{\textbf{u}}}\in{\cal P}_{U}=U{\cal P}_{n}U^{\dagger}\cap{\cal P}_{n}.

(97)

$\blacksquare$

Proof. [of Lemma 9] For any $a_{1},a_{2}\in A$ , notice that

	$\displaystyle a_{2}^{-1}a_{1}\in B\rightarrow a_{1}B=a_{2}B,$		(98)
	$\displaystyle a_{2}^{-1}a_{1}\not\in B\rightarrow a_{1}B\cap a_{2}B=\emptyset.$		(99)

Thus $A\times B$ can be written as the union of disjoint cosets: If we write $\hat{A}$ as the set of coset representatives, that is a maximum set which satisfies

\displaystyle\left\{\begin{aligned} &\hat{A}\subseteq A,\\ &\forall a_{1},a_{2}\in\hat{A},\,a_{2}^{-1}a_{1}\not\in B.\end{aligned}\right.

(100)

Then we have

	$\displaystyle A\times B=\cup_{a\in\hat{A}}aB,$		(101)
	$\displaystyle\forall a_{1},a_{2}\in\hat{A},a_{1}B\cap a_{2}B=\emptyset.$		(102)

Thus

\displaystyle|A\times B|=|\hat{A}|\cdot|B|

(103)

Since $A,B$ are groups, thus $A\cap B$ is a group. Further notice that since $\hat{A}\subseteq A$ , Eq. (100) is equivalent to

\displaystyle\left\{\begin{aligned} &\hat{A}\subseteq A,\\ &\forall a_{1},a_{2}\in\hat{A},\,a_{2}^{-1}a_{1}\not\in B\cap A.\end{aligned}\right.

(104)

This implies $\hat{A}$ is also the set of coset representative for $A\cap B$ in $A$ . Thus

\displaystyle|\hat{A}|=\frac{|A|}{|A\cap B|}.

(105)

Combine Eq. (103) and Eq. (105) we finally conclude that

\displaystyle|A\times B|=\frac{|A|\cdot|B|}{|A\cap B|}.

(106)

$\blacksquare$

Appendix D Detailed proofs of main results

D.1 Detailed proof for Theorem 14

Proof. [Proof of Theorem 14] Fix any $n$ -qubit stabilizer state, that is $|\psi\rangle=C|0\rangle^{\otimes n}$ for some Clifford operator $C\in{\cal C}_{n}.$ For any ${{\textbf{u}}}\in 4^{[n]}$ , notice that the condition that $|0\rangle^{\otimes n}$ is an eigenvector of $C^{\dagger}U^{\dagger}\sigma_{{\textbf{u}}}UC$ , would imply $P_{U|\psi\rangle}({{\textbf{u}}})=\pm 1,$ then

\displaystyle C^{\dagger}U^{\dagger}\sigma_{{\textbf{u}}}UC\in\pm\{I,Z\}^{\otimes n}\rightarrow P_{U|\psi\rangle}({{\textbf{u}}})=\pm 1.

(107)

Note that in the following all the matrix product is the matrix product modulo phases. For Clifford operator $C\in{\cal C}_{n}$ , define

$\displaystyle H$	$\displaystyle\mathrel{\mathop{\mathchar 58\relax}}={\cal P}_{n},$
$\displaystyle A$	$\displaystyle\mathrel{\mathop{\mathchar 58\relax}}=C\{I,Z\}^{\otimes n}C^{\dagger},$
$\displaystyle B$	$\displaystyle\mathrel{\mathop{\mathchar 58\relax}}={\cal P}_{U^{\dagger}}=U^{\dagger}{\cal P}_{n}U\cap{\cal P}_{n}.$	(108)

Notice that $A$ , $B$ and $A\cap B$ are subgroups of $H$ , with respect to the matrix-product modulo phases. Besides, we have

$\displaystyle\|H\|$	$\displaystyle=4^{n},$
$\displaystyle\|A\|$	$\displaystyle=2^{n},$
$\displaystyle\|B\|$	$\displaystyle=\|{\cal P}_{U^{\dagger}}\|=\|{\cal P}_{U}\|=s(U).$	(by Lemma 3)	(109)

Further, we have

$\displaystyle\|A\cap B\|$	$\displaystyle=\|C\{I,Z\}^{\otimes n}C^{\dagger}\cap U^{\dagger}{\cal P}_{n}U\cap{\cal P}_{n}\|$
	$\displaystyle=\|\{I,Z\}^{\otimes n}\cap C^{\dagger}U^{\dagger}{\cal P}_{n}UC\cap{\cal P}_{n}\|$	(110)
	$\displaystyle=\|\{I,Z\}^{\otimes n}\cap C^{\dagger}U^{\dagger}{\cal P}_{n}UC\|$	(111)
	$\displaystyle\leq s(U\|\psi\rangle).$	(112)

The Eqs. (110) (111) (112) use the fact that $C^{\dagger}{\cal P}_{n}C={\cal P}_{n}$ , $\{I,Z\}^{\otimes n}\in{\cal P}_{n}$ and Eq. (107) respectively. By Lemma 9, we conclude

$\displaystyle 2^{n}\cdot s(U)$	$\displaystyle\leq\|A\cap B\|\cdot 4^{n},$	(113)
	$\displaystyle\leq s(U\|\psi\rangle)\cdot 4^{n},$
$\displaystyle n-\log_{2}s(U\|\psi\rangle)$	$\displaystyle\leq 2n-\log_{2}s(U).$

Thus

\displaystyle v_{s}(U|\psi\rangle)\leq v(U).

(114)

The equality in (114) holds if and only if equality holds for Eq. (112) and Eq. (113), that is

	$\displaystyle\{{{\textbf{u}}}\in 4^{[n]}\,\|\,\langle 0^{\otimes n}C^{\dagger}U^{\dagger}\sigma_{{\textbf{u}}}UC\|0\rangle^{\otimes n}=\pm 1\}$
	$\displaystyle=\{{{\textbf{u}}}\in 4^{[n]}\|C^{\dagger}U^{\dagger}\sigma_{{\textbf{u}}}UC\in\pm\{I,Z\}^{\otimes n}\},$		(115)

and $A\times B=H$ . $\blacksquare$

D.2 Detailed proof of Lemma 16

Proof. [Proof of Lemma 16] We prove the inclusion relationships for both sides.

$\leftarrow$ Suppose ${{\textbf{u}}}\in 4^{[n]}$ satisfies that $U^{\dagger}\sigma_{{\textbf{u}}}U\in\pm\{I,X\}^{\otimes n}$ . Since

\displaystyle H^{\otimes n}\{I,X\}^{\otimes n}H^{\otimes n}=\{I,Z\}^{\otimes n}.

(116)

We have

\displaystyle\langle+|^{\otimes n}U^{\dagger}\sigma_{{\textbf{u}}}U|+\rangle^{\otimes n}

\displaystyle=\pm 1.

(117)

$\rightarrow$ Since $U$ is a diagonal unitary, we can write

\displaystyle U=diag(\cdots,\lambda_{{\textbf{x}}},\cdots),{{\textbf{x}}}\in\{0,1\}^{n},|\lambda_{{\textbf{x}}}|=1.

(118)

Since

\displaystyle U|+\rangle^{\otimes n}=\frac{1}{\sqrt{2^{n}}}\sum_{{{\textbf{x}}}\in\{0,1\}^{n}}\lambda_{{{\textbf{x}}}}|{{\textbf{x}}}\rangle,

(119)

then

\displaystyle\langle+|^{\otimes n}U^{\dagger}\sigma_{{\textbf{u}}}U|+\rangle^{\otimes n}

\displaystyle=\frac{1}{2^{n}}\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}\lambda_{{\textbf{x}}}^{\dagger}\lambda_{{\textbf{y}}}\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle..

(120)

Note that $|\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle|\in\{0,1\}$ and Eq. (120) has in total $2^{n}\times 2^{n}$ terms. However, for fixed u, for any ${{\textbf{x}}}\in\{0,1\}^{n}$ , there exists exactly one ${{\textbf{y}}}_{{{\textbf{x}}}}\in\{0,1\}^{n}$ such that $|\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}_{{{\textbf{x}}}}\rangle|=1$ , and other terms are all $0$ , that is

	$\displaystyle\|\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}_{{{\textbf{x}}}}\rangle\|=1,$
	$\displaystyle\|\langle{{\textbf{x}}}\sigma_{{{\textbf{u}}}}{{\textbf{y}}}\rangle\|=0,\forall{{\textbf{y}}}\neq{{\textbf{y}}}_{{{\textbf{x}}}}.$		(121)

Thus if $\langle+|^{\otimes n}U^{\dagger}\sigma_{{\textbf{u}}}U|+\rangle^{\otimes n}=1$ (The case for $-1$ is similar), we must have all the nonzero term $\lambda_{{\textbf{x}}}^{\dagger}\lambda_{{{\textbf{y}}}_{{{\textbf{x}}}}}\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}_{{{\textbf{x}}}}\rangle=1$ . Together with the fact that $\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle=0,\forall{{\textbf{y}}}\neq{{\textbf{y}}}_{{\textbf{x}}}$ . Thus we have

\displaystyle\lambda_{{\textbf{x}}}^{\dagger}\lambda_{{\textbf{y}}}\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle=|\lambda_{{\textbf{x}}}^{\dagger}\lambda_{{\textbf{y}}}\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle|,\quad\forall{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{\otimes n}.

(122)

Note that for any operator $(\cdot)$ , the following holds

\displaystyle(\cdot)=\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}\langle{{\textbf{x}}}(\cdot){{\textbf{y}}}\rangle|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}|.

(123)

Thus

$\displaystyle U^{\dagger}\sigma_{{\textbf{u}}}U$	$\displaystyle=\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}\langle{{\textbf{x}}}(U^{\dagger}\sigma_{{\textbf{u}}}U){{\textbf{y}}}\rangle\|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}\|$
	$\displaystyle=\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}\lambda_{{\textbf{x}}}^{\dagger}\lambda_{{\textbf{y}}}\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle\|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}\|$
	$\displaystyle=\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}\|\lambda_{{\textbf{x}}}^{\dagger}\lambda_{{\textbf{y}}}\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle\|\cdot\|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}\|$
	$\displaystyle=\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}\|\langle{{\textbf{x}}}\sigma_{{\textbf{u}}}{{\textbf{y}}}\rangle\|\cdot\|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}\|$
	$\displaystyle\in\{I,X\}^{\otimes n}.$	(124)

The above four equalities and the final inclusion are obtained by Eq. (123), the fact that $U|{{\textbf{y}}}\rangle=\lambda_{{\textbf{y}}}|{{\textbf{y}}}\rangle$ , Eq. (122), the fact that $|\lambda_{{\textbf{x}}}|=|\lambda_{{\textbf{y}}}|=1$ and Lemma 15 respectively. $\blacksquare$

D.3 Detailed proof of Theorem 20

Proof. [of Theorem 20] We prove this theorem by directly calculating the unitary Pauli functions. Recall that for any ${{\textbf{x}}}\in\{0,1\}^{n}$ , $\odot({{\textbf{x}}})\mathrel{\mathop{\mathchar 58\relax}}=x_{1}x_{2}...x_{n}$ , and $1^{n}$ is the $n$ -bit string of all ones. If we ignore a global phase $\pm 1$ , we may write any $\sigma_{{\textbf{u}}},\sigma_{{\textbf{v}}}\in{\cal P}_{n}$ as

\displaystyle\sigma_{{\textbf{u}}}=X^{{{\textbf{s}}}}Z^{{{\textbf{t}}}},\sigma_{{\textbf{v}}}=X^{{{\textbf{p}}}}Z^{{{\textbf{q}}}}.

(125)

where ${{\textbf{s}}},{{\textbf{t}}},{{\textbf{p}}},{{\textbf{q}}}\in\{0,1\}^{n}$ . Notice that ignoring the global phase $\pm 1$ does not influence the number of $\pm 1$ s in the Pauli functions. Write

\displaystyle U=C^{n-1}Z\,H^{\otimes n}\,C^{n-1}Z.

(126)

One can verify that for any ${{\textbf{x}}}\in\{0,1\}^{n}$ ,

	$\displaystyle\langle{{\textbf{x}}}\|\sigma_{{\textbf{u}}}U\sigma_{{\textbf{v}}}U^{\dagger}\|{{\textbf{x}}}\rangle$
	$\displaystyle=\frac{1}{2^{n}}(-1)^{{{\textbf{s}}}\cdot{{\textbf{p}}}+{{\textbf{s}}}\cdot{{\textbf{t}}}}(-1)^{{{\textbf{x}}}\cdot({{\textbf{p}}}+{{\textbf{t}}})}(-1)^{\odot({{\textbf{x}}})+\odot({{\textbf{s}}}+{{\textbf{x}}})}$
	$\displaystyle\,\quad\times\!\!\!\!\sum_{{{\textbf{y}}}\in\{0,1\}^{n}}(-1)^{({{\textbf{q}}}+{{\textbf{s}}})\cdot{{\textbf{y}}}}(-1)^{\odot({{\textbf{y}}})+\odot({{\textbf{y}}}+{{\textbf{p}}})}.$		(127)

Define

\displaystyle f({{\textbf{q}}},{{\textbf{s}}},{{\textbf{p}}})=\sum_{{{\textbf{y}}}\in\{0,1\}^{n}}(-1)^{({{\textbf{q}}}+{{\textbf{s}}})\cdot{{\textbf{y}}}}(-1)^{\odot({{\textbf{y}}})+\odot({{\textbf{y}}}+{{\textbf{p}}})}.

(128)

We can see that

	$\displaystyle\operatorname{Tr}(\sigma_{{\textbf{u}}}U\sigma_{{\textbf{v}}}U^{\dagger})$	$\displaystyle=\sum_{{{\textbf{x}}}\in\{0,1\}^{n}}\langle{{\textbf{x}}}\|\sigma_{{\textbf{u}}}U\sigma_{{\textbf{v}}}U^{\dagger}\|{{\textbf{x}}}\rangle$		(129)
		$\displaystyle=\frac{1}{2^{n}}(-1)^{{{\textbf{s}}}\cdot{{\textbf{p}}}+{{\textbf{s}}}\cdot{{\textbf{t}}}}f({{\textbf{p}}},{{\textbf{t}}},{{\textbf{s}}})f({{\textbf{q}}},{{\textbf{s}}},{{\textbf{p}}}).$		(130)

To further simplify the equations, similar as in [25] we notice that

\displaystyle(-1)^{\odot({{\textbf{y}}})+\odot({{\textbf{y}}}+{{\textbf{p}}})}=\left\{\begin{aligned} &1\text{\quad$\forall{{\textbf{y}}}$, if ${{\textbf{p}}}=0$};\\ &1\text{\quad if ${{\textbf{p}}}\neq 0$;\, ${{\textbf{y}}}\neq 1^{n}$ and ${{\textbf{y}}}\neq{{\textbf{p}}}\oplus 1^{n}$};\\ &-1\text{\quad if ${{\textbf{p}}}\neq 0$;\, ${{\textbf{y}}}=1^{n}$ or ${{\textbf{p}}}+1^{n}$. }\end{aligned}\right.

(131)

Combine the fact that

\displaystyle\sum_{{{\textbf{y}}}\in\{0,1\}^{n}}(-1)^{{{\textbf{z}}}\cdot{{\textbf{y}}}}=\left\{\begin{aligned} &2^{n},\text{ if ${{\textbf{z}}}=0$,}\\ &0,\text{ else.}\end{aligned}\right.

(132)

We can see that

\displaystyle f({{\textbf{q}}},{{\textbf{s}}},{{\textbf{p}}})=\left\{\begin{aligned} &\bullet\quad 2^{n},\text{ if ${{\textbf{p}}}=0,{{\textbf{q}}}={{\textbf{s}}}$};\\ &\bullet\quad 0,\text{ if ${{\textbf{p}}}=0,{{\textbf{q}}}\neq{{\textbf{s}}}$};\\ &\bullet\quad 2^{n}-4,\text{ if ${{\textbf{p}}}\neq 0,{{\textbf{q}}}={{\textbf{s}}}$};\\ &\bullet\quad-2(-1)^{({{\textbf{q}}}+{{\textbf{s}}})\cdot 1^{n}}-2(-1)^{({{\textbf{q}}}+{{\textbf{s}}})\cdot(1^{n}+{{\textbf{p}}})},\\ &\quad\quad\text{ if ${{\textbf{p}}}\neq 0,{{\textbf{q}}}\neq{{\textbf{s}}}$.}\\ \end{aligned}\right.

(133)

Combine with Eq. (129) we know that the unitary Pauli function $\operatorname{Tr}(\sigma_{{\textbf{u}}}U\sigma_{{\textbf{v}}}U^{\dagger})/2^{n}=\pm 1$ if and only if both $f({{\textbf{p}}},{{\textbf{t}}},{{\textbf{s}}})=2^{n},f({{\textbf{q}}},{{\textbf{s}}},{{\textbf{p}}})=2^{n}$ , thus by Eq. (133) we conclude this implies

\displaystyle{{\textbf{p}}}={{\textbf{t}}}={{\textbf{q}}}={{\textbf{s}}}=0.

(134)

Thus we conclude that

	$\displaystyle s(U)=1,$
	$\displaystyle v(U)=2n-\log_{2}s(U)=2n.$		(135)

$\blacksquare$

D.4 Detailed proof of Theorem 24

Proof. [Proof of Theorem 24] Since for any $d\geq d^{\prime}$ , we have

	$\displaystyle\max_{C\in{\cal C}_{d+n}}v_{s}\left((I_{2^{d}}\otimes U)C\|0\rangle^{\otimes d+n}\right)$
	$\displaystyle\geq\max_{C^{\prime}\in{\cal C}_{d^{\prime}+n}}v_{s}\left((I_{2^{d^{\prime}}}\otimes U)C^{\prime}\|0\rangle^{\otimes d^{\prime}+n}\right).$		(136)
	(Appendix C.3)

It suffices to give proofs for sufficiently large $d$ , namely $d\geq n$ . For any $d\geq n$ , by Theorem 14 we know that

\displaystyle v(I_{d}\otimes U)\geq\max_{C\in{\cal C}_{d+n}}v_{s}\left((I_{2^{d}}\otimes U)C|0\rangle^{\otimes d+n}\right).

(137)

Besides notice that since the unitary-stabilizer nullity satisfies the additivity under tensor product and faithfulness, we have

	$\displaystyle v(I_{d}\otimes U)$	$\displaystyle=v(I_{d})+v(U),$	(Theorem 7)
		$\displaystyle=0+v(U).$	(Theorem 5)		(138)

Thus, we have

\displaystyle v(U)\geq\max_{C\in{\cal C}_{d+n}}v_{s}\left((I_{2^{d}}\otimes U)C|0\rangle^{\otimes d+n}\right).

(139)

Moreover, by Theorem 22 we have

$\displaystyle v(U)$	$\displaystyle=v_{s}\left(I_{2^{n}}\otimes U\|\phi\rangle\right)$
	$\displaystyle\leq\max_{C\in{\cal C}_{2n}}v_{s}\left((I_{2^{n}}\otimes U)C\|0\rangle^{\otimes 2n}\right)$
	$\displaystyle\leq\max_{C\in{\cal C}_{d+n}}v_{s}\left((I_{2^{d}}\otimes U)C\|0\rangle^{\otimes d+n}\right).$	(140)

The last inequality is obtained by noticing $d\geq n$ and using Eq. (137). Combine the above inequalities (139) and (140) we conclude for $d\geq n$ ,

\displaystyle v(U)=\max_{C\in{\cal C}_{d+n}}v_{s}\left((I_{2^{d}}\otimes U)C|0\rangle^{\otimes d+n}\right).

(141)

Combine with Eq. (137), we conclude

\displaystyle v(U)=\max_{d\in\mathbb{N}^{+}}\max_{C\in{\cal C}_{d+n}}v_{s}\left((I_{2^{d}}\otimes U)\,C|0\rangle^{\otimes(d+n)}\right).

(142)

$\blacksquare$

References

Gottesman [1998] D. Gottesman, The heisenberg representation of quantum computers, arXiv preprint quant-ph/9807006 (1998).
Aaronson and Gottesman [2004] S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Physical Review A 70, 052328 (2004).
Dawson and Nielsen [2006] C. Dawson and M. Nielsen, The solovay-kitaev algorithm, Quantum Information and Computation 6, 81 (2006).
Nielsen and Chuang [2002] M. A. Nielsen and I. Chuang, Quantum computation and quantum information, American Association of Physics Teachers (2002).
Bravyi and Gosset [2016] S. Bravyi and D. Gosset, Improved classical simulation of quantum circuits dominated by clifford gates, Physical review letters 116, 250501 (2016).
Bravyi et al. [2016] S. Bravyi, G. Smith, and J. A. Smolin, Trading classical and quantum computational resources, Physical Review X 6, 021043 (2016).
Bravyi et al. [2019] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, Simulation of quantum circuits by low-rank stabilizer decompositions, Quantum 3, 181 (2019).
Seddon et al. [2021] J. R. Seddon, B. Regula, H. Pashayan, Y. Ouyang, and E. T. Campbell, Quantifying quantum speedups: Improved classical simulation from tighter magic monotones, PRX Quantum 2, 010345 (2021).
Kocia [2020] L. Kocia, Improved strong simulation of universal quantum circuits, arXiv preprint arXiv:2012.11739 (2020).
Zhou et al. [2000] X. Zhou, D. W. Leung, and I. L. Chuang, Methodology for quantum logic gate construction, Physical Review A 62, 052316 (2000).
Bravyi and Kitaev [2005] S. Bravyi and A. Kitaev, Universal quantum computation with ideal clifford gates and noisy ancillas, Physical Review A 71, 022316 (2005).
Gottesman [1997] D. Gottesman, Stabilizer Codes and Quantum Error Correction, Ph.D. thesis, California Institute of Technology (1997).
Gottesman and Chuang [1999] D. Gottesman and I. L. Chuang, Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations, Nature 402, 390 (1999).
Bravyi and Haah [2012] S. Bravyi and J. Haah, Magic-state distillation with low overhead, Physical Review A 86, 052329 (2012).
Campbell et al. [2017] E. T. Campbell, B. M. Terhal, and C. Vuillot, Review Roads towards fault-tolerant universal quantum computation, Nature Publishing Group 549, 172 (2017).
Hastings and Haah [2018] M. B. Hastings and J. Haah, Distillation with Sublogarithmic Overhead, Physical Review Letters 120, 050504 (2018).
Chamberland and Cross [2019] C. Chamberland and A. W. Cross, Fault-tolerant magic state preparation with flag qubits, Quantum 3, 143 (2019).
Wang et al. [2020] X. Wang, M. M. Wilde, and Y. Su, Efficiently Computable Bounds for Magic State Distillation, Physical Review Letters 124, 090505 (2020).
O’Gorman and Campbell [2017] J. O’Gorman and E. T. Campbell, Quantum computation with realistic magic-state factories, Physical Review A 95, 032338 (2017).
Krishna and Tillich [2019] A. Krishna and J.-P. Tillich, Towards Low Overhead Magic State Distillation, Physical Review Letters 123, 070507 (2019).
Fang and Liu [2020] K. Fang and Z.-W. Liu, No-Go Theorems for Quantum Resource Purification, Physical Review Letters 125, 060405 (2020).
Regula et al. [2020] B. Regula, K. Bu, R. Takagi, and Z.-W. Liu, Benchmarking one-shot distillation in general quantum resource theories, Physical Review A 101, 062315 (2020).
Wang et al. [2019] X. Wang, M. M. Wilde, and Y. Su, Quantifying the magic of quantum channels, New Journal of Physics 21, 103002 (2019).
Chitambar and Gour [2019] E. Chitambar and G. Gour, Quantum resource theories, Reviews of Modern Physics 91, 025001 (2019).
Beverland et al. [2020] M. E. Beverland, E. Campbell, M. Howard, and V. Kliuchnikov, Lower bounds on the non-clifford resources for quantum computations, Quantum Science and Technology 10.1088/2058-9565/ab8963 (2020).
Selinger [2015] P. Selinger, Efficient clifford+ t approximation of single-qubit operators, Quantum Information & Computation 15, 159 (2015).
Ross and Selinger [2016] N. J. Ross and P. Selinger, Optimal ancilla-free clifford+ t approximation of z-rotations., Quantum Inf. Comput. 16, 901 (2016).
Heyfron and Campbell [2018] L. E. Heyfron and E. T. Campbell, An efficient quantum compiler that reduces t count, Quantum Science and Technology 4, 015004 (2018).
Gosset et al. [2014] D. Gosset, V. Kliuchnikov, M. Mosca, and V. Russo, An algorithm for the $T$ count, Quantum Information & Computation 14, 1261 (2014).
Mosca and Mukhopadhyay [2020] M. Mosca and P. Mukhopadhyay, A polynomial time and space heuristic algorithm for $T$ count, arXiv preprint arXiv:2006.12440 (2020).
Howard and Campbell [2017] M. Howard and E. Campbell, Application of a resource theory for magic states to fault-tolerant quantum computing, Physical review letters 118, 090501 (2017).
Jones [2013] C. Jones, Low-overhead constructions for the fault-tolerant toffoli gate, Physical Review A 87, 022328 (2013).
Regula [2018] B. Regula, Convex geometry of quantum resource quantification, Journal of Physics A: Mathematical and Theoretical 51, 045303 (2018).
Seddon and Campbell [2019] J. R. Seddon and E. T. Campbell, Quantifying magic for multi-qubit operations, Proceedings of the Royal Society A 475, 20190251 (2019).
Gross [2006] D. Gross, Hudson’s theorem for finite-dimensional quantum systems, Journal of mathematical physics 47, 122107 (2006).
Veitch et al. [2014] V. Veitch, S. A. H. Mousavian, D. Gottesman, and J. Emerson, The resource theory of stabilizer quantum computation, New Journal of Physics 16, 013009 (2014).
Dummit and Foote [2004] D. S. Dummit and R. M. Foote, Abstract algebra, Vol. 3 (Wiley Hoboken, 2004).
Díaz et al. [2018] M. G. Díaz, K. Fang, X. Wang, M. Rosati, M. Skotiniotis, J. Calsamiglia, and A. Winter, Using and reusing coherence to realize quantum processes, Quantum 2, 100 (2018).
Wang and Wilde [2019] X. Wang and M. M. Wilde, Resource theory of asymmetric distinguishability for quantum channels, Physical Review Research 1, 033169 (2019).
Rosset et al. [2018] D. Rosset, F. Buscemi, and Y.-C. Liang, Resource Theory of Quantum Memories and Their Faithful Verification with Minimal Assumptions, Physical Review X 8, 021033 (2018).
Li et al. [2020] L. Li, K. Bu, and Z.-w. Liu, Quantifying the resource content of quantum channels: An operational approach, Physical Review A 101, 022335 (2020).
Regula and Takagi [2021] B. Regula and R. Takagi, Fundamental limitations on distillation of quantum channel resources, Nature Communications 12, 1 (2021).
Liu and Winter [2019] Z.-W. Liu and A. Winter, Resource theories of quantum channels and the universal role of resource erasure, arXiv preprint arXiv:1904.04201 (2019).
Wang and Wilde [2023] X. Wang and M. M. Wilde, Exact entanglement cost of quantum states and channels under positive-partial-transpose-preserving operations, Physical Review A 107, 012429 (2023).
Arunachalam et al. [2022] S. Arunachalam, S. Bravyi, C. Nirkhe, and B. O’Gorman, The parameterized complexity of quantum verification, arXiv preprint arXiv:2202.08119 (2022).
Welch et al. [2014] J. Welch, A. Bocharov, and K. M. Svore, Efficient approximation of diagonal unitaries over the clifford+ t basis, arXiv preprint arXiv:1412.5608 (2014).
Oliviero et al. [2022] S. F. Oliviero, L. Leone, A. Hamma, and S. Lloyd, Measuring magic on a quantum processor, arXiv preprint arXiv:2204.00015 (2022).
Haug and Kim [2022] T. Haug and M. Kim, Scalable measures of magic for quantum computers, arXiv preprint arXiv:2204.10061 (2022).
Giles and Selinger [2013] B. Giles and P. Selinger, Exact synthesis of multiqubit clifford+ t circuits, Physical Review A 87, 032332 (2013).
Fowler et al. [2012] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Physical Review A 86, 032324 (2012).

$\displaystyle\|{\cal P}_{UV}\|$	$\displaystyle=\|V{\cal P}_{n}V^{\dagger}\cap U^{\dagger}{\cal P}_{n}U\|$
	$\displaystyle\geq\|V{\cal P}_{n}V^{\dagger}\cap U^{\dagger}{\cal P}_{n}U\cap{\cal P}_{n}\|$
	$\displaystyle\geq\|{\cal P}_{V}\cap{\cal P}_{U^{\dagger}}\|.$	(20)

	$\displaystyle P_{(I\otimes U)\|\Phi\rangle}({{\textbf{u}}}{{\textbf{v}}})$
	$\displaystyle=\operatorname{Tr}_{AB}\left(\sigma_{{\textbf{u}}}\otimes\sigma_{{\textbf{v}}}\,(I\otimes U)\,\|\Phi\rangle\langle\Phi\|\,(I\otimes U^{\dagger})\right)$
	$\displaystyle=\operatorname{Tr}_{AB}\left((I\otimes U^{\dagger})\,\sigma_{{\textbf{u}}}\otimes\sigma_{{\textbf{v}}}\,(I\otimes U)\,\|\Phi\rangle\langle\Phi\|\right)$
	$\displaystyle=\operatorname{Tr}_{AB}\left(\,(I\otimes U^{\dagger}\sigma_{{\textbf{v}}}U)\,(\sigma_{{\textbf{u}}}\otimes I)\,\|\Phi\rangle\langle\Phi\|\right)$
	$\displaystyle=\operatorname{Tr}_{AB}\left(\,(I\otimes U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}}^{T})\|\Phi\rangle\langle\Phi\|\right)$
	$\displaystyle=\gamma\operatorname{Tr}_{AB}\left(\,(I\otimes U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}})\|\Phi\rangle\langle\Phi\|\right).$		(48)

	$\displaystyle P_{(I\otimes U)\|\Phi\rangle}({{\textbf{u}}}{{\textbf{v}}})$
	$\displaystyle=\gamma\operatorname{Tr}_{AB}\left(\,(I\otimes U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}})\frac{1}{2^{n}}\sum_{{{\textbf{x}}},{{\textbf{y}}}\in\{0,1\}^{n}}\|{{\textbf{x}}}\rangle\|{{\textbf{x}}}\rangle\langle{{\textbf{y}}}\|\langle{{\textbf{y}}}\|\right)$
	$\displaystyle=\gamma\operatorname{Tr}_{B}\left(\,U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}}\frac{1}{2^{n}}\sum_{{{\textbf{x}}}\in\{0,1\}^{n}}\|{{\textbf{x}}}\rangle\langle{{\textbf{x}}}\|\right)$
	$\displaystyle=\gamma\operatorname{Tr}_{B}\left(\,U^{\dagger}\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}}\frac{1}{2^{n}}I\right)$
	$\displaystyle=\frac{\gamma}{2^{n}}\operatorname{Tr}_{B}\left(\sigma_{{\textbf{v}}}U\sigma_{{{\textbf{u}}}}U^{\dagger}\right)$
	$\displaystyle={\gamma}\,P_{U}({{\textbf{v}}}\|{{\textbf{u}}}).$		(50)

$\displaystyle v_{s}\left((I_{2^{d}}\otimes U)C\|0\rangle^{\otimes d+n}\right)$	$\displaystyle=v_{s}\left((I_{2^{d-d^{\prime}}}\otimes I_{2^{d^{\prime}}}\otimes U)C\|0\rangle^{\otimes d+n}\right)$
	$\displaystyle=v_{s}\left(\|0\rangle^{d-d^{\prime}}\otimes(I_{2^{d^{\prime}}}\otimes U)C^{\prime}\|0\rangle^{\otimes d^{\prime}+n}\right)$
	$\displaystyle=v_{s}\left(\|0\rangle^{d-d^{\prime}}\right)+v_{s}\left((I_{2^{d^{\prime}}}\otimes U)C^{\prime}\|0\rangle^{\otimes d^{\prime}+n}\right)$	(78)
	$\displaystyle=v_{s}\left((I_{2^{d^{\prime}}}\otimes U)C^{\prime}\|0\rangle^{\otimes d^{\prime}+n}\right).$	(79)

	$\displaystyle\|{\cal P}_{U}\|$	$\displaystyle=\|U{\cal P}_{n}U^{\dagger}\cap{\cal P}_{n}\|=\|U({\cal P}_{n}\cap U^{\dagger}{\cal P}_{n}U)U^{\dagger}\|$
		$\displaystyle=\|{\cal P}_{n}\cap U^{\dagger}{\cal P}_{n}U\|=\|{\cal P}_{U^{\dagger}}\|.$		(95)

Lower bound for the TT count via unitary stabilizer nullity

Abstract

I Introduction

Outline and main contributions

II Preliminaries

II.1 Notations

II.2 Pauli function

Definition 1 (State Pauli function)

Definition 2 (Unitary Pauli function)

Definition 3 (Pauli subgroup associated with UU)

II.3 Stabilizer nullity

Definition 4 (state-stabilizer nullity [25])

Definition 5 (unitary-stabilizer nullity)

III Basic properties of unitary-stabilizer nullity

III.1 Basic properties of the unitary Pauli function

Lemma 1

Lemma 2

Lemma 3

Corollary 4

III.2 Basic properties of the unitary-stabilizer nullity

Theorem 5 (Faithfulness)

Theorem 6 (Invariant under Clifford operation)

Theorem 7 (Additivity under tensor product)

Lemma 8

Lemma 9

Theorem 10 (Subadditivity under composition)

IV Applications

IV.1 Lower bounds for the TT count

Theorem 11 (Lower bound for the TT count)

Theorem 12

Theorem 13 (Lower bound for gate synthesis)

IV.2 Comparison between the unitary and state-stabilizer nullity

Theorem 14

Lemma 15

Lemma 16

Lemma 17

Theorem 18

Corollary 19

IV.3 Explicit expressions of the unitary-stabilizer nullity for unitary families

Theorem 20

Corollary 21

IV.4 Adding auxiliary systems improves the state-stabilizer nullity

Theorem 22

Corollary 23

Theorem 24

IV.5 Estimating the TT count for quantum gates of interests

V Conclusion

Appendix A Equivalence between the definitions of the state-stabilizer nullity

Appendix B Non-Clifford resources in two computational models

B.1 Two computation models

B.2 Non-Clifford resources used in the two models

B.3 Relation between number of non-Clifford resources in two models

Proposition 25

Proposition 26

B.4 Background of stabilizer extent

Definition 6 ([25].)

Theorem 27 ([25])

Appendix C Clarification on properties of the state-stabilizer nullity

C.1 Corollary 23 does not violate properties of the state-stabilizer nullity

C.2 The state-stabilizer nullity does not satisfy the subadditivity under composition

C.3 Non-decreasing of state-stabilizer nullity with higher-dimensional systems

Lemma 28

C.4 Detailed proofs of Lemma 1, Lemma 2, and Lemma 9

Appendix D Detailed proofs of main results

D.1 Detailed proof for Theorem 14

D.2 Detailed proof of Lemma 16

D.3 Detailed proof of Theorem 20

D.4 Detailed proof of Theorem 24

References

Lower bound for the $T$ count via unitary stabilizer nullity

Definition 3 (Pauli subgroup associated with $U$ )

IV.1 Lower bounds for the $T$ count

Theorem 11 (Lower bound for the $T$ count)

IV.5 Estimating the $T$ count for quantum gates of interests