Multiqubit Clifford groups are unitary 3-designs

I Introduction

Unitary designs are a ubiquitous tool in quantum information science DiVincenzo et al. (2002); Chau (2005); Dankert (2005); Dankert et al. (2009); Gross et al. (2007); Roy and Scott (2009); Cleve et al. (2016). They are particularly useful in derandomizing constructions that rely on random unitaries, such as randomized benchmarking Knill et al. (2008); Magesan et al. (2011); Wallman and Flammia (2014), quantum process tomography Scott (2008); Kimmel and Liu (2017), quantum cryptography Chau (2005); Ambainis et al. (2009), and data hiding DiVincenzo et al. (2002). In addition, they can generate complex projective designs Renes et al. (2004); Scott (2006); Ambainis and Emerson (2007), which are equally useful in derandomizing constructions that rely on random quantum states. Recently, projective and unitary designs have also found increasing applications beyond quantum information science, especially in the study of chaos and scrambling Hayden and Preskill (2007); Sekino and Susskind (2008); Hosur et al. (2016); Roberts and Yoshida (2017).

Most previous studies on this subject have focused on unitary 2-designs, among which the Clifford group is the most prominent Gottesman (1997); Chau (2005); Dankert (2005); Dankert et al. (2009); Gross (2006); Gross et al. (2007); Knill et al. (2008); Magesan et al. (2011); Wallman and Flammia (2014); Cleve et al. (2016) due to its extensive applications in various research areas, such as quantum computation, quantum error correction, and randomized benchmarking. Complex projective 2-designs constructed from Clifford orbits, including the set of stabilizer states in particular, are also of special interest Gottesman (1997); Gross (2006); Howard et al. (2014). By contrast, little is known about $t$-designs with $t\geq 3$ except for randomized constructions Ambainis and Emerson (2007); Harrow and Low (2009); Brandão et al. (2016); Ćwikliński et al. (2013); Nakata et al. (2017), despite the intensive efforts of many researchers in the past decade. This situation has set a big barrier in realizing many tasks that rely on higher $t$-designs, such as quantum state discrimination Ambainis and Emerson (2007); Matthews et al. (2009), quantum tomography Hayashi et al. (2005); Gross et al. (2010); Kimmel and Liu (2017), phase retrieval Gross et al. (2015); Kueng et al. (2017), and reduction of query complexity Brandão and Horodecki (2013).

Here we show that the multiqubit (including single-qubit) Clifford group is not only a unitary 2-design, but also a 3-design. Moreover, it is minimal except for dimension 4 in the sense that it does not contain any proper subgroup that is also a unitary 3-design. As a consequence, any orbit of pure states of the multiqubit Clifford group, including the set of stabilizer states in particular, forms a 3-design, which extends the result in Ref. Kueng and Gross (2015). Our study not only provides infinite families of well-structured 3-designs, but also paves the way for constructing $t$-designs with even higher strengths Zhu et al. (2016). Recently, these results have found satisfactory applications in quantum state discrimination Kueng et al. (2016a) and phase retrieval Kueng et al. (2016b). Furthermore, our work is helpful to studying multipartite entanglement in stabilizer tensor networks, which stand as an effective tool for understanding holographic duality Nezami and Walter (2016).

In addition, our study leads to a simple explanation of the distinction between discrete Wigner functions in even prime-power dimensions and those in odd prime-power dimensions Wootters (1987); Gross (2006); Zhu (2016). This distinction has been an elusive question and has profound implications for various interesting subjects, such as computational speedup and contextuality Veitch et al. (2012); Howard et al. (2014); Delfosse et al. (2015). In each odd prime-power dimension, the discrete Wigner function introduced by Wootters Wootters (1987) is covariant with respect to the Clifford group Gross (2006); Zhu (2016); by contrast, none is covariant with respect to the multiqubit Clifford group Zhu (2016). Here we reveal a surprising connection between unitary 3-designs and the physics of discrete phase spaces and thereby clarify the reason behind this distinction.

II Preliminaries

A set of pure quantum states $\{|\psi_{j}\rangle\}$ in a $d$-dimensional Hilbert space $\mathcal{H}$ is a (complex projective) t-design for a positive integer $t$ if $\sum_{j}(|\psi_{j}\rangle\langle\psi_{j}|)^{\otimes t}$ is proportional to the projector onto the symmetric subspace of $\mathcal{H}^{\otimes t}$ Ambainis and Emerson (2007); Renes et al. (2004); Scott (2006); Appleby et al. (2015). A set of $K$ unitary operators $\{U_{j}\}$ acting on $\mathcal{H}$ is a unitary $t$-design Dankert (2005); Dankert et al. (2009); Gross et al. (2007) if it satisfies

for any linear operator $M$ acting on $\mathcal{H}^{\otimes t}$, where ${\dagger}$ stands for the Hermitian conjugate and the integral is taken with respect to the normalized Haar measure. By definition, a unitary $t$-design is also a $t^{\prime}$-design for $t^{\prime}<t$. Note that the above equation remains intact when $U_{j}$ are multiplied by arbitrary phase factors, so what we are concerned with are actually projective unitary $t$-designs. Alternatively, the set $\{U_{j}\}$ is a unitary $t$-design if the $t$th frame potential

Besides the current application, frame potentials also play an important role in studying chaos and circuit complexity Hayden and Preskill (2007); Sekino and Susskind (2008); Hosur et al. (2016); Roberts and Yoshida (2017).

Most known examples of unitary designs are constructed from subgroups of the unitary group, which are referred to as (unitary) group designs. Given a finite group $G$ of unitary operators on $\mathcal{H}$, in most cases we are only concerned with the quotient $\overline{G}$ of $G$ over the phase factors. The frame potential of $\overline{G}$ takes on the form Gross et al. (2007)

Before presenting our main results, we need to introduce the (multipartite) Heisenberg-Weyl (HW) group. In prime dimension $p$, the HW group $D$ is generated by the phase operator $Z$ and the cyclic-shift operator $X$,

III Multiqubit Clifford groups are unitary 3-designs

In this section we prove our main result that the multiqubit Clifford group is a unitary 3-design. Consequently, any orbit of the Clifford group, including the orbit of stabilizer states, forms a complex projective 3-design. To achieve this goal, we determine the frame potentials of the Clifford group up to order 4. Furthermore, we show that, except in dimension 4, the multiqubit Clifford group contains no proper subgroup that forms a unitary 3-design. Recently, these results have found applications in many research areas both within and beyond quantum information science.

The multiqubit Clifford group is a unitary 3-design but not a 4-design. The Clifford group in any odd prime-power dimension is only a unitary 2-design. The restricted Clifford group in any prime-power dimension is only a unitary 2-design except for dimension 2.

Any orbit of pure states of the multiqubit Clifford group forms a 3-design; in particular, the set of multiqubit stabilizer states forms a 3-design.

The conclusion on stabilizer states was also proved directly by Kueng and Gross Kueng and Gross (2015).

Theorem 1 is a simple corollary of Eq. (3) and the following lemma, which is proved in the appendix by virtue of Lemma 2 below.

The following lemma is useful not only in proving Lemma 1, but also in computing frame potentials of subgroups of the Clifford group that contain the HW group. See the appendix for a proof.

In many applications, unitary designs with fewer elements are desirable. Is there any proper subgroup of the multiqubit Clifford group that forms a 3-design? The answer turns out to be negative except for dimension 4. The following theorem is proved in the appendix. It shows that in a sense the multiqubit Clifford group is the most economical in constructing a unitary 3-design.

IV Applications to discrete Wigner functions

Discrete Wigner functions are the analogs of the familiar Wigner function in the continuous scenario. They are useful in many research areas, including quantum tomography and quantum computation. In each odd prime-power dimension, the Wootters discrete Wigner function is distinguished because it is covariant with respect to the Clifford group Wootters (1987); Gross (2006); Zhu (2016). In this quasiprobability representation, Clifford transformations can be understood as permutations on the discrete phase space. In addition, a pure state has a nonnegative Wootters discrete Wigner function if and only if it is a stabilizer state according to the discrete Hudson theorem Gross (2006). In particular, stabilizer states can be represented as probability distributions on the discrete phase space. These facts offer a simple explanation of the famous Gottesman-Knill theorem which states that stabilizer quantum computation can be efficiently simulated classically Nielsen and Chuang (2000). In other words, negativity in the Wootters discrete Wigner function is a necessary resource to achieve universal quantum computation Veitch et al. (2012). Incidentally, this negativity is also tied to the prominent nonclassical phenomenon known as contextuality Howard et al. (2014).

In the multiqubit setting, which is the most relevant to realizing practical quantum computation, however, no discrete Wigner function is covariant with respect to the Clifford group Zhu (2016). Consequently, it is more difficult to come up with a simple geometric picture that illustrates the Gottesman-Knill theorem. Also, it is more difficult to clarify the origin of computational speedup in quantum computation based on qubits. A focus of ongoing research is to understand the distinction between multiqubit systems and systems of odd local dimensions Veitch et al. (2012); Howard et al. (2014); Delfosse et al. (2015); Zhu (2016).

Here we show that the nonexistence of a Clifford covariant discrete Wigner function in an even prime-power dimension is closely tied to the fact that the multiqubit Clifford group is a unitary 3-design. To elucidate this point, it suffices to show that no operator basis is covariant with respect to the multiqubit Clifford group, note that any Clifford covariant discrete Wigner function determines a Clifford covariant operator basis. For example, in each odd prime-power dimension, the Wootters discrete Wigner function Wootters (1987) determines the operator basis composed of phase point operators, and vice versa Gross (2006); Zhu (2016). Here an operator basis $\{L_{j}\}$ is covariant with respect to the group $\overline{G}$ of unitary transformations if $\overline{G}$ leaves this basis invariant and acts transitively on the basis operators. In particular, each $U\in\overline{G}$ induces a permutation among the basis operators.

No operator basis is covariant with respect to any unitary group 3-design. No discrete Wigner function is covariant with respect to the multiqubit Clifford group.

This theorem is proved in the appendix. It offers a simple explanation of the distinction between multiqubit systems and systems of odd local dimensions, which is of intrinsic interest to studying quantum computation. Moreover, it reveals a surprising connection between unitary $t$-designs and the physics of discrete phase spaces, which may have profound implications for the cross fertilization of the two active research fields.

V Summary

We showed that the multiqubit Clifford group is a unitary 3-design. It is also a minimal 3-design except for dimension 4. As a consequence, any orbit of pure states of the multiqubit Clifford group is a 3-design; in particular, the set of multiqubit stabilizer states is a 3-design. The methods and conclusions presented here are also useful in studying higher moments of the Clifford group. These results are of interest to many research areas both within and beyond quantum information science.

Moreover, we offered a simple explanation of why no discrete Wigner function is covariant with respect to the multiqubit Clifford group by proving that no operator basis is covariant with respect to any group that forms a unitary 3-design. This result reveals a surprising connection between unitary designs and the physics of discrete phase spaces, which is of interest to studying quantum computation and a number of nonclassical phenomena, such as negativity and contextuality.

Note added. Upon completion of this work, we noticed a comprehensive math paper by Robert M. Guralnick and Pham Huu Tiep Guralnick and Tiep (2005), from which it is possible to deduce our Theorems 1 and 2 with some additional work. However, this paper mentions neither $t$-designs nor the Clifford group explicitly. In addition, some of their results rely on Hering’s theorem, which relies on the classification of finite simple groups (CFSG). Our proofs are completely independent of the CFSG and are thus simpler and more transparent. Recently (Sep 2015), unaware of our work (our draft without Theorem 2 was completed in May 2015 and shared with a number of experts in the field), Zak Webb also proved that the multiqubit Clifford group is a unitary 3-design (published by now Webb (2016)), which offers a complementary perspective to our approach.

Appendix A Proof of Lemma 1

Appendix B Proof of Lemma 2

Appendix C Proof of Theorem 2

Appendix D Proof of Theorem 3

In view of Theorem 1, it suffices to prove the statement that no operator basis is covariant with respect to a unitary group 3-design. Suppose on the contrary that $\{L_{j}\}$ is an operator basis on the Hilbert space $\mathcal{H}$ of dimension $d$ that is covariant with respect to a unitary group 3-design $\overline{G}$. Then $\Phi_{2}(\overline{G})=2$ and $\Phi_{3}(\overline{G})=6$ ($\Phi_{3}(\overline{G})=5$ when $d=2$) according to Eq. (3). Note that $\{L_{j}\otimes L_{k}\}$ and $\{L_{j}\otimes L_{k}\otimes L_{l}\}$ form operator bases for $\mathcal{H}^{\otimes 2}$ and $\mathcal{H}^{\otimes 3}$, respectively. According to Lemma 1 in Ref. Zhu (2016) (cf. Lemma 7.2 in Ref. Zhu (2012)), $\overline{G}$ acts transitively on ordered pairs of distinct operators in $\{L_{j}\}$ and has two orbits (one orbit when $d=2$) on ordered triples. The triple products $\operatorname{tr}(L_{j}L_{k}L_{l})$ for distinct $j,k,l$ must all be equal and thus real when $d=2$, while they can take on at most two different values when $d\geq 3$.

However, these triple products cannot all be real since, otherwise, the basis operators would commute with each other and thus cannot form an operator basis. When $d=2$, this contradiction confirms the theorem. When $d\geq 3$, these triple products must take on two distinct values, which are complex conjugates of each other. Consequently, $\overline{G}$ acts transitively on unordered triples; in other words, $\overline{G}$ is 3-homogeneous in the language of permutation groups Dixon and Mortimer (1996); Cameron (1999); Zhu (2015c). According to Theorem 1 of Kantor Kantor (1972) (see also Theorem 9.4B in Ref. Dixon and Mortimer (1996) and Lemma 2 in Ref. Zhu (2015c)), any 3-homogeneous permutation group on $m$ objects with $m\geq 9$ a perfect square is $3$-transitive. Therefore, $\overline{G}$ acts transitively on ordered triples, which means all triple products $\operatorname{tr}(L_{j}L_{k}L_{l})$ are real, in contradiction with the previous observation. ∎

References